#algorithm #path-finding #d-star
#алгоритм #поиск пути #d-звезда
Вопрос:
Моя реализация A * хорошо работает для моей статической среды. Если бы я сейчас хотел работать с динамической средой, то есть определенные затраты между моими узлами изменяются, пока мы проходим от начала до конца.
Из прочитанного до сих пор я нашел алгоритмы LPA *, D * и D * Lite, которые могли бы мне помочь. Что ж, моим наихудшим сценарием было бы реализовать все и посмотреть, что работает лучше всего.
Проводится ли какое-либо исследование по сравнению возможностей этих алгоритмов?Статьи, которые я прочитал до сих пор, сосредоточены только на одном алгоритме за раз, и поскольку их экспериментальные среды различны, трудно провести сравнение.
** Некоторая справочная информация: я использую C , и моя среда представляет собой 3D-сцену с моим графиком поиска, представленным с помощью навигационных сеток.
Комментарии:
1. Смотрите cstheory.stackexchange.com/questions/11855
Ответ №1:
Возможно, эта статья могла бы вам помочь, Дорожные карты реактивной деформации: планирование движения нескольких роботов в динамических средах Рассел Гейл Авниш Суд Минг К. Лин Динеш Маноча; Аннотация звучит так:
Мы представляем новый алгоритм для планирования движения нескольких роботов среди динамических препятствий. Наш подход основан на новом представлении дорожной карты, которое использует деформируемые ссылки и динамически втягивается, чтобы обеспечить связность свободного пространства. Мы используем ньютоновскую физику и закон Гука, чтобы обновлять положение контрольных точек и деформировать связи в ответ на движение других роботов и препятствий. На основе этого представления дорожной карты мы описываем наши алгоритмы планирования, которые могут вычислять пути без столкновений для десятков роботов в сложных динамических средах.
Они представляют алгоритм, основанный на физических данных, адаптивное представление дорожной карты, которое убирает и изменяет свою топологию в зависимости от динамической среды. Iit может использоваться для планирования движения одного робота или нескольких роботов среди динамических препятствий.
Ответ №2:
Прошло некоторое время с тех пор, как вы задавали этот вопрос, так что, возможно, у вас уже было время попробовать их все… Но как бы то ни было, статья D *-Lite (http://www.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf в конце есть раздел «Экспериментальные результаты«, в котором сравнивается производительность с LPA *, D * и A *.