Using uncertain sensing data to create reliable maps: an algorithm for exploring/mapping unknown graphlike worlds
Gregory Dudek, Paul Freedman, Souad Hadjres · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
We describe an approach to the exploration and mapping of unknown environments using a mobile robot. This technique presupposes that the world can be described in terms of a fixed set of discrete locations or regions with an ordered set of paths between them. This is abstracted as a graph with a cyclic edge ordering. In previous work, it was shown that such worlds can be fully explored and described in limited complexity using a single movable marker (like a pebble) even if there are no spatial metrics and almost no sensory ability on the part of the robot [Dudek et al. 1991]. Here we present an approach to the exploration of unknown worlds without such a moveable marker. Locations in the world are identified by a non-unique 'signature' that serves as an abstraction for a percept that might be obtained from a robotic sensor. While the signature of any single location may not be unique, under appropriate conditions the distinctiveness of a particular set of signatures in a neighborhood increases with neighborhood size. By using a collection of non-unique local signatures we can thereby construct an 'extended' signature that uniquely determines the robot's position (although in certain degenerate worlds, additional information is also required). The algorithm makes use of no metric information such as the distances of the paths traversed, but the availability of such measurements would simplify the mapping problem.