Где я могу найти информацию об алгоритме поиска пути D * или D * Lite?

Ответ 1

В Википедии есть статья по теме: http://en.wikipedia.org/wiki/D*

Также реализация D * Lite в C доступна на странице Sven Koenig: http://idm-lab.org/code/dstarlite.tar Однако я считаю, что непробиваемая математика гораздо легче читать чем исходный код C; -)

Другая реализация D * Lite (на С++) доступна здесь: http://code.google.com/p/dstarlite/

Ответ 2

Ну, если псевдокод вам сложно (вам не нужно читать теоремы и доказательства - псевдокод довольно прямолинейный, если вы знаете стандартные алгоритмы), и вы жалуетесь на опубликованный код C и С++, тогда я думаю, вы будете нужно делать что-то еще: -)

Серьезно, не ожидайте, что кто-то может научить вас алгоритму высшего класса в нескольких параграфах веб-сайта. Возьмите ручку и бумагу и напишите, рисуйте и следуйте на бумаге, что происходит. Возможно, вам придется прочитать что-то дважды и google одну или две ссылки, чтобы познакомиться с несколькими концепциями вокруг него, и нет необходимости копаться в теоремах и доказательствах вообще - если вы не хотите доказать, что автор ошибается:-) )

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

Ответ 3

Сказав это, почему бы не добавить еще несколько документов, да, у них тоже есть математика:-), но я постараюсь получить несколько новых материалов. Люди обычно лучше разбираются в своей работе с течением времени, поэтому основное внимание уделяется Stentz, Likhachev и Koenig

• Stentz, 2007 - Поле D * - утверждает, что лучше, чем D * Lite: -)
• Stentz, 2010 - Имитация Lerning - в основном говорят о объединении полей D * и LEARCH
• Ratliff, 2009 - LEARCH - также говорит о объединении с полем D * - да циклический ref: -)
• Лихачев, 2005 - В любое время D * - вместе со Stentz
• Yanyan, 2009 - BDD-Dynamic A *
• Koenig, 2008 - Сравнение в реальном времени и инкрементный эвристический поиск

Ответ 4

D * Lite Объяснение для Layperson

D * начинается с вороньи, идеалистического пути между Start и Goal; он обрабатывает препятствия только тогда, когда и когда он сталкивается с ними (обычно, перемещаясь в соседний node). То есть - D * Lite не знает никаких препятствий, пока не начнет двигаться по этому идеальному пути.

Священный Грааль с любой реализацией пути должен быстро сделать, получив кратчайший путь или, по крайней мере, достойный путь (а также обработать [все ваши особые особые условия здесь - для D * Lite это имеет дело с неизвестным карта, как может сделать Марс-Ровер]).

Таким образом, одна из больших проблем D * Lite - это адаптация к препятствиям дешево по мере их достижения. Найти их легко - вы просто проверяете статус соседей во время переезда node. Но как мы адаптируем существующие оценки стоимости карты, не проходя через каждый node..., который может быть очень дорогостоящим?

LPA * использует умный трюк для адаптации затрат, трюк D * Lite хорошо подходит. Нынешний node спрашивает своих соседей: вы знаете меня лучше всего, думаете ли вы, что я реалист о себе? В частности, он запрашивает это значение g, которое является известной стоимостью получения от начального node до себя, то есть текущего node. Соседи смотрят на свои собственные g, посмотрите, где находится текущий node, и затем предложите оценку того, что, по их мнению, будет стоить. Минимальное количество этих предложений устанавливается как текущее значение node rhs, которое затем используется для обновления его значения g; при оценке соседи учитывают вновь открытые препятствия (или свободные пространства), так что при текущих обновлениях g с использованием rhs он делает это с учетом новых препятствий (или свободных пространств).

И как только мы получим реалистичные значения g по всей доске, конечно, появится новый самый короткий путь.

Ответ 5

Я придумал это http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf и это
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf

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