D* Lite
Инкрементальный поиск пути, который дёшево чинит маршрут при изменении карты, не начиная поиск заново.
Робот, исследующий незнакомую местность, узнаёт о препятствиях лишь добравшись до них. D* Lite ищет путь от цели назад и хранит стоимости дерева поиска: когда ребро внезапно дорожает — например, дверь оказалась закрыта, — обновляются только те вершины, у которых расстояние до цели действительно изменилось. Остальная прежняя работа переиспользуется, и это несравнимо быстрее, чем гонять A* заново при каждом сдвиге мира.
Свен Кёниг и Максим Лихачёв опубликовали алгоритм в 2002 году как более чистую переработку D* Энтони Стенца (1994) на основе своего Lifelong Planning A*. Его варианты водили настоящих полевых роботов; классический сценарий — агент, который планирует оптимистично и перепланирует, когда датчики противоречат карте.