Info about Anytime Nonparametric A* (ANA*) Algorithm

Anytime Nonparametric A* (ANA*) Algorithm

  1. ANA*: Anytime Nonparametric A*. Jur van den Berg, Rajat Shah, Arthur Huang, and Ken Goldberg. Association for the Advancement of Artificial Intelligence: Annual Conference (AAAI). San Francisco, CA. August 2011.

  2. ANA* Technical Report. February 2011.

  3. Code (freely available with attribution) from Maxim Likhachev's Search-Based Planning Library (SBPL).

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
UC Berkeley
2011
{berg,rajatm.shah,arthurhuang,goldberg} @ berkeley.edu