robots task assignment

Multi-robot Task Allocation: A Review of the State-of-the-Art

• First Online: 01 January 2015

Cite this chapter

• Alaa Khamis 4 ,
• Ahmed Hussein 5 &
• Ahmed Elmogy 6  

Part of the book series: Studies in Computational Intelligence ((SCI,volume 604))

8360 Accesses

155 Citations

24 Altmetric

Multi-robot systems (MRS) are a group of robots that are designed aiming to perform some collective behavior. By this collective behavior, some goals that are impossible for a single robot to achieve become feasible and attainable. There are several foreseen benefits of MRS compared to single robot systems such as the increased ability to resolve task complexity, increasing performance, reliability and simplicity in design. These benefits have attracted many researchers from academia and industry to investigate how to design and develop robust versatile MRS by solving a number of challenging problems such as complex task allocation, group formation, cooperative object detection and tracking, communication relaying and self-organization to name just a few. One of the most challenging problems of MRS is how to optimally assign a set of robots to a set of tasks in such a way that optimizes the overall system performance subject to a set of constraints. This problem is known as Multi-robot Task Allocation (MRTA) problem. MRTA is a complex problem especially when it comes to heterogeneous unreliable robots equipped with different capabilities that are required to perform various tasks with different requirements and constraints in an optimal way. This chapter provides a comprehensive review on challenging aspects of MRTA problem, recent approaches to tackle this problem and the future directions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

• Available as EPUB and PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Yi-Lin, L., Kuo-Lan, S.: Multi-robot-based intelligent security system. Artif. Life Robot. 16 , 137–141 (2011)

Article   Google Scholar  

Nagatani, K., Okada, Y., Tokunaga, N., Kiribayashi, S., Yoshida, K., Ohno, K., Koyanagi, E., et al.: Multi-robot exploration for search and rescue missions. In: IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR), pp. 373–387 (2009)

Google Scholar  

Marino, A., Parker, L.E., Antonelli, G., Caccavale, F.: A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling. J. Intell. Robot. Syst. 71 , 423–444 (2013)

Khamis, A., ElGindy, A.: Minefield mapping using cooperative multirobot systems. J. Robot. 2012 (2012)

Espina, M.V., Grech, R., De Jager, D., Remagnino, P., Iocchi, L., Marchetti, L., King, C., et al.: Multi-robot teams for environmental monitoring. Innovations Defence Support Syst. 336 , 183–209 (2011)

Shkurti, F., Xu, A., Meghjani, M., Gamboa Higuera, J.C., Girdhar, Y., Giguere, P., Dudek, G., et al.: Multi-domain monitoring of marine environments using a heterogeneous robot team. Intell. Robots Syst. (IROS) 1747–1753 (2012)

Shiomi, M., Kamei, K., Kondo, T., Miyashita, T., Hagita, N.: Robotic service coordination for elderly people and caregivers with ubiquitous network robot platform. In: IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO) (2013)

Lerman, K., Jones, C., Galstyan, A., Mataric, M.: Analysis of dynamic task allocation in multi-robot systems. Int. J. Robot. Res. 25 , 225–241 (2006)

Tang, F., Parker, L.E.: A complete methodology for generating multi-robot task solutions using asymtre-d and market-based task allocation. In: International Conference on Robotics and Automation, IEEE, pp. 3351–3358 (2007)

Gerkey, B., Mataric, M.: A framework for studying multi-robot task allocation (2003)

Korsah, G.A., Stentz, A., Dias, M.B.: A comprehensive taxonomy for multi-robot task allocation. Int. J. Robot. Res. 32 , 1495–1513 (2013)

Dias, M.B.: Trader-bots: a new paradigm for robust and efficient multirobot coordination in dynamic environments. Ph.D. Thesis, Robotics Institute, Carnegie Mellon University (2004)

Zlot, R., Stentz, A.: Market-based multirobot coordination for complex tasks. Int. J. Robot. Res. 73–101 (2006)

de Longueville, M.: A Course in Topological Combinatorics. Springer, New York (2012)

Vatsolaki, P., Tsalpatouros, A.: Ewos: A sealed-bid auction system design and implementation for electricity interconnector capacity allocation. In: Information, Intelligence, Systems and Applications (IISA) (2013)

Kim, D., So, Y., Kim, S.: Study of marker array list method for augmented reality service based smart home. Int. J. Smart Home 5 , 51–64 (2011)

Higuera, J., Dudek, G.: Fair subdivision of multi-robot tasks. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), pp. 3014–3019 (2013)

Kuhn, H.W.: The hungarian method for the assignment problem. Nav. Res. Logistics Quart. 2 , 83–97 (1955)

Nam, C., Shell, D.: Assignment algorithms for modeling resource contention and interference in multi-robot task-allocation. In: Presentation at IEEE International Conference on Robotics and Automation (ICRA) (2014)

Lattarulo, V., Parks, G.T.: A preliminary study of a new multi-objective optimization algorithm. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–8 (2012)

Xu, Z., Wen, Q.: Approximation hardness of min-max tree covers. Oper. Res. Lett. 38 , 169–173 (2010)

Sarin, S.C., Sherali, H.D., Bhootra, A.: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper. Res. Lett. 33 , 62–70 (2005)

Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. In: Omega, vol. 34, pp. 209–219. Elsevier (2006)

Hussein, A., Khamis, A.: Market-based approach to multi-robot task allocation. In: International Conference on Individual and Collective Behaviors in Robotics (ICBR), IEEE (2013)

Dasgupta, P.: Multi-robot task allocation for performing cooperative foraging tasks in an initially unknown environment. Innovations Defence Support Syst., 338 , 5–20 (2011)

Khamis, A.M., Elmogy, A.M., Karray, F.O.: Complex task allocation in mobile surveillance systems. J. Intell. Robot. Syst. 64 , 33–55 (2011)

Aylett, R., Barnes, D.: A multi-robot architecture for planetary rovers. In: Proceedings of the 5th ESA Workshop on Advanced Space Technologies for Robotics and Automation, pp. 1–3 (1998)

Botelho, S.C., Alami, R.: M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement. In: International Conference on Robotics and Automation, pp. 1234–1239 (1999)

Horling, B., Lesser, V.: A survey of multi-agent organizational paradigms. Knowl. Eng. Rev. 19 , 281–316 (2004)

Brumitt, B.L., Stentz, A.: Grammps: a generalized mission planner for multiple mobile robots in unstructured environments. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 1564–1571 (1998)

Al-Yafi, K., Lee, H., Mansouri, A.: Mtap-masim: a multi-agent simulator for the mobile task allocation problem. In: IEEE International Workshop on Enabling Technologies: Infrastructures for Collaborative Enterprises, pp. 25–27 (2009)

Coltin, B., Veloso, M.: Mobile robot task allocation in hybrid wireless sensor networks. In: Intelligent Robots and Systems (IROS), pp. 2932–2937 (2010)

Liu, C., Kroll, A.: A centralized multi-robot task allocation for industrial plant inspection by using a* and genetic algorithms. Artif. Intell. Soft Comput. 466–474 (2012)

Giordani, S., Lujak, M., Martinelli, F.: A distributed algorithm for the multi-robot task allocation problem. In: Trends Applied Intelligent System, Springer, pp. 721–730 (2010)

Han-Lim, C., Brunet, L., How, J.: Consensus-based decentralized auctions for robust task allocation In: IEEE Transactions on Robotics, pp. 912–926 (2009)

Ping-an, G., Zi-xing, C., Ling-li, Y.: Evolutionary computation approach to decentralized multi-robot task allocation. In: International Conference on Natural Computation (ICNC), pp. 415–419 (2009)

Elmogy, A.: Market-based framework for mobile surveillance systems. Ph.D. Thesis, University of Waterloo (2010)

Zlot, R.M.: An auction-based approach to complex task allocation for multirobot teams. Ph.D. Thesis, Carnegie Mellon University (2006)

Smith, R.: Communication and control in problem solver. In: IEEE Transactions on Computers (1980)

Alibhai, Z.: What is contract net interaction protocol? IRMS Laboratory, SFU (2003)

Dias, M., Stentz, A.: Opportunistic optimization for market-based multirobot control. In: International Conference on Intelligent Robots and Systems, pp. 2714–2720 (2002)

Badreldin, M., Hussein, A., Khamis, A.: A comparative study between optimization and market-based approaches to multi-robot task allocation. Adv. Artif. Intell. 2013 , 1–11 (2013)

Dias, M.B., Stentz, A.: A free market architecture for distributed control of a multirobot system. In: International Conference on Intelligent Autonomous Systems, pp. 115–122 (2000)

Zlot, R., Stentz, A., Dias, M.B., Thayer, S.: Multi-robot exploration controlled by a market economy. In: International Conference on Robotics and Automation (ICRA) (2002)

Dias, M., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. In: Proceedings of the IEEE, pp. 1257–1270 (2006)

Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization: Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2000)

Spall, J.C.: Stochastic optimization. In: Handbook of Computational Statistics, Springer, New York, pp. 173–201 (2012)

Diwekar, U.: Optimization under uncertainty. In: Introduction to Applied Optimization. Springer, New York, pp. 1–54 (2008)

Lenagh, W.H.: Multi-robot task allocation: a spatial queuing approach. Ph.D. dissertation, University of Nebraska, Omaha (2013)

Khamis, A.: Ece457a: Cooperative and Adaptive Algorithms. University of Waterloo. Springer, Canada (2014)

Atay, N., Bayazit, B.: Mixed-integer linear programming solution to multi-robot task allocation problem. Washington Univ. St. Louis, Tech. Rep. (2006)

Darrah, M., Niland, W., Stolarik, B.M.: Multiple uav dynamic task allocation using mixed integer linear programming in a sead mission. In: American Institute of Aeronautics and Astronautics, pp. 2324–2334 (2005)

Mosteo, A.R., Montano, L.: Simulated annealing for multi-robot hierarchical task allocation with flexible constraints and objective functions. In: Workshop on Network Robot Systems Toward Intelligent Robotic Systems Integrated with Environments (2006)

Mosteo, A.R.: Multi-robot task allocation for service robotics: from unlimited to limited communication range. Ph.D. Thesis, Universidad de Zaragoza (2010)

Juedes, D., Drews, F., Welch, L., Fleeman, D.: Heuristic resource allocation algorithms for maximizing allowable workload in dynamic, distributed real-time systems. In: Parallel and Distributed Processing Symposium, pp. 1631–1638 (2004)

Kmiecik, W., Wojcikowski, M., Koszalka, L., Kasprzak, A.: Task allocation in mesh connected processors with local search meta-heuristic algorithms. In: Intelligent Information and Database Systems, Springer, pp. 215–224 (2010)

Shea, P.J., d Alexander, K., Peterson, J.: Group tracking using genetic algorithms. In: Proceedings of the International Society Information Fusion (2003)

Jones, E.G., Dias, M., Stentz, A.: Time-extended multi-robot coordination for domains with intra-path constraints. Auton. Robots 59 , 41–56 (2011)

Wang, J., Gu, Y., Li, X.: Multi-robot task allocation based on ant colony algorithm. J. Comput. 7 , 2160–2167 (2012)

Ding, Y., He, Y., Jiang, J.: Multi-robot cooperation method based on the ant algorithm. In: IEEE Swarm Intelligence Symposium, pp. 14–18 (2003)

Chen, W., Lin, C.: A hybrid heuristic to solve a task allocation problem. Comput. Oper. Res. 27 , 287–303 (2000)

Liu, D.K., Kulatunga, A.K.: Simultaneous planning and scheduling for multi-autonomous vehicles. In: Evolutionary Scheduling, Springer, pp. 437–464 (2007)

Download references

Author information

Authors and affiliations.

Engineering Science Department, Suez University Egypt and Vestec. Inc., 125 Northfield Drive West, Waterloo, N2L 6N8, Canada

Alaa Khamis

Intelligent Systems Lab (LSI) Research Group, Universidad Carlos III de Madrid (UC3M), Av. de la Universidad 30, 28911, Madrid, Spain

Ahmed Hussein

Computers and Control Engineering Department, Tanta University, Egypt and Arab East Colleges, Abdalla Elsahmi Road, Elhada District, Riyadh, 11583, KSA

Ahmed Elmogy

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Alaa Khamis .

Editor information

Editors and affiliations.

College of Computer and Information Sciences (CCIS), Prince Sultan University, Riyadh, Saudi Arabia, and CISTER/INESC-TEC, ISEP, Polytechnic Institute of Porto, Porto, Portugal

Anis Koubâa

Depto. Ing. de Sistemas y Automática Escuela Superior de Ingenieros, University of Seville, Sevilla, Spain

J.Ramiro Martínez-de Dios

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this chapter

Khamis, A., Hussein, A., Elmogy, A. (2015). Multi-robot Task Allocation: A Review of the State-of-the-Art. In: Koubâa, A., Martínez-de Dios, J. (eds) Cooperative Robots and Sensor Networks 2015. Studies in Computational Intelligence, vol 604. Springer, Cham. https://doi.org/10.1007/978-3-319-18299-5_2

Download citation

DOI : https://doi.org/10.1007/978-3-319-18299-5_2

Published : 19 May 2015

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-18298-8

Online ISBN : 978-3-319-18299-5

eBook Packages : Engineering Engineering (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Distributed Algorithm Design for Constrained Multi-robot Task Assignment

The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.

Degree Type

• Dissertation
• Robotics Institute

Degree Name

• Doctor of Philosophy (PhD)

Usage metrics

• Adaptive Agents and Intelligent Robotics

Multi-robot task assignment in obstacle environment

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Multi-robot task assignment for serving people quarantined in multiple hotels during COVID-19 pandemic

Affiliations.

• 1 Shenzhen University, College of Mechatronics and Control Engineering, Shenzhen, China.
• 2 Shenzhen City Joint Laboratory of Autonomous Unmanned Systems and Intelligent Manipulation, Shenzhen University, Shenzhen, China.
• 3 Shenzhen University, College of Physics and Optoelectronic Engineering, Shenzhen, China.
• 4 Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS), Shenzhen, China.
• PMID: 36915326
• PMCID: PMC10006103
• DOI: 10.21037/qims-22-842

Background: Efficiently combating with the coronavirus disease 2019 (COVID-19) has been challenging for medics, police and other service providers. To reduce human interaction, multi-robot systems are promising for performing various missions such as disinfection, monitoring, temperature measurement and delivering goods to people quarantined in prescribed homes and hotels. This paper studies the task assignment problem for multiple dispersed homogeneous robots to visit a set of prescribed hotels to perform tasks such as body temperature assessment or oropharyngeal swabs for people quarantined in the hotels while trying to minimize the robots' total operation time. Each robot can move to multiple hotels sequentially within its limited maximum operation time to provide the service.

Methods: The task assignment problem generalizes the multiple traveling salesman problem, which is an NP-hard problem. The main contributions of the paper are twofold: (I) a lower bound on the robots' total operation time to serve all the people has been found based on graph theory, which can be used to approximately evaluate the optimality of an assignment solution; (II) several efficient marginal-cost-based task assignment algorithms are designed to assign the hotel-serving tasks to the robots.

Results: In the Monte Carlo simulations where different numbers of robots need to serve the people quarantined in 30 and 90 hotels, the designed task assignment algorithms can quickly (around 30 ms) calculate near-optimal assignment solutions (within 1.15 times of the optimal value).

Conclusions: Numerical simulations show that the algorithms can lead to solutions that are close to the optimal compared with the competitive genetic algorithm and greedy algorithm.

Keywords: Multi-robot systems; coronavirus disease 2019 (COVID-19); lower bound; marginal cost; task assignment.

2023 Quantitative Imaging in Medicine and Surgery. All rights reserved.