Three aspects of mobile-robot navigation are studied via the development of a new navigation algorithm. First, the controllability of robots with six common wheel and axle configurations is proved. A dynamic model is developed and used to prove that simple controllers suffice to guarantee stability for synchro-drive vehicles. The results also demonstrate that, although the underlying control systems are stable, potential-field navigation can lead robot trajectories to an unexpected invariant set. Second, the new navigation algorithm is developed by integrating the heuristic-search and the potential-field methods. The algorithm is theoretically proved to be convergent and convergence is also demonstrated experimentally with practical robots in both known and unknown environments. The trap recovery provided by this algorithm can be used in conjunction with any obstacle-avoidance algorithm suffering from the local-minimum problem. Finally, two algorithm-implementation strategies are examined for solving memory-limitation and communication-bandwidth-limitation problems associated with the navigation of single or multiple robots in large dynamic environments. On-board main-memory-management mechanisms, cache policies, auxiliary-memory data structures, and two path planners are explored by simulation based on the new navigation algorithm. One- and two-level caches with one- and two-level planning, respectively, are investigated; these can easily be extended to a higher-level implementation. The simulation results show that among the seven (three local and four global) cache policies studied, the predicted-window, aisle, and via-point policies overcame the above limitations without compromising robot performance. Therefore, one or more of these three policies can be used, with specific implementation strategies for dealing with the memory-limitation and communication-bandwidth-limitation problems encountered in real-world mobile-robot navigation.
展开▼
