A New Method for Improving the Fairness of Multi-Robot Task Allocation by Balancing the Distribution of Tasks
Abstract
This paper presents an innovative task allocation method for multi-robot systems that aims to optimize task distribution while taking into account various performance metrics such as efficiency, speed, and cost. Contrary to conventional approaches, the proposed method takes a comprehensive approach to initialization by integrating the K-means clustering algorithm, the Hungarian method for solving the assignment problem, and a genetic algorithm specifically adapted for Open Loop Travel Sales Man Problem (OLTSP). This synergistic combination allows for a more robust initialization, effectively grouping similar tasks and robots, and laying a strong foundation for the subsequent optimization process. The suggested method is flexible enough to handle a variety of situations, including Multi-Robot System (MRS) with robots that have unique capabilities and tasks of varying difficulty. The method provides a more adaptable and flexible solution than traditional algorithms, which might not be able to adequately address these variations because of the heterogeneity of the robots and the complexity of the tasks. Additionally, ensuring optimal task allocation is a key component of the suggested method. The method efficiently determines the best task assignments for robots through the use of a systematic optimization approach, thereby reducing the overall cost and time needed to complete all tasks. This contrasts with some existing methods that might not ensure optimality or might have limitations in their ability to handle a variety of scenarios. Extensive simulation experiments and numerical evaluations are carried out to validate the method's efficiency. The extensive validation process verifies the suggested approach's dependability and efficiency, giving confidence in its practical applicability.
Keywords
Full Text:
PDFReferences
Y. Chang, Y. Tian, J. P. How, and L. Carlone, “Kimera-multi: a system for distributed multi-robot metric-semantic simultaneous localization and mapping,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 11 210–11 218, 2021.
C. Wei, Z. Ji, and B. Cai, “Particle Swarm Optimization for Cooper- ative Multi-Robot Task Allocation: A Multi-Objective Approach,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 2530–2537, Apr. 2020.
X. Chen, S. He, Y. Zhang, L. C. Tong, P. Shang, and X. Zhou, “Yard crane and AGV scheduling in automated container terminal: A multi-robot task allocation framework,” Transportation Research Part C: Emerging Technologies, vol. 114, pp. 241–271, May 2020.
M. Otte, M. J. Kuhlman, and D. Sofge, “Auctions for multi-robot task allocation in communication limited environments,” Autonomous Robots, vol. 44, pp. 547–584, 2020.
S. Choudhury, J. K. Gupta, M. J. Kochenderfer, D. Sadigh, and J. Bohg, “Dynamic multi-robot task allocation under uncertainty and temporal constraints,” Autonomous Robots, vol. 46, no. 1, pp. 231–247, Jan. 2022.
X. Chen, P. Zhang, G. Du, and F. Li, “A distributed method for dynamic multi-robot task allocation problems with critical time constraints,” Robotics and Autonomous Systems, vol. 118, Aug. 2019.
C. Cai, J. Chen, Q. Yan, and F. Liu, “A multi-robot coverage path planning method for maritime search and rescue using multiple auvs,” Remote Sensing, vol. 15, no. 1, p. 93, 2022.
A. Borboni, I. Elamvazuthi, and N. Cusano, “EEG-Based Empathic Safe Cobot,” Machines, vol. 10, no. 8, p. 603, 2022.
B. Sahu, P. K. Das, and R. Kumar, “A modified cuckoo search algorithm implemented with SCA and PSO for multi-robot cooperation and path planning,” Cognitive Systems Research, vol. 79, pp. 24-42, 2023.
O. Hamed and M. Hamlich, “Improvised multi-robot cooperation strategy for hunting a dynamic target,” in 2020 International Symposium on Advanced Electrical and Communication Technologies (ISAECT), pp. 1–4, 2020.
O. Hamed and M. Hamlich, “Hybrid formation control for multi-robot hunters based on multi-agent deep deterministic policy gradient,” in Mendel, vol. 27, no. 2, pp. 23–29, 2021.
B. A. Baba, S. Garba, and N. Faruk, “Analysis of multi-robot cooperative hunting using differential game technique,” SLU Journal of Science and Technology, vol. 6, no. 1&2, pp. 1–7, 2023.
A. Farinelli, E. Zanotto, and E. Pagello, “Advanced approaches for multi-robot coordination in logistic scenarios,” Robotics and Autonomous Systems, vol. 90, pp. 34–44, 2017.
H. Aziz, A. Pal, A. Pourmiri, F. Ramezani, and B. Sims, “Task allocation using a team of robots,” Current Robotics Reports, pp. 1–12, 2022.
H. Kang, H. Kim, and Y. M. Kwon, “Recen: resilient manet based centralized multi robot system using mobile agent system,” in 2019 IEEE symposium series on computational intelligence (SSCI), pp. 1952– 1958, 2019.
A. Elfakharany and Z. H. Ismail, “End-to-end deep reinforcement learning for decentralized task allocation and navigation for a multi-robot system,” Applied Sciences, vol. 11, no. 7, p. 2895, 2021.
Y. Msala, M. Hamlich, and A. Mouchtachi, “A new robust heterogeneous multi-robot approach based on cloud for task allocation,” in 2019 5th International Conference on Optimization and Applications (ICOA), pp. 1–4, 2019.
F. Quinton, C. Grand, and C. Lesire, “Market approaches to the multi-robot task allocation problem: a survey,” Journal of Intelligent & Robotic Systems, vol. 107, no. 2, p. 29, 2023.
W. Yu, Y. Huang, and A. Garcia-Ortiz, “Optimal Task Allocation Algorithms for Energy Constrained Multihop Wireless Networks,” IEEE Sensors Journal, vol. 19, no. 17, pp. 7744–7754, Sep. 2019.
P. Zhou, W. Chen, S. Ji, H. Jiang, L. Yu, and D. Wu, “Privacy-Preserving Online Task Allocation in Edge-Computing-Enabled Massive Crowdsensing,” IEEE Internet of Things Journal, vol. 6, no. 5, pp. 7773– 7787, Oct. 2019.
H. Wu, A. Ghadami, A. E. Bayrak, J. M. Smereka, and B. I. Epureanu, “Task allocation with load management in multi-agent teams,” in 2022 International Conference on Robotics and Automation (ICRA), pp. 8823–8830, 2022.
J. Hu, H. Coffin, J. Whitman, M. Travers, and H. Choset, “Large-Scale Heterogeneous Multi-Robot Coverage via Domain Decomposition and Generative Allocation,” in Algorithmic Foundations of Robotics XV, pp. 52–67, 2023.
R. J. Alitappeh and K. Jeddisaravi, “Multi-robot exploration in task allocation problem,” Applied Intelligence, vol. 52, no. 2, pp. 2189–2211, Jan. 2022.
J. G. Martin, F. J. Muros, J. M. Maestre, and E. F. Camacho, “Multi- robot task allocation clustering based on game theory,” Robotics and Autonomous Systems, vol. 161, p. 104314, 2023.
X. Kong, Y. Gao, T. Wang, J. Liu, and W. Xu, "Multi-robot Task Allocation Strategy based on Particle Swarm Optimization and Greedy Algorithm," 2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), pp. 1643–1646, 2019.
F. Zitouni, R. Maamri, and S. Harous, “FA–QABC–MRTA: a solution for solving the multi-robot task allocation problem,” Intelligent Service Robotics, vol. 12, no. 4, pp. 407–418, Oct. 2019.
T. Li, H.-S. Shin, and A. Tsourdos, “Threshold Greedy Based Task Allocation for Multiple Robot Operations,” arXiv preprint arXiv:1909.01239, 2019.
G. M. Skaltsis, H.-S. Shin, and A. Tsourdos, “A survey of task allocation techniques in MAS,” in 2021 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 488–497, Jun. 2021.
Y. Chen, U. Rosolia, and A. D. Ames, “Decentralized Task and Path Planning for Multi-Robot Systems,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 4337–4344, Jul. 2021.
L. Zhou, V. D. Sharma, Q. Li, A. Prorok, A. Ribeiro, P. Tokekar, and V. Kumar, “Graph Neural Networks for Decentralized Multi-Robot Submodular Action Selection,” arXiv preprint arXiv:2105.08601, 2021.
P. Ghassemi and S. Chowdhury, “Multi-robot task allocation in disaster response: Addressing dynamic tasks with deadlines and robots with range and payload constraints,” Robotics and Autonomous Systems, vol. 147, p. 103905, 2022.
P. Mahato, S. Saha, C. Sarkar, and M. Shaghil, “Consensus-based fast and energy-efficient multi-robot task allocation,” Robotics and Autonomous Systems, vol. 159, p. 104270, 2023.
S. Guo, S. Cao, and J. Guo, “Study on Decentralization of Spherical Amphibious Multi-robot Control System Based on Smart Contract and Blockchain,” Journal of Bionic Engineering, vol. 18, no. 6, pp. 1317–1330, Nov. 2021.
G. Notomista, S. Mayya, S. Hutchinson, and M. Egerstedt, “An Optimal Task Allocation Strategy for Heterogeneous Multi-Robot Systems,” in 2019 18th European Control Conference (ECC), pp. 2071–2076, Jun. 2019.
D. Albani, W. Ho¨nig, D. Nardi, N. Ayanian, and V. Trianni, “Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms,” Applied Sciences, vol. 11, no. 7, p. 3115, Jan. 2021.
X. Huang, W. Zhang, J. Yang, L. Yang, and C. K. Yeo, “Market-based dynamic resource allocation in Mobile Edge Computing systems with multi-server and multi-user,” Computer Communications, vol. 165, pp. 43–52, Jan. 2021.
N. Seenu, K. C. R.M., M. M. Ramya, and M. N. Janardhanan, “Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems,” Industrial Robot: the international journal of robotics research and application, vol. 47, no. 6, pp. 929–942, Jan. 2020.
P. Gautier, J. Laurent, and J.-P. Diguet, “DQN as an alternative to Market-based approaches for Multi-Robot processing Task Allocation (MRpTA),” International Journal of Robotic Computing, vol. 3, no. 1, 2021.
Y. Emam, S. Mayya, G. Notomista, A. Bohannon, and M. Egerstedt, “Adaptive Task Allocation for Heterogeneous Multi-Robot Teams with Evolving and Unknown Robot Capabilities,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 7719– 7725, May 2020.
W. Yao, N. Qi, N. Wan, and Y. Liu, “An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles,” Aerospace Science and Technology, vol. 86, pp. 455–464, Mar. 2019.
D. T. Nguyen, L. B. Le, and V. K. Bhargava, “A Market-Based Framework for Multi-Resource Allocation in Fog Computing,” IEEE/ACM Transac- tions on Networking, vol. 27, no. 3, pp. 1151–1164, Jun. 2019.
S. A. Nelke, S. Okamoto, and R. Zivan, “Market Clearing–based Dynamic Multi-agent Task Allocation,” ACM Transactions on Intelligent Systems and Technology, vol. 11, no. 1, pp. 1–25, Jan. 2020.
N. Geng, Z. Chen, Q. A. Nguyen, and D. Gong, “Particle swarm optimization algorithm for the optimization of rescue task allocation with uncertain time constraints,” Complex & Intelligent Systems, vol. 7, no. 2, pp. 873–890, Apr. 2021.
H. Wu and H. Shang, “Potential game for dynamic task allocation in multi-agent system,” ISA Transactions, vol. 102, pp. 208–220, Jul. 2020.
R. H. A. Zubo and G. Mokryani, “Active Distribution Network Operation: A Market-Based Approach,” IEEE Systems Journal, vol. 14, no. 1, pp. 1405–1416, Mar. 2020.
J. Ma, H. Lu, J. Xiao, Z. Zeng, and Z. Zheng, “Multi-robot Target Encirclement Control with Collision Avoidance via Deep Reinforcement Learning,” Journal of Intelligent & Robotic Systems, vol. 99, no. 2, pp. 371–386, Aug. 2020.
C. Shyalika, T. Silva, and A. Karunananda, “Reinforcement Learning in Dynamic Task Scheduling: A Review,” SN Computer Science, vol. 1, no. 6, p. 306, Sep. 2020.
J. G. Martin, J. R. D. Frejo, R. A. Garc´ıa, and E. F. Camacho, “Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms,” Intelligent Service Robotics, vol. 14, no. 5, pp. 707–727, 2021.
O. M. Gul, “Energy harvesting and task-aware multi-robot task allocation in robotic wireless sensor networks,” Sensors, vol. 23, no. 6, p. 3284, 2023.
J. Li, J. Wu, J. Li, A. K. Bashir, M. J. Piran, and A. Anjum, “Blockchain-Based Trust Edge Knowledge Inference of Multi-Robot Systems for Collaborative Tasks,” IEEE Communications Magazine, vol. 59, no. 7, pp. 94–100, Jul. 2021.
W. Liang, Z. Ning, S. Xie, Y. Hu, S. Lu, and D. Zhang, “Secure fusion approach for the Internet of Things in smart autonomous multi-robot systems,” Information Sciences, vol. 579, pp. 468–482, Nov. 2021.
H.-Y. Lee et al., “A distributed dynamic framework to allocate collaborative tasks based on capability matching in heterogeneous multi-robot systems,” IEEE Transactions on Cognitive and Developmental Systems, 2023.
J. Hu, P. Bhowmick, I. Jang, F. Arvin, and A. Lanzon, “A Decentralized Cluster Formation Containment Framework for Multirobot Systems,” IEEE Transactions on Robotics, vol. 37, no. 6, pp. 1936–1955, Dec. 2021.
H. Mitiche, D. Boughaci, and M. Gini, “Iterated Local Search for Time-extended Multi-robot Task Allocation with Spatio-temporal and Capacity Constraints,” Journal of Intelligent Systems, vol. 28, no. 2, pp. 347–360, Apr. 2019.
A. Rauniyar and P. K. Muhuri, “Multi-robot coalition formation and task allocation using immigrant based adaptive genetic algorithms,” Computational Intelligence in Emerging Technologies for Engineering Applications, pp. 205–225, 2020.
H. H. E. Kayir, “An effective method to use centralized q-learning in multi-robot task allocation,” Pamukkale U¨ niversitesi Mu¨hendislik Bilim-leri Dergisi, vol. 27, no. 5, pp. 579–588, 2021.
M. De Ryck, D. Pissoort, T. Holvoet, and E. Demeester, “Decentral task allocation for industrial AGV-systems with routing constraints,” Journal of Manufacturing Systems, vol. 62, pp. 135–144, Jan. 2022.
W. Mao, Z. Liu, H. Liu, F. Yang, and M. Wang, “Research Progress on Synergistic Technologies of Agricultural Multi-Robots,” Applied Sciences, vol. 11, no. 4, p. 1448, Jan. 2021.
S. Wang, Y. Liu, Y. Qiu, Q. Zhang, F. Huo, Y. Huangfu, C. Yang, and J. Zhou, “Cooperative task allocation for multi-robot systems based on multi-objective ant colony system,” IEEE Access, vol. 10, pp. 56 375– 56 387, 2022.
R. J. Alitappeh and K. Jeddisaravi, “Multi-robot exploration in task allocation problem,” Applied Intelligence, vol. 52, no. 2, pp. 2189–2211, 2022.
X. Jing and Z. Cui, “An optimization task scheduling model for multi- robot systems in intelligent warehouses,” in Bio-Inspired Computing: Theories and Applications: 16th International Conference, pp. 3–17, 2022.
J. MacQueen, “Classification and analysis of multivariate observations,” in 5th Berkeley Symp. Math. Statist. Probability, pp. 281–297, 1967.
M.-S. Yang and I. Hussain, “Unsupervised Multi-View K-Means Cluster- ing Algorithm,” IEEE Access, vol. 11, pp. 13 574–13 593, 2023.
L. YiFei, H.-L. Minh, S. Khatir, T. Sang-To, T. Cuong-Le, C. MaoSen, and M. Abdel Wahab, “Structure damage identification in dams using sparse polynomial chaos expansion combined with hybrid K-means clustering optimizer and genetic algorithm,” Engineering Structures, vol. 283, p. 115891, May 2023.
J. Wang, Z. Cao, G. Xu, J. Yang, and A. Kareem, “An adaptive Kriging method based on K-means clustering and sampling in n-ball for structural reliability analysis,” Engineering Computations, vol. 40, no. 2, pp. 378– 410, Jan. 2023.
Z. Huang, “Extensions to the k-means algorithm for clustering large data sets with categorical values,” Data mining and knowledge discovery, vol. 2, no. 3, pp. 283–304, 1998.
J. Cai, J. Hao, H. Yang, X. Zhao, and Y. Yang, “A review on semi- supervised clustering,” Information Sciences, vol. 632, pp. 164–200, Jun. 2023.
Q. Huang, R. Gao, and H. Akhavan, “An ensemble hierarchical clustering algorithm based on merits at cluster and partition levels,” Pattern Recognition, vol. 136, p. 109255, Apr. 2023.
H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistic Quaterly, vol. 2, pp. 83–97, 1955.
S. Dhouib, “Novel optimization method for unbalanced assignment problems with multiple jobs: The Dhouib-Matrix-AP2,” Intelligent Systems with Applications, vol. 17, p. 200179, Feb. 2023.
Z. K. Hashim and M. A. K. Shiker, “A new technique to solve the assignment problems,” AIP Conference Proceedings, vol. 2414, no. 1, p. 040018, Feb. 2023.
S. Zhang, Y. Xue, H. Zhang, X. Zhou, K. Li, and R. Liu, “Improved Hungarian algorithm–based task scheduling optimization strategy for remote sensing big data processing,” Geo-spatial Information Science, pp. 1–14, Apr. 2023.
R. Aggarwal and N. Singh, “An Approach to Learn Structural Similarity Between Decision Trees Using Hungarian Algorithm,” in Proceedings of 3rd International Conference on Recent Trends in Machine Learning, IoT, Smart Cities and Applications, ser. Lecture Notes in Networks and Systems, V. K. Gunjan and J. M. Zurada, Eds., 2023, pp. 185–199.
P. Li and L. Zhou, “Assignment Algorithms for Multi-Robot Multi-Target Tracking with Sufficient and Limited Sensing Capability,” arXiv preprint arXiv:2303.04894, Mar. 2023.
B. Liu, S. Wang, Q. Li, X. Zhao, Y. Pan, and C. Wang, “Task Assignment of UAV Swarms Based on Deep Reinforcement Learning,” Drones, vol. 7, no. 5, p. 297, May 2023.
C.-H. Tsai, Y.-D. Lin, C.-H. Yang, C.-K. Wang, L.-C. Chiang, and P.-J. Chiang, “A Biogeography-Based Optimization with a Greedy Randomized Adaptive Search Procedure and the 2-Opt Algorithm for the Traveling Salesman Problem,” Sustainability, vol. 15, no. 6, p. 5111, Jan. 2023.
Y. Rocha and A. Subramanian, “Hybrid genetic search for the travel ing salesman problem with hybrid electric vehicle and time windows,” Computers & Operations Research, vol. 155, p. 106223, Jul. 2023.
J. Zheng, K. He, J. Zhou, Y. Jin, and C.-M. Li, “Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman prob lems,” Knowledge-Based Systems, vol. 260, p. 110144, Jan. 2023.
P. Akshatha, V. Vashisht, and T. Choudhury, “Open loop travelling salesman problem using genetic algorithm,” International Journal of In- novative Research in Computer and Communication Engineering, vol. 1, no. 1, pp. 112–116, 2013.
DOI: https://doi.org/10.18196/jrc.v4i6.18650
Refbacks
- There are currently no refbacks.
Copyright (c) 2023 Youssef MSALA
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Journal of Robotics and Control (JRC)
P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com