A Collision-free And Deadlock-free Path-planning Algorithm For Multiple Mobile Robots Without Mutual Communication

A bstra ct- --In this paper, we propose a good pathplanning algorithm for multiple robots without mutual communication. In this research, we first select and call one ol' the multiple robots as the target robot, and then plan a collisionfree and deadlock-free path of' the targct robot toward its goal against the other moving robots in a workspace. The other robots moves as their pleases and the targct robot cannot know their future actions because of no communication. Thus we call such a workspace as an uncertain and dynamic workspace. In the workspace, the target robot obliges to find and avoid the other robots with the help of' some scnsor information. In all previous algorithms, the target robot pay attention to only avoiding its nearest robot, and consequently we could not discuss whether the target robot arrives at the goal or not (whether some deadlock occurs or not). In the proposed algorithm, not only the target robot avoids its nearest robot and also it leaves the nearest robot in order to arrive at the goal surely. Such a leave point is selected on the basis of an asymptotical decrease of the Euclidean distance bctwccn the target robot and the goal. According to this character, the robot comes close to the goal asymptotically and finally the robot arrives at the goal without occurrence of any deadlock.