Multi-robot Path Planning Algorithm in Dense Environments Using Particular Collision-free Traffic Rules

Scheduling collision-free paths for a large number of robots in dense environments with high efficiency is achieved in this work. We propose an algorithm, OMPP (One-way Multi-robot Path Planning), using a new topological skeleton representation of the dense environment by introducing the particular collision-free traffic rules. We propose the integer programming technique based on the topological skeleton graph to tackle the multi-robot path planning optimization problem using distance metrics. We realize two practical achievements in solving multi-robot path planning problems in dense environments: collision-free robotic path generation and an efficient solving process. We have performed numerous simulations. According to the extensive simulation data, our algorithm suggests a higher overall performance in dense environments than the existing representative algorithms.