Аналитический обзор подходов к распределению задач в группах мобильных роботов на основе технологий мягких вычислений
- Авторы: Даринцев О.В1, Мигранов А.Б1
-
Учреждения:
- Институт механики им. Р.Р. Мавлютова — обособленное структурное подразделение Уфимского федерального исследовательского центра Российской академии наук
- Выпуск: Том 21, № 4 (2022)
- Страницы: 729-757
- Раздел: Робототехника, автоматизация и системы управления
- URL: https://bakhtiniada.ru/2713-3192/article/view/266359
- DOI: https://doi.org/10.15622/ia.21.4.4
- ID: 266359
Цитировать
Полный текст
Аннотация
Рассматривается использование различных типов эвристических алгоритмов на основе технологий мягких вычислений для распределения задач в группах мобильных роботов, выполняющих односложные операции в едином рабочем пространстве: генетические алгоритмы, муравьиные алгоритмы и искусственные нейронные сети. Показано, что данная задача является NP-сложной и ее решение прямым перебором для большого числа заданий невозможно. Исходная задача сведена к типовым NP-полным задачам: обобщенной задаче поиска оптимальной группы замкнутых маршрутов от одного депо и задаче коммивояжера. Представлены описание каждого из выбранных алгоритмов и сравнение их характеристик. Приводится пошаговый алгоритм работы с учетом выбранных генетических операторов и их параметров при заданном объеме популяции. Представлена общая структура разработанного алгоритма, позволяющего достаточно эффективно решить многокритериальную оптимизационную задачу с учетом временных затрат и интегрального критерия эффективности роботов, учитывающего энергетические затраты, функциональную насыщенность каждого агента группы и т.д. Показана возможность решения исходной задачи с использованием муравьиного алгоритма и обобщенного поиска оптимальной группы замкнутых маршрутов. Для многокритериальной оптимизации показана возможность линейной свертки полученного векторного критерия оптимальности за счет введения дополнительных параметров, характеризующих групповое управление: общее КПД функционирования всех роботов, затраты энергии на функционирование группы поддержки и энергия на размещение одного робота на рабочем поле. Для решения задачи распределения заданий с использованием нейронной сети Хопфилда произведено ее представление в виде графа, полученного в ходе перехода от обобщенной задачи поиска оптимальной группы замкнутых маршрутов от одного депо к задаче коммивояжера. Показателем качества выбран суммарный путь, пройденный каждым из роботов группы.
Об авторах
О. В Даринцев
Институт механики им. Р.Р. Мавлютова — обособленное структурное подразделение Уфимского федерального исследовательского центра Российской академии наук
Email: ovd@uimech.org
Проспект Октября 71
А. Б Мигранов
Институт механики им. Р.Р. Мавлютова — обособленное структурное подразделение Уфимского федерального исследовательского центра Российской академии наук
Email: abm.imech.anrb@mail.ru
Проспект Октября 71
Список литературы
- 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.
- 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.
- 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.
- 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.
- 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.
- Yi-Lin, L., Kuo-Lan, S. Multi-robot-based intelligent security system. Artif. Life Robot. 16, 137–141 (2011).
- 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.
- Иванов Д.Я. Распределение ролей в коалициях роботов при ограниченных коммуникациях на основе роевого взаимодействия // Управление большими системами. Институт проблем управления им. ВА Трапезникова РАН, 2019. Vol. 78. С. 23–45.
- 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.
- Кубил В.Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестник РГУПС, № 2, 2018. С. 97-109.
- 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.
- 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.
- Кубил В.Н. Пространство решений задач коммивояжера и маршрутизации транспорта // Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы 16-ой Междунар. молодежн. науч.-практ. конф. ЮРГПУ (НПИ). Новочеркасск : Лик. 2017. С. 33-39.
- 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.
- Зайцев А.А. Обзор эволюционных методов оптимизации на основе роевого интеллекта / А.А. Зайцев, В.В. Курейчик, А.А. Полупанов // Известия ЮФУ. 2010. № 12 (113). С. 7‒12.
- Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.
- Литовка Н.В. Роевой интеллект в задачах оптимального размещения объектов пространственно распределенного предприятия/ Н.В. Литовка// Научные труды КубГТУ, № 11, 2018 год.
- 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.
- 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.
- Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. 2010. №7. C. 28-32.
- 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).
- Ежов А.А. Дообучение нейронной сети Хопфилда: поиск глобального минимума функционала и модель быстрого сна// Ежов А.А., Черепнев А.С./ Математическое моделирование. 2009. Т. 21. № 5. С. 10-20.
- Лоскутов А.И. Решение задачи о ранце на основе динамической нейронной сети Хопфилда// Лоскутов А.И., Горбулин В.И., Карпушев С.И., Ряхова Е.А./ Нелинейный мир. 2019. Т. 17. № 3. С. 25-35.
- Хайкин С. Нейронные сети. Полный курс. Изд. 2-е, испр. М.: Вильямс. 2016. 1104 с.
- Музычин В.В. Исследование возможности использования рекуррентной нейронной сети Хопфилда для решения задачи коммивояжера// Музычин В.В., Мациевский С.В./ Современная наука: актуальные проблемы теории и практики. Серия: Естественные и технические науки. 2020. № 5. С. 93-99.
- Кубил В.Н. Исследование и разработка методов решения многокритериальных задач маршрутизации транспорта на основе муравьиного алгоритма: дис.. канд. т. наук. Южно-Российский гос. политехнический университет имени М.И. Платова, Новочеркасск, 2019.
- Кубил В.Н., Мохов В.А. Многоколониальный муравьиный алгоритм с модификациями для решения многокритериальных задач маршрутизации транспорта // Известия высших учебных заведений. Электромеханика, Т. 61, № 6, 2018. С. 94-109.
- 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.
- Лотов А.В. Многокритериальные задачи принятия решений: Учебное пособие/ А.В. Лотов, И.И. Поспелова. – М.: МАКС Пресс, 2008. – 197 с.
- Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning/ D. Goldberg. – Massachusetts: Addison-Wesley, 1989.
- Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие/ Т.В. Панченко; под ред. Ю.Ю. Тарасевича. – Астрахань: Издательский дом «Астраханский университет», 2007. – 87 с.
- 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.
- Hopfield, J.J., Tank, D.W. (1985). Neural Computation of Decisions in Optimization Problems. Biological Cybernetics, Vol. 52, pp.141-152.
- Кононов А.А. Использование метода нейронных сетей Хопфилда для решения задачи маршрутизации в сети// Кононов А.А/ Московский экономический журнал, №9, 2019. С.74
- 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
Дополнительные файлы
