Real-time deadlock-free navigation for multiple mobile robots

This paper proposes a practicable navigation method for multiple mobile robots in a realistic environment. In the past, many navigation methods have been developed. However, they were often limited to a single robot and sometimes assumed robots with special mobility such as holonomic ones. From the viewpoint of practical applications it is indispensable that the number of robots is arbitrary and a general shape and mobility for them is allowed. In this study, deadlock-free navigation for non-holonomic mobile robots in a practical environment is given. In the proposed scheme, states of the environment and robots are fed back in real time, and global path planning is cyclically executed. This enables an adaptation to a changing environment and reliable, deadlock-free navigation for multiple robots. The real-time online path planning is performed by an efficient A* search in Configuration Spaces representing the robots and environment. The proposed method is tested in several simulations which represent typical complicated navigation situations. As a result, the effectiveness of the method is verified. (c) 2008 Wiley Periodicals, Inc.