A multi-strategy genetic algorithm for solving multi-point dynamic aggregation problems with priority relationships of tasks

Yu Shen; Hecheng Li; Yu Shen; Hecheng Li

doi:10.3934/era.2024022

Electronic Research Archive

2024, Volume 32, Issue 1: 445-472. doi: 10.3934/era.2024022

Previous Article Next Article

Research article Special Issues

A multi-strategy genetic algorithm for solving multi-point dynamic aggregation problems with priority relationships of tasks

Yu Shen ¹,
Hecheng Li ^{2
,
,}

1.
School of Computer Science and Technology, Qinghai Normal University, Xining 810008, China
2.
School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, China

Received: 29 September 2023 Revised: 01 December 2023 Accepted: 19 December 2023 Published: 28 December 2023

The multi-point dynamic aggregation problem (MPDAP) that arises in practical applications is characterized by a group of robots that have to cooperate in executing a set of tasks distributed over multiple locations, in which the demand for each task grows over time. To minimize the completion time of all tasks, one needs to schedule the robots and plan the routes. Hence, the problem is essentially a combinatorial optimization problem. The manuscript presented a new MPDAP in which the priority of the task was considered that is to say, some tasks must be first completed before others begin to be executed. When the tasks were located at different priority levels, some additional constraints were added to express the priorities of tasks. Since route selection of robots depends on the priorities of tasks, these additional constraints caused the presented MPDAP to be more complex than ever. To efficiently solve this problem, an improved optimization algorithm, called the multi-strategy genetic algorithm (MSGA), was developed. First of all, a two-stage hybrid matrix coding scheme was proposed based on the priorities of tasks, then to generate more route combinations, a hybrid crossover operator based on 0-1 matrix operations was proposed. Furthermore, to improve the feasibility of individuals, a repair schedule was designed based on constraints. Meanwhile, a $ q $-tournament selection operator was adopted so that better individuals can be kept into the next generation. Finally, experimental results showed that the proposed algorithm is feasible and effective for solving the MPDAP.
- multi-point dynamic aggregation problem,
- multi-robot system,
- task allocation,
- genetic algorithm,
- priority
Citation: Yu Shen, Hecheng Li. A multi-strategy genetic algorithm for solving multi-point dynamic aggregation problems with priority relationships of tasks[J]. Electronic Research Archive, 2024, 32(1): 445-472. doi: 10.3934/era.2024022

Related Papers:

Abstract

The multi-point dynamic aggregation problem (MPDAP) that arises in practical applications is characterized by a group of robots that have to cooperate in executing a set of tasks distributed over multiple locations, in which the demand for each task grows over time. To minimize the completion time of all tasks, one needs to schedule the robots and plan the routes. Hence, the problem is essentially a combinatorial optimization problem. The manuscript presented a new MPDAP in which the priority of the task was considered that is to say, some tasks must be first completed before others begin to be executed. When the tasks were located at different priority levels, some additional constraints were added to express the priorities of tasks. Since route selection of robots depends on the priorities of tasks, these additional constraints caused the presented MPDAP to be more complex than ever. To efficiently solve this problem, an improved optimization algorithm, called the multi-strategy genetic algorithm (MSGA), was developed. First of all, a two-stage hybrid matrix coding scheme was proposed based on the priorities of tasks, then to generate more route combinations, a hybrid crossover operator based on 0-1 matrix operations was proposed. Furthermore, to improve the feasibility of individuals, a repair schedule was designed based on constraints. Meanwhile, a $ q $-tournament selection operator was adopted so that better individuals can be kept into the next generation. Finally, experimental results showed that the proposed algorithm is feasible and effective for solving the MPDAP.

References

[1]	B. Xin, Y. G. Zhu, Y. L. Ding, G. Q. Gao, Coordinated motion planning of multiple robots in multi-point dynamic aggregation task, in 2016 12th IEEE International Conference on Control and Automation (ICCA), Kathmandu, Nepal, (2016), 933–938. https://doi.org/10.1107/ICCA.2016.7505398
[2]	Y. L. Liao, K. L. Su, Multi-robot-based intelligent security system, Artif. Life Rob., 16 (2011), 137. https://doi.org/10.1007/s10015-011-0888-x doi: 10.1007/s10015-011-0888-x
[3]	C. Y. Ju, J. Kim, J. Seol, H. I. Son, A review on multirobot systems in agriculture, Comput. Electron. Agric., 202 (2022), 107336. https://doi.org/10.1016/j.compag.2022.107336 doi: 10.1016/j.compag.2022.107336
[4]	V. Akbari, F. S. Salman, Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity, Eur. J. Oper. Res., 257 (2017), 625–640. https://doi.org/10.1016/j.ejor.2016.07.043 doi: 10.1016/j.ejor.2016.07.043
[5]	W. Q. Jin, S. Q. Dong, C. Q. Yu, Q. Q. Luo, A data-driven hybrid ensemble AI model for COVID-19 infection forecast using multiple neural networks and reinforced learning, Comput. Biol. Med., 146 (2022), 105560. https://doi.org/10.1016/j.compbiomed.2022.105560 doi: 10.1016/j.compbiomed.2022.105560
[6]	N. N. Zheng, S. Y. Du, J. J. Wang, H. Zhang, W. T. Cui, Z. J. Kang, et al., Predicting COVID-19 in China using hybrid AI model, IEEE Trans. Cybern., 50 (2020), 2891–2904. https://doi.org/10.1109/tcyb.2020.2990162 doi: 10.1109/tcyb.2020.2990162
[7]	C. Robin, S. Lacroix, Multi-robot target detection and tracking: taxonomy and survey, Auton. Rob., 40 (2016), 729–760.
[8]	R. P. Yuan, J. T. Li, X. L. Wang, L. Y. He, Multirobot task allocation in e-Commerce robotic mobile fulfillment systems, Math. Probl. Eng., 2021 (2021), 6308950. https://doi.org/10.1155/2021/6308950 doi: 10.1155/2021/6308950
[9]	A. Khan, B. Rinner, A. Cavallaro, Cooperative robots to observe moving targets: Review, IEEE Trans. Cybern., 48 (2018), 187–198. https://doi.org/10.1109/TCYB.2016.2628161 doi: 10.1109/TCYB.2016.2628161
[10]	G. A. Korash, A. Stentz, M. Dias, A comprehensive taxonomy for multi-robot task allocation, Int. J. Rob. Res., 32 (2013), 1495–1512. https://doi.org/10.1177/0278364913496484 doi: 10.1177/0278364913496484
[11]	B. P. Gerkey, M. J. Mataric, A formal analysis and taxonomy of task allocation in multi-robot systems, Int. J. Rob. Res., 23 (2004), 939–954. https://doi.org/10.1177/0278364904045564 doi: 10.1177/0278364904045564
[12]	G. Q. Gao, Y. Mei, Y. H. Jia, W. N. Browne, B. Xin, Adaptive coordination ant colony optimization for multipoint dynamic aggregation, IEEE Trans. Cybern., 52 (2022), 7362–7376. https://doi.org/10.1109/TCYB.2020.3042511 doi: 10.1109/TCYB.2020.3042511
[13]	B. Xin, S. Liu, Z. Peng, G. Gao, An estimation of distribution algorithm for multi-robot multi-point dynamic aggregation problem, in 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Miyazaki, Japan, (2018), 775–780.
[14]	S. Lu, B. Xin, L. Dou, L. Wang, A multi-model estimation of distribution algorithm for agent routing problem in multi-point dynamic task, in Proceedings of the 37th Chinese Control Conference (CCC), Wuhan, China, (2018), 2468–2473.
[15]	G. Q. Gao, Y. Mei, X. Bin, Y. H. Jia, W. N. Browne, A memetic algorithm for the task allocation problem on multi-robot multi-point dynamic aggregation missions, in 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, U.K., (2020), 1–8.
[16]	R. Hao, J. Zhang, B. Xin, C. Chen, L. Dou, A hybrid differential evolution and estimation of distribution algorithm for the multi-point dynamic aggregation problem, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, (2018), 251–252.
[17]	J. Chen, Y. Guo, Z. Qiu, B. Xin, Q. S. Jia, W. H. Gui, Multiagent dynamic task assignment based on forest fire point model, IEEE Trans. Autom. Sci. Eng., 19 (2022), 833–849. https://doi.org/10.1109/TASE.2021.3061757 doi: 10.1109/TASE.2021.3061757
[18]	R. P. Yuan, J. T. Dou, J. T. Li, W. Wang, Y. F. Jiang, Multi-robot task allocation in e-commerce RMFS based on deep reinforcement learning, Math. Biosci. Eng., 20 (2023), 1903–1918. https://doi.org/10.3934/mbe.2023087 doi: 10.3934/mbe.2023087
[19]	X. B. Zhou, X. Cai, H. Zhang, Z. H. Zhang, T. Jin, H. Y. Chen, et al., Multi-strategy competitive-cooperative co-evolutionary algorithm and its application, Inf. Sci., 635 (2023), 328–344. https://doi.org/10.1016/j.ins.2023.03.142 doi: 10.1016/j.ins.2023.03.142
[20]	C. Huang, X. Zhou, X. Ran, J. Wang, H. Chen, W. Deng, Adaptive cylinder vetor particle syarm optimization with differential evolution for UAV path planning, Eng. Appl. Artif. Intell., 121 (2023), 105942. https://doi.org/10.1016/jengappai.2023.105942 doi: 10.1016/jengappai.2023.105942
[21]	X. Wu, J. Peng, Z. Xie, N. Zhao, S. Wu, An improved muli-obiective optimization algorithm for solving flexible job shop scheduling problem with variable batches, J. Syst. Eng. Electron., 32 (2021), 272–285. https://doi.org/10.23919/JSEE.2021.000024 doi: 10.23919/JSEE.2021.000024
[22]	J. Xu, Y. L. Zhao, H. Y. Chen, W. Deng, ABC-GSPBFT: PBFT with grouping score mechanism and optimized consensus pro-cess for flight operation data-sharing, Inf. Sci., 624 (2023), 110–127. https://doi.org/10.1016/j.ins.2022.12.068 doi: 10.1016/j.ins.2022.12.068
[23]	M. Li, J. Y. Zhang, J. Song, Z. J. Li, S. F. Lu, A clinical-oriented non-Severe depression diagnosis method based on cognitive behavior of emotional conflict, IEEE Trans. Comput. Social Syst., 10 (2023), 131–141. http://dx.doi.org/10.1109/TCSS.2022.3152091 doi: 10.1109/TCSS.2022.3152091
[24]	M. Li, W. Zhang, B. Hu, J. M. Kang, Y. Q. Wang, S. F. Lu, Automatic assessment of depression and anxiety through encoding pupil-wave from HCI in VR scenes, ACM Trans. Multimedia Comput. Commun. Appl., 20 (2023), 1–22. https://doi.org/10.1145/3513263 doi: 10.1145/3513263
[25]	Z. Yan, H. Y. Yang, Y. K. Wu, Y. Lin, A multi-view attention-based spatia Ctemporal network for airport arrival flow prediction, Transp. Res. Part E Logist. Transp. Rev., 170 (2023), 102997. https://doi.org/10.1016/j.tre.2022.102997 doi: 10.1016/j.tre.2022.102997
[26]	H. J. Wang, Z. J. Fu, J. J. Zhou, M. Y. Fu, R. Li, Cooperative collision avoidance for unmanned surface vehicles based on improved genetic algorithm, Ocean Eng., 222 (2021), 108612. https://doi.org/10.1016/j.oceaneng.2021.108612 doi: 10.1016/j.oceaneng.2021.108612
[27]	N. Milad, K. Esmaeel, D. Samira, Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Syst. Appl., 115 (2019), 106–120. https://doi.org/10.1016/j.eswa.2018.08.008 doi: 10.1016/j.eswa.2018.08.008
[28]	J. F. Xin, J. B. Zhong, F. R. Yang, Y. Cui, J. L. Sheng, An improved genetic algorithm for path-planning of unmanned surface vehicle, Sensors, 19 (2019), 2640. https://doi.org/10.3390/s19112640 doi: 10.3390/s19112640
[29]	X. H. Guo, M. J. Ji, W. D. Zhang, Research on a new two-level scheduling approach for unmanned surface vehicles transportation containers in automated terminals, Comput. Ind. Eng., 175 (2023), 108901. https://doi.org/10.1016/j.cie.2022.108901 doi: 10.1016/j.cie.2022.108901
[30]	G. Xia, X. Sun, X. Xia, Multiple task assignment and path planning of a multiple unmanned surface vehicles system based on improved self-organizing mapping and improved genetic algorithm, J. Mar. Sci. Eng., 9 (2021), 556. https://doi.org/10.3390/jmse9060556 doi: 10.3390/jmse9060556
[31]	H. Y. Lee, H. Shin, J. Chae, Path planning for mobile agents using a genetic algorithm with a direction guided factor, Electronics, 7 (2018), 212. https://doi.org/10.3390/electronics7100212 doi: 10.3390/electronics7100212
[32]	A. K. Cechinel, E. R. D. Pieri, A. L. F. Perez, P. D. M. Plentz, Multi-robot task allocation using island model genetic algorithm, IFAC-PapersOnLine, 54 (2021), 558–563. https://doi.org/10.1016/j.ifacol.2021.08.063 doi: 10.1016/j.ifacol.2021.08.063
[33]	Z. Entezari, M. Mahootchi, Developing a mathematical model for staff routing and scheduling in home health care industries: genetic algorithm-based solution scheme, Sci. Iran., 28 (2021), 3692–3718. https://doi.org/10.24200/SCI.2020.54116.3600 doi: 10.24200/SCI.2020.54116.3600
[34]	C. Ramirez-Atencia, G. Bello-Orgaz, M. D. R-Moreno, D. Camacho, Solving complex multi-UAV mission planning problme using multi-objective genetic algorithms, Soft Comput., 21 (2017), 4883–4900. https://doi.org/10.1007/s00500-016-2376-7 doi: 10.1007/s00500-016-2376-7
[35]	X. Wang, T. M. Choi, Z. Li, S. Shao, An effective local search algorithm for the multidepot cumulative capacitated vehicle routing problem, IEEE Trans. Syst. Man Cybern. Syst., 50 (2020), 4948–4958. https://doi.org/10.1109/TSMC.2019.2938298 doi: 10.1109/TSMC.2019.2938298

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)