B. J. Kuipers & Y.-T. Byun. 1988.
A robust qualitative method for spatial learning in
unknown environments.
In Proceedings of the National Conference on Artificial Intelligence (AAAI-88).
Los Altos, CA: Morgan Kaufman, 1988.
We present a qualitative method for a mobile robot to explore an unknown environment and learn a map, which can be robust in the face of various possible errors in the real world. Procedural knowledge for the movement, topological model for the structure of the environment, and metrical information for geometrical accuracy are separately represented in our method, whereas traditional methods describe the environment mainly by metrical information. The topological model consists of distinctive places and local travel edges linking nearby distinctive places. A distinctive place is defined as the local maximum of some measure of distinctiveness appropriate to its immediate neighborhood, and is found by a hill-climbing search. Local travel edges are defined in terms of local control strategies required for travel. How to find distinctive places and follow edges is the procedural knowledge which the robot learns dynamically during exploration stage and guides the robot in the navigation stage. An accurate topological model is created by linking places and edges, and allows metrical information to be accumulated with reduced vulnerability to metrical errors. We describe a working simulation in which a robot, NX, with range sensors explores a variety of 2-D environments and we give its successful results under varying levels of random sensor error.