Sensing-based shape formation on modular multi-robot systems: a theoretical study

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.

• Publication year

  2008

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2008-05-12

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1145/1402383.1402398
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Non-negative Matrices and Markov Chains

  2008cited by this paper
• Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events

  2008cited by this paper
• Self-organization of environmentally-adaptive shapes on a modular robot

  2007cited by this paper
• Consensus and Cooperation in Networked Multi-Agent Systems

  2007influential reference
• Flocking for multi-agent dynamic systems: algorithms and theory

  2006cited by this paper
• Multimode locomotion via SuperBot reconfigurable robots

  2006cited by this paper
• Information flow and cooperative control of vehicle formations

  2004cited by this paper
• M-TRAN: self-reconfigurable modular robotic system

  2002cited by this paper
• Self-reconfiguring robots

  2002cited by this paper
• The Laplacian spectrum of graphs

  2001cited by this paper
• Emergent structures in modular self-reconfigurable robots

  2000cited by this paper
• Eigenvalues, diameter, and mean distance in graphs

  1991cited by this paper
• THE LAPLACIAN SPECTRUM OF GRAPHS y

  1991cited by this paper
• Non‐Negative Matrices and Markov Chains

  1983cited by this paper

• Bio-inspired Shape Self-Assembly in Large-Scale Swarm Robots Under Information Asymmetry *

  2025cites this paper
• Vein-Based Coalitions for Multi-Agent Pattern Formation Tasks

  2022cites this paper
• A modular robot architecture capable of learning to move and be automatically reconfigured

  2020cites this paper
• Shape Formation in Homogeneous Swarms Using Local Task Swapping

  2020cites this paper
• Decentralized progressive shape formation with robot swarms

  2018cites this paper
• The JaCalIVE framework for MAS in IVE: A case study in evolving modular robotics

  2018cites this paper
• Social Emotions in Multiagent Systems

  2018cites this paper
• Developing Adaptive Agents Situated in Intelligent Virtual Environments

  2014cites this paper
• SWARMORPH: Morphogenesis with Self-Assembling Robots

  2012cites this paper
• I Have a Robot, and I'm Not Afraid to Use It!

  2012cites this paper
• A non-deadlock reconfiguration strategy in cooperative module systems

  2012cites this paper
• Chapter 2 SWARMORPH : Morphogenesis with Self-Assembling Robots

  2012cites this paper
• Consensus acceleration in multiagent systems with the Chebyshev semi-iterative method

  2011cites this paper
• A Self-adaptive Framework for Modular Robots in a Dynamic Environment: Theory and Applications

  2011cites this paper
• Optimal design for active self-assembly system

  2011cites this paper
• Coordinating collective locomotion in an amorphous modular robot

  2010influential citation
• Biologically-Inspired Control for Multi-Agent Self-Adaptive Tasks

  2010cites this paper
• Collective decision-making in multi-agent systems by implicit leadership

  2010influential citation
• Biologically-inspired control for self-adaptive multiagent systems

  2010cites this paper
• Distributed multiagent learning with a broadcast adaptive subgradient method

  2010cites this paper
• Developing Scalable Abilities for Self-Reconfigurable Robots

  2010cites this paper
• Self-adapting modular robotics: A generalized distributed consensus framework

  2009influential citation
• Engineering self-adaptive modular robotics: A bio-inspired approach

  2009cites this paper
• SWARMORPH-script: a language for arbitrary morphology generation in self-assembling robots

  2008cites this paper
• Morpho: A self-deformable modular robot inspired by cellular structure

  2008cites this paper