Skip to main content
Top
Published in: The Journal of Supercomputing 2/2014

01-08-2014

An energy and memory-efficient distributed self-reconfiguration for modular sensor/robot networks

Authors: Hicham Lakhlef, Hakim Mabed, Julien Bourgeois

Published in: The Journal of Supercomputing | Issue 2/2014

Log in

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

search-config
loading …

Abstract

Self-reconfiguration for mobile microrobots currently needs a positioning system and a map of the target shape. Traditional positioning solutions, such as GPS or multilateration are not applicable in the micro-world, and maps sharing does not scale. In the literature, if we want a self-reconfiguration of microrobots to a target shape that consists of millions of positions, each microrobot should have a memory capacity of at least million positions. Therefore, this is not scalable. In this paper, nodes do not record any position. We present self-reconfiguration methods where nodes are unaware of their positions and where they do not have the final coordinates of each microrobot. In other words, nodes do not store the coordinates that build the target shape. Therefore, memory usage for each node is hugely reduced to \(O(1)\) and communications are limited to neighboring nodes. These algorithms aim to improve the logical topology of a set of microrobots by restructuring their physical topology. To that end, we consider here the case of restructuring a set of microrobots from a chain to a square and we study two algorithms: the first algorithm ensures the connectivity of the network at the end of the algorithm, where the second guarantees the connectivity of the network through the execution time. The paper presents both analytical and experimental assessments of the algorithms performances using the declarative language \(Meld\) and executed under the Dynamic Physical Rendering Simulator (DPRSim).

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

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!

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!

Footnotes
1
The time of one movement depends on the size (the diameter) of the microrobot, as shown in Sect. 4.
 
Literature
1.
go back to reference Ashley-Rollman MP, Goldstein SC, Lee P, Mowry TC, Pillai P (2007) Meld: a declarative approach to programming ensembles. In: Proceedings of the IEEE international conference on intelligent robots and systems (IROS ’07) Ashley-Rollman MP, Goldstein SC, Lee P, Mowry TC, Pillai P (2007) Meld: a declarative approach to programming ensembles. In: Proceedings of the IEEE international conference on intelligent robots and systems (IROS ’07)
2.
go back to reference Ashley-Rollman MP, Lee P, Goldstein SC, Pillai P, Campbell JD (2009) A language for large ensembles of independently executing nodes. In: Proceedings of the international conference on logic programming (ICLP ’09) Ashley-Rollman MP, Lee P, Goldstein SC, Pillai P, Campbell JD (2009) A language for large ensembles of independently executing nodes. In: Proceedings of the international conference on logic programming (ICLP ’09)
3.
go back to reference Bourgeois J, Goldstein SC (2012) Distributed intelligent MEMS: progresses and perspectives. Thirrd international conference on ICT innovations, Advances in Intelligent and Soft Computing, Ohrid, pp 15–25 Bourgeois J, Goldstein SC (2012) Distributed intelligent MEMS: progresses and perspectives. Thirrd international conference on ICT innovations, Advances in Intelligent and Soft Computing, Ohrid, pp 15–25
4.
go back to reference Bojinov H, Casal A, Hogg T (2000) Emergent structures in modular self-reconfigurable robots. In: Proceedings of the IEEE international conference on robotics and automation, vol 2. IEEE Computer Society Press, Los Alamitos, pp 1734–1741 Bojinov H, Casal A, Hogg T (2000) Emergent structures in modular self-reconfigurable robots. In: Proceedings of the IEEE international conference on robotics and automation, vol 2. IEEE Computer Society Press, Los Alamitos, pp 1734–1741
5.
go back to reference Bulusu N, Heidemann J, Estrin D (2000) GPS-less low-cost outdoor localization for very small devices. IEEE Pers Commun Mag 7:28–34CrossRef Bulusu N, Heidemann J, Estrin D (2000) GPS-less low-cost outdoor localization for very small devices. IEEE Pers Commun Mag 7:28–34CrossRef
6.
go back to reference Butler ZJ, Kotay K, Rus D, Tomita K (2004) Generic decentralized control for lattice-based self-reconfigurable robots. Int J Robot Res 23(9):919–937CrossRef Butler ZJ, Kotay K, Rus D, Tomita K (2004) Generic decentralized control for lattice-based self-reconfigurable robots. Int J Robot Res 23(9):919–937CrossRef
7.
go back to reference Dewey D, Srinivasa SS, Ashley-Rollman MP, Rosa MD, Pillai P, Mowry TC, Campbell JD, Goldstein SC (2008) Generalizing metamodules to simplify planning in modular robotic systems. In: Proceedings of IEEE/RSJ 2008 international conference on intelligent robots and systems (IROS ’08) Dewey D, Srinivasa SS, Ashley-Rollman MP, Rosa MD, Pillai P, Mowry TC, Campbell JD, Goldstein SC (2008) Generalizing metamodules to simplify planning in modular robotic systems. In: Proceedings of IEEE/RSJ 2008 international conference on intelligent robots and systems (IROS ’08)
8.
go back to reference Funiak S, Pillai P, Ashley-Rollman MP, Campbell JD, Goldstein SC (2008) Distributed localization of modular robot ensembles. In: Proceedings of robotics science and systems Funiak S, Pillai P, Ashley-Rollman MP, Campbell JD, Goldstein SC (2008) Distributed localization of modular robot ensembles. In: Proceedings of robotics science and systems
9.
go back to reference Jones C, Mataric MJ (2003) From local to global behavior in intelligent self-assembly. In: Proceedings of the 2003 IEEE international conference on robotics and automation, ICRAM 2003, vol 1. IEEE Computer Society Press, Los Alamitos, pp 721–726 Jones C, Mataric MJ (2003) From local to global behavior in intelligent self-assembly. In: Proceedings of the 2003 IEEE international conference on robotics and automation, ICRAM 2003, vol 1. IEEE Computer Society Press, Los Alamitos, pp 721–726
10.
go back to reference Jeon S, Ji C (2008) Randomized distributed configuration management of wireless networks: multi-layer Markov random fields and near-optimality CoRR abs/0809.1916 Jeon S, Ji C (2008) Randomized distributed configuration management of wireless networks: multi-layer Markov random fields and near-optimality CoRR abs/0809.1916
11.
go back to reference Hollar S, Flynn A, Bellew C, Pister KSJ (2003) Solar powered 10 mg silicon robot. In: MEMS, Kyoto Hollar S, Flynn A, Bellew C, Pister KSJ (2003) Solar powered 10 mg silicon robot. In: MEMS, Kyoto
12.
go back to reference Karagozler ME, Thaker A, Goldstein SC, Ricketts DS (2011) Electrostatic actuation and control of micro robots using a post-processed high-voltage SOI CMOS chip. IEEE international symposium on circuits and systems (ISCAS) Karagozler ME, Thaker A, Goldstein SC, Ricketts DS (2011) Electrostatic actuation and control of micro robots using a post-processed high-voltage SOI CMOS chip. IEEE international symposium on circuits and systems (ISCAS)
13.
go back to reference Kotay K, Rus D, Vona M, McGray C (1998) The self-reconfiguring robotic molecule. In: Proceedings of the 1998 IEEE international conference on robotics and automation, Leuven Kotay K, Rus D, Vona M, McGray C (1998) The self-reconfiguring robotic molecule. In: Proceedings of the 1998 IEEE international conference on robotics and automation, Leuven
14.
go back to reference Kribi F, Minet P, Laouiti A (2009) Redeploying mobile wireless sensor networks with virtual forces. IFIP Wireless Days, Paris Kribi F, Minet P, Laouiti A (2009) Redeploying mobile wireless sensor networks with virtual forces. IFIP Wireless Days, Paris
15.
go back to reference Lakhlef H, Mabed H, Bourgeois J (2013) Distributed and efficient algorithm for self-reconfiguration of MEMS microrobots. In: The 28th ACM symposium on applied computing, Coimbra Lakhlef H, Mabed H, Bourgeois J (2013) Distributed and efficient algorithm for self-reconfiguration of MEMS microrobots. In: The 28th ACM symposium on applied computing, Coimbra
16.
go back to reference Lakhlef H, Mabed H, Bourgeois J (2013) Distributed and dynamic map-less self-reconfiguration for microrobot networks. In: IEEE NCA 2013, 12th IEEE international symposium on network computing and applications, Cambridge, pp 55–60 Lakhlef H, Mabed H, Bourgeois J (2013) Distributed and dynamic map-less self-reconfiguration for microrobot networks. In: IEEE NCA 2013, 12th IEEE international symposium on network computing and applications, Cambridge, pp 55–60
17.
go back to reference Lakhlef H, Mabed H, Bourgeois J (2013) Parallel self-reconfiguration for MEMS Microrobot. In: Seventh IEEE international conference on computer as a tool, Zagreb, pp 283–290 Lakhlef H, Mabed H, Bourgeois J (2013) Parallel self-reconfiguration for MEMS Microrobot. In: Seventh IEEE international conference on computer as a tool, Zagreb, pp 283–290
18.
go back to reference Lakhlef H, Mabed H, Bourgeois J (2013) Dynamicity to save energy in microrobots reconfiguration. In: Tenth IEEE international conference on ubiquitous intelligence and computing (UIC-2013), Italy, pp 246–253 Lakhlef H, Mabed H, Bourgeois J (2013) Dynamicity to save energy in microrobots reconfiguration. In: Tenth IEEE international conference on ubiquitous intelligence and computing (UIC-2013), Italy, pp 246–253
20.
go back to reference Liu L, Antonopoulos N, Mackin S (2008) Managing peer-to-peer networks with human tactics in social interactions. J Supercomput 44(3):217–236CrossRef Liu L, Antonopoulos N, Mackin S (2008) Managing peer-to-peer networks with human tactics in social interactions. J Supercomput 44(3):217–236CrossRef
21.
go back to reference Liu L, Xu J, Russell D, Antonopoulos N (2008) Self-organization of autonomous peers with human strategies. Third international conference on internet and web applications and services, pp 348–357 Liu L, Xu J, Russell D, Antonopoulos N (2008) Self-organization of autonomous peers with human strategies. Third international conference on internet and web applications and services, pp 348–357
22.
go back to reference Microrobot design using fiber reinforced composites. J Mech Design 130(5) Microrobot design using fiber reinforced composites. J Mech Design 130(5)
23.
go back to reference Mamei M, Roli A, Zambonelli F (2004) Emergence and control of macro spatial structures in perturbed cellular automata, and implications for pervasive computing systems, IEEE transactions on systems, man, and cybernetics, vol 36, no 5; 2005. J Appl Artif Intell 8(9–10):903–919 Mamei M, Roli A, Zambonelli F (2004) Emergence and control of macro spatial structures in perturbed cellular automata, and implications for pervasive computing systems, IEEE transactions on systems, man, and cybernetics, vol 36, no 5; 2005. J Appl Artif Intell 8(9–10):903–919
24.
go back to reference Minet P, Mahfoudh S (December 2009) Energy, bandwidth and time efficiency in data gathering applications. IFIP Wireless Days, Paris Minet P, Mahfoudh S (December 2009) Energy, bandwidth and time efficiency in data gathering applications. IFIP Wireless Days, Paris
25.
go back to reference Moses R, Krishnamurthy D, Patterson R (2003) A self-localization method for wireless sensor networks. Eur J Appl Signal Process 4:348–358CrossRef Moses R, Krishnamurthy D, Patterson R (2003) A self-localization method for wireless sensor networks. Eur J Appl Signal Process 4:348–358CrossRef
26.
go back to reference Petrina AM (2011) Advances in robotics (review). Autom Doc Math Linguist 45(2):43 Petrina AM (2011) Advances in robotics (review). Autom Doc Math Linguist 45(2):43
27.
go back to reference Ravichandran R, Gordon G, Goldstein SC (2007) A scalable distributed algorithm for shape transformation in multi-robot systems. In: Proceedings of the IEEE international conference on intelligent robots and systems (IROS ’07) Ravichandran R, Gordon G, Goldstein SC (2007) A scalable distributed algorithm for shape transformation in multi-robot systems. In: Proceedings of the IEEE international conference on intelligent robots and systems (IROS ’07)
28.
go back to reference Rosa MD, Goldstein SC, Lee P, Campbell JD, Pillai P (2008) Programming modular robots with locally distributed predicates. In: Proceedings of the IEEE international conference on robotics and automation (ICRA ’08) Rosa MD, Goldstein SC, Lee P, Campbell JD, Pillai P (2008) Programming modular robots with locally distributed predicates. In: Proceedings of the IEEE international conference on robotics and automation (ICRA ’08)
29.
go back to reference Rus D, Vona M (2001) Crystalline robots: self-reconfiguration with compressible unit modules. Auton Robots 10(1):107–124CrossRefMATH Rus D, Vona M (2001) Crystalline robots: self-reconfiguration with compressible unit modules. Auton Robots 10(1):107–124CrossRefMATH
30.
go back to reference Soua R, Saidane L, Minet P (April 2010) Sensors deployment enhancement by a mobile robot in wireless sensor networks. IEEE ICN 2010, Les Menuires Soua R, Saidane L, Minet P (April 2010) Sensors deployment enhancement by a mobile robot in wireless sensor networks. IEEE ICN 2010, Les Menuires
31.
go back to reference Stoy K, Nagpal R (2004) Self-reconfiguration using directed growth. Seventh international symposium on distributed autonomous robotic systems (DARs), France Stoy K, Nagpal R (2004) Self-reconfiguration using directed growth. Seventh international symposium on distributed autonomous robotic systems (DARs), France
32.
go back to reference Spears W, Spears D, Hamann J, Heil R (2004) Distributed, physics-based control of swarms of vehicles. Auton Robots 17(2–3):137–162CrossRef Spears W, Spears D, Hamann J, Heil R (2004) Distributed, physics-based control of swarms of vehicles. Auton Robots 17(2–3):137–162CrossRef
33.
go back to reference Stoy K, Nagpal R (2004) Self-repair through scale independent self-reconfiguration. In: Proceedings of 2004 IEEE/RSJ international conference on intelligent robots and systems, Sendai Stoy K, Nagpal R (2004) Self-repair through scale independent self-reconfiguration. In: Proceedings of 2004 IEEE/RSJ international conference on intelligent robots and systems, Sendai
34.
go back to reference Shen W, Will P, Galstyan A (2004) Hormone-inspired self-organization and distributed control of robotic swarms. Auton Robots 17(1):93–105CrossRef Shen W, Will P, Galstyan A (2004) Hormone-inspired self-organization and distributed control of robotic swarms. Auton Robots 17(1):93–105CrossRef
35.
go back to reference Sty K (2006) Using cellular automata and gradients to control self-reconfiguration. Robot Auton Syst 54(2):135–141CrossRef Sty K (2006) Using cellular automata and gradients to control self-reconfiguration. Robot Auton Syst 54(2):135–141CrossRef
36.
go back to reference Walter J, Tsai B, Amato N (2005) Algorithms for fast concurrent reconfiguration of hexagonal metamorphic robots. IEEE Trans Robot 21(4):621–631CrossRef Walter J, Tsai B, Amato N (2005) Algorithms for fast concurrent reconfiguration of hexagonal metamorphic robots. IEEE Trans Robot 21(4):621–631CrossRef
37.
go back to reference Walter J, Welch J, Amato N (2004) Distributed reconfiguration of metamorphic robot chains. Springer Verlag J Distrib Comput 17:171–189 Walter J, Welch J, Amato N (2004) Distributed reconfiguration of metamorphic robot chains. Springer Verlag J Distrib Comput 17:171–189
38.
go back to reference Wong S, Walter J (2013) Deterministic distributed algorithm for self-reconfiguration of modular robots from arbitrary to straight chain configurations. The IEEE international conference on robotics and automation (ICRA 2013) Wong S, Walter J (2013) Deterministic distributed algorithm for self-reconfiguration of modular robots from arbitrary to straight chain configurations. The IEEE international conference on robotics and automation (ICRA 2013)
39.
go back to reference Ward A, Jones A, Hopper A (2002) A new location technique for the active office. IEEE Pers Commun Mag 4:42–47CrossRef Ward A, Jones A, Hopper A (2002) A new location technique for the active office. IEEE Pers Commun Mag 4:42–47CrossRef
40.
go back to reference Warneke B, Last M, Leibowitz B, Pister KSJ (2001) Smart dust: communicating with a cubic-millimeter. Computer Magazine, pp 44–51 Warneke B, Last M, Leibowitz B, Pister KSJ (2001) Smart dust: communicating with a cubic-millimeter. Computer Magazine, pp 44–51
41.
go back to reference White P, Zykov V, Bongard JC, Lipson H (2005) Three dimensional stochastic reconfiguration of modular robots. In: Proceedings of robotics science and systems. MIT Press, Cambridge, pp 161–168 White P, Zykov V, Bongard JC, Lipson H (2005) Three dimensional stochastic reconfiguration of modular robots. In: Proceedings of robotics science and systems. MIT Press, Cambridge, pp 161–168
42.
go back to reference Zambonelli F, Gleizes MP, Mamei M, Tolksdorf R (2005) Spray computers: explorations in self-organization. J Pervas Mobile Comput Elsevier 1:1–20CrossRef Zambonelli F, Gleizes MP, Mamei M, Tolksdorf R (2005) Spray computers: explorations in self-organization. J Pervas Mobile Comput Elsevier 1:1–20CrossRef
Metadata
Title
An energy and memory-efficient distributed self-reconfiguration for modular sensor/robot networks
Authors
Hicham Lakhlef
Hakim Mabed
Julien Bourgeois
Publication date
01-08-2014
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2014
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-014-1196-8

Other articles of this Issue 2/2014

The Journal of Supercomputing 2/2014 Go to the issue

Premium Partner