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
Published in:
Introduction to Mobile Robot Path Planning Read chapter Read first chapter

2018 | OriginalPaper | Chapter

6. General Background on Multi-robot Task Allocation

Authors : Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Published in: Robot Path Planning and Cooperation

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Multi-robot systems (MRSss) face several challenges, but the most typical problem is the multi-robot tasks allocation (MRTA). It consists in finding the efficient allocation mechanism in order to assign different tasks to the set of available robots. Toward this objective, robots will work as cooperative agents. MRTA aims at ensuring an efficient execution of tasks under consideration and thus minimizing the overall system cost. Various research works have solved the MRTA problem using the multiple traveling salesman problem (MTSP) formulation. In this context, an overview on MRTA and MTSP is given in this chapter. Furthermore, a summary of the related works is presented.

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

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!

inform now
previous chapter Robot Path Planning Using Cloud Computing for Large Grid Maps
next chapter Different Approaches to Solve the MRTA Problem
Literature
1.
Diego, Pizzocaro and A. Preece. 2009. Towards a taxonomy of task allocation in sensor networks. In Proceedings of the 28th IEEE international conference on Computer Communications Workshops (INFOCOM), 413–414.
2.
Nidhi, Kalra, Robert Zlot, M. Bernardine Dias, and Anthony Stentz. 2005. Market-based multirobot coordination: A comprehensive survey and analysis. Technical report, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST.
3.
Dias Bernardine, M., Robert Zlot, Nidhi Kalra, and Anthony Stentz. 2006. Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE 94 (7): 1257–1270.CrossRef
4.
Brian, P.G., and M.J. Matarić. 2004. A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research 23 (9): 939–954.CrossRef
5.
Sylvia C. Botelho and Rachid Alami. 1999. M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement. In IEEE International Conference on Robotics and Automation, Proceedings, vol. 2, 1234–1239. IEEE.
6.
Gerkey, B.P., and M.J. Mataric. 2002. Sold!: Auction methods for multirobot coordination. IEEE transactions on robotics and automation 18 (5): 758–768.CrossRef
7.
Fang, Tang and Spondon Saha. 2008. An anytime winner determination algorithm for time-extended multi-robot task allocation. In ARCS, 123–130.
8.
Zlot, Robert, and Anthony Stentz. 2006. Market-based multirobot coordination for complex tasks. The International Journal of Robotics Research 25 (1): 73–101.CrossRef
9.
Barry L, Brumitt and Anthony Stentz. 1998. Grammps: A generalized mission planner for multiple mobile robots in unstructured environments. In IEEE International Conference on Robotics and Automation, Proceedings., vol. 2, 1564–1571. IEEE.
10.
Philippe, Caloud, Wonyun Choi, J.-C. Latombe, Claude Le Pape, and Mark Yim. 1990. Indoor automation with many mobile robots. In IEEE International Workshop on Intelligent Robots and Systems’ 90. ’Towards a New Frontier of Applications’, Proceedings. IROS’90., 67–72. IEEE.
11.
Parker, Lyne E. 1998. Alliance: An architecture for fault tolerant multirobot cooperation. IEEE transactions on robotics and automation 14 (2): 220–240.CrossRef
12.
Brian, Barry, and Werger and M.J. Matarić. 2000. Broadcast of local eligibility for multi-target observation. Distributed autonomous robotic systems 4, 347–356. Berlin: Springer.
13.
Sanem, Sariel and Tucker R. Balch. 2006. Efficient bids on task allocation for multi-robot exploration. In FLAIRS Conference, 116–121.
14.
Sven Koenig, Craig A. Tovey, Xiaoming Zheng, and Ilgaz Sungur. 2007. Sequential bundle-bid single-sale auction algorithms for decentralized control. In IJCAI, 1359–1365.
15.
Liu, Lin and Zhiqiang Zheng. 2005. Combinatorial bids based multi-robot task allocation method. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, ICRA, 1145–1150. IEEE.
16.
Antidio, Viguria, Ivan Maza, and Anibal Ollero. 2008. S+ t: An algorithm for distributed multirobot task allocation based on services for improving robot cooperation. In IEEE International Conference on Robotics and Automation ICRA, 3163–3168. IEEE.
17.
Ahmed M. Elmogy, Alaa M. Khamis, and Fakhri O. Karray. 2009. Dynamic complex task allocation in multisensor surveillance systems. In 2009 3rd International Conference on Signals, Circuits and Systems (SCS), 1–6. IEEE.
18.
Ahmed M. Elmogy, Alaa M. Khamis, and Fakhri O. Karray. 2009. Market-based dynamic task allocation in mobile surveillance systems. In 2009 IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR), 1–6. IEEE.
19.
Khamis, Alaa M., Ahmed M. Elmogy, and Fakhri O. Karray. 2011. Complex task allocation in mobile surveillance systems. Journal of Intelligent and Robotic Systems 64 (1): 33–55.CrossRef
20.
Yan, Zhi, Nicolas Jouandeau, and Arab Ali Cherif. 2013. A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems 10 (12): 399.CrossRef
21.
Michael M. Zavlanos, Leonid Spesivtsev, and George J. Pappas. 2008. A distributed auction algorithm for the assignment problem. In 47th IEEE Conference on Decision and Control CDC, 1212–1217. IEEE.
22.
Nathan, Michael, Michael M. Zavlanos, Vijay Kumar, and George J. Pappas. 2008. Distributed multi-robot task assignment and formation control. In IEEE International Conference on Robotics and Automation ICRA, 128–133. IEEE.
23.
Antidio, Viguria, and Ayanna M. Howard. 2009. An integrated approach for achieving multirobot task formations. IEEE/ASME Transactions on Mechatronics 14 (2): 176–186.CrossRef
24.
Lingzhi, Luo, Nilanjan Chakraborty, and Katia Sycara. 2011. Multi-robot assignment algorithm for tasks with set precedence constraints. In 2011 IEEE International Conference on Robotics and Automation (ICRA), 2526–2533. IEEE.
25.
Lingzhi, Luo, Nilanjan Chakraborty, and Katia Sycara. 2013. Distributed algorithm design for multi-robot task assignment with deadlines for tasks. In 2013 IEEE International Conference on Robotics and Automation (ICRA), 3007–3013. IEEE.
26.
Charles, Pippin, Henrik Christensen, and Lora Weiss. 2013. Performance based task assignment in multi-robot patrolling. In Proceedings of the 28th annual ACM symposium on applied computing, 70–76. ACM.
27.
Stefano, Giordani, Marin Lujak, and Francesco Martinelli. 2010. A distributed algorithm for the multi-robot task allocation problem. International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, 721–730. Berlin: Springer.
28.
29.
Bektas, Tolga. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34 (3): 209–219.MathSciNetCrossRef
30.
Holland, John H. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Michigan: U Michigan Press.MATH
31.
András, Király, and János Abonyi. 2011. Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. Intelligent Computational Optimization in Engineering, 241–269. Berlin: Springer.
32.
Jun, Li, Qirui Sun, MengChu Zhou, and Xianzhong Dai. 2013. A new multiple traveling salesman problem and its genetic algorithm-based solution. In 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 627–632. IEEE.
33.
Harpreet, Singh, and Ravreet Kaur. 2013. Resolving multiple traveling salesman problem using genetic algorithms. International Journal of Computer Science Engineering 3 (2): 209–212.
34.
Shalini, Singh, and Ejaz Aslam Lodhi. 2014. Comparison study of multiple traveling salesmen problem using genetic algorithm. International Journal of Computer Science and Network Security (IJCSNS) 14 (7): 107–110.
35.
Yuan, Shuai, Bradley Skinner, Shoudong Huang, and Dikai Liu. 2013. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research 228 (1): 72–82.MathSciNetCrossRefMATH
36.
Falkenauer, Emanuel. 1992. The grouping genetic algorithms-widening the scope of the gas. Belgian Journal of Operations Research, Statistics and Computer Science 33 (1): 79–102.MATH
37.
Evelyn, C. 2007. Brown, Cliff T Ragsdale, and Arthur E Carter. A grouping genetic algorithm for the multiple traveling salesperson problem. International Journal of Information Technology and Decision Making 6 (02): 333–347.CrossRef
38.
Alok, Singh, and Anurag Singh Baghel. 2009. A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing-A Fusion of Foundations, Methodologies and Applications 13 (1): 95–101.
39.
Arthur, E. 2006. Carter and Cliff T Ragsdale. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research 175 (1): 246–257.MathSciNetCrossRef
40.
Imen Châari, Anis Koubaa, Hachemi Bennaceur, Sahar Trigui, and Khaled Al-Shalfan. 2012. Smartpath: A hybrid aco-ga algorithm for robot path planning. In 2012 IEEE Congress on Evolutionary Computation (CEC), 1–8. IEEE.
41.
Châari, Imen, Anis Koubâa, Sahar Trigui, Hachemi Bennaceur, Adel Ammar, and Khaled Al-Shalfan. 2014. Smartpath: An efficient hybrid aco-ga algorithm for solving the global path planning problem of mobile robots. International Journal of Advanced Robotic Systems 11 (7): 94.CrossRef
42.
Anis, Koubâa, Sahar Trigui, and Imen Châari. 2012. Indoor surveillance application using wireless robots and sensor networks: Coordination and path planning, 19–57. Mobile Ad Hoc Robots and Wireless Robotic Systems: Design and Implementation.
43.
Weimin, Liu, Sujian Li, Fanggeng Zhao, and Aiyun Zheng. 2009. An ant colony optimization algorithm for the multiple traveling salesmen problem. In 4th IEEE Conference on Industrial Electronics and Applications ICIEA, 1533–1537. IEEE.
44.
Yousefikhoshbakht, Majid, Farzad Didehvar, and Farhad Rahmati. 2013. Modification of the ant colony optimization for solving the multiple traveling salesman problem. Romanian Academy Section for Information Science and Technology 16 (1): 65–80.
45.
Venkatesh, Pandiri, and Alok Singh. 2015. Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing 26: 74–89.CrossRef
46.
Dervis, Karaboga. 2005. An idea based on honey bee swarm for numerical optimization. Technical report, Technical report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department.
47.
Reza, Ali, and Mehrabian and Caro Lucas. 2006. A novel numerical optimization algorithm inspired from weed colonization. Ecological Informatics 1 (4): 355–366.
48.
Elad, Kivelevitch, Kelly Cohen, and Manish Kumar. 2013. A market-based solution to the multiple traveling salesmen problem. Journal of Intelligent and Robotic Systems, 1–20.
49.
Kaisa, Miettinen. 2012. Nonlinear multiobjective optimization, vol. 12. Berlin: Springer Science and Business Media.MATH
50.
Bolaños, R., M. Echeverry, and J. Escobar. 2015. A multiobjective non-dominated sorting genetic algorithm (nsga-ii) for the multiple traveling salesman problem. Decision Science Letters 4 (4): 559–568.CrossRef
51.
Zhenzhen, Xu, Yiping Li, and Xisheng Feng. 2008. Constrained multi-objective task assignment for uuvs using multiple ant colonies system. In ISECS International Colloquium on Computing, Communication, Control, and Management CCCM’08, vol. 1, 462–466. IEEE.
52.
Elango, Murugappan, Subramanian Nachiappan, and Manoj Kumar Tiwari. 2011. Balancing task allocation in multi-robot systems using k-means clustering and auction based mechanisms. Expert Systems with Applications 38 (6): 6486–6491.CrossRef
53.
54.
John, Bradford Gregory, and Heap and Maurice Pagnucco. 2012. Repeated sequential auctions with dynamic task clusters. In AAA I: 19972002.
55.
Thibaut, Lust, and Jacques Teghem. 2010. The multiobjective traveling salesman problem: A survey and a new approach, 119–141. Berlin: Springer.MATH
56.
Ke, Liangjun, Qingfu Zhang, and Roberto Battiti. 2013. Moea/d-aco: A multiobjective evolutionary algorithm using decomposition and antcolony. IEEE Transactions on Cybernetics 43 (6): 1845–1859.CrossRef
57.
Vui Ann, Shim, Kay Chen Tan, and Kok Kiong Tan. 2012. A hybrid estimation of distribution algorithm for solving the multi-objective multiple traveling salesman problem. In 2012 IEEE Congress on Evolutionary Computation (CEC), 1–8. IEEE.
58.
Wei, Peng, Qingfu Zhang, and Hui Li. 2009. Comparison between moea/d and nsga-ii on the multi-objective travelling salesman problem. Multi-objective memetic algorithms, 309–324.
Metadata
Title
General Background on Multi-robot Task Allocation
Authors
Anis Koubaa
Hachemi Bennaceur
Imen Chaari
Sahar Trigui
Adel Ammar
Mohamed-Foued Sriti
Maram Alajlan
Omar Cheikhrouhou
Yasir Javed
Copyright Year
2018
Book
Robot Path Planning and Cooperation

Print ISBN: 978-3-319-77040-6

Electronic ISBN: 978-3-319-77042-0

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-77042-0_6

Premium Partner

    Image Credits