Доступ открыт Открытый доступ  Доступ закрыт Только для подписчиков

Алгоритм многокритериального поиска траекторий движения робота на многослойной карте


https://doi.org/10.15217/issn1684-8853.2018.3.45

Полный текст:


Аннотация

Постановка проблемы: сложная среда характеризуется возможностью декомпозиции воздействующих на робота факторов на независимые слои. В процессе движения робота в сложной среде на него воздействуют негативные факторы, влияющие на возможность достижения цели. В связи с этим возникает проблема выбора траектории движения при одновременной минимизации нежелательных воздействий на робота и длины пройденного пути.

Цель: разработка и анализ результатов работы алгоритма двухкритериальной оптимизации траектории движения робота с учетом желаемых критериев взаимодействия со средой и длины траектории.

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

 Практическая значимость: разработанный алгоритм может быть применен в системах планирования индивидуального или группового движения роботов. Полученное пространство состояний отражает диапазоны эффективных характеристик робота при выполнении поставленных задач в заданной среде. Продолжением работы станет применение разработанного алгоритма при поиске пути на разномасштабных картах и построение семейств траекторий в пространстве состояний группы роботов.


Об авторах

Д. Е. Моторин
Санкт-Петербургский политехнический университет Петра Великого
Россия

МОТОРИН Дмитрий Евгеньевич, аспират кафедры телематики 

Политехническая ул., 29, Санк-тПетербург, 195251



С. Г. Попов
Санкт-Петербургский политехнический университет Петра Великого
Россия

ПОПОВ Сергей Геннадьевич, кандидат технических наук, доцент кафедры телематики 

Политехническая ул., 29, Санк-тПетербург, 195251



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

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. 3rd. — MIT Press, 2009. — 1313 p.

2. Eraghi N. O., López-Colino F., de Castro A., Garrido J. Path Length Comparison in Grid Maps of Planning Algorithms: HCTNav, A* and Dijkstra // Design of Circuits and Integrated Systems, Madrid, 2014. P. 1–6. doi:10.1109/DCIS.2014.7035557

3. Столяров А. А., Санников Е. В. Выбор эффективного алгоритма планирования для формирования информационной подсистемы движения мобильного робота // Universum: Технические науки: электрон. науч. журн. 2015. № 8-9(20). http://7universum.com/ru/tech/archive/item/2586 (дата обращения: 28.04.2018).

4. Нейдорф Р. А., Полях В. В., Черногоров И. В., Ярахмедов О. Т. Исследование эвристических алгоритмов в задачах прокладки и оптимизация маршрутов в среде с препятствиями // Изв. ЮФУ. Технические науки. 2016. № 3 (176). С. 127–143.

5. Lin M., Yuan K., Shi C., Wang Y. Path Planning of Mobile Robot based on Improved A* Algorithm // 2017 29th Chinese Control and Decision Conf. (CCDC), Chongqing, 2017. P. 3570–3576. doi:10.1109/CCDC.2017.7979125

6. Da K., Xiaoyu L., Bi Z. Variable-Step-Length A* Algorithm for Path Planning of Mobile Robot // 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, 2017. P. 7129–7133. doi:10.1109/ CCDC.2017.7978469

7. Cherni F., Boutereaa Y., Rekik C., Derbel N. Autonomous Mobile Robot Navigation Algorithm for Planning Collision-Free Path Designed in Dynamic Environments // 2015 9th Jordanian International Electrical and Electronics Engineering Conf. (JIEEEC), Amman, 2015. P. 1–6. doi:10.1109/JIEEEC.2015.7470747

8. Даринцев О. В., Мигранов А. Б. Синтез гибридных интеллектуальных алгоритмов планирования траектории // Фундаментальные исследования. 2015. № 12. Ч. 4. С. 676–681. http://www.fundamentalresearch.ru/ru/article/view?id=39603 (дата обращения: 28.04.2018).

9. Моторин Д. Е., Попов С. Г., Курочкин Л. М. Алгоритм разрешения коллизий при планировании движения группы роботов в условиях пространственно-ситуационной неопределенности // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2017. Т. 10. № 2. С. 32–44. doi:10.18721/JCSTCS.10203

10. Дивеев А. И., Шмалько Е. Ю. Эволюционные методы вычислений для синтеза управления группой роботов и поиска оптимальных траекторий их движения // Cloud of Science. 2017. T. 4. № 3. С. 395– 414.

11. Федоренко К. В., Оловянников А. Л. Исследование основных параметров генетического алгоритма применительно к задаче поиска оптимального маршрута // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. 2017. Т. 9. № 4. С. 714–723. doi:10. 21821/2309-5180-2017-9-4-714-723

12. Ni J., Wang K., Huang H., Wu L., Luo C. Robot Path Planning based on an Improved Genetic Algorithm with Variable Length Chromosome // 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNCFSKD), Changsha, 2016. P. 145–149. doi:10.1109/ FSKD.2016.7603165

13. Li J., Huang Y., Xu Z., Wang J., Chen M. Path Planning of UAV based on Hierarchical Genetic Algorithm with Optimized Search Region // 2017 13th IEEE Intern. Conf. on Control & Automation (ICCA), Ohrid, 2017. P. 1033–1038. doi:10.1109/ICCA.2017.800320323

14. Schäfle T. R., Mohamed S., Uchiyama N., Sawodny O. Coverage Path Planning for Mobile Robots using Genetic Algorithm with Energy Optimization // 2016 International Electronics Symposium (IES), Denpasar, 2016. P. 99–104. doi:10.1109/ELECSYM.2016.7860983

15. Ming K. Solving Path Planning Problem based on Ant Colony Algorithm // 2017 29th Chinese Control and Decision Conference (CCDC), Chongqing, 2017. P. 5391–5395. doi:10.1109/CCDC.2017.7979455

16. Ватутин Э. И., Титов В. С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Изв. ЮФУ. Технические науки. 2014. № 12 (161). С. 111–120.

17. Мартынов А. В., Курейчик В. М. Гибридный алгоритм решения задачи коммивояжера//Изв. ЮФУ. Технические науки. 2015. № 4 (165). С. 36–44.

18. Zhang W., Gong X., Han G., Zhao Y. An Improved Ant Colony Algorithm for Path Planning in One Scenic Area With Many Spots // IEEE Access. 2017. Vol. 5. P. 13260–13269. doi:10.1109/ACCESS.2017.2723892

19. Uriol R., Moran A. Mobile Robot Path Planning in Complex Environments using Ant Colony Optimization Algorithm // 2017 3rd Intern. Conf. on Control, Automation and Robotics (ICCAR), Nagoya, 2017. P. 15–21. doi:10.1109/ICCAR.2017.7942653

20. Xiao S. Optimal Travel Path Planning and Real Time Forecast System based on Ant Colony Algorithm // 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conf. (IAEAC), Chongqing, 2017. P. 2223–2226. doi:10.1109/IAEAC.2017.8054413

21. Lin T., Zhang K., Cui N., Tu Z., Zhang H. Path Planning of Aircraft based on Adaptive Multiobjective Estimation of Distribution Algorithm // 2016 IEEE Symp. Series on Computational Intelligence (SSCI), Athens, 2016. P. 1–8. doi:10.1109/SSCI.2016.7850199

22. Tan J., Zhao L., Wang Y., Zhang Y., Li L. The 3D Path Planning based on A* Algorithm and Artificial Potential Field for the Rotary-Wing Flying Robot // 2016 8th Intern. Conf. on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2016. P. 551–556. doi:10.1109/IHMSC.2016.155

23. Song R., Liu W., Liu Y., Bucknall R. A Two-Layered Fast Marching Path Planning Algorithm for an Unmanned Surface Vehicle Operating in a Dynamic Environment // OCEANS 2015, Genova, Genoa, 2015. P. 1–8. doi:10.1109/OCEANS-Genova.2015.7271405

24. Chen H., Wang H., Jiang L. Path Planning of UAV based on Cultural Algorithm in Dynamic Environments // 2016 6th Intern. Conf. on Electronics Information and Emergency Communication (ICEIEC), Beijing, 2016. P. 130–134. doi:10.1109/ICEIEC.2016.7589704


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

Для цитирования: Моторин Д.Е., Попов С.Г. Алгоритм многокритериального поиска траекторий движения робота на многослойной карте. Информационно-управляющие системы. 2018;(3):45-53. https://doi.org/10.15217/issn1684-8853.2018.3.45

For citation: Motorin D.E., Popov S.G. Multi-Criteria Path Planning Algorithm for a Robot on a Multilayer Map. Information and Control Systems. 2018;(3):45-53. (In Russ.) https://doi.org/10.15217/issn1684-8853.2018.3.45

Просмотров: 115


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)