Тема: Построение множества непересекающихся маршрутов для автономных агентов на основе диаграммы Вороного

В настоящее время все чаще возникает необходимость в алгоритмах построения маршрутов. Данные алгоритмы могут использоваться в раз­личных сферах. Например, в автопилотировании дорожных транспортных средств, в алгоритмах, обеспечивающих работу роботов манипуляторов на производствах или же в сфере компьютерных игр, для создания естествен­ного окружения, создающегося за счет реалистичного движения персона­жей. В данной работе будет рассмотрен алгоритм построения маршрутов для беспилотных летательных аппаратов.
Основная сложность этой задачи заключается в том, что необходимо прокладывать маршрут между точками в пространстве(в конкретном слу­чае на плоскости), обладающий определенными свойствами. Свойства эти представляют собой физические и технические ограничения, такие как ра­диус поворота, минимальное расстояние между точками изменения тра­ектории. К тому же в реализации конкретной задачи была важна высокая точность итогового результата построения, вследствие чего приходилось прибегать к геометрическим изысканиям.
Итоговые свойства изделия, которые должен учитывать алгоритм:
1. Изменяемая эллипсовидная навигационная ошибка аппарата.
2. Ненулевой радиус разворота аппарата.
3. Множественный запуск аппаратов и условие не пересечения их марш­рутов.
4. Оптимальность с точки либо пройденного расстояния, либо с точки зрения свободного пространства вокруг аппарата, движущегося по построенному маршруту.
Для решения задачи построения маршрута с учетом всех этих свойств бы­ли рассмотрены различные алгоритмы[1], но за основу была взята диа­грамма Вороного и стандартный алгоритм воронки, который был перера­ботан для решения всех поставленных задач.
Так же стоит сказать, что поскольку в некоторых случаях предполага­лось запускать данный алгоритм на системе QNX, было принято решение о разработке алгоритма, не использующего ни какие фреймворки постро­ения маршрутов, так как в дальнейшем это могло привести к невозможно­сти запуска итогового программного обеспечения на некоторых платфор­мах.
Проведем обзор известных методов построения маршрутов, и разбе­ремся, почему были выбраны конкретные методы.
Купить

В процессе выполнения данной работы были изучены методы постро­ения маршрутов. Были выбраны конкретные методы для дальнейшей ре­ализации и реализованы на языке программирования C++. Написанный код применяется в рабочем программном обеспечении компании Радар ММС в нескольких проектах связанных с навигацией.
Правильная работа алгоритма, приведенного в данном тексте показы­вает правильность выбора метода решения поставленных задач. Действи­тельно подход в основе которого лежит диаграмма Вороного позволили обеспечить взаимодействие между маршрутами на таком уровне, что ста­ла возможна их параллельное построение с оптимальностью коридоров и длин всех маршрутов в построении. Дальнейшее направление работы ви­дится в усилении качества этого взаимодействия, потому что при тесном построении маршрутов сейчас маршруты все же иногда могут вести себя не так, как кажется оптимально.
Купить