  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.
