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 series 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.