Multi-Robot Formation Morphing through a Graph Matching Problem

摘要

We consider the problem of changing smoothly between formations of spatially deployed multi-robot systems. The algorithm presented in this paper addresses scenarios in which gradual and seamless formation transitions are needed, a problem which we term formation morphing. We show that this can be achieved by routing agents on a Euclidean graph that corresponds to paths computed on --and projected from-- an underlying three-dimensional matching graph. The three-dimensional matching graph is advantageous in that it simultaneously represents a logical assignment problem (for which an optimal solution must be sought) and metric information that comprises the spatial aspects of the Euclidean graph. Together, these features allow one to find concurrent disjoint routing paths for multiple source multiple goal (MSMG) routing problems, for which we prove one may find routing solutions to optimize different criteria. These disjoint MSMG paths efficiently steer the agents from the source positions to the goal positions, the process of which enables the seamless transition from an old formation to a new one.