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 fo
- PDF / 1,741,369 Bytes
- 16 Pages / 439.363 x 666.131 pts Page_size
- 102 Downloads / 233 Views
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 threedimensional 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.
1 Introduction Part of multi-robot formation control involves manoeuvring a spatially dispersed system from one formation to another. Formation control has received a great deal of attention and extensive investigation in the past decades (see reviews by Murray [17], Chen and Wang [4]). Most previous studies consider formation control of the whole system, but, in many situations, only parts of the system need to be changed to reach a new formation. For example, sometimes only patches of agents in certain corners need move to other locations, or boundary agents need to fill inner holes. If the majority the system keeps its structure unchanged, while a minority migrate to Lantao Liu · Dylan A. Shell Dept. of Computer Science and Engineering, Texas A&M University, College Station, TX, USA e-mail: {lantao,dshell}@cse.tamu.edu M.A. Hsieh and G. Chirikjian (eds.), Distributed Autonomous Robotic Systems, Springer Tracts in Advanced Robotics 104, c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-55146-8_21,
291
292
L. Liu and D.A. Shell
(a)
(b)
(c)
(d)
(e)
Fig. 1 Evolution of formation morphing. Source nodes are colored in green (top triangles) and gradually disappear. Goal nodes are colored in orange (right triangles) and gradually grow.
other places, then an incremental variation of the problem is worth addressing. We call formation control in such scenarios formation morphing since the formation is changed as if it is gradually “deformed” in places, while the major pattern is unaltered. Fig. 1 shows an example of seamless formation morphing. Recently we have shown that by exploring the matching graph version of the Hungarian method [10] and interpreting it in three dimensional space, the assignment problem can also be used to deal with the standard routing problems [12]. In this paper we focus on more complicated conditions involving multiple paths generated from the matching graph, and devel
Data Loading...
