This paper addresses the problem of robot navigation in an unknown and dynamic environment. To be mobile, it must be able to safely navigate within its environment and reliably get from A to B. We envisage a robot that can be placed in a dynamic and unknown environment and can, unaided, discover and maintain sufficient information about its surroundings to enable it to accomplish these tasks.
For such a robot, the first requirement is adequate spatial sensing. The second requirement is that it be able to retain and integrate sensor readings over a period of time to create a reliable map for navigation. Since the environment is dynamic, the robot must be able to adapt to changes within its work area. Finally, to obtain a complete map without supervision, exploration capabilities are desirable.
There has been considerable research in the field of mobile robot navigation [2][9][5][11]. However, relatively few complete and working systems have been reported[3][12]. Most systems to date have used laser range finder and sonar array sensing devices. Very few mobile robot systems have used real--time stereo vision for acquiring 3-D sensory data. This can be attributed to the difficulty in calibrating stereo vision systems, their expense, and the high computation cost for computing accurate and dense stereo data in real--time.
The system presented in this paper combines several approaches to sensing, mapping, path planning and exploration. The experiment was conducted with the Laboratory for Computational Intelligence mobile robot Spinoza at the University of British Columbia [14]. Spinoza (shown in Figure 1) uses a trinocular stereo system that greatly improves sensing accuracy and reliability relative to binocular systems. The vision system combines highly calibrated wide angle cameras and high speed dedicated digital signal processors (DSPs) to provide fast, dense depth sensing.
Obstacles detected through the vision system are mapped into an ``occupancy grid'', a raster map of the robot's environment. This map is updated continuously as stereo data is acquired, and is used for planning paths and exploration.
Path planning is achieved by minimizing a cost function that is a weighted representation of the proximity to obstacles and the distance to an attractive goal. The cost function combines shortest path search methods [7] with potential field approaches [6] [1] to achieve direct paths that pass obstacles at sufficiently safe distances.
The same path planning algorithm is adapted for exploration by assigning goal attributes to unknown regions in the map. The robot moves towards the nearest unexplored region, updating the map as it goes, until all accessible areas have been explored.
The system is robust and performs at speeds significantly faster than those previously reported.
