Multi-Robot Path-Planning Problem for a Heavy Traffic Control Application: A Survey

This survey looked at the methods used to solve multi-autonomous vehicle path-planning for an application of heavy traffic control in cities. Formally, the problem consisted of a graph and a set of robots. Each robot has to reach its destination in the minimum time and number of movements, considering the obstacles and other robots' paths, hence, the problem is NP-hard. The study found that decoupled centralised approaches are the most relevant approaches for an autonomous vehicle path-planning problem for three reasons: (1) a city is a large environment and coupled centralised approaches scale weakly, (2) the overhead of a coupled decentralised approach to achieve the global optimal will affect the time and memory of the other robots, which is not important in a city configuration and (3) the coupled approaches suppose that the number of robots is defined before they start to find the paths and resolve collisions, while in a city, any car can start at any time and hence, each car should work individually and resolve collisions as they arise. In addition, the study reviewed four decoupled centralised techniques to solve the problem: multi-robot path-planning rapidly exploring random tree (MRRRT), push and swap (PAS), push and rotate (PAR) and the Bibox algorithm. The experiments showed that MRRRT is the best for exploring any search space and optimizing the solution. On the other hand, PAS, PAR and Bibox are better in terms of providing a complete solution for the problem and resolving collisions in significantly much less time, the analysis, however, shows that a wider class of solvable instances are excluded from PAS and PAR domain. In addition, Bibox solves a smaller class than the class solved by PAS and PAR in less time, in the worst case, and with a shorter path than PAS and PAR.