Какие существуют методы обхода графов в робототехнике?

Некоторые методы обхода графов, которые используются в робототехнике:

• Алгоритм двунаправленных графов. 3 Состоит из двух этапов: прокладки предварительного маршрута и корректировки. 3 На первом этапе строится кратчайшая линия, соединяющая начальную и конечную точки. 3 На втором этапе маршрут проверяется и, если нужно, корректируется с учётом информации о запрещённых точках. 3
• Алгоритм A*. 1 Позволяет определить наилучший маршрут от робота до цели по первому совпадению на графе. 1 В основе алгоритма лежит формула эвристики. 1
• Алгоритм Беллмана-Форда. 1 Помогает построить маршрут, если в графе есть рёбра с отрицательным весом. 1 Если в результате у конечного пути сумма весов рёбер принимает негативное значение, то он именуется отрицательным циклом. 1
• Алгоритм Джонсона. 1 Используется для определения всех кратчайших маршрутов от одной вершины до другой. 1 Метод можно применять для рёбер как с положительным, так и с отрицательным весом. 1
• Алгоритм Discretize Space. 1 Конфигурационное пространство разбивается на одинаковые квадраты, все ячейки внутри препятствий отмечаются как непроходимые. 1 Проходимые ячейки превращаются в узлы, каждый из которых соединяется со всеми соседними в графе. 1
• Рандомизированный поиск пути. 1 Суть метода в разбиении пространства на одинаковые квадраты, соединении всех ближайших вершин, переборе всех путей и их сортировке для поиска пути с наименьшей ценностью. 1