Dudek, G., Jenkin, M., Milios, E. and Wilkes, D., Robotic exploration as graph construction, RBCV-TR-88-23, Techinical Report on Research in Biological and Computational Vision, Department of Computer Science, University of Toronto, 1988.
A fundamental problem in robotics is the exploration of an unknown environment. Most current approaches to exploration make use of a global distance metric that is used to relate past sensory experiences to local measurements. Rather than rely on such an assumption we consider the more general problem of exploration without a distance metric: we propose robot exploration as graph building. We demonstrate that the problem is unsolvable in general and that additional requirements are needed in order for a robot to be able to map its environment. By augmenting the robot with k distinct markers which can be put down or picked up at will, we show that a robot can successfully map its environment. Algorithms are developed for the 1, k, and n marker problem (where n is the number of locations in the environment), and some heuristics are suggested for improving the performance of the algorithm.By defining a minimal model for the world and the sensory ability of the robot, we separate spatial reasoning from visual perception. In this report we deal only with the spatial reasoning component of the exploration problem, and assume that visual perception can identify distinct markers and the edges incident on the current location.
