DEVELOPMENT OF A METHOD FOR SOLVING THE PROBLEM OF TASK ALLOCATION IN A MULTI-AGENT SYSTEM
Abstract
This paper considers the problem of task distribution within a multi-agent system, where each agent is an autonomous robot, and each task corresponds to a point in a two-dimensional environment that one of the agents must visit. This problem is essentially similar to a multi-agent version of the classical traveling salesman problem, where several agents are involved instead of one participant. Each of them must go through a unique route covering a certain set of points. In this regard, a study of the multi-agent traveling salesman problem is conducted as one of the formats for setting the problem of distributing goals among agents. This problem is of great importance in the field of routing and optimal task distribution. Its solution includes two closely related subproblems: determining the set of points assigned to each agent and constructing the optimal route for visiting them. There are three main approaches to solving this problem in the scientific literature: Optimization approach, where both subproblems are solved jointly; Cluster-First, Route-Second model, where tasks are first distributed among agents, and then routes are built; The Route-First, Cluster-Second model assumes initial optimization of the route for all points with its subsequent division between agents without changing the order of visits. In this paper, a hybrid method is proposed that combines elements of the Cluster-First, Route-Second and Route-First, Cluster-Second approaches. The goal is to combine the strengths of both concepts and minimize their drawbacks. To test the effectiveness of the developed method, a comparative study was conducted. The evaluation was carried out according to three main metrics: the time spent on constructing a solution, the total length of all routes, and the maximum route length among all agents. The experimental results showed that the use of the proposed method allows for a reduction in the maximum route length (thereby reducing the load imbalance between agents) by an average of 26%.
References
1. Sundar K., Rathinam S. Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems, J. Intell. Robot. Syst., Theory Appl., 2017, 88 (2–4), pp. 513-526. Available at: http://dx.doi.org/10.1007/s10846- 016-0458-5.
2. Vali M., Salimifard K. A constraint programming approach for solving multiple traveling salesman prob-lem, The Sixteenth International Workshop on Constraint Modelling and Reformulation, 2017.
3. Shuai Y., Bradley S., Shoudong H., Dikai L. A new crossover approach for solving the multiple travel-ling salesmen problem using genetic algorithms, European J. Oper. Res., 2013, pp. 72-82.
4. Al-Omeer M.A., Ahmed Z.H. Comparative study of crossover operators for the mtsp, 2019 International Conference on Computer and Information Sciences (ICCIS). IEEE, 2019, pp. 1-6.
5. Xu Z., Li Y., Feng X. Constrained multi-objective task assignment for UUVS using multiple ant colonies system, 2008 ISECS International Colloquium on Computing, Communication, Control, and Manage-ment, 2008, Vol. 1, pp. 462-466. Available at: http://dx.doi.org/10.1109/CCCM.2008.318.
6. Shabanpour M., Yadollahi M., Hasani M.M. A New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering Technique, IJCSNS International Journal of Computer Science and Network Security, May 2017, Vol. 17, No. 5.
7. Basma H., Bashir H., Cheaitou A. A Novel Clustering Method for Breaking Down the Symmetric Mul-tiple Traveling Salesman Problem, Journal of Industrial Engineering and Management JIEM, 2021, Vol. 14, No. 2.
8. Arthur D., Vassilvitskii S. K-Means++: The Advantages of careful seeding, Proceedings of the 8th an-nual ACM-SIAM symposium on Discrete algorithms, 2007.
9. Sofge D., Schultz A., & De Jong K. Evolutionary computational approaches to solving the multiple trav-eling salesman problem using a neighborhood attractor schema, Proceedings of the Applications of Evo-lutionary Computing on EvoWorkshops, 2002, pp. 153-162.
10. Beasley J.E. Route First - Cluster Second Methods for Vehicle Routing, Omega, 1983, Vol. 11,
Issue 4, pp. 403-408.
11. Bozdemir M.K., Bozdemir M., Burcu Ö. Route First - Cluster Second Method for Personal Service Routing Problem, Journal of Engineering Studies and Research, 2019, Vol. 25. No. 2, pp. 18-24.
12. Houssein F.A., Kostyukov V.F. and Evdokimov I.D. A method for solving the multi-traveling salesman problem based on reducing the size of the solution space, 2024 10th International Conference on Con-trol, Decision and Information Technologies (CoDIT), Vallette, Malta, 2024, pp. 1729-1733. DOI: 10.1109/CoDIT62066.2024.10708116.
13. Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem // Comput. Oper. Res. – 2004. – 31. – P. 1985-2002.
14. Morissette, Laurence & Chartier, Sylvain. The k-means clustering technique: General considerations and implementation in Mathematica, Tutorials in Quantitative Methods for Psychology, 2013, 9,
pp. 15-24. 10.20982/tqmp.09.1.p015.
15. Dorigo M., Birattari M., Stutzle T. Ant colony optimization, IEEE Comput. Intell. Mag., 2006, pp. 28-39.
16. Khusseyn F.A. Razrabotka i issledovanie metoda tsentralizovannogo raspredeleniya zadach v mul'tia-gentnykh sistemakh [Development and research of the method of centralized distribution of tasks in mul-ti-agent systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 4.
17. Ruprecht-Karls. TSPLIB. Available online: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95 (ac-cessed on 4 August 2024).
18. Latah M. Solving multiple TSP problem by K-means and crossover based modified ACO algorithm, International Journal of Engineering Research and Technology, 2016, Vol. 5, No. 02.
19. Kostyukov V.A., Khusseyn F.A., Evdokimov I.D. Metod resheniya problemy mul'tikommivoyazhera v srede bez prepyatstviy na osnove umen'sheniya razmera prostranstva resheniy [Method for solving the multi-traveling salesman problem in an obstacle-free environment based on reducing the size of the solution space], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 1.
20. Dorigo M., Maniezzo V., & Colorni A. Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics—Part B, 1996, 26 (1), pp. 29-41.
