Anytime Nonparametric A* (ANA*) Algorithm
Anytime variants quickly produce a suboptimal solution and then improve it over time. For example, ARA* introduces a weighting value (e) to rapidly find an initial suboptimal path and then reduces e to improve path quality over time. In ARA*, e 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 e 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 Likhachevs Search-Based Planning Library (SBPL) (above).
Contact:
Jur van den Berg, Rajat Shah, Arthur Huang, Ken Goldberg
|