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

Обзор алгоритмов 
– Комбинаторный подход, оптимальные алгоритмы. Поиск в ширину. Данный алгоритм, по 
сути, представляет собой перебор всех возможных путей на графе. При этом выполняется 
переход от одной ячейки графа к следующей равномерно во всех направлениях. Таким 
образом, одинаково исследуются все возможные пути, и не учитывается положение цели в 
пространстве. 

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
155 
При этом для каждой новой исследуемой ячейки записывается число, равное 
количеству шагов от стартовой ячейки. При исследовании всех ячеек сетки и достижении 
цели строится
кратчайший маршрут. Таким образом, алгоритм гарантирует нахождение 
оптимального решения: кратчайшего пути между точками. 
– Алгоритм Дейкстры. Когда пространство представлено взвешенным графом, с целью 
нахождения оптимального пути, применяется алгоритм Дейкстры. 
В рамках данного алгоритма происходит поочередное оценивание стоимости 
перемещения из каждой ячейки по всем доступным направлениям, и вводится приоритет 
исследования: в первую очередь переход осуществляется в ячейки, стоимость перемещения в 
которые меньше. 
– Алгоритмы с использованием эвристики. В условиях большого количества элементов 
сетки, с целью быстрого нахождения кратчайшего пути, необходимо введение эвристики. 
Алгоритмы с использованием эвристики подразумевают введение априорных знаний или 
допущений с целью оптимизации порядка перебора при исследовании новых путей и 
улучшения алгоритма. Таким образом, можно заметно ускорить нахождение пути. 
– Жадный поиск. Примером эвристического алгоритма может послужить «жадный» поиск. 
В жадном поиске для присвоения приоритета исследования используется оцененное 
расстояние до цели. Ячейка, наиболее близкая к цели, будет исследована первой [2]. При 
этом при оценивании расстояния препятствия не учитываются. Таким образом, поиск идет 
в перспективном направлении. Однако, так как при оценивании расстояния не 
учитываются расположение и вид препятствий, в определенных условиях, например, при 
наличии сложного препятствия, кратчайший маршрут может быть не найден. 
– Sample-based (вероятностный) подход. Эффективность комбинаторного подхода имеет 
место при условии небольшой размерности пространства поиска. Когда рассматривается 
объект с множеством степеней свободы, например, манипулятор или имитатор движения 
объекта, полное разбиение пространства поиска на элементы графа нецелесообразно и 
неэффективно. В таком случае необходимо использовать алгоритмы вероятностного 
подхода. 
– PRM (Probabilistic Roadmap)-алгоритм. Основной идеей метода является вероятностное 
построение карты местности и последующий поиск пути с ее использованием. Карта 
местности представляет собой ненаправленный граф, вершинами которого являются 
свободные от пересечений положения робота, а ребрами – свободные пути между этими 
положениями (рисунок) [3]. 
 
Рисунок. Построение графа с помощью PRM-алгоритма 
Вершины графа генерируются случайным образом. Анализируется допустимость их 
соединения и наличие пересечений с препятствиями. На сгенерированном случайным 
образом графе ищется путь с помощью комбинаторного подхода. 
– RRT/RRT-Connect алгоритмы. Метод базируется на идее последовательного исследования 
конфигурационного пространства путем построения древовидного графа, имеющего старт 
в известной начальной конфигурации [4]. Пространство исследуется путем присоединения 
к ветвям дерева новых вершин в направлениях. Таким образом, генерация новых вершин 
происходит в еще неисследованных областях [3]. 

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
156 
– RRT-Connect. В процессе выполнения данного алгоритма строится не одно дерево, а два – 
из начальной и конечной конфигурации. Эти два дерева исследуют пространство 
навстречу друг другу, что повышает эффективность работы метода [5].