Sage Journals: Discover world-class research

Abstract

Stochastic assembly approaches can reduce the power, computation, and/or actuation demands on assembly systems by taking advantage of probabilistic processes. At the same time, however, they relinquish the efficiency and predictability of deterministic alternatives. This makes planning error-free assembly sequences challenging, particularly in the face of changing environmental conditions or goals. Here we address these challenges with an on-line approach to assembly planning for stochastically reconfigurable systems where the spatial and temporal availability of modules is uncertain, either due to a stochastic assembly mechanism, resource fluctuations, or large numbers of uncoordinated agents. We propose an assembly algorithm that is guaranteed to find an assembly path for finite-sized, connected objects. This is achieved by sampling the space of possible assembly paths to the target structure that satisfy assembly constraints. Assembly is accelerated by pursuing multiple paths in parallel. The algorithm computes these parallel assembly paths on-line during assembly and is thus able to adapt to changing conditions, as well as predict the remaining assembly time. For situations where the number of paths found exceeds the number that can be pursued in parallel, the assembly algorithm further maximizes assembly rates according to domain-specific local assembly costs.

Keywords

Cellular and modular robots assembly planning self-assembly biologically-inspired robots micro/nano robots reconfigurable robots

Get full access to this article

View all access options for this article.

References

Ayanian

White

Halaz

Yim

Kumar

(2008) Stochastic control for self-assembly of XBots. In: Proceedings of ASME 2008 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, New York, pp. 1169–1176.

Detweiler

Vona

Yoon

Yun

S.-K

Rus

(2007) Self-assembling mobile linkages. IEEE Robotics and Automation Magazine 14: 45–55.

Everist

Mogharei

Suri

Ranasignhe

Will

Shen

W-M

(2004) A system for in-space assembly. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Sendai, Japan, pp. 2356–2361.

Fitch

Butler

Rus

(2003) Reconfiguration planning for heterogeneous self-reconfiguring robots. In: Intelligent Robots and Systems, Las Vegas, NV, pp. 2460–2467.

Gibson

Bruck

(2000) Efficient exact stochastic simulation of chemical systems with many species and many channels. Physical Chemistry A 104: 1876–1889.

Gillespie

(1977) Exact stochastic simulation of coupled chemical reactions. Physical Chemistry 81: 2340–2361.

Gilpin

Kotay

Rus

Vasilescu

(2008) Miche: modular shape formation by self-disassembly. The International Journal of Robotics Research 27: 345–372.

Griffith

Goldwater

Jacobson

(2005) Robotics: self-replication from random parts. Nature 437: 636.

Hjelle

Lipson

(2009) A robotically reconfigurable truss. In: Proceedings of ASME/IFToMM International Conference on Reconfigurable Mechanisms and Robots, London.

10.

Jones

Mataric

(2004) Automatic synthesis of communication-based coordinated multi-robot systems. In: Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, pp. 381–387.

11.

Klavins

Ghrist

Lipsky

(2006) A grammatical approach to self-organizing robotic systems. IEEE Transactions on Automatic Control 51: 949–962.

12.

Krishnan

Tolley

Lipson

Erickson

(2009) Hydrodynamically tunable affinities for fluidic assembly. Langmuir 25: 3769–3774.

13.

LaValle

Kuffner

(1999) Randomized kinodynamic planning. In: Proceedings of the International Conference on Robotics and Automation, Detroit, MI, pp. 473–479.

14.

Lerman

Jones

Galstyan

Mataric

(2006) Analysis of dynamic task allocation in multi-robot systems. International Journal of Robotics Research 25: 225–241.

15.

Lobo

Hjelle

Lipson

(2009) Reconfiguration algorithms for robotically manipulatable structures. In: Proceedings of the ASME/IFToMM International Conference on Reconfigurable Mechanisms and Robots, London.

16.

Murata

Kurokawa

(2007) Self-reconfigurable robots: shape-changing cellular robots can exceed conventional robot flexibility. IEEE Robotics and Automation Magazine 14: 71–78.

17.

Nagpal

Shrobe

Bachrach

(2003) Organizing a global coordinate system from local information on an ad hoc sensor network. In: Proceedings of the International Workshop on Information Processing in Sensor Networks, Palo Alto, CA, pp. 333–348.

18.

Napp

Burden

Klavins

(2006) The statistical dynamics of programmed self-assembly. In: Proceedings of the IEEE International Conference of Robotics and Automation, Orlando, FL.

19.

Rus

Vona

(2001) Crystalline robots: self-reconfiguration with compressible unit-modules. Autonomous Robots 10: 107–124.

20.

Sacerdoti

(1975) The nonlinear nature of plans. In: Proceedings of the Joint Conference on Artificial Intelligence, Tbilisi, Georgia, p. 206.

21.

Terada

Murata

(2004) Automatic assembly system for a largescale modular structure - hardware design of module and assembler robot. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, pp. 2349–2355.

22.

Tolley

Kalontarov

Neubert

Erickson

Lipson

(2010) Stochastic modular robotic systems: a study of fluidic assembly strategies. IEEE Transactions on Robotics 26: 518–530.

23.

Tolley

Krishnan

Erickson

Lipson

(2008) Dynamically programmable fluidic assembly. Applied Physics Letters 93: 254105-1-3.

24.

Tomita

Murata

Kurokawa

Yoshida

Kokaji

(1999) Self-assembly and self-repair method for a distributed mechanical system. IEEE Transactions on Robotics and Automation 15: 1035–1045.

25.

Varshavskaya

Kaelbling

Rus

(2008) Automated design of adaptive controllers for modular robots using reinforcement learning. The International Journal of Robotics Research 27: 505–526.

26.

Werfel

Bar-Yam

Rus

Nagpal

(2006) Distributed construction by mobile robots with enhanced building blocks. In: Proceedings of International Conference on Robotics and Automation, Orlando, FL, pp. 2787–2794.

27.

Werfel

Nagpal

(2008) Three-dimensional construction with mobile robots and modular blocks. The International Journal of Robotics Research 27: 463–479.

28.

White

Zykov

Bongard

Lipson

(2005) Three dimensional stochastic reconfiguration of modular robots. In: Proceedings of Robotics Science and Systems, Cambridge, pp. 161–168.

29.

White

Kopanski

Lipson

(2004) Stochastic self-reconfigurable cellular robotics. In: Proceeding of the IEEE International Conference on Robotics and Automation, vol. 3, New Orleans, LA, pp. 2888–2893.

30.

Yim

Shen

W-M

Salemi

Rus

Moll

Lipson

. (2007). Modular self-reconfigurable robotic systems. IEEE Robotics and Automation Magazine 14: 43–52.

31.

Zykov

Lipson

(2007) Experiment design for stochastic three-dimensional reconfiguration of modular robots. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Self-Reconfigurable Robotics Workshop, San Diego, CA.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

On-line assembly planning for stochastically reconfigurable systems

Abstract

Keywords

Get full access to this article

References

Supplementary Material