Sequential path planning for a formation of mobile robots with split and merge
This addresses path planning for multi-robot formations in tasks like cooperative surveillance, but it is incremental as it builds on existing graph-based methods.
The paper tackles the problem of path planning for a formation of mobile robots that can split and merge, presenting an algorithm that finds a deterministic and complete solution using an extended Dijkstra's method, with experimental results in complex environments for tens of robots.
An algorithm for robot formation path planning is presented in this paper. Given a map of the working environment, the algorithm finds a path for a formation taking into account possible split of the formation and its consecutive merge. The key part of the solution works on a graph and sequentially employs an extended version of Dijkstra's graph-based algorithm for multiple robots. It is thus deterministic, complete, computationally inexpensive, and finds a solution for a fixed source node to another node in the graph. Moreover, the presented solution is general enough to be incorporated into high-level tasks like cooperative surveillance and it can benefit from state-of-the-art formation motion planning approaches, which can be used for evaluation of edges of an input graph. The performed experimental results demonstrate the behavior of the method in complex environments for formations consisting of tens of robots.