Paper Info
Title
Multi-Robot Formation Morphing through a Graph Matching Problem.
Abstract
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.
Year
DOI
Venue
2012
10.1007/978-3-642-55146-8_21
Springer Tracts in Advanced Robotics
Field
DocType
Volume
Hungarian algorithm,Morphing,Graph,Mathematical optimization,Disjoint sets,Computer science,Theoretical computer science,Matching (graph theory),Assignment problem,Euclidean geometry,Robot,Distributed computing
Conference
104
ISSN
Citations 
PageRank 
1610-7438
2
0.40
References 
Authors
14
2
Name
Order
Citations
PageRank
Lantao Liu115716.49
Dylan A. Shell233447.94