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
Intelligent Service Robotics
Erschienen in: Intelligent Service Robotics 3/2013

01.07.2013 | Original Research

Multi-robot, dynamic task allocation: a case study

verfasst von: Soheil Keshmiri, Shahram Payandeh

Erschienen in: Intelligent Service Robotics | Ausgabe 3/2013

Einloggen

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

search-config
loading …

Abstract

This article presents a subgrouping approach to the multi-robot, dynamic multi-task allocation problem. It utilizes the percentile values of the distributional information of the tasks to reduce the task space into a number of subgroups that are equal to the number of robotic agents. The subgrouping procedure takes place at run-time and at every designated decision-cycle to update the elements of these subgroups using the relocation information of the elements of the task space. Furthermore, it reduces the complexity of the decision-making process proportional to the number of agents via introduction of the virtual representatives for these subgroups. The coordination strategy then uses the votes of the robotic agents for these virtual representatives to allocate the available subgroups. We use the elapsed time, the distance traveled, and the frequency of the decision-cycle as metrics to analyze the performance of this strategy in contrast to the prioritization, the instantaneous, and the time-extended coordination strategies.
Vorheriger Artikel A multitasking architecture for humanoid robot programming
Nächster Artikel Intelligent adaptive immune-based motion planner of a mobile robot in cluttered 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
Fußnoten
1
These representatives are not the actual subtasks. However, it is possible that the location of a representative coincides with a subtask at a given execution cycle.
 
2
The formulation of the decision engine along with its analysis (both, theoretical and numerical) are provided in Keshmiri and Payandeh [54] and hence are not included in this article to avoid repetition.
 
3
There are 24 permutations of the votes.
 
4
Liu and Shell [56] introduce an interval-based version of the Hungarian algorithm. However, we do not use the interval-based version of the Hungarian algorithm in the context of the analysis of this article.
 
5
The prioritization does not involve any decision-making. It coordinates the allocation of the subgroups to the robotic agents at the commencement of a mission preemptively.
 
6
The upper boundary \(O(n^4)\) corresponds to the scenarios where \(m=n\).
 
Literatur
1.
Atay N, Bayazit B (2006) Mixed-integer linear programming solution to multi-robot task allocation problem. Technical Report WUCSE-2006-54, Department of Computer Science and Engineering, Washington University
2.
Bertsekas DP (1990) The auction algorithm for assignment and other network flow problems: a tutorial introduction. Computat Optim Appl 1:7–66MathSciNetCrossRef
3.
Berhault M, Huang H, Keskinocak P, Koenig S, Elmaghraby W, Griffin P, Kleywegt A (2003) Robot exploration with combinatorial auctions. In: Proc. IEEE/RSJ int. conf. intelligent robots and systems (IROS), pp 1957–1962.
4.
Boltyanski V, Martini H, Soltan V (1999) Geometric methods and optimization problems. Kluwer, BostonMATH
5.
Botelho S, Alami R (2009) \(\text{ M }^{+}\): a scheme for multi-robot cooperation through negotiated task allocation and achievement. IEEE international conference on robotics and automation, ICRA’99, pp 1234–1239
6.
Campbell A, Wu AS (2011) Multi-Agent Role Allocation: Issues, Approaches, and Multiple Perspectives. Autonomous Agents and Multi-Agent Systems 23:317–355CrossRef
7.
Dahl TS, Mataric M, Sukhatme GS (2009) Multi-robot task allocation through vacancy chain scheduling. Robot Autonom Syst 57:674–687CrossRef
8.
Dias MB, Stentz A (2001) A market-based approach to multi-robot coordination. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Technical, Report CMU-RI-TR-01-26
9.
Dias MB, Stentz A (2002) Opportunistic optimization for market-based mulitrobot control. Proceedings of IEEE/RSJ international conference on intelligent robots and systems (IROS), pp 2714–2720
10.
Dias MB, Goldberg D, Stentz A (2003) Market-based multirobot coordination for complex space applications. In: 7th int. symp. artificial intelligence, robotics and automation in space (i-SAIRAS)
11.
Dias MB, Browning B, Veloso MM, Stentz A (2005) Dynamic heterogenous robot teams engaged in adversarial tasks. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-05-14
12.
Dias MB, Zlot R, Kalra N, Stentz A (2006) Market-based multirobot coordination: a survey and analysis. Proc IEEE J 94(7):1257–1270CrossRef
13.
Gerkey BP, Mataric MJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Robot Res 23: 939–954
14.
Gerkey BP, Mataric MJ (2002) Sold!: auction methods for multi-robot control. IEEE Trans Robot Autom Specl Issue Multi-Robot Syst 18(5):758–768CrossRef
15.
Gravetter FJ, Wallnau LB (2008) Statistics for the behavioral sciences. Wadsworth Cengage Learning, Belmont
16.
Kose H, Tatlidede U, Mericli C, Kaplan K, Akin HL (2004) Q-learning based market-driven multi-agent collaboration in robot soccer. In: Proc. Turkish symp. artificial intelligence and neural networks, pp 219–228
17.
Kuhn HW (1955) The hungarian method for the assignment problem. Naval Res Logist Q 2:83–97CrossRef
18.
Lagoudakis M, Markakis E, Kempe D, Keskinocak P, Kleywegt S, Koenig S, Tovey C, Meyerson A, Jain S (2005) Auction-based multi-robot routing. robotics: science and system
19.
Liu L, Shell DA (2011) Assessing optimal assignment under uncertainty: an interval-based algorithm. Int J Robot Res 936–953
20.
Martinoli A (1999) Swarm intelligence in autonomous collective robotics: from tools to the analysis and synthesis of distributed control strategies. Ph.D. Thesis No 2069, EPFL
21.
Mei Y, Lu YH, Hu YC, Lee CSG (2005) A case study of mobile robot’s energy consumption and conservation techniques. In: Proceedings of \(12\)th international conference on advanced robotics, Seattle, WA, pp 492–497
22.
Morters P, Peres Y (2010) Brownian motion. Cambridge University Press, UKCrossRef
23.
24.
Nair R, Ito T, Tambe M, Marsella S (2002) Task allocation in the rescue simulation domain: a short note. In: Proc. RoboCup-2001: fifth robot world cup games and conf, pp 751–754
25.
Nanjanath M, Gini M (2010) Repeated auctions for robust task execution by a robot team. Robot Autonom Syst 58: 900–909
26.
Parker LE (1998) Alliance: an architecture for fault-tolerant multi-robot cooperation. IEEE Trans Robot Autom 220–240
27.
Rabideau G, Estlin T, Chien S, Barrett A (1999) A comparison of coordinated planning methods for cooperating rovers. In: Proc. AIAA 1999 space technology conf
28.
Rus D, Vona M (1999) Self-reconfiguration planning with compressible unit modules. IEEE international conference on robotics and automation (ICRA99), pp 2513–2520
29.
Salemi B, Shen WM, Will P (2001) Hormone-controlled metamorphic robots. IEEE Trans Robot Autom (ICRA01), pp 4194–4199
30.
31.
Hartigan JA, Wong MA (1979) Algorithm AS 136: a K-means clustering algorithm. J R Stat Soc Ser C (Appl Stat) 28(1):100–108MATH
32.
33.
Sariel-Talay S, Balch TR, Erdogan N (2011) A generic framework for distributed multirobot cooperation. Intell Robot Syst 63:323–358CrossRef
34.
Zhang Y, Parker LE (2010) IQ-ASyMTRe: synthesizing coalition formation and execution for tightly-coupled multirobot tasks. IEEE/RSJ international conference on intelligent robots and systems (IROS). Knoxville, TN USA, pp 5595–5602
35.
Zhang Y, Parker LE (2012) Task allocation with executable coalitions in multirobot tasks. IEEE international conference on robotics and automation (ICRA). At. Paul, MN, USA
36.
Service TC, Adams JA (2011) Coallition formation for task-allocation: theory and algorithms. Autonom Agents Multi-Agent Syst 22:225–248CrossRef
37.
Tovey C, Lagoudakis MG, Jain S, Koenig S (2005) The generation of bidding rules for auction-based robot coordination. In: Proc. 3rd int. multi-robot systems, workshop. pp 3–14
38.
Walker JH, Wilson MS (2011) Task allocation for robots using inspiration from hormones. Adapt Behav 19(3):208–224CrossRef
39.
Werger BB, Mataric MJ (2001) Broadcast of local eligibility for multi-target observation. In: Parker LE, Bekey G, Barhen J (eds) Distributed autonomous robotic systems, vol 4. Springer, New York, pp 347–356
40.
Zlot R, Stentz A, Dias MB, Thayer S (2002) Multi-robot exploration controlled by a market economy. In: Proc. IEEE int. conf. robotics and automation (ICRA), pp 3016–3023
41.
Wolfstetter E (1996) Auctions: an introduction. Econ Surv 10(4):367–420CrossRef
42.
Karaboga D, Akay B (2009) A survey: algorithms simulating bee swarm intelligence. Artif Intell Rev 31(1–4):61–85CrossRef
43.
Ostergaard E, Sukhatme GS, Mataric MJ (2001) Emergent bucket brigading–a simple mechanism for improving performance in multi-robot constrained-space foraging tasks. International conference on autonomous agents, pp 2219–2223
44.
Lein A, Vaughan R (2008) Adaptive multi-robot bucket brigade foraging. In: Bullock S, Noble J, Watson R, Bedau MA (eds) Artificial life XI: proceedings of the \(11\)th international conference on the simulation and synthesis of living systems. MIT Press, Cambridge, pp 337–342
45.
Pini G, Brutschy A, Birattari M, Dorigo M (2011) Task partitioning in swarms of robots: reducing performance losses due to interference at shared resources. Lect Notes Electr Eng 85(3):217–228CrossRef
46.
Pini G, Brutschy A, Frison M, Roli A, Dorigo M, Birattari M (2011) Task partitioning in swarms of robots: an adaptive method for strategy selection. Swarm Intell 5(3–4):283–304CrossRef
47.
Tou JT, Gonzalez RC (1974) Pattern recognition principles. Addison-Wesley, MassachusettsMATH
48.
Boots B, Okabe A, Sugihara K (2006) Nearest neighborhood operations with generalized voronoi diagrams: a review. Int J Geogr Inf Syst 8(1):43–71
49.
Okabe A, Boots B (2000) Spatial tessellations: concepts and applications of Voronoi diagrams. Wiley Series in Probability and Statistics
50.
Kamal S, Gani M, Seneviratne L (2010) A game-theoretic approach to non-cooperative target assignment. Robot Autonom Syst 58(8):955–962
51.
Okabe A, Suzuki A (1997) Locational optimization problems solved through voronoi diagrams. Eur J Oper Res 98(3):445–456
52.
Karavelas MI (2004) A robust and efficient implementation for the segment Voronoi diagram. \(1^{st}\) international symposium on voronoi diagrams in science and, engineering, pp 51–62
53.
Boltyanski V, Martini H, Soltan V Geometric methods and optimization problems. Kluwer, Boston.
54.
Keshmiri S, Payandeh S (2013) On confinement of the initial location of an intruder in a multi-robot pursuit game. J Intell Robot Syst
55.
Mei Y, Lu YH, Hu YC, Lee C (2005) A case study of mobile robot’s energy consumption and conservation techniques. In: \(12\)th international conference on, advanced robotics (ICAR05)
56.
Liu L, Shell DA (2011) Assessing optimal assignment under uncertainty: an interval-based algorithm. Robot Res 30(7):936–953CrossRef
Metadaten
Titel
Multi-robot, dynamic task allocation: a case study
verfasst von
Soheil Keshmiri
Shahram Payandeh
Publikationsdatum
01.07.2013
Verlag
Springer Berlin Heidelberg
Erschienen in
Intelligent Service Robotics / Ausgabe 3/2013
Print ISSN: 1861-2776
Elektronische ISSN: 1861-2784
DOI
https://doi.org/10.1007/s11370-013-0130-x

Neuer Inhalt

    Bildnachweise