Towards constant time SLAM using postponement

Many recent approaches to simultaneous localisation and mapping (SLAM) use an extended Kalman filter (EKF) to update and maintain a map of vehicle location. and multiple feature positions as a sensor moves through a scene. Although it is a highly powerful and well-used tool, it suffers from a well-known complexity problem. In this paper we outline the postponement technique which allows for much greater flexibility on when to use the available processing time, while not affecting the optimality of the filter. It works by updating a constant-sized data set based on current measurements, which can be used to affect the updates on all unobserved parts of the map at a later stage. By expanding the set of updated features when each new feature is observed we show that the full map update can be postponed indefinitely. We also demonstrate how postponement can be used to improve the performance of sub-optimal algorithms by applying it to a simple constant time method.