Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Autonomous Agents and Multi-Agent Systems

01.01.2014

Self-organized task allocation to sequentially interdependent tasks in swarm robotics

verfasst von: Arne Brutschy, Giovanni Pini, Carlo Pinciroli, Mauro Birattari, Marco Dorigo

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this article we present a self-organized method for allocating the individuals of a robot swarm to tasks that are sequentially interdependent. Tasks that are sequentially interdependent are common in natural and artificial systems. The proposed method does neither rely on global knowledge nor centralized components. Moreover, it does not require the robots to communicate. The method is based on the delay experienced by the robots working on one subtask when waiting for input from another subtask. We explore the capabilities of the method in different simulated environments. Additionally, we evaluate the method in a proof-of-concept experiment using real robots. We show that the method allows a swarm to reach a near-optimal allocation in the studied environments, can easily be transferred to a real robot setting, and is adaptive to changes in the properties of the tasks such as their duration. Finally, we show that the ideal setting of the parameters of the method does not depend on the properties of the environment.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Also referred to as intentional approaches to task allocation [24].
 
2
In biology, the interface delay is commonly referred to as “queuing delay” (cf. [2, 3]]). We do not use the term “queue” as it implies an order in the arrival of robots at the task interface, which is not present in the stochastic system that we consider.
 
3
Differences in average interface delays can be caused by differences in the properties of the problem such as subtask duration or swarm size.
 
7
The short duration of the segments is due to two reasons. First, we used robots equipped with old and non-replaceable batteries. Second, robots depleted their batteries in an inhomogeneous way—robots that transported many objects depleted their battery at a much faster pace—and we had to stop the experiment as soon as the first robot ran out of energy.
 
Literatur
1.
Agassounon, W., & Martinoli, A. (2002). Efficiency and robustness of threshold-based distributed allocation algorithms in multi-agent systems. Proceedings of the first international joint conference on autonomous agents and multi-agent systems (AAMAS-02) (pp. 1090–1097). New York: ACM Press.
2.
Anderson, C., & Ratnieks, F. L. W. (1999a). Task partitioning in insect societies. I: Effect of colony size on queueing delay and colony ergonomic efficiency. The American Naturalist, 154(5), 521–535.CrossRef
3.
Anderson, C., & Ratnieks, F. L. W. (1999b). Task partitioning in insect societies. II: Use of queueing delay information in recruitment. The American Naturalist, 154(5), 536–548.CrossRef
4.
Anderson, C., & Ratnieks, F. L. W. (2000). Task partitioning in insect societies: Novel situations. Insectes Sociaux, 47(2), 198–199.CrossRef
5.
Berman, S., Halasz, A., Hsieh, M. A., & Kumar, V. (2009). Optimized stochastic policies for task allocation in swarms of robots. IEEE Transactions on Robotics, 25, 927–937.CrossRef
6.
Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: From natural to artificial systems. New York: Oxford University Press.MATH
7.
8.
Campo, A., & Dorigo, M. (2007). Efficient multi-foraging in swarm robotics. In M. Capcarrere, A. A. Freitas, P. J. Bentley, C. G. Johnson, & J. Timmis (Eds.), Advances in artificial life: Proceedings of the VIIIth European conference on artificial life (ECAL 2005) (Vol. 4648, pp. 696–705). Berlin: Springer.
9.
Christensen, A. L., O’Grady, R., & Dorigo, M. (2007). Morphology control in a multirobot system. IEEE Robotics and Automation Magazine, 11(6), 732–742.
10.
Cicirello, V. A., & Smith, S. F. (2004). Wasp-like agents for distributed factory coordination. Autonomous Agents and Multi-Agent Systems, 8(3), 237–266.CrossRef
11.
Dahl, T. S., Matarić, M. J., & Sukhat, G. S. (2009). Multi-robot task allocation through vacancy chain scheduling. Robotics and Autonomous Systems, 57, 674–687.CrossRef
12.
Dasgupta, P. (2011). Multi-robot task allocation for performing cooperative foraging tasks in an initially unknown environment. In L. C. Jain, E. V. Aidman, & C. Abeynayake (Eds.), Innovations in defence support systems 2. Studies in computational intelligence (Vol. 338, pp. 5–20). Berlin: Springer.
13.
Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94, 1257–1270.CrossRef
14.
Dorigo, M. (2005). SWARM-BOT: An experiment in swarm robotics. In P. Arabshahi & A. Martinoli (Eds.), 2005 IEEE swarm intelligence symposium (SIS-05) (pp. 192–200). Piscataway, NJ: IEEE Press.
15.
Dorigo, M., Floreano, D., Gambardella, L. M., Mondada, F., Nolfi, S., Baaboura, T., et al. (2013). Swarmanoid: A novel concept for the study of heterogeneous robotic swarms. IEEE Robotics and Automation Magazine (in press).
16.
Dorigo, M., Trianni, V., Şahin, E., Groß, R., Labella, T. H., Baldassarre, G., et al. (2004). Evolving self-organizing behaviors for a swarm-bot. Autonomous Robots, 17(2–3), 223–245.CrossRef
17.
Ferreira, P. R., Boffo, F. S., & Bazzan, A. L. C. (2008). Using Swarm-GAP for distributed task allocation in complex scenarios. In N. Jamali, P. Scerri, & T. Sugawara (Eds.), Massively multi-agent technology. LNCS (Vol. 5043, pp. 107–121). Berlin: Springer.
18.
Fowler, H. H., & Robinson, S. W. (1979). Foraging by Atta sexdens (Formicidae: Attini): Seasonal patterns, caste and efficiency. Ecological Entomology, 4(3), 239–247.CrossRef
19.
Gerkey, B. P., & Matarić, M. J. (2003). Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In Proceedings of the IEEE international conference on robotics and automation (ICRA 2003) (pp. 3862–3867). Pitscataway, NJ: IEEE Press.
20.
Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research, 23(9), 939–954.CrossRef
21.
Goldberg, D., Cicirello, V., Dias, M. B., Simmons, R., Smith, S., & Stentz, A. (2003). Task allocation using a distributed market-based planning mechanism. In Proceedings of the second international joint conference on autonomous agents and multiagent systems (pp. 996–997). New York, NY: ACM Press.
22.
Groß, R., Bonani, M., Mondada, F., & Dorigo, M. (2006). Autonomous self-assembly in swarm-bots. IEEE Transactions on Robotics, 22(6), 1115–1130.CrossRef
23.
Ikemoto, Y., Miura, T., & Asama, H. (2010). Adaptive division-of-labor control algorithm for multi-robot systems. Journal of Robotics and Mechatronics, 22(4), 514–525.
24.
Kalra, N., & Martinoli, A. (2006). A comparative study of market-based and threshold-based task allocation. In Distributed autonomous robotic systems 7 (pp. 91–102). Berlin: Springer.
25.
Krieger, M. J. B., & Billeter, J.-B. (2000). The call of duty: Self-organised task allocation in a population of up to twelve mobile robots. Journal of Robotics and Autonomous Systems, 30, 65–84.CrossRef
26.
Labella, T. H., Dorigo, M., & Deneubourg, J.-L. (2006). Division of labor in a group of robots inspired by ants’ foraging behavior. ACM Transactions on Autonomous and Adaptive Systems, 1(1), 4–25.CrossRef
27.
Liu, W., Winfield, A., Sa, J., Chen, J., & Dou, L. (2007). Towards energy optimization: Emergent task allocation in a swarm of foraging robots. Adaptive Behavior, 15(3), 289–305.CrossRef
28.
Mondada, F., Pettinaro, G. C., Guignard, A., Kwee, I. V., Floreano, D., Deneubourg, J.-L., et al. (2004). SWARM-BOT: A new distributed robotic concept. Autonomous Robots, 17(2–3), 193–221.CrossRef
29.
Nouyan, S., Campo, A., & Dorigo, M. (2008). Path formation in a robot swarm. Self-organized strategies to find your way home. Swarm Intelligence, 2(1), 1–23.CrossRef
30.
Nouyan, S., Groß, R., Bonani, M., Mondada, F., & Dorigo, M. (2009). Teamwork in self-organized robot colonies. IEEE Transactions on Evolutionary Computation, 13(4), 695–711.CrossRef
31.
Pinciroli, C., Trianni, V., O’Grady, R., Pini, G., Brutschy, A., Brambilla, M., et al. (2011a). ARGoS: A modular, multi-engine simulator for heterogeneous swarm robotics. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS 2011) (pp. 5027–5034). Los Alamitos, CA: IEEE Computer Society Press.
32.
Pinciroli, C., Trianni, V., O’Grady, R., Pini, G., Brutschy, A., Brambilla, M., et al. (2012). ARGoS: A modular, parallel, multi-engine simulator for multi-robot systems. Swarm intelligence, 6(4), 271–295.
33.
Pini, G., Brutschy, A., Birattari, M., & Dorigo, M. (2011a). Task partitioning in swarms of robots: Reducing performance losses due to interference at shared resources. In J.-L. Ferrier & J. Filipe (Eds.), Informatics in control, automation and robotics: Selected papers from the international conference on informatics in control, automation and robotics 2009. LNEE (Vol. 85). Berlin: Springer.
34.
Pini, G., Brutschy, A., Frison, M., Roli, A., Dorigo, M., & Birattari, M. (2011b). Task partitioning in swarms of robots: An adaptive method for strategy selection. Swarm Intelligence, 5(3–4), 283–304.CrossRef
35.
Ratnieks, F. L. W., & Anderson, C. (1999). Task partitioning in insect societies. Insectes Sociaux, 46(2), 95–108.CrossRef
36.
Scheidler, A., Merkle, D., & Middendorf, M. (2008). Stability and performance of ant queue inspired task partitioning methods. Theory in Biosciences, 127(2), 149–161.CrossRefMathSciNet
37.
Theraulaz, G., Bonabeau, E., & Deneubourg, J.-L. (1998). Response threshold reinforcement and division of labour in insect societies. Proceedings: Biological Sciences, 265(1393), 327–332.
Metadaten
Titel
Self-organized task allocation to sequentially interdependent tasks in swarm robotics
verfasst von
Arne Brutschy
Giovanni Pini
Carlo Pinciroli
Mauro Birattari
Marco Dorigo
Publikationsdatum
01.01.2014
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 1/2014
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-012-9212-y