Reusing cost-minimal paths for goal-directed navigation in partially known terrains

Abstract

Situated agents frequently need to solve search problems in partially known terrains in which the costs of the arcs of the search graphs can increase (but not decrease) when the agents observe new information. An example of such search problems is goal-directed navigation with the freespace assumption in partially known terrains, where agents repeatedly follow cost-minimal paths from their current locations to given goal locations. Incremental heuristic search is an approach for solving the resulting sequences of similar search problems potentially faster than with classical heuristic search, by reusing information from previous searches to speed up its current search. There are two classes of incremental heuristic search algorithms, namely those that make the h-values of the current search more informed (such as Adaptive A*) and those that reuse parts of the A* search trees of previous searches during the current search (such as D* Lite). In this article, we introduce Path-Adaptive A* and its generalization Tree-Adaptive A*. Both incremental heuristic search algorithms terminate their searches before they expand the goal state, namely when they expand a state that is on a provably cost-minimal path to the goal. Path-Adaptive A* stores a single cost-minimal path to the goal state (the reusable path), while Tree-Adaptive A* stores a set of cost-minimal paths to the goal state (the reusable tree), and is thus potentially more efficient than Path-Adaptive A* since it uses information from all previous searches and not just the last one. Tree-Adaptive A* is the first incremental heuristic search algorithm that combines the principles of both classes of incremental heuristic search algorithms. We demonstrate experimentally that both Path-Adaptive A* and Tree-Adaptive A* can be faster than Adaptive A* and D* Lite, two state-of-the-art incremental heuristic search algorithms for goal-directed navigation with the freespace assumption.