Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a theoretical study of decentralized control for sensing-based shape formation on modular multi-robot systems, where the desired shape is specified in terms of local sensor constraints between neighboring robot agents. We show that this problem can be formulated more generally as distributed constraint-maintenance on a networked multi-agent system. It is strongly related to a class of multi-agent algorithms called distributed consensus, which includes several bio-inspired algorithms such as flocking and firefly synchronization. By exploiting this connection, we can theoretically analyze several important aspects of the decentralized shape formation algorithm and generalize it to more complex multi-agent scenarios. We show that the convergence time depends on (a) the number of robot agents and agent connection topology, (b) the complexity of the user-specified goal, and (c) the initial state of the robots. Using these results, we can provide precise statements on how the approach scales, and how quickly the system can adapt to perturbations. These results provide a deeper understanding of the contrast between centralized and decentralized multi-agent algorithms.

REFERENCES

• 1: http://www.eecs.harvard.edu/~chyu/aamas08-appdx.pdf.
• 2: H. Bojinov, A. Casal, and T. Hogg. Emergent structures in modular self-reconfigurable robots. In Proc. of ICRA, 2000.
• 3: Ming Cao , A. Stephen Morse , Brian D. O. Anderson, Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach, SIAM Journal on Control and Optimization, v.47 n.2, p.575-600, March 2008 [doi>10.1137/060657005]
• 4: J. A. Fax and R. M. Murray. Information flow and cooperative control of vehicle formations. IEEE Trans. on Automatic Control, 49:1465--1476, 2004.
• 5: B. Mohar. Eigenvalues, diameter, and mean distance in graphs. Graphs and Combinatorics, 7:53--64, 1991.
• 6: B. Mohar. The laplacian spectrum of graphs. Graph Theory, Combinatorics, and Applications, 2, 1991.
• 7: S. Murata, E. Yoshida, A. Kamimura, H. Kurokawa, K. Tomita, and S. Kokaji. M-tran: Self-reconfigurable modular robotic system. IEEE/ASME Trans. Mechatron, 7(4):431--441, 2002.
• 8: R. Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Trans, on Automatic Control, 51(3):401--420, 2006.
• 9: R. Olfati-Saber, J. Fax, and R. Murray. Consensus and cooperation in networked multi-agent systems. In Proc. of IEEE, 2007.
• 10: Daniela Rus , Zack Butler , Keith Kotay , Marsette Vona, Self-reconfiguring robots, Communications of the ACM, v.45 n.3, March 2002 [doi>10.1145/504729.504752]
• 11: E. Seneta. Non-negative Matrices and Markov Chains. Springer Verlag, 1981.
• 12: Wei-Min Shen , Maks Krivokon , Harris Chiu , Jacob Everist , Michael Rubenstein , Jagadesh Venkatesh, Multimode locomotion via SuperBot reconfigurable robots, Autonomous Robots, v.20 n.2, p.165-177, March 2006 [doi>10.1007/s10514-006-6475-7]
• 13: C.-H. Yu, F.-X. Willems, D. Ingber, and R. Nagpal. Self-organization of environmentally-adaptive shapes on a modular robot. In Proc. of IROS, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Theory

Keywords:
collective dynamics, convergence, decentralized control, graph Laplacian, modular robot, shape formation