Moving target D^* Lite^*

Incremental search algorithms, such as Generalized Fringe-Retrieving A ^* and D^* Lite, reuse search trees from previous searches to speed up the current search and thus often find cost-minimal paths for scries of similar search problems faster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D^* Lite is slow on moving target search problems, where both the start and goal states can change over time. In this paper, we therefore introduce Moving Target D ^* Lite, an extension of D^* Lite that uses the principle behind Generalized Fringe-Retrieving A^* to repeatedly calculate a cost-minimal path from the hunter to the target in environments whose blockages can change over time. We demonstrate experimentally that Moving Target D^* Lite is four to five times faster than Generalized Adaptive A^*, which so far was believed to be the fastest incremental search algorithm for solving moving target search problems in dynamic environments.