On the Optimal Efficiency of Cost-Algebraic A

Robert C. Holte, Sandra Zilles

Abstract

A* is widely recognized as the optimal search algorithm for shortest-path problems. While its optimality extends to generalized "cost algebras," its efficiency—the guarantee of expanding the minimum number of nodes—is less certain in these settings. This paper re-evaluates the classic efficiency results established by Dechter and Pearl (1985), identifying a significant error in the original additive setting and exploring how these guarantees translate to non-additive cost structures.

Introduction

The A algorithm has long been the benchmark for finding optimal paths in graphs. In their seminal 1985 work, Dechter and Pearl identified five conditions (Results R1 through R5) under which A is "0-optimal," meaning no other algorithm in its class can find an optimal solution while expanding fewer nodes. However, modern applications often require "cost algebras" where path costs are not simply summed. For instance, in the widest path problem, the cost is the minimum capacity along the route. This paper investigates whether A* maintains its efficiency edge in these generalized mathematical structures.

Methods: Cost Algebras and DXBB Algorithms

The researchers define a cost algebra as a monoid with a total ordering and an "isotonic" operator. Isotonicity ensures that if path A is cheaper than path B, adding the same segment to both preserves their relative order. To evaluate A, the authors compare it against the class of DXBB algorithms* (Deterministic, Expansion-based, Black Box). These algorithms interact with the graph solely through node expansion, lacking any global "peek" at the structure.

The Fall of Result R3

One of the most striking findings is the discovery of a 34-year-old error. Result R3, which claimed A's optimal efficiency among algorithms using consistent heuristics, is shown to be false even in traditional additive settings. The authors introduce the GC1 algorithm as a counterexample. Unlike A, GC1 can "learn" and update heuristic values during the search process, allowing it to skip nodes that A* would be forced to expand.

Figure 3: A trace of the GC1 algorithm demonstrating how updating heuristic values allows it to outperform A*.

Generalizing Efficiency to Cost Algebras

The paper systematically tests R1-R5 in the context of cost algebras:

  • R1, R2, and R5 remain valid; A* is still optimally efficient under these conditions.
  • R4 fails in cost algebras. Unlike the continuous nature of real numbers, cost algebras can have "gaps" (discrete cost sets). These gaps allow competing algorithms to find shortcuts that A* misses due to its assumption of a more fluid cost landscape.
  • Strict Isotonicity: The authors show that Nilsson’s Result 6 (stronger heuristics lead to fewer expansions) only holds in cost algebras if isotonicity is strict—meaning adding a cost must strictly increase the total cost.

New Theoretical Foundations

To provide a more robust framework, the authors propose Theorem 8. This theorem defines the set of nodes that any DXBB algorithm "cost-dominating" A* must expand. It centers on the concept of "surely expanded" nodes—those whose estimated cost is strictly less than the optimal cost $C^*$.

Figure 4: Comparison of node expansion sets relative to the optimal cost C*.

Conclusion

This research refines our understanding of heuristic search. By correcting a long-standing error in the shortest-path literature and mapping the boundaries of efficiency in cost algebras, the authors pave the way for more advanced search algorithms. The success of heuristic-updating algorithms like GC1 suggests that the next generation of search techniques may move beyond the static heuristic approach of traditional A*.

Summary updated

Abstract

Edelkamp et al. (2005) proved that A*, given an admissible heuristic, is guaranteed to return an optimal solution in any cost algebra, not just in the traditional shortest path setting. In this paper, we investigate cost-algebraic A*’s optimal efficiency: in the cost-algebraic setting, under what conditions is A* guaranteed to expand the fewest possible states? In the traditional setting, this question was examined in detail by Dechter & Pearl (1985). They identified five different situations in which A* was optimally efficient. We show that three of them continue to hold in the cost-algebraic setting, but that one does not. We also show that one of them is false, it does not hold even in the traditional setting. We introduce an alternative that does hold in the cost-algebraic setting. Finally, we show that a well-known result due to Nilsson does not hold in the general cost-algebraic setting but does hold in a slightly less general setting.
BibTeX
@inproceedings{holte2019optimal,
  author = {Robert C. Holte and Sandra Zilles},
  title = {{On the Optimal Efficiency of Cost-Algebraic A}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012288},
}
Figure