Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Robots
Published in: Autonomous Robots 4/2019

28-04-2018

Distributed configuration formation with modular robots using (sub)graph isomorphism-based approach

Authors: Ayan Dutta, Prithviraj Dasgupta, Carl Nelson

Published in: Autonomous Robots | Issue 4/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the problem of configuration formation in modular robot systems where a set of modules that are initially in different configurations and located at different locations are required to assume appropriate positions so that they can get into a new, user-specified, target configuration. We propose a novel algorithm based on (sub)graph isomorphism, where the modules select locations or spots in the target configuration using a utility-based framework, while retaining their original configuration to the greatest extent possible, to reduce the time and energy required by the modules to disconnect and connect multiple times to form the target configuration. We have shown analytically that our proposed algorithm is complete and guarantees a Pareto-optimal allocation. Experimental simulations of our algorithm with different numbers of modules in different initial configurations and located initially at different locations, show that the planning time of our algorithm is nominal (order of msec for 100 modules). We have also compared our algorithm against a market-based allocation algorithm and shown that our proposed algorithm performs better in terms of time and number of messages exchanged.
previous article Predicting the global structure of indoor environments: A constructive machine learning approach
next article Simultaneous learning of hierarchy and primitives for complex robot tasks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
A common coordinate system can be maintained by modules for localizing themselves following the model described in Suzuki and Yamashita (1997).
 
Literature
Ahmadzadeh, H., & Masehian, E. (2015). Modular robotic systems: Methods and algorithms for abstraction, planning, control, and synchronization. Artificial Intelligence, 223, 27–64.MathSciNetCrossRefMATH
Aho, A. V., & Hopcroft, J. E. (1974). The design and analysis of computer algorithms. Bengaluru: Pearson Education India.MATH
Akutsu, T. (1993). A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 76(9), 1488–1493.
Alonso-Mora, J., Breitenmoser, A., Rufli, M., Siegwart, R., & Beardsley, P. (2011). Multi-robot system for artistic pattern formation. In 2011 IEEE international conference on robotics and automation (ICRA) (pp. 4512–4517). IEEE.
Asadpour, M., Sproewitz, A., Billard, A., Dillenbourg, P., & Ijspeert, A.J. (2008). Graph signature for self-reconfiguration planning. In IEEE/RSJ international conference on intelligent robots and systems, 2008. IROS 2008 (pp. 863–869). IEEE.
Baca, J., Hossain, S., Dasgupta, P., Nelson, C. A., & Dutta, A. (2014). Modred: Hardware design and reconfiguration planning for a high dexterity modular self-reconfigurable robot for extra-terrestrial exploration. Robotics and Autonomous Systems, 62(7), 1002–1015.CrossRef
Baca, J., Woosley, B., Dasgupta, P., Dutta, A., & Nelson, C. (2016). Coordination of modular robots by means of topology discovery and leader election: Improvement of the locomotion case. In Distributed autonomous robotic systems (pp. 447–458). Berlin: Springer.
Bertsekas, D. P. (1990). The auction algorithm for assignment and other network flow problems: A tutorial. Interfaces, 20(4), 133–149.CrossRef
Brandes, U. (2001). A faster algorithm for betweenness centrality*. Journal of Mathematical Sociology, 25(2), 163–177.CrossRefMATH
Chen, I. M., & Burdick, J. W. (1998). Enumerating the non-isomorphic assembly configurations of modular robotic systems. The International Journal of Robotics Research, 17(7), 702–719.CrossRef
Chirikjian, G., Pamecha, A., & Ebert-Uphoff, I. (1996). Evaluating efficiency of self-reconfiguration in a class of modular robots. Journal of Field Robotics, 13(5), 317–338.MATH
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (sub) graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10), 1367–1372.CrossRef
Dasgupta, P., Ufimtsev, V., Nelson, C., & Hossain, S. (2012). Dynamic reconfiguration in modular robots using graph partitioning-based coalitions. In Proceedings of the 11th international conference on autonomous agents and multiagent systems-volume 1. International foundation for autonomous agents and multiagent systems (pp. 121–128).
Davis, J. D., Sevimli, Y., Eldridge, B. R., & Chirikjian, G. S. (2016). Module design and functionally non-isomorphic configurations of the Hex-DMR II system. Journal of Mechanisms and Robotics, 8(5), 051,008.CrossRef
Dutta, A., Chaudhuri, S.G., Datta, S., & Mukhopadhyaya, K. (2012). Circle formation by asynchronous fat robots with limited visibility. In Distributed Computing and Internet Technology (pp. 83–93). Berlin: Springer.
Dutta, A., & Dasgupta, P. (2016). Simultaneous configuration formation and information collection by modular robotic systems. In 2016 IEEE international conference on robotics and automation (ICRA) (pp. 5216–5221).
Dutta, A., Dasgupta, P., & Nelson, C. (2018). Distributed adaptive locomotion learning in modred modular self-reconfigurable robot. In Distributed Autonomous Robotic Systems (pp. 345–357). Cham: Springer.
Enner, F., Rollinson, D., & Choset, H. (2013). Motion estimation of snake robots in straight pipes. In International conference on robotics and automation (pp. 5148–5153).
Fitch, R., & Butler, Z. (2008). Million module march: Scalable locomotion for large self-reconfiguring robots. The International Journal of Robotics Research, 27(3–4), 331–343.CrossRef
Hossain, S., Nelson, C. A., Chu, K. D., & Dasgupta, P. (2014). Kinematics and interfacing of modred: A self-healing capable, four-dof modular self-reconfigurable robot. JMR, 13, 1256.
Hou, F., & Shen, W.M. (2008). Distributed, dynamic, and autonomous reconfiguration planning for chain-type self-reconfigurable robots. In IEEE international conference on robotics and automation, 2008. ICRA 2008 (pp. 3135–3140). IEEE.
Hou, F., & Shen, W. M. (2014). Graph-based optimal reconfiguration planning for self-reconfigurable robots. Robotics and Autonomous Systems, 62(7), 1047–1059.CrossRef
Kamimura, A., Kurokawa, H., Yoshida, E., Tomita, K., Kokaji, S., & Murata, S. (2004). Distributed adaptive locomotion by a modular robotic system, M-TRAN II. In Proceedings. 2004 IEEE/RSJ international conference on intelligent robots and systems, 2004.(IROS 2004) (Vols. 3, pp. 2370–2377). IEEE.
Klavins, E. (2007). Programmable self-assembly. IEEE, Control Systems, 27(4), 43–56.CrossRef
Knight, S., Rabideau, G., Chien, S., Engelhardt, B., & Sherwood, R. (2001). Casper: Space exploration through continuous planning. IEEE Intelligent Systems, 16(5), 70–75.CrossRef
Kobler, J., Schöning, U., & Torán, J. (2012). The graph isomorphism problem: Its structural complexity. Berlin: Springer.MATH
Kurokawa, H., Tomita, K., Kamimura, A., Kokaji, S., Hasuo, T., & Murata, S. (2008). Distributed self-reconfiguration of M-TRAN III modular robotic system. The International Journal of Robotics Research, 27(3–4), 373–386.CrossRef
Nelson, C.A., & Cipra, R.J. (2004). An algorithm for efficient self-reconfiguration of chain-type unit-modular robots. In ASME DETC, (pp. 1283–1291). New York City: American Society of Mechanical Engineers.
Neubert, J., & Lipson, H. (2016). Soldercubes: A self-soldering self-reconfiguring modular robot system. Autonomous Robots, 40(1), 139–158.CrossRef
Pamecha, A., Ebert-Uphoff, I., & Chirikjian, G. S. (1997). Useful metrics for modular robot motion planning. IEEE Transactions on Robotics and Automation, 13(4), 531–545.CrossRefMATH
Park, M., Chitta, S., Teichman, A., & Yim, M. (2008). Automatic configuration recognition methods in modular robots. The International Journal of Robotics Research, 27(3–4), 403–421.CrossRef
Raymond, J. W., & Willett, P. (2002). Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design, 16(7), 521–533.CrossRef
Rosa, M., Goldstein, S., Lee, P., Campbell, J., & Pillai, P. (2006). Scalable shape sculpturing via hole motions. In IEEE international conference on robotics and automation, (pp. 1462–1468). Orlando, FL.
Rubenstein, M., Cornejo, A., & Nagpal, R. (2014). Programmable self-assembly in a thousand-robot swarm. Science, 345(6198), 795–799.CrossRef
Shamir, R., & Tsur, D. (1997). Faster subtree isomorphism. In Proceedings of the Fifth Israeli symposium on theory of computing and systems, 1997 (pp. 126–131). IEEE.
Stoy, K., Brandt, D., & Christensen, D. J. (2010). Self-reconfigurable robots: An introduction. Cambridge: The MIT Press.
Suzuki, I., & Yamashita, M. (1997). Agreement on a common XY coordinate system by a group of mobile robots. In Intelligent Robots—Sensing, Modeling And Planning (pp. 305–321).
Tolley, M.T., & Lipson, H. (2010). Fluidic manipulation for scalable stochastic 3D assembly of modular robots. In 2010 IEEE international conference on robotics and automation (ICRA) (pp. 2473–2478). IEEE.
Werfel, J., & Nagpal, R. (2008). Three-dimensional construction with mobile robots and modular blocks. The International Journal of Robotics Research, 27(3–4), 463–479.CrossRef
Yim, M., Shen, W. M., Salemi, B., Rus, D., Moll, M., Lipson, H., et al. (2007). Modular self-reconfigurable robot systems [grand challenges of robotics]. IEEE Robotics & Automation Magazine, 14(1), 43–52.CrossRef
Metadata
Title
Distributed configuration formation with modular robots using (sub)graph isomorphism-based approach
Authors
Ayan Dutta
Prithviraj Dasgupta
Carl Nelson
Publication date
28-04-2018
Publisher
Springer US
Published in
Autonomous Robots / Issue 4/2019
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-018-9759-9

Other articles of this Issue 4/2019

Autonomous Robots 4/2019 Go to the issue

OriginalPaper

Simultaneous learning of hierarchy and primitives for complex robot tasks

OriginalPaper

Computing the best grasp in a discrete point set with wrench-oriented grasp quality measures

OriginalPaper

Linking human motions and objects to language for synthesizing action sentences

OriginalPaper

Robust and adaptive dynamic controller for fully-actuated robots in operational space under uncertainties

OriginalPaper

Predicting the global structure of indoor environments: A constructive machine learning approach

OriginalPaper

Learning position and orientation dynamics from demonstrations via contraction analysis