Article

Programmable self-assembly using biologically-inspired multiagent control

Author:

Radhika NagpalAuthors Info & Claims

AAMAS '02: Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1

Pages 418 - 425

https://doi.org/10.1145/544741.544839

Published: 15 July 2002 Publication History

Abstract

This paper presents a programming language that species a robust process for shape formation on a sheet of identically programed agents, by combining local organization primitives from epithelial cell orphogenesis and Drosophila cell differentiation with combination rules from geometry. This work represents a significantly different approach to the design of self-organizing systems: the desired global shape is specified using an abstract geometry-based language, and the agent program is directly compiled from the global specification. The resulting self-assembly process is extremely reliable in the face of random agent distributions, random agent death and varying agent numbers, without relying on global coordinates or centralized control.

References

[1]

H. Abelson, D. Allen, D. Coore, C. Hanson, G. Homsy, T. Knight, R. Nagpal, E. Rauch, G. Sussman, and R. Weiss. Amorphous computing. Communications of the ACM, 43(5), May 2000.

Digital Library

[2]

A. Berlin. Towards Intelligent Structures: Active Control of Buckling. PhD thesis, MIT, Dept of Electrical Eng. and Computer Science, May 1994.

Digital Library

[3]

D. Coore. Botanical Computing: A Developmental Approach to Generating Interconnect Topologies on an Amorphous Computer. PhDthesis, MIT, Dept of Electrical Eng. and Computer Science, Feb. 1999.

Digital Library

[4]

S. Forrest and M. Mitchell. What makes a problem hard for a genetic algorithm? Machine Learning, 13: 285--319, 1993.

Digital Library

[5]

Hogg, Bojinov, and Casal. Multiagent control of self-reconfigurable robots. In 4th International Conference on Multi-Agent Systems, July 2000.

Digital Library

[6]

H. Huzita and B. Scimemi. The algebra of paper-folding. In First International Meeting of Origami Science and Technology, Ferrara, Italy, 1989.

[7]

R. Jack an, S. Brittain, A. Ada s, M. Prentiss, and G. Whitesides. Design and fabrication of topologically complex, three-dimensional icrostructures. Science, 280: 2089--2091, 1998.

[8]

L. Kleinrock and J. Silvester. Optimum tranmission radii for packet radio networks or why six is a magic number. In Proc. Natnl. Telecomm. Conf., pages 4.3.1--4.3.5, 1978.

[9]

R. J. Lang. A computational algorith for origami design. In Annual Symposium on Computational Geometry, Philadelphia, PA, 1996.

Digital Library

[10]

P. A. Lawrence. TheMakingofaFly: heGeneicsof Animal Design. Blackwell Science, Oxford, U.K., 1992.

[11]

M. Mataric. Issues and approaches in the design of collective autonomous agents. Robotics and Autonomous Systems, 16((2--4)): 321--331, Dec. 1995.

[12]

R. Nagpal. Programmable Self-Assembly: Constructing Global Shape using Biologically-inspired Local Interactions and Origami Mathematics. PhDthesis, MIT, Dept of Electrical Engineering and Computer Science, June 2001.

Digital Library

[13]

G. Odell, G. Oster, P. Alberch, and B. Burnside. The mechanical basis of orphogenesis: 1. epithelial folding and invagination. Developmental Biology, 85: 446--462, 1981.

[14]

Pamecha, Ebert-Uphoff, and Chirikjian. Useful metrics for modular robot planning. IEEE Trans. on Robotics and Automation, 13(4), Aug. 1997.

[15]

M. Resnick. Turtles, Termites and Traffic Jams. MIT Press, Cambridge, MA, 1994.

Digital Library

[16]

R. Weiss, G. Homsy, and T. Knight. Toward in vivo digital circuits. In Dimacs Workshop on Evolution as Computation, Jan. 1999.

[17]

L. Wolpert. Positional information and the spatial pattern of cellular differentiation. Journal of Theore ical Biology, 25: 1--47, 1969.

Cited By

Valentini GHamann HDorigo M(2022)Global-to-Local Design for Self-Organized Task Allocation in SwarmsIntelligent Computing10.34133/2022/97616942022Online publication date: Jan-2022
https://doi.org/10.34133/2022/9761694
Kua JLoke SArora CFernando NRanaweera C(2021)Internet of Things in Space: A Review of Opportunities and Challenges from Satellite-Aided Computing to Digitally-Enhanced Space LivingSensors10.3390/s2123811721:23(8117)Online publication date: 4-Dec-2021
https://doi.org/10.3390/s21238117
Hrabia CLützenberger MAlbayrak S(2018)Towards adaptive multi-robot systems: self-organization and self-adaptationThe Knowledge Engineering Review10.1017/S026988891800017633Online publication date: 4-Oct-2018
https://doi.org/10.1017/S0269888918000176
Show More Cited By

Index Terms

Programmable self-assembly using biologically-inspired multiagent control
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems
  2. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Biologically-inspired control for self-adaptive multiagent systems
An agent framework for agent societies
SPLASH '11 Workshops: Proceedings of the compilation of the co-located workshops on DSM'11, TMC'11, AGERE! 2011, AOOPES'11, NEAT'11, & VMIL'11

A key weakness of agent frameworks is the difficulty of specifying and controlling the global (emergent) behavior of the Multi-Agent System (MAS) in which they operate. The spatial computing language Proto, however, compiles descriptions of global ...
Biologically-inspired self-assembly of two-dimensional shapes using global-to-local compilation
IJCAI'03: Proceedings of the 18th international joint conference on Artificial intelligence

In this paper, we present a programming language approach for the assembly of arbitrary two-dimensional shapes by decentralized, identically-programmed agents. Our system compiles a predetermined global shape into a program that instructs these agents ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '02: Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1

July 2002

540 pages

ISBN:1581134800

DOI:10.1145/544741

Conference Chairs:
Maria Gini
University of Minnesota, USA
,
Toru Ishida
Kyoto University, Japan
,
Program Chairs:
Cristiano Castelfranchi
CNR and Università di Siena, Italy
,
W. Lewis Johnson
University of Southern California, USA

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

AAMAS02

Sponsor:

AAMAS02: The First International Joint Conference on Autonomous Agents and Multi-Agent Systems ( formerly known as Autonomous Agents )

July 15 - 19, 2002

Bologna, Italy

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
1,266
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Valentini GHamann HDorigo M(2022)Global-to-Local Design for Self-Organized Task Allocation in SwarmsIntelligent Computing10.34133/2022/97616942022Online publication date: Jan-2022
https://doi.org/10.34133/2022/9761694
Kua JLoke SArora CFernando NRanaweera C(2021)Internet of Things in Space: A Review of Opportunities and Challenges from Satellite-Aided Computing to Digitally-Enhanced Space LivingSensors10.3390/s2123811721:23(8117)Online publication date: 4-Dec-2021
https://doi.org/10.3390/s21238117
Hrabia CLützenberger MAlbayrak S(2018)Towards adaptive multi-robot systems: self-organization and self-adaptationThe Knowledge Engineering Review10.1017/S026988891800017633Online publication date: 4-Oct-2018
https://doi.org/10.1017/S0269888918000176
Oh HRamezan Shirazi ASun CJin Y(2017)Bio-inspired self-organising multi-robot pattern formationRobotics and Autonomous Systems10.1016/j.robot.2016.12.00691:C(83-100)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.robot.2016.12.006
Mahmoud MXia Y(2017)The interaction between control and computing theoriesInternational Journal of Automation and Computing10.1007/s11633-017-1070-214:3(254-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11633-017-1070-2
Yeom K(2017)Evolutionary Metaphor of Genetic Encoding for Self-organizable RobotsIntelligent Computing Theories and Application10.1007/978-3-319-63309-1_13(131-139)Online publication date: 20-Jul-2017
https://doi.org/10.1007/978-3-319-63309-1_13
Valentini GValentini G(2017)IntroductionAchieving Consensus in Robot Swarms10.1007/978-3-319-53609-5_1(1-5)Online publication date: 16-Feb-2017
https://doi.org/10.1007/978-3-319-53609-5_1
Nallur VCardozo NClarke S(2016)Clonal plasticityProceedings of the 11th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1145/2897053.2897067(122-128)Online publication date: 14-May-2016
https://dl.acm.org/doi/10.1145/2897053.2897067
Dutta A(2016)Self-Assembly in Heterogeneous Multi-agent System Using Constrained Matching Algorithm2016 IEEE/WIC/ACM International Conference on Web Intelligence (WI)10.1109/WI.2016.0056(351-358)Online publication date: Oct-2016
https://doi.org/10.1109/WI.2016.0056
Pinciroli CBeltrame G(2016)Buzz: An extensible programming language for heterogeneous swarm robotics2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2016.7759558(3794-3800)Online publication date: Oct-2016
https://doi.org/10.1109/IROS.2016.7759558
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents