Computationally Tractable SLAM

摘要

Simultaneous Localisation and Mapping (SLAM) is a well-known, and seemingly well-understood problem in robot navigation. A robot with some kind of sensing device moves through an environment making measurements of features or objects in that space. As it does so it creates and maintains a map of the locations of these features, and of its own location in the map. SLAM usually refers to navigation techniques involving the use of the Kalman lter or one of its variants. Using this lter we gain a very clear understanding of the map update process, but at a price | the computational requirements for the optimal update, however cleverly the equations are rearranged and calculated, increase at least at a rate proportional to the square of the number of features in the map. The only solution is to limit the range of the robot, or use a suboptimal method. A number of possible short-cut methods have been proposed. The report describes many of the methods in the current literature and some new ones which have been tested on the Oxford system. This report looks at exactly what is meant by whether the method is working, and concludes that not only do few methods give convincing proof of validity, but that such proof is actually impossible in all but the simplest cases, and only sucien t empirical testing can be seen as true evidence. Some ideas about the best way forward are suggested.