A—An Efficient Near Admissible Heuristic Search

IJCAI 1983

TL;DR

This paper introduces AE, a novel heuristic search algorithm that sacrifices strict optimality for significant gains in computational efficiency. By allowing solutions within a tunable factor of the optimal cost, AE avoids much of the exhaustive search and backtracking inherent in traditional A* search, making it more practical for complex real-world problems.

What Problem Does This Paper Address?

Heuristic search algorithms, like the well-known A, are fundamental to solving problems where we need to find a path from a start state to a goal state. A guarantees finding the optimal path (the one with the absolute lowest cost). However, this guarantee comes at a steep price: A can be computationally very expensive, often requiring an exponential number of steps in the worst case. This is because A can get bogged down exploring many "almost optimal" paths, leading to extensive backtracking. Furthermore, A* doesn't explicitly consider the cost of the search itself, only the cost of the path found. In many practical scenarios, a "good enough" solution found quickly is far more valuable than a perfect solution found too late or at an prohibitive computational cost. This paper addresses this trade-off, aiming to create a more efficient search algorithm that can still provide near-optimal solutions.

Methods

The core innovation is the AE algorithm, a generalization of A*. Instead of aiming for strict optimality, AE seeks a solution path whose cost is within a factor of $(1+\epsilon)$ of the optimal cost, where $\epsilon$ is a user-defined parameter. This allows AE to be more selective about which paths it explores.

Key features of AE include:

  • Near-Admissible Heuristics: AE allows for a bounded loss of optimality, meaning its heuristic estimates don't need to be perfectly accurate (admissible) to guarantee a near-optimal solution.
  • "Acceptable" Nodes: AE prioritizes exploring "acceptable" nodes, which are those whose estimated cost $f(n)$ is below a dynamically adjusted threshold, $\epsilon_{threshold}$. This threshold is initially set based on the estimated cost of the goal and is updated as the search progresses.
  • Perserverant Strategy: When the current path doesn't yield an "acceptable" successor, AE employs an inner loop. This "perserverant strategy" attempts to make successors acceptable by expanding the current frontier node multiple times. This is crucial for avoiding premature backtracking and for potentially improving the estimated cost of promising paths.
  • Selective Backtracking: AE uses a SelectOPEN function to choose which node to backtrack to from the set of open nodes, considering both the estimated path cost $f(n)$ and an explicit guess of the computational cost to reach a goal $h_c(n)$.

AE differs from the related algorithm A$_{\epsilon}^*$ (Pearl and Kim, 1982) by incorporating a depth-oriented search preference and the perserverant strategy, which helps avoid unnecessary backtracking.

Datasets

The paper evaluates AE on the Traveling Salesman Problem (TSP). They used test conditions with 9 cities randomly distributed in a unit square, employing the same heuristics ($h$ and $h_c$) as used in Pearl and Kim's work. Tests were conducted on sixty different distributions of cities. They also tested AE on "difficult problems" where intercity distances were confined to a narrow interval (0.75, 1.25).

Key Insights and Ideas

  • The "Good Enough" Principle: The fundamental insight is that for many real-world problems, a solution that is "good enough" (within a reasonable factor of optimal) is often sufficient and vastly more computationally tractable than a strictly optimal solution.
  • Efficiency Through Selectivity: By relaxing the strict optimality constraint, AE can be much more selective about which nodes to expand, leading to significantly reduced search space exploration and backtracking.
  • The Value of Perserverance: The perserverant strategy is key to AE's efficiency. It allows the algorithm to "stick with" a promising path and try to make its successors acceptable, rather than immediately abandoning it and backtracking.
  • Tuning for Performance: The $\epsilon$ parameter provides a crucial knob for users to tune the trade-off between solution quality and search efficiency, allowing them to adapt the algorithm to specific application needs.

Key Results

  • Significant Speedup: AE demonstrated a dramatic reduction in computational cost compared to A* (represented by $\epsilon=0$). As $\epsilon$ increased, the computational cost (measured by nodes expanded, generated, and backtracks) decreased rapidly, moving from exponential complexity towards linear complexity.
  • Near-Optimal Solutions: Despite the efficiency gains, the actual costs of the solutions found by AE remained remarkably close to optimal. For instance, with $\epsilon=\infty$, the solution was guaranteed to be within 27% of optimal.
  • Favorable Comparison: AE's performance, particularly in terms of computational effort, compared favorably to the related algorithm A$_{\epsilon}^*$ from Pearl and Kim (1982).

Limitations and Future Work

  • Heuristic Dependence: While AE is more robust to less precise heuristics than A*, the performance of SelectOPEN still relies on the quality of both the path cost estimator $f(n)$ and the computational cost estimator $h_c(n)$.
  • Parameter Tuning: Determining the optimal weights for $f(n)$ and $h_c(n)$ in SelectOPEN, as well as the best value for $\epsilon$, might require experimentation for specific problem domains.
  • Future Work: The authors suggest further testing on TSP and other search problems to experiment with the search strategies discussed in section II. They also note that for specific problem classes (e.g., monotone heuristics), some conditions within the perserverant strategy might become less useful.

Summary updated

BibTeX
@inproceedings{1983aan,
  title = {{A—An Efficient Near Admissible Heuristic Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure