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