Bipartite graph matching-based coordination mechanism for multi-robot path planning under communication constraints

Abstract

We propose a coordination mechanism to avoid inter-robot collisions when the robots' paths overlap with each other. Our proposed coordination technique uses a weighted bipartite matching-based formulation to solve this problem. Initially, each robot is given a unique goal location. But the robots do not know about other robots' planned paths until they come within each other's communication ranges. When two or more robots get within an unsafe distance, they coordinate their paths to avoid collisions with each other. The objective of the coordination mechanism is to plan a modified path for each coordinating robot (if needed) so that all the robots can reach their goal locations without collision with each other and also while reducing the extra distance introduced while resolving path conflicts. We have proved the correctness and convergence of our coordination strategy. Our experimental results show that the robots using our proposed strategy travel up to 4.2 times less than a comparable heuristic approach.