Подходы к алгоритму динамического поиска пути

Question

Моя реализация A * хорошо работает для моей статической среды. Если я теперь хочу работать с динамической средой, то есть определенные затраты между моими узлами изменяются, пока мы переходим от начала к концу.

Из моего прочтения я нашел алгоритм LPA *, D * и D * Lite, который мог бы помочь мне. Ну, мой худший сценарий - реализовать все и посмотреть, что работает лучше всего.

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

** Некоторая справочная информация: я использую C ++, и моя среда представляет собой трехмерную сцену с моим графом поиска, представленным с помощью навигационных сеток.

Answer 1

Может быть эта статья может помочь вам, Схемы реактивной деформации: планирование движения нескольких роботов в динамических средах от Рассел Гейл Авниш Суд Минг С. Лин Динеш Маноча ;Аннотация выглядит следующим образом:

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

Они представляют алгоритм, который является физически-основанным, адаптивным представлением дорожной карты, котороевтягивает и изменяет свою топологию как функцию динамической среды.Его можно использовать для планирования движения одного робота или нескольких роботов среди динамических препятствий .

Answer 2

Прошло некоторое время с тех пор, как вы спросили, так что, может быть, у вас уже было время попробовать их все ... Но что стоит, статья D * -Lite (http://www.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf) имеет раздел в конце, Экспериментальные результаты , сравнение производительности с LPA *, D * и A *.