Michael Schuresko and Jorge Cortes
12/31/2007 09:00 AM
Applied Mathematics & Statistics
This paper studies distributed algorithms for performing graph rearrangements that preserve the connectivity of a robotic network. Given a connected graph describing the topology of the network, preserving a fixed set of edges while performing a coordination task guarantees that connectivity is maintained. However, the preservation of a fixed set of edges often results in suboptimal and over-constrained robot operation. This paper presents a distributed algorithm to perform graph rearrangements that allow the robotic network to transform its interconnection topology between any two trees. We present a method for composing this algorithm with other control algorithms, and make preference guarantees about the choices of links to be preserved under the resulting composition. We use these ideas to propose a distributed formation morphing algorithm, and characterize its time complexity.
