АНАЛИЗ АЛГОРИТМОВ ВЫБОРА ОПТИМАЛЬНЫХ МАРШРУТОВ ГРУППЫ СУДОВ
Аннотация
Решается задача построения кратчайших маршрутов для группы судов, получивших задание достижения условных целей с известными координатами, расположенных в ограниченном пространстве. Рассмотрен случай, когда число целей у всех судов одинаковое. Задача считается выполненной при достижении судами всех своих целей. Предлагается два алгоритма решения задачи координации действий судов с расчетом минимальных по длине маршрутов. Эффективность решения задачи по выбору маршрутов оценивается по времени ожидания судна, последним достигшего цель. Решается задача об оптимальном выборе начальных положений судов. Численный эксперимент обнаруживает экстремальные значения параметра распределения судов в предположении о равномерном их распределении по заранее выбранной прямой. Предложенные алгоритмы и выводы из их анализа могут найти применение в организации движения морского, воздушного и наземного транспорта.
Ключевые слова
маршрут, цель, алгоритм, оптимизация пути, групповое управление, транспорт
Читать полный текст статьи: PDF
Список литературы
Касьянов В. Н. Графы в программировании: обработка, визуализация и применение / В. Н. Касьянов, В. А. Евстигнеев. - СПб.: БХВ-Петербург, 2003. - 1104 с.
Сазонов А. Е. Прогнозирование траектории движения судна при помощи нейронной сети / А. Е. Сазонов, В. В. Дерябин // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2013. - № 3 (22). - С. 6-13.
Gao S. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks / S. Gao, H. Huang // Transportation Research Part C: Emerging Technologies. - 2012. - Vol. 21. - Pp. 196-213.
Fu L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information / L. Fu // Transportation Research Part B: Methodological. - 2001. - Vol. 35. - № 8. - Pp. 749-765. DOI:10.1016/ S0191-2615(00)00019-9.
Castillo O. Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots / O. Castillo, L. Trujillo, P. Melin // Soft Computing. - 2007. - Vol. 11. - № 3. - Pp. 269-279. DOI: 10.1007/s00500-006-0068-4.
Fonseca C. M. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization / C. M. Fonseca, C. J. Fleming // 5th international conference genetic algorithms. - 1993. - Pp. 416-423.
Каляев И. А. Модели и алгоритмы коллективного управления в группах роботов / И. А. Каляев, А. Р. Гайдук, С. Г. Капустян. - М.: Физматлит, 2009. - 280 с.
Каляев И. А. Управление группой БЛА в задаче формирования строя / И. А. Каляев, А. Р. Гайдук, С. Г. Капустян // Робототехника и техническая кибернетика. - 2014. - № 4 (5). - С. 28-39.
Александров В. А. Коллективный алгоритм выделения операционных подпространств для группы роботов при решении задачи покрытия территории / В. А. Александров, А. И. Кобрин // Известия высших учебных заведений. Машиностроение. - 2011. - № 9. - С. 65-69.
Александров В. А. Аппаратно-программный комплекс для моделирования задач группового управления мобильными роботами / В. А. Александров, А. И. Кобрин // Вестник МЭИ. - 2011. - № 3. - С. 88-95.
Александров В. А. Исследование алгоритма выделения операционных подпространств при решении задачи покрытия территории группой роботов / В. А. Александров, А. И. Кобрин // Мат. междунар. молодежной науч.-практ. конф. «Мобильные роботы и мехатронные системы». - М.: Изд-во Московского университета, 2011. - С. 19-22.
Александров В. А. Коллективно-ориентированные мобильные роботы для исследования алгоритмов группового управления / В. А. Александров, К. А. Кирик, А. И. Кобрин // Машиностроение: сетевой электронный научный журнал. - 2014. - № 1. - С. 70-76.
Кобрин А. И. Программно-аппаратный комплекс для моделирования задач обучения, потоковой обработки сенсорной информации и адаптивного группового управления мобильными роботами / А. И. Кобрин, В. А. Александров, О. Ю. Синявский // Вестник Нижегородского университета им. Н. И. Лобачевского. - 2011. - № 4-5. - С. 2238-2240.
Kuipers B. A Robot Exploration and Mapping Strategy Basedon a Semantic Hierarchy of Spatial Representations / B. Kuipers, Y.-T. Byun // Robotics and Autonomous Systems. - 1991. - Vol. 8. - № 1-2. - Pp. 47-63. DOI:10.1016/0921-8890(91)90014-C.
Александров В. А. Разрешение конфликтных ситуаций в коллективе автономных аппаратов / В. А. Александров, К. А. Кирик, А. И. Кобрин // Известия Волгоградского государственного технического университета. - 2013. - Т. 19. - № 24 (127). - С. 6-10.
Александров В. А. Программное обеспечение комплекса аппаратного моделирования алгоритмов группового управления / В. А. Александров, К. А. Кирик, А. И. Кобрин // Trends in Applied Mechanics and Mechatronics. - М: Инфра-М, 2015. - Т. 1. - С. 66-69.
Sinyavskiy O. Y. Construction of adaptive robot control system and robot sensor information processing using spiking neural networks / O. Y. Sinyavskiy, A. I. Kobrin // Proceedings Taiwan-Russian Bilateral Symposium on Problems in Advanced Mechanics. - M.: Moscow State University, 2010. - Pp. 218-227.
Breitenmoser A. Voronoi coverage of nonconvex environments with a group of networked robots / A. Breitenmoser, M. Schwager, J. C. Metzger, R. Siegwart, D. Rus // Robotics and Automation (ICRA), 2010 IEEE International Conference on. - IEEE, 2010. - Pp. 4982-4989.
Шкорупо Д. А. Оптимизация морской транспортной сети в линейном судоходстве / Д. А. Шкорупо, М. В. Волощук // Економічні інновації. - 2012. - № 49. - С. 253-266.
Dedkov V. A. The problem of control for multirobot systems / V. A. Dedkov, M. N. Kirsanov // Инновационные информационные технологии. - 2013. - Т. 2. - № 2. - С. 206-213.
Hachour O. A Three dimensional Path Planning algorithm / O. Hachour // Proceeding ICS’10. 14th WSEAS international conference on Systems : part of the 14th WSEAS CSCC multiconference. - 2010. - Vol. I. - Pp. 60-65.
Kirsanov A. Path planning for the autonomous underwater vehicle / A. Kirsanov, S. Anavatti, T. Ray // Lecture Notes in Computer Science. - 2013. - Vol. 8298. - Part 2. - Pp. 476-486. DOI: 10.1007/978-3-319- 03756-1_43.
Zeng Z. A survey on path planning for persistent autonomy of autonomous underwater vehicles / Z. Zeng, L. Lian, K. Sammut, F. He, Y. Tang, A. Lammas // Ocean Engineering. - 2015. - Vol. 110. - Part A. - Pp. 303-313. DOI:10.1016/j.oceaneng.2015.10.007.
Ataei M. Three-dimensional optimal path planning for waypoint guidance of an autonomous underwater vehicle / M. Ataei, A. Yousefi-Koma // Robotics and Autonomous Systems. - 2015. - Vol. 67. - Pp. 23-32. DOI:10.1016/j.robot.2014.10.007.
Alvarez A. Evolutionary path planning for autonomous underwater vehicles in a variable ocean / A. Alvarez, A. Caiti, R. Onken // IEEE Journal of Oceanic Engineering. - 2004. - Vol. 29. - № 2. - Pp. 418-429. DOI: 10.1109/JOE.2004.827837.
Асанов М. О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 288 с.
Голоскоков Д. П. Практический курс математической физики в системе Maple / Д. П. Голоскоков. - СПб.: ПаркКом, 2010. - 644 с.
[Архив]. - Режим доступа: http://vuz.exponenta.ru/Maple-path-animation.rar
Об авторах
Кирсанов Михаил Николаевич - доктор физико-математических наук, профессор
ФГБОУ ВО «НИУ «МЭИ»
