Abstract
This paper presents a complete system architecture for multi-robot coordination for unbalanced task assignments, where a number of robots are supposed to visit and accomplish missions at different locations. The proposed method first clusters tasks into clusters according to the number of robots, then the assignment is done in the form of one-cluster-to-one-robot, followed by solving the traveling salesman problem (TSP) to determine the visiting order of tasks within each cluster. A nonlinear model predictive controller (NMPC) is designed for robots to navigate to their assigned tasks while avoiding colliding with other robots. Several simulations are conducted to evaluate the feasibility of the proposed architecture. Video examples of the simulations can be viewed at https://youtu.be/5C7zTnv2sfo and https://youtu.be/-JtSg5V2fTI?si=7PfzZbleOOsRdzRd. Besides, we compare the cluster-based assignment with a simulated annealing (SA) algorithm, one of the typical solutions for the multiple traveling salesman problem (mTSP), and the result reveals that with a similar optimization effect, the cluster-based assignment demonstrates a notable reduction in computation time. This efficiency becomes increasingly pronounced as the task-to-agent ratio grows.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. V. Dileep, B. Yu, S. Kim, and H. Oh, “Task assignment for deploying unmanned aircraft as decoys,” International Journal of Control, Automation, and Systems, vol. 18, pp. 3204–3217, 2021
D. Koung, I. Fantoni, O. Kermorgant, and L. Belouaer, “Consensus-based formation control and obstacle avoidance for nonholonomic multi-robot system,” Proc. of International Conference on Control, Automation, Robotics and Vision (ICARCV), 2020.
Z. Pan, D. Wang, H. Deng, and K. Li, “A virtual spring method for the multi-robot path planning and formation control,” International Journal of Control, Automation, and Systems, vol. 17, pp. 1272–1282, 2019.
A. Nath, A. R. Arun, and R. Niyogi, “A distributed approach for road clearance with multi-robot in urban search and rescue environment,” International Journal of Intelligent Robotics and Applications, vol. 3, pp. 392–406, 2019.
J. P. Queralta, J. Taipalmaa, B. C. Pullinen, V. K. Sarker, T. N. Gia, H. Tenhunen, M. Gabbouj, J. Raitoharju, and T. Westerlund, “Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision,” IEEE Access, vol. 8, pp. 191617–191643, 2020.
Z. Chen, J. Alonso-Mora, X. Bai, D. D. Harabor, and P. J. Stuckey, “Integrated task assignment and path planning for capacitated multi-agent pickup and delivery,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 5816–5823, 2021.
J. Yu and S. M. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs,” Proc. of 27th AAAI Conference on Artificial Intelligence, 2013.
S. Kartik and C. S. R. Murthy, “Task allocation algorithms for maximizing reliability of distributed computing systems,” IEEE Transactions on Computers, vol. 46, no. 6, pp. 719–724, 1997.
G. M. Skaltsis, H. Shin, and A. Tsourdos, “A survey of task allocation techniques in MAS,” Proc. of International Conference on Unmanned Aircraft Systems (ICUAS), pp. 488–497, 2021.
H. Zhao, L. Wang, H. Zhou, and D. Du, “Consensus for a Class of Sampled-data Heterogeneous Multi-agent Systems,” International Journal of Control, Automation, and Systems, vol. 19, pp. 1751–1759, 2021.
Y. Bai, C. Christoforos, and G. Nikolakopoulos, “SAreCBS: Multi-robot task assignment with integrated reactive path generation,” arXiv:2304.02418, 2023.
C. Jiang, Z. Wan, and Z. Peng, “A new efficient hybrid algorithm for large scale multiple traveling salesman problems,” Expert Systems with Applications, vol. 139, 112867, 2020.
G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40–66, 2015.
M. Barer, G. Sharon, R. Stern, and A. Felner, “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” Proc. of 7th Annual Symposium on Combinatorial Search, 2014.
E. Boyarski, A. Felner, R. Stern, G. Sharon, D. Tolpin, O. Betzalel, and E. Shimony, “ICBS: Improved conflict-based search algorithm for multi-agent pathfinding,” Proc. of 24th International Joint Conference on Artificial Intelligence, 2015.
G. Wagner and H. Choset, “Subdimensional expansion for multirobot path planning,” Artificial Intelligence, vol. 219, pp. 1–24, 2015.
P. Fiorini and Z. Shiller, “Motion planning in dynamic environments using velocity obstacles,” The International Journal of Robotics Research, vol. 17, no. 7, pp. 760–772, 1998.
J. Van den Berg, M. Lin, and D. Manocha, “Reciprocal velocity obstacles for real-time multi-agent navigation,” Proc. of IEEE International Conference on Robotics and Automation, pp. 1928–1935, 2008.
B. Lindqvist, S. S. Mansouri, A.-A. Agha-mohammadi, and G. Nikolakopoulos, “Nonlinear MPC for collision avoidance and control of UAVs with dynamic obstacles,” IEEE Robotics and Automation Letters, vol. 5, no. 4, pp. 6001–6008, 2020.
M. Turpin, N. Michael, and V. Kumar, “CAPT: Concurrent assignment and planning of trajectories for multiple robots,” The International Journal of Robotics Research, vol. 33, no. 1, pp. 98–112, 2014.
W. Hönig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Conflict-based search with optimal task assignment,” Proc. of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS’ 18), pp. 757–765, 2018.
V. G. Nair, R. S. Adarsh, K. P. Jayalakshmi, M. V. Dileep, and K. R. Guruprasad, “Cooperative online workspace allocation in the presence of obstacles for multi-robot simultaneous exploration and coverage path planning problem,” International Journal of Control, Automation, and System, vol. 21, pp. 2338–2349, 2023
X. Zhong, J. Li, S. Koenig, and H. Ma, “Optimal and bounded-suboptimal multi-goal task assignment and pathfinding,” Proc. of International Conference on Robotics and Automation (ICRA), pp. 10731–10737, 2022.
Q. Xu, J. Li, S. Koenig, and H. Ma, “Multi-goal multi-agent pickup and delivery,” arXiv preprint arXiv:2208.01223, 2022.
Z. Ren, S. Rathinam, and H. Choset, “MS*: A new exact algorithm for multi-agent simultaneous multi-goal sequencing and path finding,” Proc. of IEEE International Conference on Robotics and Automation (ICRA), pp. 11560–11565, 2021.
S. Kaarthik and S. Rathinam, “An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem,” Proc. of International Conference on Unmanned Aircraft Systems (ICUAS), pp. 366–371, 2015.
S. C. Johnson, “Hierarchical clustering schemes,” Psychometrika, vol. 32, no. 3, pp. 241–254, 1967.
H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1–2, pp. 83–97, 1955.
C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of traveling salesman problems,” Journal of the ACM, vol. 7, no. 4, pp. 326–329, 1960.
IBM ILOG Cplex, “V12.1: User’s Manual for CPLEX,” International Business Machines Corporation, vol. 46, no. 53, p. 157, 2009.
S. Koenig and M. Likhachev, “D* Lite,” Proc. of the AAAI Conference on Artificial Intelligence, vol. 18, pp. 476–483, 2002.
S. Karlsson, A. Koval, C. Kanellakis, and G. Nikolakopoulos, “D+*: A risk-aware platform-agnostic heterogeneous path planner,” Expert Systems with Applications, vol. 215, 119408, 2023.
X. Tang, M. Li, S. Wei, and B. Ding, “Event-triggered synchronous distributed model predictive control for multiagent systems,” The Internation Journal of Control, Automation, and Systems, vol. 19, pp. 1273–1282, 2021.
B. Lindqvist, P. Sopasakis, and G. Nikolakopoulos, “A scalable distributed collision avoidance scheme for multiagent UAV systems,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 9212–9218, 2021.
M. Kamel, T. Stastny, K. Alexis, and R. Siegwart, “Model predictive control for trajectory tracking of unmanned aerial vehicles using robot operating system,” Robot Operating System (ROS): The Complete Reference, vol. 2, pp. 3–39, 2017.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The authors declare that there is no competing financial interest or personal relationship that could have appeared to influence the work reported in this paper.
Additional information
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is part of the research project SP14 ‘Autonomous Drones for Underground Mining Operations’, which is included in the Sustainable Underground Mining (SUM) project academic programme spanning from 2021 to 2024. The programme is jointly financed by LKAB and the Swedish Energy Agency. Additionally, this work has been partially funded by the European Union’s Horizon 2020 Research and Innovation Programme under Grant Agreement No. 101003591 Nexgen SIMS.
Yifan Bai is currently pursuing a Ph.D. degree at the Robotics and AI team of the Luleå University of Technology, Sweden. His current research interests include developing task assignment and multi-agent path-finding algorithms to enable efficient collaboration of multiple robots.
Björn Lindqvist received his Ph.D. degree from the Robotics and AI team, Luleå University of Technology (LTU), Sweden. He is currently an assistant professor with the Department of Computer Science, Electrical and Space Engineering, LTU. Björn’s research interests include collision avoidance and path planning for single and multi-agent systems.
Samuel Nordström is currently pursuing a Ph.D. degree at the Robotics and AI Team at the Department of Computer Science, Electrical and Space Engineering, Luleå University of Technology, Sweden, working in the field of aerial and ground robotics. Samuel’s research interests include path planning and obstacle avoidance, with a focus on real-life verification of methods.
Christoforos Kanellakis received his Ph.D. degree from the Control Engineering Group, Luleå University of Technology (LTU), Sweden. He is currently an assistant professor with the Department of Computer Science, Electrical and Space Engineering, LTU. His research interests include the field of robotics, focusing on the combination of control and vision to enable robots to perceive and interact with the environment
George Nikolakopoulos is acting Chair on Robotics and AI, a Professor on Robotics and Automation at the Department of Computer Science, Electrical and Space Engineering at Luleå University of Technology. His research interests include the area of robotics, control applications, and cyberphysical systems.
Rights and permissions
About this article
Cite this article
Bai, Y., Lindqvist, B., Nordström, S. et al. Cluster-based Multi-robot Task Assignment, Planning, and Control. Int. J. Control Autom. Syst. 22, 2537–2550 (2024). https://doi.org/10.1007/s12555-023-0745-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-023-0745-4