D* Extra Lite: A dynamic A* with search-tree cutting and frontier-gap repairing - Przybylski, Maciej; Putz, Barbara (Zielona Góra: Uniwersytet Zielonogórski)
Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting.
Keywords: shortest-path planning; incremental heuristic search; mobile robot navigation; video games