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