Использование графоаналитических методов для формирования траектории группы подвижных объектов в двумерной среде
Ключевые слова:
групповое управление, подвижный объект, графоаналитические методы, алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм A*Аннотация
Рассматривается задача формирования траекторий движения группы подвижных объектов, функционирующих в двумерной среде с неподвижными препятствиями. Эта задача решалась графоаналитическими методами, основанными на алгоритмах Дейкстры, Беллмана-Форда и A*. Поставлен эксперимент, включающий компьютерное моделирование, результатами которого явились данные о времени движения группы подвижных объектов по траекториям. На основании данных результатов моделирования произведено их сравнение, которое позволило сделать вывод об эффективности различных методов решения задачи, и помогло выявить наиболее оптимальный.Литература
1. Чернухин Ю.В., Пшихопов В.Х., Писаренко С.Н., Трубачев О.Е. Программная среда для моделирования поведения адаптивных мобильных роботов с двухуровневой системой управления // Мехатроника. 2000. № 6. С. 26–30.
2. Алфимов С.М. Перспективные направления развития базовых военных технологий в области создания систем управления и обработки информации // Мехатроника, автоматизация и управление. 2008. № 2. С. 2–5.
3. Черноусько Ф.Л., Болотник Н.Н., Градецкий В.Г. Мобильные роботы: проблемы управления и оптимизации движений // Труды XII Всероссийского совещания по проблемам управления. Москва. 2014. С. 19.
4. Пшихопов В.Х. Позиционно-траекторное управление подвижными объ-ектами. // Таганрог: ТТИ ЮФУ. 2009. 183 с.
5. Гузик В.Ф. и др. Интеллектуальное планирование траекторий подвижных объектов в средах с препятствиями / Под редакцией В.Х. Пшихопова // М.: Физматлит. 2014. 350 с.
6. Macek K., Petrovic I., Ivanjko E. An Approach to Motion Planning of Indoor Mobile Robots // In Proc. IEEE International Conference on Industrial Technology. 2003. pp. 969–973.
7. Stentz A et. al. The Focussed D* Algorithm for Real-Time Replanning // In Proc. International Joint Conference on Artificial Intelligence. 1995. vol. 95. pp. 1652–1659.
8. Платонов А.К., Карпов И.И., Кирильченко А.А. Метод потенциалов в задаче прокладки трассы // М.: Препринт Института прикладной мате-матики АН СССР. 1974. 27 с.
9. Пшихопов В.Х., Медведев М.Ю. Управление подвижными объектами в определенных и неопределенных средах // М.: Наука. 2011. 350 с.
10. Pozna C., Precup R.E., Koczy L.T., Ballagi A. Potential field-based approach for obstacle avoidance trajectories // The IPSI BgD Transactions on Inter-net Research. vol. 8. no 2. 2002. pp. 40–45.
11. Попел Е.В. Обработка информации о поле расстояний в задаче модели-рования движения людей // Перспективы развития информационных технологий. 2012. № 10. С. 20–25.
12. Щербаков В.С., Корытов М.С. Использование алгоритмов поиска пути перемещения груза автокраном на графах // Вестник ВГТУ. 2009. № 5. С. 37–41.
13. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische mathematik. 1959. vol. 1. no. 1. pp. 269–271.
14. Bellman R. On a Routing Problem // Quarterly of Applied Mathematics. 1958. vol. 16. no. 1. pp. 87–90.
15. Hart P.E., Nilsson N. J. Raphael B. A. Formal Basis for the Heuristic De-termination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics. 1968. no. 2. pp. 100–107.
16. Hart P.E., Nilsson N.J., Raphael B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. 1972. vol. 37. С. 28–29.
17. Hagberg A., Schult D., Swart P. NetworkX Reference Release 1.11 URL: ttps://media.readthedocs.org/pdf/networkx/stable/networkx.pdf. (Дата обращения: 31.01.16).
18. Кипер А.В., Станкевич Т.С. Система для выбора кратчайшего безопасного маршрута спасения людей из горящего здания на территории морского порта // Вестник АГТУ. Управление, вычислительная техника и информатика. 2013. № 2. С. 144–152.
19. Сундетов Р.Н., Есламгалиев Т.Н. Обоснование выбора алгоритма поиска оптимального пути с расчетом показателей светофора в городской сети // Естественные и математические науки в современном мире. 2015. № 5(29). С. 133–137.
20. Беляков С.Л., Белякова М.Л., Боженюк А.В., Савельева М.Н. Оптимизация потоков в транспортных системах // Известия ЮФУ. Технические науки. 2014. № 5(154). С. 161–167.
21. Дубовик Н.Н., Лавров А.В., Ногин О.А., Туманов В.М. Анализ методов пространственной навигации и трассировки маршрутов с линейными ограничениями // МНИЖ. 2015. № 11–2(42). С. 35–42.
2. Алфимов С.М. Перспективные направления развития базовых военных технологий в области создания систем управления и обработки информации // Мехатроника, автоматизация и управление. 2008. № 2. С. 2–5.
3. Черноусько Ф.Л., Болотник Н.Н., Градецкий В.Г. Мобильные роботы: проблемы управления и оптимизации движений // Труды XII Всероссийского совещания по проблемам управления. Москва. 2014. С. 19.
4. Пшихопов В.Х. Позиционно-траекторное управление подвижными объ-ектами. // Таганрог: ТТИ ЮФУ. 2009. 183 с.
5. Гузик В.Ф. и др. Интеллектуальное планирование траекторий подвижных объектов в средах с препятствиями / Под редакцией В.Х. Пшихопова // М.: Физматлит. 2014. 350 с.
6. Macek K., Petrovic I., Ivanjko E. An Approach to Motion Planning of Indoor Mobile Robots // In Proc. IEEE International Conference on Industrial Technology. 2003. pp. 969–973.
7. Stentz A et. al. The Focussed D* Algorithm for Real-Time Replanning // In Proc. International Joint Conference on Artificial Intelligence. 1995. vol. 95. pp. 1652–1659.
8. Платонов А.К., Карпов И.И., Кирильченко А.А. Метод потенциалов в задаче прокладки трассы // М.: Препринт Института прикладной мате-матики АН СССР. 1974. 27 с.
9. Пшихопов В.Х., Медведев М.Ю. Управление подвижными объектами в определенных и неопределенных средах // М.: Наука. 2011. 350 с.
10. Pozna C., Precup R.E., Koczy L.T., Ballagi A. Potential field-based approach for obstacle avoidance trajectories // The IPSI BgD Transactions on Inter-net Research. vol. 8. no 2. 2002. pp. 40–45.
11. Попел Е.В. Обработка информации о поле расстояний в задаче модели-рования движения людей // Перспективы развития информационных технологий. 2012. № 10. С. 20–25.
12. Щербаков В.С., Корытов М.С. Использование алгоритмов поиска пути перемещения груза автокраном на графах // Вестник ВГТУ. 2009. № 5. С. 37–41.
13. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische mathematik. 1959. vol. 1. no. 1. pp. 269–271.
14. Bellman R. On a Routing Problem // Quarterly of Applied Mathematics. 1958. vol. 16. no. 1. pp. 87–90.
15. Hart P.E., Nilsson N. J. Raphael B. A. Formal Basis for the Heuristic De-termination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics. 1968. no. 2. pp. 100–107.
16. Hart P.E., Nilsson N.J., Raphael B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. 1972. vol. 37. С. 28–29.
17. Hagberg A., Schult D., Swart P. NetworkX Reference Release 1.11 URL: ttps://media.readthedocs.org/pdf/networkx/stable/networkx.pdf. (Дата обращения: 31.01.16).
18. Кипер А.В., Станкевич Т.С. Система для выбора кратчайшего безопасного маршрута спасения людей из горящего здания на территории морского порта // Вестник АГТУ. Управление, вычислительная техника и информатика. 2013. № 2. С. 144–152.
19. Сундетов Р.Н., Есламгалиев Т.Н. Обоснование выбора алгоритма поиска оптимального пути с расчетом показателей светофора в городской сети // Естественные и математические науки в современном мире. 2015. № 5(29). С. 133–137.
20. Беляков С.Л., Белякова М.Л., Боженюк А.В., Савельева М.Н. Оптимизация потоков в транспортных системах // Известия ЮФУ. Технические науки. 2014. № 5(154). С. 161–167.
21. Дубовик Н.Н., Лавров А.В., Ногин О.А., Туманов В.М. Анализ методов пространственной навигации и трассировки маршрутов с линейными ограничениями // МНИЖ. 2015. № 11–2(42). С. 35–42.
Опубликован
2016-04-04
Как цитировать
Лазарев, В. С., & Агаджанов, Д. Э. (2016). Использование графоаналитических методов для формирования траектории группы подвижных объектов в двумерной среде. Труды СПИИРАН, 2(45), 45-57. https://doi.org/10.15622/sp.45.3
Раздел
Методы управления и обработки информации
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
