A New Multirobot Path Planning With Priority Order Based on the Generalized Voronoi Diagram

Abstract

This paper proposes a new path planning method called the priority order navigation algorithm (PONA) for multi-robot navigation in a large flat space. The PONA can guarantee collision-free and efficient travel in the space with fixed or/and dynamic obstacles. The priority order of robots is assigned by the user based on the importance degree of the robots’ tasks and the objective is to make the higher priority robot reach its target faster than the lower priority robot. This study uses the generalized Voronoi diagram (GVD) to establish the initial map for PONA and links the navigation points in GVD to plan the path for each robot. Further, we modify the navigation point links to shorten feasible paths for the lower priority robot and its shortest two feasible paths can be switched to each other based on a certain condition to avoid hitting the higher priority robot. The proposed PONA is compared to several benchmark path planning methods, which are the shortest distance algorithm (SDA) and reciprocal orientation algorithm (ROA), in the simulation section and it is found that the PONA can reduce the average length of the trajectory by more than 10% compared with ROA and SDA.

Keywords

• Voronoi diagram
• Yen’s algorithm
• multi-robot path planning
• collision-free
• path-priority order