Нахождение пути: подробное описание для дилетанта алгоритма D *

Question

Большая сеть (типа графов маленьких миров), с которой я хочу иметь дело, имеет динамический характер, новые узлы добавляются и часто вычитаются. Предположительно использование D * над A * было бы лучшим способом обнаружения путей в этой динамической среде?

Насколько твердый D *? у него был какой-то опыт в реальном мире? как криптографический алгоритм - D * усилен многочисленными рецензиями и тестированием? Вы бы использовали D * для этой проблемы?

Answer 1

Как я понимаю, при первом запуске D * он находит тот же путь, что и A *, почти с тем же временем выполнения. Однако, когда узел меняет свое значение ребра или добавляются узлы, A * пересчитывает ВСЕ пути, в то время как D * просто пересчитывает несовместимые узлы во второй раз, а не в целом.

Алгоритм Энтони Стенца D * (оригинальный документ здесь ) в значительной степени устарел из-за его производных. D * Lite и LPA * наиболее часто встречаются и их гораздо проще кодировать / реализовывать.

Что касается опыта реального мира, Джозеф Карстен и Арт Ранкин из Лаборатории реактивного движения НАСА установили версию Field D * с использованием элементов D * Lite на марсоходах "Spirit" и "Opportunity" (показ слайдов с использованием D * здесь ). В феврале 2007 года он использовался для полной навигации марсохода автономно.

альтернативный текст http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg

Очевидно, D * действительно полезен в области робототехники, потому что встроенные датчики роботов постоянно пересматривают граничные значения. Это сделало бы это довольно "испытанным в бою" по моему собственному мнению.

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

Я закончу этот ответ, заявив, что я никогда не реализовывал D *, только A *. Из-за значительного увеличения сложности я бы сказал, что D * (или D * Lite) следует использовать только в тех случаях, когда на графике происходят значительные и частые изменения. Вы описали свою ситуацию как похожую на эту, поэтому я бы сказал, определенно перейти на D * Lite. Если НАСА использует его, вы можете спокойно поспорить, что оно было тщательно расследовано.

Answer 2

Я реализовал оба алгоритма D * и A *. Итак, я советую вам, если на вашей карте нет динамических препятствий, вы должны реализовать A *. Иначе, внедрите D *. По основной причине это: При первом поиске D * вычисляет все узлы на карте, затем показывает кратчайший путь, а A * вычисляет только ограниченную область вокруг цели и начальных точек на карте. Таким образом, это намного быстрее, чем D *. В динамической среде D * быстрее и эффективнее, чем A *. Поскольку на пути робота, если он обнаруживает новое препятствие, он обновляет только несколько узлов вокруг неожиданного препятствия. В то время как A * снова вычислит все.