Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений

Обложка

Цитировать

Полный текст

Аннотация

Рассматривается использование различных типов эвристических алгоритмов на основе технологий мягких вычислений для распределения задач в группах мобильных роботов, выполняющих односложные операции в едином рабочем пространстве: генетические алгоритмы, муравьиные алгоритмы и искусственные нейронные сети. Показано, что данная задача является NP-сложной и ее решение прямым перебором для большого числа заданий невозможно. Исходная задача сведена к типовым NP-полным задачам: обобщенной задаче поиска оптимальной группы замкнутых маршрутов от одного депо и задаче коммивояжера. Представлены описание каждого из выбранных алгоритмов и сравнение их характеристик. Приводится пошаговый алгоритм работы с учетом выбранных генетических операторов и их параметров при заданном объеме популяции. Представлена общая структура разработанного алгоритма, позволяющего достаточно эффективно решить многокритериальную оптимизационную задачу с учетом временных затрат и интегрального критерия эффективности роботов, учитывающего энергетические затраты, функциональную насыщенность каждого агента группы и т.д. Показана возможность решения исходной задачи с использованием муравьиного алгоритма и обобщенного поиска оптимальной группы замкнутых маршрутов. Для многокритериальной оптимизации показана возможность линейной свертки полученного векторного критерия оптимальности за счет введения дополнительных параметров, характеризующих групповое управление: общее КПД функционирования всех роботов, затраты энергии на функционирование группы поддержки и энергия на размещение одного робота на рабочем поле. Для решения задачи распределения заданий с использованием нейронной сети Хопфилда произведено ее представление в виде графа, полученного в ходе перехода от обобщенной задачи поиска оптимальной группы замкнутых маршрутов от одного депо к задаче коммивояжера. Показателем качества выбран суммарный путь, пройденный каждым из роботов группы.

Об авторах

О. В Даринцев

Институт механики им. Р.Р. Мавлютова — обособленное структурное подразделение Уфимского федерального исследовательского центра Российской академии наук

Email: ovd@uimech.org
Проспект Октября 71

А. Б Мигранов

Институт механики им. Р.Р. Мавлютова — обособленное структурное подразделение Уфимского федерального исследовательского центра Российской академии наук

Email: abm.imech.anrb@mail.ru
Проспект Октября 71

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).