Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений
Ключевые слова:
коллектив роботов, распределение задач, генетический алгоритм, муравьиный алгоритм, нейросеть ХопфилдаАннотация
Рассматривается использование различных типов эвристических алгоритмов на основе технологий мягких вычислений для распределения задач в группах мобильных роботов, выполняющих односложные операции в едином рабочем пространстве: генетические алгоритмы, муравьиные алгоритмы и искусственные нейронные сети. Показано, что данная задача является NP-сложной и ее решение прямым перебором для большого числа заданий невозможно. Исходная задача сведена к типовым NP-полным задачам: обобщенной задаче поиска оптимальной группы замкнутых маршрутов от одного депо и задаче коммивояжера. Представлены описание каждого из выбранных алгоритмов и сравнение их характеристик. Приводится пошаговый алгоритм работы с учетом выбранных генетических операторов и их параметров при заданном объеме популяции. Представлена общая структура разработанного алгоритма, позволяющего достаточно эффективно решить многокритериальную оптимизационную задачу с учетом временных затрат и интегрального критерия эффективности роботов, учитывающего энергетические затраты, функциональную насыщенность каждого агента группы и т.д. Показана возможность решения исходной задачи с использованием муравьиного алгоритма и обобщенного поиска оптимальной группы замкнутых маршрутов. Для многокритериальной оптимизации показана возможность линейной свертки полученного векторного критерия оптимальности за счет введения дополнительных параметров, характеризующих групповое управление: общее КПД функционирования всех роботов, затраты энергии на функционирование группы поддержки и энергия на размещение одного робота на рабочем поле. Для решения задачи распределения заданий с использованием нейронной сети Хопфилда произведено ее представление в виде графа, полученного в ходе перехода от обобщенной задачи поиска оптимальной группы замкнутых маршрутов от одного депо к задаче коммивояжера. Показателем качества выбран суммарный путь, пройденный каждым из роботов группы.
Литература
1. Kalyaev I. et al. A novel method for distribution of goals among UAVs for oil field monitoring // IEEE 6th ICIEVISCMHT, Himeji, Japan. 2017. pp. 1–4.
2. ONDRACEK J. Intelligent Algorithms for Monitoring of the Environment Around Oil Pipe Systems Using Unmanned Aerial Systems. – Bachelor’s thesis. Czech Technical University in Prague, 2014.
3. CASBEER D.W. et al. Forest fire monitoring with multiple small UAVs // Proc. of the American Control Conference, June 2005, Portland, Oregon. 2005. pp. 3530–3535.
4. SUJIT P.B., KINGSTON D., BEARD R. Cooperative forest fire monitoring using multiple UAVs // 46th IEEE Conference on Decision and Control, 10-11 December 2007, New Orleans, Louisiana USA. 2007. pp. 4875–4880.
5. Khamis A., Hussein A., Elmogy A. Multi-robot Task Allocation: A Review of the State-of-the-Art. In: Koubâa A., Martínez-de Dios J. (eds) Cooperative Robots and Sensor Networks 2015. Studies in Computational Intelligence, vol 604. Springer, Cham.
6. Yi-Lin, L., Kuo-Lan, S. Multi-robot-based intelligent security system. Artif. Life Robot. 16, 137–141 (2011).
7. Marino, A., Parker, L.E., Antonelli, G., Caccavale, F. A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling. J. Intell. Robot. Syst. 71, pp. 423–444.
8. Иванов Д.Я. Распределение ролей в коалициях роботов при ограниченных коммуникациях на основе роевого взаимодействия // Управление большими системами. Институт проблем управления им. ВА Трапезникова РАН, 2019. Vol. 78. С. 23–45.
9. Jian-Ping Wang, Yuesheng Gu and Xiao-Min Li Multi-robot Task Allocation Based on Ant Colony Algorithm // Journal of Computers vol. 7, no. 9, pp. 2160-2167, 2012.
10. Кубил В.Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестник РГУПС, № 2, 2018. С. 97-109.
11. Chao I.M., Golden B.L., Wasil E. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions // American Journal of Mathematical and Management Sciences, Vol. 13, No. 3-4, 1993. pp. 371-406.
12. Choi E., Tcha D.W. A column generation approach to the heterogeneous fleet vehicle routing problem // Computers & Operations Research, Vol. 34, No. 7, 2007. pp. 2080-2095.
13. Кубил В.Н. Пространство решений задач коммивояжера и маршрутизации транспорта // Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы 16-ой Междунар. молодежн. науч.-практ. конф. ЮРГПУ (НПИ). Новочеркасск : Лик. 2017. С. 33-39.
14. Bremermann H.J. Optimization through evolution and recombination // Yovits M.C., Jacobi G.T. and Goldstein G.D. (Eds.), Self-Organizing Systems, 1962. pp. 93-106.
15. Зайцев А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта / А.А. Зайцев, В.В. Курейчик, А.А. Полупанов // Известия ЮФУ. 2010. № 12 (113). С. 7‒12.
16. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.
17. Литовка Н.В. Роевой интеллект в задачах оптимального размещения объектов пространственно распределенного предприятия/ Н.В. Литовка// Научные труды КубГТУ, № 11, 2018 год.
18. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System». Budapest, Central European University, 2001. pp. 1–38.
19. Caro G.D., Dorigo M. Anet a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97-12. IRIDA. Universite Libre de Brusseles. Brussels, Belgium, 1997. 27 p.
20. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. 2010. №7. C. 28-32.
21. Liping Zhu Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism// Liping Zhu, Song-Ju Kim, Masahiko Hara and Masashi Aono, 2018 (https://royalsocietypublishing.org/doi/10.1098/rsos.180396).
22. Ежов А.А. Дообучение нейронной сети Хопфилда: поиск глобального минимума функционала и модель быстрого сна// Ежов А.А., Черепнев А.С./ Математическое моделирование. 2009. Т. 21. № 5. С. 10-20.
23. Лоскутов А.И. Решение задачи о ранце на основе динамической нейронной сети Хопфилда// Лоскутов А.И., Горбулин В.И., Карпушев С.И., Ряхова Е.А./ Нелинейный мир. 2019. Т. 17. № 3. С. 25-35.
24. Хайкин С. Нейронные сети. Полный курс. Изд. 2-е, испр. М.: Вильямс. 2016. 1104 с.
25. Музычин В.В. Исследование возможности использования рекуррентной нейронной сети Хопфилда для решения задачи коммивояжера// Музычин В.В., Мациевский С.В./ Современная наука: актуальные проблемы теории и практики. Серия: Естественные и технические науки. 2020. № 5. С. 93-99.
26. Кубил В.Н. Исследование и разработка методов решения многокритериальных задач маршрутизации транспорта на основе муравьиного алгоритма: дис.. канд. т. наук. Южно-Российский гос. политехнический университет имени М.И. Платова, Новочеркасск, 2019.
27. Кубил В.Н., Мохов В.А. Многоколониальный муравьиный алгоритм с модификациями для решения многокритериальных задач маршрутизации транспорта // Известия высших учебных заведений. Электромеханика, Т. 61, № 6, 2018. С. 94-109.
28. Migranov A.B., Darintsev O.V. Choosing a Swarm Algorithm to Synthesis an Optimal Mobile Robot Team Control Strategy // 2020 International Multi-Conference on Industrial Engineering and Modern Technologies, Vladivostok, Russia, 2020, pp. 1-5.
29. Лотов А.В. Многокритериальные задачи принятия решений: Учебное пособие/ А.В. Лотов, И.И. Поспелова. – М.: МАКС Пресс, 2008. – 197 с.
30. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning/ D. Goldberg. – Massachusetts: Addison-Wesley, 1989.
31. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие/ Т.В. Панченко; под ред. Ю.Ю. Тарасевича. – Астрахань: Издательский дом «Астраханский университет», 2007. – 87 с.
32. Migranov A.B., Darintsev O.V. The Use of Genetic Algorithms for Distribution of Tasks in Groups of Mobile Robots with Minimization of Energy Consumption // 2019 International Multi-Conference on Industrial Engineering and Modern Technologies, Vladivostok, Russia, 2019, pp. 1-6.
33. Hopfield, J.J., Tank, D.W. (1985). Neural Computation of Decisions in Optimization Problems. Biological Cybernetics, Vol. 52, pp.141-152.
34. Кононов А.А. Использование метода нейронных сетей Хопфилда для решения задачи маршрутизации в сети// Кононов А.А/ Московский экономический журнал, №9, 2019. С.74
35. Darintsev O.V. Migranov A.B. Using the Hopfield Neural Network to Select a Behaviour Strategy for the Group of Mobile Robots // IOP Publishing, 2021, J. Phys.: Conf. Ser. 2096 012086
2. ONDRACEK J. Intelligent Algorithms for Monitoring of the Environment Around Oil Pipe Systems Using Unmanned Aerial Systems. – Bachelor’s thesis. Czech Technical University in Prague, 2014.
3. CASBEER D.W. et al. Forest fire monitoring with multiple small UAVs // Proc. of the American Control Conference, June 2005, Portland, Oregon. 2005. pp. 3530–3535.
4. SUJIT P.B., KINGSTON D., BEARD R. Cooperative forest fire monitoring using multiple UAVs // 46th IEEE Conference on Decision and Control, 10-11 December 2007, New Orleans, Louisiana USA. 2007. pp. 4875–4880.
5. Khamis A., Hussein A., Elmogy A. Multi-robot Task Allocation: A Review of the State-of-the-Art. In: Koubâa A., Martínez-de Dios J. (eds) Cooperative Robots and Sensor Networks 2015. Studies in Computational Intelligence, vol 604. Springer, Cham.
6. Yi-Lin, L., Kuo-Lan, S. Multi-robot-based intelligent security system. Artif. Life Robot. 16, 137–141 (2011).
7. Marino, A., Parker, L.E., Antonelli, G., Caccavale, F. A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling. J. Intell. Robot. Syst. 71, pp. 423–444.
8. Иванов Д.Я. Распределение ролей в коалициях роботов при ограниченных коммуникациях на основе роевого взаимодействия // Управление большими системами. Институт проблем управления им. ВА Трапезникова РАН, 2019. Vol. 78. С. 23–45.
9. Jian-Ping Wang, Yuesheng Gu and Xiao-Min Li Multi-robot Task Allocation Based on Ant Colony Algorithm // Journal of Computers vol. 7, no. 9, pp. 2160-2167, 2012.
10. Кубил В.Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестник РГУПС, № 2, 2018. С. 97-109.
11. Chao I.M., Golden B.L., Wasil E. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions // American Journal of Mathematical and Management Sciences, Vol. 13, No. 3-4, 1993. pp. 371-406.
12. Choi E., Tcha D.W. A column generation approach to the heterogeneous fleet vehicle routing problem // Computers & Operations Research, Vol. 34, No. 7, 2007. pp. 2080-2095.
13. Кубил В.Н. Пространство решений задач коммивояжера и маршрутизации транспорта // Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы 16-ой Междунар. молодежн. науч.-практ. конф. ЮРГПУ (НПИ). Новочеркасск : Лик. 2017. С. 33-39.
14. Bremermann H.J. Optimization through evolution and recombination // Yovits M.C., Jacobi G.T. and Goldstein G.D. (Eds.), Self-Organizing Systems, 1962. pp. 93-106.
15. Зайцев А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта / А.А. Зайцев, В.В. Курейчик, А.А. Полупанов // Известия ЮФУ. 2010. № 12 (113). С. 7‒12.
16. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.
17. Литовка Н.В. Роевой интеллект в задачах оптимального размещения объектов пространственно распределенного предприятия/ Н.В. Литовка// Научные труды КубГТУ, № 11, 2018 год.
18. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System». Budapest, Central European University, 2001. pp. 1–38.
19. Caro G.D., Dorigo M. Anet a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97-12. IRIDA. Universite Libre de Brusseles. Brussels, Belgium, 1997. 27 p.
20. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. 2010. №7. C. 28-32.
21. Liping Zhu Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism// Liping Zhu, Song-Ju Kim, Masahiko Hara and Masashi Aono, 2018 (https://royalsocietypublishing.org/doi/10.1098/rsos.180396).
22. Ежов А.А. Дообучение нейронной сети Хопфилда: поиск глобального минимума функционала и модель быстрого сна// Ежов А.А., Черепнев А.С./ Математическое моделирование. 2009. Т. 21. № 5. С. 10-20.
23. Лоскутов А.И. Решение задачи о ранце на основе динамической нейронной сети Хопфилда// Лоскутов А.И., Горбулин В.И., Карпушев С.И., Ряхова Е.А./ Нелинейный мир. 2019. Т. 17. № 3. С. 25-35.
24. Хайкин С. Нейронные сети. Полный курс. Изд. 2-е, испр. М.: Вильямс. 2016. 1104 с.
25. Музычин В.В. Исследование возможности использования рекуррентной нейронной сети Хопфилда для решения задачи коммивояжера// Музычин В.В., Мациевский С.В./ Современная наука: актуальные проблемы теории и практики. Серия: Естественные и технические науки. 2020. № 5. С. 93-99.
26. Кубил В.Н. Исследование и разработка методов решения многокритериальных задач маршрутизации транспорта на основе муравьиного алгоритма: дис.. канд. т. наук. Южно-Российский гос. политехнический университет имени М.И. Платова, Новочеркасск, 2019.
27. Кубил В.Н., Мохов В.А. Многоколониальный муравьиный алгоритм с модификациями для решения многокритериальных задач маршрутизации транспорта // Известия высших учебных заведений. Электромеханика, Т. 61, № 6, 2018. С. 94-109.
28. Migranov A.B., Darintsev O.V. Choosing a Swarm Algorithm to Synthesis an Optimal Mobile Robot Team Control Strategy // 2020 International Multi-Conference on Industrial Engineering and Modern Technologies, Vladivostok, Russia, 2020, pp. 1-5.
29. Лотов А.В. Многокритериальные задачи принятия решений: Учебное пособие/ А.В. Лотов, И.И. Поспелова. – М.: МАКС Пресс, 2008. – 197 с.
30. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning/ D. Goldberg. – Massachusetts: Addison-Wesley, 1989.
31. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие/ Т.В. Панченко; под ред. Ю.Ю. Тарасевича. – Астрахань: Издательский дом «Астраханский университет», 2007. – 87 с.
32. Migranov A.B., Darintsev O.V. The Use of Genetic Algorithms for Distribution of Tasks in Groups of Mobile Robots with Minimization of Energy Consumption // 2019 International Multi-Conference on Industrial Engineering and Modern Technologies, Vladivostok, Russia, 2019, pp. 1-6.
33. Hopfield, J.J., Tank, D.W. (1985). Neural Computation of Decisions in Optimization Problems. Biological Cybernetics, Vol. 52, pp.141-152.
34. Кононов А.А. Использование метода нейронных сетей Хопфилда для решения задачи маршрутизации в сети// Кононов А.А/ Московский экономический журнал, №9, 2019. С.74
35. Darintsev O.V. Migranov A.B. Using the Hopfield Neural Network to Select a Behaviour Strategy for the Group of Mobile Robots // IOP Publishing, 2021, J. Phys.: Conf. Ser. 2096 012086
Опубликован
2022-07-14
Как цитировать
Даринцев, О. В., & Мигранов, А. Б. (2022). Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений. Информатика и автоматизация, 21(4), 729-757. https://doi.org/10.15622/ia.21.4.4
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) Олег Владимирович Даринцев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).