A distributed and optimal algorithm to coordinate the motion of multiple mobile robots

This paper addresses the problem of planning paths for multiple mobile robots moving in the same environments. We try to decrease the computational complexity of path planning, which is one of the fundamental limiting characteristics in the existing work of path planning. Unlike many other approaches to this problem, we assume the robots are restricted by the limited-communication range such that information about other robots can be known only when they move close to each other. In our method, the computationally expensive problem is decomposed into two modules-path planning and velocity planning. Such decomposition makes approaches of path planning for multiple mobile robots applicable. Trajectory for each robot is achieved by using the approach named vector field histogram (VFH) before the robots begin to move. Then the conflicts among robots are solved by adjusting the velocities of robots. Velocity planning occurs only inside the robots that are in the same network. The method of planning velocities for the robots is called the dynamic priority assignment, which can minimize the total waiting time of robots in the same network. Finally, both simulated and real-robot experiments have validated our approach.