research-article

A Distributed Self-Assembly Planning Algorithm for Modular Robots

Authors:

Benoît Piranda,

Julien BourgeoisAuthors Info & Claims

AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

Pages 550 - 558

Published: 09 July 2018 Publication History

Abstract

A distributed modular robot is composed of many autonomous modules, capable of organizing the overall robot into a specific goal structure. There are two possibilities to change the morphology of such a robot. The first one, self-reconfiguration, moves each module to the right place, whereas the second one, self-assembly docks the modules at the right place. Self-assembly is composed of two steps, (1) identifying the free positions that are available for docking and (2) docking the modules to these positions. This work focuses on the first step. This paper presents a distributed planning algorithm that can decide which positions can be filled and can create any 3D shape, including shapes with internal holes and concavities. Our algorithm consider kinematic constraints and prevents positions from being blocked. Each module embeds the same algorithm and coordinates with the others by means of neighbor-to-neighbor communication.

References

[1]

Jérôme Barraquand and Jean-Claude Latombe. 1991. Robot Motion Planning: A Distributed Representation Approach. The International Journal of Robotics Research, Vol. 10, 6 (Dec. . 1991), 628--649.

Digital Library

[2]

Dominique Dhoutaut, Benoît Piranda, and Julien Bourgeois. 2013. Efficient simulation of distributed sensing and control environments IEEE Internet of Things (iThings/CPSCom). IEEE, 452--459.

Digital Library

[3]

Melvin Gauci, Monica E. Ortiz, Michael Rubenstein, and Radhika Nagpal. 2017. Error Cascades in Collective Behavior: A Case Study of the Gradient Algorithm on 1000 Physical Agents. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS '17). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1404--1412. http://dl.acm.org/citation.cfm?id=3091282.3091319

Digital Library

[4]

Kyle Gilpin, Ara Knaian, and Daniela Rus. 2010. Robot pebbles: One centimeter modules for programmable matter through self-disassembly Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2485--2492.

[5]

Kyle Gilpin and Daniela Rus. 2010. Modular Robot Systems. IEEE Robotics Automation Magazine Vol. 17, 3 (Sept. 2010), 38--55.

[6]

Seth Goldstein and Todd Mowry. 2004. Claytronics: A Scalable Basis For Future Robots. RoboSphere 2004 (Nov. 2004).

[7]

Seth Copen Goldstein, Jason D. Campbell, and Todd C. Mowry. 2005. Programmable matter. Computer, Vol. 38, 6 (2005), 99--101.

Digital Library

[8]

Chris Jones and Maja J. Mataric. 2003. From local to global behavior in intelligent self-assembly 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), Vol. Vol. 1. 721--726 vol.1.

[9]

André Naz, Benoît Piranda, Julien Bourgeois, and Seth Copen Goldstein. 2016. A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots Network Computing and Applications (NCA), 2016 IEEE 15th International Symposium on. IEEE, 254--263.

[10]

Michael Park, Sachin Chitta, Alex Teichman, and Mark Yim. 2008. Automatic Configuration Recognition Methods in Modular Robots. The International Journal of Robotics Research, Vol. 27, 3-4 (March. 2008), 403--421.

Digital Library

[11]

Benoit Piranda and Julien Bourgeois. 2016. Geometrical study of a quasi-spherical module for building programmable matter DARS 2016, 13th International Symposium on Distributed Autonomous Robotic Systems.

[12]

Aristides AG Requicha. 1980. Representations of rigid solid objects. Springer.

[13]

Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. 2014. Programmable self-assembly in a thousand-robot swarm. Science, Vol. 345, 6198 (2014), 795--799.

[14]

Jungwon Seo, Mark Yim, and Vijay Kumar. 2013. Assembly planning for planar structures of a brick wall pattern with rectangular modular robots 2013 IEEE International Conference on Automation Science and Engineering (CASE). 1016--1021.

[15]

Jungwon Seo, Mark Yim, and Vijay Kumar. 2016. Assembly sequence planning for constructing planar structures with rectangular modules 2016 IEEE International Conference on Robotics and Automation (ICRA). 5477--5482.

[16]

Kasper Stoy and Radhika Nagpal . 2007. Self-Reconfiguration Using Directed Growth. Distributed Autonomous Robotic Systems 6, bibfieldeditorRachid Alami, Raja Chatila, and Hajime Asama (Eds.). Springer Japan, 3-12.

[17]

Michael T. Tolley and Hod Lipson. 2010. Fluidic manipulation for scalable stochastic 3D assembly of modular robots 2010 IEEE International Conference on Robotics and Automation. 2473--2478.

[18]

Michael T Tolley and Hod Lipson. 2011. On-line assembly planning for stochastically reconfigurable systems. The International Journal of Robotics Research, Vol. 30, 13 (Nov. . 2011), 1566--1584.

Digital Library

[19]

Thadeu Tucci, Benoît Piranda, and Julien Bourgeois. 2017. Efficient scene encoding for programmable matter self-reconfiguration algorithms Proceedings of the Symposium on Applied Computing. ACM, 256--261.

Digital Library

[20]

Justin Werfel, Yaneer Bar-Yam, Daniela Rus, and Radhika Nagpal. 2006. Distributed construction by mobile robots with enhanced building blocks Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006. 2787--2794.

[21]

Justin Werfel and Radhika Nagpal. 2008. Three-Dimensional Construction with Mobile Robots and Modular Blocks. The International Journal of Robotics Research, Vol. 27, 3-4 (March. 2008), 463--479.

Digital Library

[22]

Mark Yim, Ying Zhang, and David Duff. 2002. Modular robots. IEEE Spectrum, Vol. 39, 2 (2002), 30--34.

Digital Library

Cited By

Wu LGuo BZhang QSun ZZhang JYu ZAgmon NAn BRicci AYeoh W(2023)Learning to Self-Reconfigure for Freeform Modular Robots via Altruism Multi-Agent Reinforcement LearningProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598996(2544-2546)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598996
Wu LGuo BZhang QSun ZZhang JYu ZElkind E(2023)Learning to self-reconfigure for freeform modular robots via altruism proximal policy optimizationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/610(5494-5502)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/610
Bassil JMakhoul APiranda BBourgeois J(2023)Distributed Size-constrained Clustering Algorithm for Modular Robot-based Programmable MatterACM Transactions on Autonomous and Adaptive Systems10.1145/358028218:1(1-21)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3580282
Show More Cited By

Index Terms

A Distributed Self-Assembly Planning Algorithm for Modular Robots
1. Computer systems organization
  1. Embedded and cyber-physical systems
2. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed algorithms
      1. Self-organization
  2. Modeling and simulation
    1. Simulation types and techniques
      1. Distributed simulation

Recommendations

Distributed Size-constrained Clustering Algorithm for Modular Robot-based Programmable Matter
Modular robots are defined as autonomous kinematic machines with variable morphology. They are composed of several thousands or even millions of modules that are able to coordinate to behave intelligently. Clustering the modules in modular robots has many ...
A distributed and parallel control mechanism for self-reconfiguration of modular robots using L-systems and cellular automata

For distributed self-reconfiguration of Modular Self-Reconfigurable (MSR) robots, one of the main difficulties is the contradiction between limited information of decentralized modules and well-organized global structure. This paper presents a ...
SoftCubes: Stretchable and self-assembling three-dimensional soft modular matter

This paper proposes a self-assembling soft modular matter, called SoftCubes, where soft-bodied modules are disassembled into a flexible string by an external tension and self-assemble into the preprogrammed three-dimensional (3D) shape. The developed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

July 2018

2312 pages

General Chairs:
Elisabeth Andre
Augsburg University, Germany
,
Sven Koenig
University of Southern California, USA
,
Program Chairs:
Mehdi Dastani
Utrecht University, Netherlands
,
Gita Sukthankar
University of Central Florida, USA

Sponsors

In-Cooperation

ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 09 July 2018

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ANR
Labex ACTION program
Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq Brazil)
French ``Investissements d'Avenir' program

Conference

AAMAS '18

Sponsor:

SIGAI

AAMAS '18: Autonomous Agents and MultiAgent Systems

July 10 - 15, 2018

Stockholm, Sweden

Acceptance Rates

AAMAS '18 Paper Acceptance Rate 149 of 607 submissions, 25%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu LGuo BZhang QSun ZZhang JYu ZAgmon NAn BRicci AYeoh W(2023)Learning to Self-Reconfigure for Freeform Modular Robots via Altruism Multi-Agent Reinforcement LearningProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598996(2544-2546)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598996
Wu LGuo BZhang QSun ZZhang JYu ZElkind E(2023)Learning to self-reconfigure for freeform modular robots via altruism proximal policy optimizationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/610(5494-5502)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/610
Bassil JMakhoul APiranda BBourgeois J(2023)Distributed Size-constrained Clustering Algorithm for Modular Robot-based Programmable MatterACM Transactions on Autonomous and Adaptive Systems10.1145/358028218:1(1-21)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3580282
Pescher FNapp NPiranda BBourgeois JEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)GAPCoDProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398881(1028-1036)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398881
D'Angelo GD'Emidio MDas SNavarra APrencipe GEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Leader Election and Compaction for Asynchronous Silent Programmable MatterProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398798(276-284)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398798
Thalamy PPiranda BBourgeois JElkind EVeloso MAgmon NTaylor M(2019)Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding StructureProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331685(140-148)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331685

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten