PaperlayerView exact revision on arXiv

Source-linked AI summary

Anytime Heuristic Search

E. A. Hansen, R. Zhou

arXiv:1110.2737v1cs.AI

TL;DR

A* can take too long to find optimal solutions, motivating a method that trades solution quality against time when computation is limited or uncertain. The paper continues weighted search after an initial approximate solution, improving solutions and bounds until optimality; experiments find the approach effective across search problems, with performance depending on weight selection.

  • Problem

    A* may take too long to find an optimal solution, while a quickly found approximate solution can be more useful under limited or uncertain computation time.

  • Method

    The paper transforms Weighted A* into an anytime algorithm by continuing weighted search after the first solution, using improved solutions as bounds, and also applies the strategy to RBFS.

  • Results

    Anytime WA* is effective across a wide range of search problems and often finds an optimal solution relatively quickly, then spends most of its time proving optimality.

  • Takeaways & Limitations

    With an appropriate weight, anytime heuristic search can provide attractive anytime behavior without significantly delaying convergence to a provably optimal solution.

  • Takeaways & Limitations

    Performance depends on the initial weight, and decreasing the weight can help in some settings while adding overhead or causing more node reexpansions in others.

Abstract

from arXiv · show

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.

1. Introduction

The paper extends weighted heuristic search beyond stopping at the first solution, producing improving solutions and eventual optimality under uncertain time constraints. It presents the approach as broadly applicable and illustrates it with A* and RBFS.

  • Weighted heuristic search traditionally stops after finding its first solution, emphasizing the initial tradeoff between search time and solution quality.
  • Continuing a non-admissible search yields a sequence of improved solutions that eventually converges to an optimal solution.
  • The paper evaluates this anytime-search strategy analytically and empirically, including transformations of weighted heuristic search and RBFS.
  • Anytime algorithms suit varying or uncertain time constraints because solution quality improves with additional computation time.

2. Anytime A*

A* systematically expands graph nodes using heuristic evaluations to seek a minimum-cost path. Admissibility supports optimality, while inconsistency can require reopening and reexpanding nodes.

  • A* manages systematic graph search with Open and Closed lists, expanding the most promising node toward a minimum-cost path.
  • The evaluation function f(n) = g(n) + h(n) combines known path cost with a heuristic estimate of remaining cost.
  • With an admissible heuristic and expansion in f-order, the first selected goal node is guaranteed to be optimal.
  • Consistency guarantees optimal g-costs at expansion and prevents repeated expansions, whereas inconsistency can require reopening nodes and propagating improved costs.

2.2 Weighted A*

Weighted A* modifies A* by multiplying the heuristic by a user-selected weight, usually finding solutions faster while permitting bounded suboptimality. Variants alter weighting or node-selection criteria.

  • Weighted A* uses f′(n) = g(n) + w × h(n), with user-selected weight w ≥1.0, to favor faster approximate search.
  • When w > 1.0, the search is non-admissible, so its first solution may be suboptimal but is usually found much faster.
  • For admissible h(n), the weighted solution cost is bounded by a factor of w relative to the optimal cost.
  • Dynamic weighting changes the weight with search depth, while other variants restrict expansion to nodes preserving ε-admissibility before applying additional selection criteria.

2.3 Anytime Weighted A*

Anytime Weighted A* guides expansion with a non-admissible evaluation, continues after finding a solution, and uses admissible bounds to prune search and certify optimality. It progressively improves both solutions and suboptimality bounds.

  • 2.3 Anytime Weighted A*: The transformation makes Weighted A* anytime by using a non-admissible evaluation to find good solutions quickly, continuing search, and pruning with admissible lower bounds.
  • 2.3 Anytime Weighted A*: Improved incumbent solutions provide upper bounds, allowing nodes whose admissible f-cost cannot improve the incumbent to be excluded from Open.
  • 2.3 Anytime Weighted A*: Anytime WA* reports the incumbent solution and an error bound based on the incumbent cost and the least f-cost among open nodes.
  • 2.3 Anytime Weighted A*: Anytime WA* expands more nodes than A* before optimal convergence because weighting can expand more distinct nodes and cause reexpansions after improved paths are found.
  • 2.3.1 Convergence: The algorithm terminates with an optimal final solution, provided a solution exists and h(n) ≥0 for all nodes.
  • 2.3.2 Error bound: The upper and lower bounds approach one another as search progresses, and their difference bounds the current solution's suboptimality before convergence.

2.4 Performance and evaluation

Anytime WA* uses weighted heuristic search to find solutions quickly, then continues searching to improve solutions and bounds toward optimality. Across sliding-tile puzzles, STRIPS planning, and multiple sequence alignment, its effectiveness depends on the weight and problem characteristics, while improved upper bounds can reduce memory use.

  • Sliding-tile puzzles: A weight of 1.3 gives the best overall Eight Puzzle performance among the three tested weights, although no profile dominates at every running time.With weights of 1.3 or 1.5, Anytime WA* also stores fewer nodes than unweighted A*; the increase in expansions at weight 1.3 is slight.
  • Method: Anytime WA* continues weighted search after its first solution, producing improved upper bounds that prune suboptimal nodes from the Open list.This reduces memory requirements while preserving eventual convergence to an optimal solution.
  • Multiple sequence alignment: Anytime WA* runs more than seven times faster than PEA* with cutoff C = 0 while storing about the same number of nodes in multiple-sequence alignment.Against PEA* with C = 50, it stores 44% fewer nodes and runs 65% faster; Enhanced A* runs about as fast but stores 36% more nodes.
  • Multiple sequence alignment: In the alignment experiment, Anytime WA* finds an optimal solution after 10% of total search time and spends the remaining 90% proving optimality.Its gradually converging bounds provide a tradeoff between solution quality and computation time when optimal alignment is otherwise infeasible.
  • Discussion: Across experiments, an appropriate weight can let Anytime WA* converge to optimality using less memory and even less time than A*, despite expanding more nodes.Lower weights favored fast convergence in these experiments, whereas higher weights generally find approximate solutions sooner but require more expansions before convergence.

3. Anytime RBFS

The paper transforms RBFS into an anytime algorithm by using weighted evaluation and continuing after each solution to improve solutions and prove optimality. The proposed WRBFS variant improves the time-quality tradeoff and converges faster than the original weighted-RBFS approach on Fifteen Puzzle instances.

  • 3.1 Recursive Best-First Search (RBFS): RBFS reduces memory to O(db) by using stack-based backtracking instead of storing an Open list.The stack stores the current path and each node’s siblings, where d is search depth and b is branching factor.
  • 3.2 Weighted RBFS: WRBFS expands nodes on the stack frontier in best-first order using a weighted evaluation function, unlike the original approach’s virtual-frontier ordering.The paper introduces WRBFS for this alternative weighted-RBFS scheme and distinguishes stack and virtual frontiers.
  • 3.2 Weighted RBFS: WRBFS avoids weight-dependent iteration counts because its stored values use minimum unweighted f-cost rather than minimum weighted f′-cost.This produces a smoother time-quality tradeoff as the weight changes, whereas distinct f′-costs can increase iterations and node regeneration.
  • 3.3 Anytime Weighted RBFS: Anytime Weighted RBFS saves each initial or improved solution, continues searching, and uses bounds to test convergence to optimality.Goal nodes are checked when generated, and nodes whose f-cost reaches the incumbent upper bound can be pruned.
  • 3.3 Anytime Weighted RBFS: WRBFS’s weighted heuristic can reduce recursive calls by delaying and reducing backtracking, although sufficiently large weights eventually increase distinct expansions and recursive calls.On the Fifteen Puzzle, weights from 1.2 to 1.4 converge faster than unweighted RBFS, while larger weights can reverse the efficiency gain.
  • 3.3 Anytime Weighted RBFS: Anytime WRBFS converges much faster than the original Anytime Weighted RBFS because it backtracks more efficiently and improves the lower bound on optimal solution cost more effectively.The lower bound is the minimum F(n) value stored on the stack frontier; convergence occurs when it meets the upper bound.

4. Related Work

The section compares AWA* and ARA*, focusing on ARA*'s weight-decrease and node-reexpansion strategies. Their relative performance varies across search problems, and limiting reexpansions can sometimes worsen performance.

  • Anytime Repairing A*: ARA* combines decreasing weights with a repairing technique that limits node reexpansions, whereas AWA* can use decreasing weights without that technique.The comparison implementation also adds upper bounds to reduce ARA*'s Open list for fairness.
  • Anytime Repairing A*: For eight planning problems with initial weight 2.0 and decrements of 0.1, decreasing the weight generally did not improve performance over fixed-weight AWA*.The exceptions were Logistics-6, Freecell-3, and Psr-46.
  • Anytime Repairing A*: ARA* performed about the same as AWA* on five planning problems but worse on Logistics-6, Freecell-3, and Psr-46, independently of decreasing the weight.The comparison used matching initial weights and weight-decrease schedules.
  • Anytime Repairing A*: Limiting node reexpansions can cause more distinct-node expansions by blocking improvements to paths through nodes in the INCONS list.This effect appears mainly in problems with relatively sparse solutions, including sliding-tile puzzles and some planning domains.
  • Anytime Repairing A*: Weight 3 made ARA* expand about 4.5 times more nodes than AWA* and take 7 times longer on the Eight Puzzle.The CPU-time difference exceeded the node-expansion difference because decreasing the weight adds f′-cost recalculation and Open-list reordering overhead.
  • Anytime Repairing A*: The authors caution that limiting reexpansions can cause significantly more reexpansions or distinct-node expansions, though it may help problems with many close-to-optimal solutions.They also note that performance depends on the initial weight, so results do not establish one approach as best for all problems.

5. Conclusion

The paper presents a simple anytime transformation that begins with a fast, possibly suboptimal weighted-search solution and continues toward provable optimality. Its applicability depends on weighted heuristic search being effective, with performance shaped by the chosen weight and problem characteristics.

  • 5. Conclusion: Anytime heuristic search converts weighted heuristic search into a sequence of improving solutions while bounding the current solution's suboptimality.The search continues until convergence to a provably optimal solution.
  • 5. Conclusion: The approach is applicable to best-first algorithms such as RBFS and to search problems where weighted search finds suboptimal solutions quickly but optimal search takes much longer.The paper characterizes the approach as useful when available solution time is limited or uncertain.
Loading 1110.2737v1…