Analytical Review of Approaches to the Distribution of Tasks for Mobile Robot teams Based on Soft Computing Technologies

封面

如何引用文章

全文:

详细

The use of various types of heuristic algorithms based on soft computing technologies for the distribution of tasks in groups of mobile robots performing monosyllabic operations in a single workspace is considered: genetic algorithms, ant algorithms and artificial neural networks. It is shown that this problem is NP-complex and its solution by direct iteration for a large number of tasks is impossible. The initial problem is reduced to typical NP-complete problems: the generalized problem of finding the optimal group of closed routes from one depot and the traveling salesman problem. A description of each of the selected algorithms and a comparison of their characteristics are presented. A step-by-step algorithm of operation is given, taking into account the selected genetic operators and their parameters for a given population volume. The general structure of the developed algorithm is presented, which makes it possible to solve a multi-criteria optimization problem efficiently enough, taking into account time costs and the integral criterion of robot efficiency, taking into account energy costs, functional saturation of each agent of the group, etc. The possibility of solving the initial problem using an ant algorithm and a generalized search for the optimal group of closed routes is shown. For multi-criteria optimization, the possibility of linear convolution of the obtained vector optimality criterion is shown by introducing additional parameters characterizing group control: the overall efficiency of the functioning of all robots, the energy costs for the functioning of the support group and the energy for placing one robot on the work field. To solve the task distribution problem using the Hopfield neural network, its representation is made in the form of a graph obtained during the transition from the generalized task of finding the optimal group of closed routes from one depot to the traveling salesman problem. The quality indicator is the total path traveled by each of the robots in the group.

作者简介

O. Darintsev

Mavlyutov Institute of Mechanics - Subdivision of the Ufa Federal Research Center of the Russian Academy of Sciences

Email: ovd@uimech.org
Prospekt Oktyabrya 71

A. Migranov

Mavlyutov Institute of Mechanics - Subdivision of the Ufa Federal Research Center of the Russian Academy of Sciences

Email: abm.imech.anrb@mail.ru
Prospekt Oktyabrya 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
下载

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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