Anytime Nonparametric A

Jur van den Berg, Rajat Shah, Arthur Huang, Kenneth Y. Goldberg

Abstract

In many real-world applications such as robotics and video games, path-planning algorithms must provide a solution quickly, even if it is suboptimal. While "Anytime" algorithms like Anytime Repairing A (ARA) address this by iteratively refining paths, they require manual tuning of heuristic weights ($\epsilon$), which can lead to inefficient performance if poorly chosen. This paper introduces ANA (Anytime Nonparametric A), a parameter-free anytime search algorithm. ANA adaptively adjusts its greediness based on the current search state, eliminating the need for manual parameter tuning and consistently outperforming ARA in both speed and solution quality.

Introduction

Standard A search guarantees optimality but can be prohibitively slow in large search spaces. Anytime algorithms mitigate this by finding an initial suboptimal solution rapidly and improving it as time allows. The industry-standard ARA uses a weight $\epsilon$ to inflate the heuristic, making the search greedier. However, the effectiveness of ARA is highly sensitive to the choice of initial $\epsilon$ and its subsequent reduction schedule. ANA was developed to solve this "parameter-tuning" headache by deriving the selection criterion directly from the search state.

Methodology: The Nonparametric Approach

ANA changes the fundamental way nodes are selected for expansion. Instead of minimizing a weighted sum $f(s) = g(s) + \epsilon \cdot h(s)$ with a fixed $\epsilon$, ANA considers the current best solution cost ($G$) and expands the node $s$ that maximizes:

$$e(s) = \frac{G - g(s)}{h(s)}$$

where $g(s)$ is the cost to reach node $s$ and $h(s)$ is the estimated cost to the goal. This formula represents the maximal possible greediness that could still yield a path better than the current best. By maximizing $e(s)$, the algorithm starts very greedy to find an initial solution and naturally becomes less greedy as $G$ decreases, refining the path over time.

Experimental Evaluation

The authors evaluated ANA against various ARA configurations across several domains, including robot arm planning (6-DOF and 20-DOF), large-scale gridworld planning, and multiple sequence alignment in bioinformatics.

Key Results

ANA demonstrated several advantages over ARA:

  1. Rapid Initial Solutions: In 6-DOF robot arm tests, ANA found an initial solution significantly faster than most ARA variants (0.016 seconds).
  2. Faster Convergence: ANA reached optimal solutions more quickly. For instance, in the 6-DOF uniform cost scenario, ANA found the optimum in 5 seconds, while a well-tuned ARA* variant took 36.8 seconds.
  3. Smoother Anytime Behavior: Unlike the "staircase" progress seen in ARA—where long plateaus are followed by jumps when $\epsilon$ is manually decreased—ANA exhibits a much smoother and more frequent improvement curve.
Solution cost over time for a 6DOF robot arm planning task (Uniform costs).
Solution cost over time for a 6DOF robot arm planning task (Non-uniform costs), illustrating the 'staircase' behavior of ARA* versus the smoother improvement of ANA*.

Discussion and Conclusion

By deriving its selection criterion from the current search state, ANA removes the trial-and-error phase of setting parameters. It is "maximally greedy" to improve the current solution and provides proven suboptimality bounds during execution. While it currently focuses on static environments, future work aims to extend ANA to dynamic domains where edge costs may change during search. Despite its reliance on a good heuristic, ANA* offers a more robust and user-friendly alternative to traditional anytime search algorithms.

Summary updated

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 "epsilon" to rapidly find an initial suboptimal path and then reduces "epsilon" to improve path quality over time. In ARA*, "epsilon" 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 varepsilon 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).
BibTeX
@inproceedings{berg2011anytime,
  author = {Jur van den Berg and Rajat Shah and Arthur Huang and Kenneth Y. Goldberg},
  title = {{Anytime Nonparametric A}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.1609/aaai.v25i1.7819},
}
Figure