Санкт-Петербург

УДК 681.5.011 
ОБЗОР МЕТОДОВ ПЛАНИРОВАНИЯ МАРШРУТА В ЗАДАЧАХ НАВИГАЦИИ 
Лысенко Д.П. 
Научный руководитель – к.т.н., доцент Золотаревич В.П. 
В работе выполнен обзор существующих алгоритмов планирования маршрута и траекторного 
управления для мобильных робототехнических устройств. Рассмотрены различные подходы к 
решению задачи планирования, выявлены их эффективность, достоинства и недостатки. 
Ключевые слова: планирование маршрута, построение траектории, эвристические алгоритмы, 
комбинаторный подход, оптимальные алгоритмы. 
Планирование маршрута – одна из основных задач навигации. В данной работе задача 
планирования маршрута и способы ее решения рассмотрены применительно к мобильным 
робототехническим устройствам. 
Задача планирования маршрута в робототехнике заключается в нахождении 
оптимального в том или ином смысле (или близкого к нему) пути из начального положения в 
конечное для сложных тел в некотором пространстве. При этом критерием оптимальности 
обычно выступает затраченное время, пройденное расстояние или же потраченное топливо. 
Карта, местоположение препятствий, робота и конечной точки считаются известными. 
При решении задачи планирования траектории карта обычно представляется в виде 
конфигурационного пространства, называемого также пространством поиска. Точка 
соответствует конкретному положению робота, а линии, связывающие эти точки, – путям из 
одного положения в другое. Для упрощения задачи реализовывать все последующие 
алгоритмы целесообразно именно в конфигурационном пространстве [1]. Обычно для 
представления такого пространства и осуществления в нем поиска маршрута используется 
направленный граф. Комбинаторный подход подразумевает, что граф представляет собой 
совокупность всех возможных положений объекта в пространстве, т.е. все пространство 
разбивается на координатную сетку. В рамках вероятностного подхода граф лишь частично 
покрывает пространство поиска, но достаточно для нахождения маршрута между заданными 
точками. Причем вершины графа генерируются случайным образом. 
В настоящей работе приведен обзор существующих на сегодняшний день алгоритмов 
планирования для двух точек, и обсуждаются достоинства и недостатки каждого из них. При 
этом были рассмотрены основные алгоритмы вероятностного (в том числе наиболее 
эффективный RRT-Connect алгоритм) и комбинаторного подходов.