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:
- Rapid Initial Solutions: In 6-DOF robot arm tests, ANA found an initial solution significantly faster than most ARA variants (0.016 seconds).
- 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.
- 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.
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