Я всегда увлекался робототехникой с ранних школьных лет. С появлением таких крупных компаний, как Google и Tesla, робототехника, созданная в виде самоуправляемых автомобилей, перестала быть фантастикой. Будучи студентом бакалавриата IIT Kharagpur, мне посчастливилось попасть в Группу по исследованию автономных наземных транспортных средств, что дало мне возможность познакомиться с понятием автоматизации. Летом на первом курсе я провел месяц, работая с team, во время которой мне довелось наткнуться на проблему планирования пути. Я опишу два простейших алгоритма на основе графов, которые могут достичь этой цели.

Код для этих планировщиков доступен здесь: (https://github.com/shreyas-kowshik/Planning)

Первый алгоритм, о котором мы поговорим, — это алгоритм Джикстры. Это один из самых популярных алгоритмов поиска графа, который используется для получения кратчайшего расстояния между двумя узлами в графе с положительными весами. Для наших целей , мы возьмем карту как 2D-изображение, где препятствия белого цвета. Каждый из наших узлов представляет собой пиксель на изображении, и он соединен со своими соседями ребрами, которые имеют веса, соответствующие их расстояниям. Наша формулировка проблемы : «Найти кратчайший путь между любыми двумя координатами карты такой, что он не пересекает никаких препятствий».

Алгоритм Джикстры

Алгоритм довольно понятен. Он просто выбирает следующий узел с минимальным расстоянием, исследует все возможности и находит наиболее оптимальный путь. Одна вещь, которую я не добавил выше, это инициализация расстояния всех узлов, кроме исходного, до бесконечность. Вотполученные результаты:

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

У Джикстры нет стимула на любом шагу идти к цели. Все, что он делает, это обновляет дистанции и родителей и движется дальше. В результате для любой проблемы планирования пути нас больше интересует цель, а не другие узлы, поэтому нам нужен алгоритм, который разумно определяет следующий шаг, чтобы достичь цели быстрее и оптимальным образом.

Алгоритм A*

Джикстра в некотором роде минимизировал функцию g = расстояние_от_источника. A* минимизирует другую функцию стоимости, заданную формулой: f = g + h. Здесь h называется эвристической функцией. Это может быть любая функция, призванная направлять путь к цели. Обычно за эвристику принимается евклидово расстояние от цели. Теперь наша проблема планирования та же самая, что и у Джикстры, только мы используем функцию f для нахождения соответствующих узлов на пути. A* намного более гибкий, чем Djikstra, в том смысле, что он более ориентирован на достижение наших целей, тогда как Djikstra носит более общий характер. A* завершает работу, как только достигает цели, в отличие от Djikstra, который продолжает повторяться во всем пространстве, даже если вы переходите от (1,1) к (2,2)!

Итак, здесь мы выиграли в скорости, значит, в чем-то мы проиграли, верно? Что мы потеряли, так это оптимальность. A* не всегда дает кратчайший путь. Однако есть приемы, позволяющие контролировать компромисс между затратами времени и затратами. Если вы внимательно заметите, что A* — это сумма двух алгоритмов… Первый — это Djikstra, а второй — жадный алгоритм под названием Best First Search, который жадно выбирает следующий узел, ближайший к родителю. Управляя относительными количествами g и h, мы можем сделать A* как можно более близким к джикстре или как можно более жадным.

На самом деле, установив h = константу и удалив условие достижения жадной цели, вы увидите, что A * преобразуется в Djikstra.

Именно из-за врожденного интеллекта A* нашел применение для планирования пути в играх и даже в беспилотных автомобилях (в форме Hybrid A*).

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

Репозиторий кода https://github.com/shreyas-kowshik/Planning