Модифицированные эвристические алгоритмы распределения заданий для групп мобильных роботов в условиях неопределенности
Ключевые слова:
распределение заданий, эвристические алгоритмы, группы мобильных роботов, муравьиный алгоритм, нейронная сеть Хопфилда, генетический алгоритмАннотация
Рассматривается проблема распределения заданий между группами мобильных роботов в условиях параметрической и стохастической неопределенности, возникающей из-за сенсорных погрешностей, нестационарности среды и ограниченности информации об объектах управления. Основная цель работы – адаптировать разработанные ранее эвристические алгоритмы к реальным условиям, где присутствуют сенсорные ошибки и недостаток информации о состоянии среды. В качестве базовых подходов рассматриваются три алгоритма: муравьиный алгоритм, нейронная сеть Хопфилда и генетический алгоритм. Разработаны специальные модификации для каждого алгоритма, учитывающие неопределенность исходных данных: динамическое обновление феромонных следов, адаптивная коррекция весовых коэффициентов нейронов и интервальная оценка параметров среды. Приведены общая постановка задачи, математические модели и принципы построения предложенных алгоритмов распределения заданий. Было проведено численное моделирование для сравнения модифицированных версий алгоритмов с их базовыми аналогами в условиях различных уровней неопределенности функционирования системы. Установлено, что предложенные адаптивные механизмы улучшают эффективность распределения заданий до 20 % по сравнению с базовыми методами. На основании полученных результатов сформулированы рекомендации по выбору оптимального алгоритма в зависимости от конкретных условий функционирования системы и задач управления. Сделан вывод о целесообразности использования разработанных подходов при проектировании интеллектуальных адаптивных систем группового управления мобильными роботами. Предложенные решения могут применяться и для более широкого круга задач, включая динамическое переназначение ресурсов и организацию кооперативного поведения технических агентов.
Литература
1. Lin X., Gao F., Bian W. A high-effective swarm intelligence-based multi-robot cooperation method for target searching in unknown hazardous environments // Expert Systems with Applications. 2025. vol. 262. DOI: 10.1016/j.eswa.2024.125609.
2. Cardona G.A., Calderon J.M. Robot Swarm Navigation and Victim Detection Using Rendezvous Consensus in Search and Rescue Operations // Applied Sciences. 2019. vol. 9(8). DOI: 10.3390/app9081702.
3. Alotaibi E.T., Alqefari S.S., Koubaa A. LSAR: Multi-UAV Collaboration for Search and Rescue Missions // IEEE Access. 2019. vol. 7. pp. 55817–55832. DOI: 10.1109/ACCESS.2019.2912306.
4. Cao Y.U., Fukunaga A.S., Kahng A. Cooperative mobile robotics: Antecedents and directions // Autonomous Robots. 1997. vol. 4. pp. 7–27.
5. Gerkey B.P., Matarić M.J. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems // International Journal of Robotics Research. 2004. vol. 23(9). pp. 939–954. DOI: 10.1177/0278364904045564.
6. Kalyaev I.A., Melnik E.S., Klimenko A.V. Distributed Ledger Based Workload Logging in the Robot Swarm // Proc. 4th Int. Conf. Interactive Collaborative Robotics (ICR 2019). LNCS, 2019. pp. 119–128. DOI: 10.1007/978-3-030-26118-4_12.
7. Kalyaev I.A. Melnik E.S., Klimenko A.V. Distributed Methods for Autonomous Robot Groups Fault-Tolerant Management // Proc. 5th Int. Conf. Interactive Collaborative Robotics (ICR 2020). LNCS, 2020. vol. 12336. pp. 135–147. DOI: 10.1007/978-3-030-60337-3_14.
8. Brambilla M., Ferrante E., Birattari M., Dorigo M. Swarm robotics: a review from the swarm engineering perspective // Swarm Intelligence. 2013. vol. 7. pp. 1–41. DOI: 10.1007/s11721-012-0075-2.
9. Parker L.E. ALLIANCE: An Architecture for Fault Tolerant Multi-Robot Cooperation // IEEE Transactions on Robotics and Automation. 1998. vol. 14(2). pp. 220–240. DOI: 10.1109/70.681242.
10. Dadgar E., Jafari S., Hamzeh A. A PSO-based multi-robot cooperation method for target searching in unknown environments // Neurocomputing. 2016. vol. 177. pp. 62–74. DOI: 10.1016/j.neucom.2015.11.007.
11. Garg R. E2RGWO: Exploration enhanced robotic Grey Wolf Optimizer for cooperative multiple target search for robotic swarms // Arabian Journal for Science and Engineering. 2023. vol. 48. pp. 9887–9903. DOI: 10.1007/s13369-022-07438-5.
12. Dorri A., Kanhere S.S., Jurdak R. Multi-Agent Systems: A Survey // IEEE Access. 2018. vol. 6. pp. 28573–28593. DOI: 10.1109/ACCESS.2018.2831228.
13. Fox D., Ko J., Konolige K., Limketkai B., Schulz D., Stewart B. Distributed multirobot exploration and mapping // Proceedings of the IEEE. 2006. vol. 94(7). pp. 1325–1339. DOI: 10.1109/JPROC.2006.876927.
14. Dorigo M., Blum C., Stutzle T. Ant Colony Optimization – Introduction and Recent Trends // IEEE Computational Intelligence Magazine. 2007. vol. 1(4). pp. 28–39. DOI: 10.1109/MCI.2006.329691.
15. Liu F., Tan Y. Multi-robot Task Allocation Based on Ant Colony Algorithm // Journal of Computers. 2012. vol. 7(9). pp. 2160–2167.
16. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities // Proceedings of the National Academy of Sciences USA. 1982. vol. 79(8). pp. 2554–2558. DOI: 10.1073/pnas.79.8.2554.
17. Cechinel A.K., De Pieri E.R., Pérez A.L.F., Plentz P.D.M. Multi-robot Task Allocation Using Island Model Genetic Algorithm // IFAC-PapersOnLine. 2021. vol. 54(1). pp. 558–563. DOI: 10.1016/j.ifacol.2021.08.063.
18. Darintsev O.V., Migranov A.B. Multi-criteria Optimization of the Mobile Robot Group Strategy Using the Ant Algorithm // Eds.: Ronzhin A., Shishlakov V. Electromechanics and Robotics. Smart Innovation. Systems and Technologies. Springer. Singapore. 2022. vol. 232. pp. 97–108. DOI: 10.1007/978-981-16-2814-6_9.
19. Даринцев О.В., Мигранов А.Б. Модификация аппарата нейронной сети Хопфилда для решения задачи оптимального распределения заданий в группе мобильных роботов // Известия РАН. Теория и системы управления. 2024. № 2. С. 169–182.
20. Darintsev O.V., Migranov A.B. Task Distribution Module for a Team of Robots Based on Genetic Algorithms: Synthesis Methodology and Testing // Proc. XXI Int. Conf. Complex Systems: Control and Modeling Problems (CSCMP). 2019. pp. 296–300. DOI: 10.1109/CSCMP45713.2019.8976649.
21. Khamis A.M., Hussein A., Elmogy A.M. Multi-robot Task Allocation: A Review of the State-of-the-Art // Eds. Koubâa A., Martínez-de-Dios J.R. Cooperative Robots and Sensor Networks. Studies in Computational Intelligence. Springer. Cham. 2015. pp. 31–51. DOI: 10.1007/978-3-319-18299-5_2.
22. Dias M.B., Zlot R., Kalra N., Stentz A. Market-based multirobot coordination: A survey and analysis // Proceedings of the IEEE. 2006. vol. 94(7). pp. 1257–1270. DOI: 10.1109/JPROC.2006.876939.
23. Garg R., Shukla A., Tiwari R. AERPSO – An adaptive exploration robotic PSO based cooperative algorithm for multiple target searching // Expert Systems with Applications. 2022. vol. 209. DOI: 10.1016/j.eswa.2022.118245.
24. Zhu B., Xie W.-F. An improved genetic algorithm with Euclidean geometry and hybrid heuristic crossover for the traveling salesman problem //2023 IEEE Congress on Evolutionary Computation (CEC). Chicago, IL, USA, 2023. pp. 1-8. DOI: 10.1109/CEC53210.2023.10254179.
25. Fan M., Li J. Surrogate-assisted genetic algorithms for the travelling salesman problem and vehicle routing problem // Proc. IEEE Congress on Evolutionary Computation (CEC). 2020. pp. 1–7. DOI: 10.1109/CEC48606.2020.9185817.
26. Ojeda Rios B.H., Xavier E.C., Miyazawa F., Amorim P., Curcio E., Joao Santos M. Recent dynamic vehicle routing problems: A survey // Computers & Industrial Engineering. 2021. vol. 160. DOI: 10.1016/j.cie.2021.107604.
27. Ding H., Cheng H.-J., Shan X. Modified Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem // DEStech Transactions on Social Science, Education and Human Science. 2018. DOI: 10.12783/dtssehs/amse2018/24837.
28. Gendreau M., Hertz A., Laporte G. A tabu search heuristic for the vehicle routing problem // Management Science. 1994. vol. 40(10). pp. 1276–1290. DOI: 10.1287/mnsc.40.10.1276.
29. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. vol. 220(4598). pp. 671–680. DOI: 10.1126/science.220.4598.671.
30. Даринцев О.В., Мигранов А.Б. Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений // Информатика и автоматизация. 2022. Т. 21. № 4. С. 729–757.
31. Chao I.M., Golden B.L., Wasil E.A. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions // American Journal of Mathematical and Management Sciences. 1993. vol. 13(3–4). pp. 371–406. DOI: 10.1080/01966324.1993.10737363.
32. Dorigo M., Stützle T. Ant Colony Optimization, MIT Press, 2004.
2. Cardona G.A., Calderon J.M. Robot Swarm Navigation and Victim Detection Using Rendezvous Consensus in Search and Rescue Operations // Applied Sciences. 2019. vol. 9(8). DOI: 10.3390/app9081702.
3. Alotaibi E.T., Alqefari S.S., Koubaa A. LSAR: Multi-UAV Collaboration for Search and Rescue Missions // IEEE Access. 2019. vol. 7. pp. 55817–55832. DOI: 10.1109/ACCESS.2019.2912306.
4. Cao Y.U., Fukunaga A.S., Kahng A. Cooperative mobile robotics: Antecedents and directions // Autonomous Robots. 1997. vol. 4. pp. 7–27.
5. Gerkey B.P., Matarić M.J. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems // International Journal of Robotics Research. 2004. vol. 23(9). pp. 939–954. DOI: 10.1177/0278364904045564.
6. Kalyaev I.A., Melnik E.S., Klimenko A.V. Distributed Ledger Based Workload Logging in the Robot Swarm // Proc. 4th Int. Conf. Interactive Collaborative Robotics (ICR 2019). LNCS, 2019. pp. 119–128. DOI: 10.1007/978-3-030-26118-4_12.
7. Kalyaev I.A. Melnik E.S., Klimenko A.V. Distributed Methods for Autonomous Robot Groups Fault-Tolerant Management // Proc. 5th Int. Conf. Interactive Collaborative Robotics (ICR 2020). LNCS, 2020. vol. 12336. pp. 135–147. DOI: 10.1007/978-3-030-60337-3_14.
8. Brambilla M., Ferrante E., Birattari M., Dorigo M. Swarm robotics: a review from the swarm engineering perspective // Swarm Intelligence. 2013. vol. 7. pp. 1–41. DOI: 10.1007/s11721-012-0075-2.
9. Parker L.E. ALLIANCE: An Architecture for Fault Tolerant Multi-Robot Cooperation // IEEE Transactions on Robotics and Automation. 1998. vol. 14(2). pp. 220–240. DOI: 10.1109/70.681242.
10. Dadgar E., Jafari S., Hamzeh A. A PSO-based multi-robot cooperation method for target searching in unknown environments // Neurocomputing. 2016. vol. 177. pp. 62–74. DOI: 10.1016/j.neucom.2015.11.007.
11. Garg R. E2RGWO: Exploration enhanced robotic Grey Wolf Optimizer for cooperative multiple target search for robotic swarms // Arabian Journal for Science and Engineering. 2023. vol. 48. pp. 9887–9903. DOI: 10.1007/s13369-022-07438-5.
12. Dorri A., Kanhere S.S., Jurdak R. Multi-Agent Systems: A Survey // IEEE Access. 2018. vol. 6. pp. 28573–28593. DOI: 10.1109/ACCESS.2018.2831228.
13. Fox D., Ko J., Konolige K., Limketkai B., Schulz D., Stewart B. Distributed multirobot exploration and mapping // Proceedings of the IEEE. 2006. vol. 94(7). pp. 1325–1339. DOI: 10.1109/JPROC.2006.876927.
14. Dorigo M., Blum C., Stutzle T. Ant Colony Optimization – Introduction and Recent Trends // IEEE Computational Intelligence Magazine. 2007. vol. 1(4). pp. 28–39. DOI: 10.1109/MCI.2006.329691.
15. Liu F., Tan Y. Multi-robot Task Allocation Based on Ant Colony Algorithm // Journal of Computers. 2012. vol. 7(9). pp. 2160–2167.
16. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities // Proceedings of the National Academy of Sciences USA. 1982. vol. 79(8). pp. 2554–2558. DOI: 10.1073/pnas.79.8.2554.
17. Cechinel A.K., De Pieri E.R., Pérez A.L.F., Plentz P.D.M. Multi-robot Task Allocation Using Island Model Genetic Algorithm // IFAC-PapersOnLine. 2021. vol. 54(1). pp. 558–563. DOI: 10.1016/j.ifacol.2021.08.063.
18. Darintsev O.V., Migranov A.B. Multi-criteria Optimization of the Mobile Robot Group Strategy Using the Ant Algorithm // Eds.: Ronzhin A., Shishlakov V. Electromechanics and Robotics. Smart Innovation. Systems and Technologies. Springer. Singapore. 2022. vol. 232. pp. 97–108. DOI: 10.1007/978-981-16-2814-6_9.
19. Даринцев О.В., Мигранов А.Б. Модификация аппарата нейронной сети Хопфилда для решения задачи оптимального распределения заданий в группе мобильных роботов // Известия РАН. Теория и системы управления. 2024. № 2. С. 169–182.
20. Darintsev O.V., Migranov A.B. Task Distribution Module for a Team of Robots Based on Genetic Algorithms: Synthesis Methodology and Testing // Proc. XXI Int. Conf. Complex Systems: Control and Modeling Problems (CSCMP). 2019. pp. 296–300. DOI: 10.1109/CSCMP45713.2019.8976649.
21. Khamis A.M., Hussein A., Elmogy A.M. Multi-robot Task Allocation: A Review of the State-of-the-Art // Eds. Koubâa A., Martínez-de-Dios J.R. Cooperative Robots and Sensor Networks. Studies in Computational Intelligence. Springer. Cham. 2015. pp. 31–51. DOI: 10.1007/978-3-319-18299-5_2.
22. Dias M.B., Zlot R., Kalra N., Stentz A. Market-based multirobot coordination: A survey and analysis // Proceedings of the IEEE. 2006. vol. 94(7). pp. 1257–1270. DOI: 10.1109/JPROC.2006.876939.
23. Garg R., Shukla A., Tiwari R. AERPSO – An adaptive exploration robotic PSO based cooperative algorithm for multiple target searching // Expert Systems with Applications. 2022. vol. 209. DOI: 10.1016/j.eswa.2022.118245.
24. Zhu B., Xie W.-F. An improved genetic algorithm with Euclidean geometry and hybrid heuristic crossover for the traveling salesman problem //2023 IEEE Congress on Evolutionary Computation (CEC). Chicago, IL, USA, 2023. pp. 1-8. DOI: 10.1109/CEC53210.2023.10254179.
25. Fan M., Li J. Surrogate-assisted genetic algorithms for the travelling salesman problem and vehicle routing problem // Proc. IEEE Congress on Evolutionary Computation (CEC). 2020. pp. 1–7. DOI: 10.1109/CEC48606.2020.9185817.
26. Ojeda Rios B.H., Xavier E.C., Miyazawa F., Amorim P., Curcio E., Joao Santos M. Recent dynamic vehicle routing problems: A survey // Computers & Industrial Engineering. 2021. vol. 160. DOI: 10.1016/j.cie.2021.107604.
27. Ding H., Cheng H.-J., Shan X. Modified Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem // DEStech Transactions on Social Science, Education and Human Science. 2018. DOI: 10.12783/dtssehs/amse2018/24837.
28. Gendreau M., Hertz A., Laporte G. A tabu search heuristic for the vehicle routing problem // Management Science. 1994. vol. 40(10). pp. 1276–1290. DOI: 10.1287/mnsc.40.10.1276.
29. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. vol. 220(4598). pp. 671–680. DOI: 10.1126/science.220.4598.671.
30. Даринцев О.В., Мигранов А.Б. Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений // Информатика и автоматизация. 2022. Т. 21. № 4. С. 729–757.
31. Chao I.M., Golden B.L., Wasil E.A. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions // American Journal of Mathematical and Management Sciences. 1993. vol. 13(3–4). pp. 371–406. DOI: 10.1080/01966324.1993.10737363.
32. Dorigo M., Stützle T. Ant Colony Optimization, MIT Press, 2004.
Опубликован
2025-06-25
Как цитировать
Мигранов, А. Б. (2025). Модифицированные эвристические алгоритмы распределения заданий для групп мобильных роботов в условиях неопределенности. Информатика и автоматизация, 24(3), 884-913. https://doi.org/10.15622/ia.24.3.6
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) Айрат Барисович Мигранов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).