ANA*: anytime nonparametric A*

Abstract

Anytime variants of Dijkstra’s and A * shortest path algorithms quickly produce a suboptimal solution and then improve it over time. For example, ARA * introduces a weighting value (ε) to rapidly find an initial suboptimal path and then reduces ε to improve path quality over time. In ARA*, ε is based on a linear trajectory with ad-hoc parameters chosen by each user. We propose a new Anytime A * algorithm, Anytime Nonparametric A * (ANA*), that does not require ad-hoc parameters, and adaptively reduces ε to expand the most promising node per iteration, adapting the greediness of the search as path quality improves. We prove that each node expanded by ANA * provides an upper bound on the suboptimality of the current-best solution. We evaluate the performance of ANA * with experiments in the domains of robot motion planning, gridworld planning, and multiple sequence alignment. The results suggest that ANA * is as efficient as ARA * and in most cases: (1) ANA * finds an initial solution faster, (2) ANA * spends less time between solution improvements, (3) ANA * decreases the suboptimality bound of the current-best solution more gradually, and (4) ANA * finds the optimal solution faster. ANA * is freely available from Maxim Likhachev’s Search-based Planning Library (SBPL).