Is a solution available immediately?

Not necessarily. There may be an initial search period before the first feasible solution is found.

Must every extra second lower the solution cost?

No. Improvement can be uneven, and additional work may only strengthen a bound.

Is the first solution necessarily optimal?

No. The method is designed to retain and improve an early solution when appropriate.

AI Glossary / Graphs and symbolic AI / Advanced

Anytime A*

Definition

Anytime A* is a form of heuristic search that retains a solution once one is found and continues searching for better solutions when more computation time is available. It extends the A* family to support a tradeoff between search time and solution quality. Under the relevant assumptions, continued search can eventually establish an optimal solution.

What it means

Ordinary optimal search may spend substantial time before returning its first result. In some applications, a feasible route or plan now is more useful than waiting indefinitely for the best one.

Anytime A* keeps the best complete solution found so far, called the incumbent. The search can return that solution if interrupted, while extra time may produce improvements or strengthen a bound on how far the incumbent could be from optimal.

There can still be an initial period before any solution is found. Anytime does not mean a valid solution exists at the first instant of execution, nor does it imply that every additional second improves the answer.

How it works

Hansen and Zhou describe an approach that uses an aggressive evaluation function to select promising search nodes, continues after finding a solution, and retains an admissible lower-bound function for pruning and convergence checks.

A weighted version selects nodes using g + w h, where g is the cost already incurred, h estimates the remaining cost, and w is at least one. Weighting can encourage early solutions, but the weighted score should not be mistaken for a guaranteed lower bound.

The unweighted admissible estimate g + h plays a separate role. Branches whose lower bound cannot improve the incumbent can be excluded. When no remaining branch can beat the incumbent, optimality can be established under the algorithm's assumptions.

The precise guarantees depend on correct duplicate handling, admissibility, the graph and cost assumptions, and sufficient resources. The published convergence analysis assumes finite branching, a positive lower bound on edge costs, nonnegative admissible heuristics, and the existence of a solution. Different anytime A* variants need their own guarantee checks.

Three practical examples

1. A routing prototype returns its current feasible route at a deadline while preserving an explicit statement that a cheaper route may still exist.

2. A planning application uses extra idle computation to improve a previously found action sequence before execution begins.

3. A search experiment records both incumbent cost and a valid lower bound, showing whether more time improved the plan, improved the certificate, or neither.

Think of it this way

Think of a researcher who finds a workable travel itinerary and keeps it on the desk while checking alternatives. There is always a known option to return after that first discovery, and better discoveries replace it.

The analogy omits the mathematical work needed to rule out unseen alternatives. Having inspected many itineraries does not prove the best one has been found. Anytime A* needs valid bounds and correct search bookkeeping for that stronger conclusion.

Worked example

Consider an original cost-minimization snapshot. The best complete plan found so far costs U = 30 units. Suppose the search also has a valid positive lower bound L = 24 on the optimal cost C*. Then 24 ≤ C* ≤ 30.

The incumbent is therefore at most 30/24 = 1.25 times the optimal cost, or at most 25% above optimum. This is a bound, not a claim that its actual error is exactly 25%.

Later, the search finds a plan costing 27 while the valid lower bound rises to 25. The ratio becomes 27/25 = 1.08, giving an 8% bound. Improvement came from both a cheaper plan and a stronger lower bound.

If the lower bound reaches 27 while the incumbent remains 27, optimality is certified for the modeled problem. These numbers are an illustrative sequence of search summaries, not a benchmark or a claim that every run improves in this pattern. A weighted selection score cannot simply be substituted for L.

Illustrative case study

Fictional case: Spruce Routing gives a planner a limited preparation window. Its interface initially shows only the latest route cost. Reviewers add whether a feasible route has been found and whether its quality is bounded or proved optimal.

When preparation ends, the system returns the retained feasible route and the associated search status. This invented case illustrates communication of an anytime result; it does not establish suitability for live transportation or report an actual performance gain.

Common misconceptions and mistakes

Continuing search after finding a solution is essential to the anytime behavior, but simply rerunning an arbitrary search does not automatically reproduce the algorithm's efficiency or guarantees.

Do not confuse the heuristic weight with a probability of correctness. It changes search priorities; any quality guarantee follows from a mathematical analysis with stated assumptions.

Also distinguish better solutions from better proof of quality. A run can keep the same incumbent while tightening its bound. Conversely, a long period without improvement does not by itself prove optimality. Memory limits, incomplete search, or incorrect pruning can prevent the claimed convergence.

Business use

Anytime A* is relevant when a team must balance planning delay against plan quality and the problem fits graph-based cost search. A useful evaluation measures time to first feasible solution, quality over time, memory consumption, and the reliability of the reported bounds.

The operational deadline should account for returning and validating the retained solution, not merely stopping the search loop. If the environment changes during computation, a previously feasible plan may require rechecking. The algorithm's result concerns the search model used; it does not automatically remain valid after the underlying facts change.

Check your understanding

A plan costs 18 and a valid lower bound is 15. What relative guarantee follows?

Answer: Its cost is at most 18/15 = 1.2 times optimum, or at most 20% above optimum, under the assumptions supporting that bound.

Related terms

Anytime algorithm
Admissible heuristic
A* search
weighted A*
incumbent solution
branch and bound
optimality gap

Learn next

Next, plot incumbent cost and a valid lower bound against search effort on a small problem. Mark the first feasible result separately from the point where optimality is proved.

Sources

Hansen and Zhou, Anytime Heuristic Search, original research paper: https://arxiv.org/pdf/1110.2737

Primary algorithm and convergence discussion read. The entry explains the Hansen–Zhou approach and distinguishes its assumptions from guarantees of other variants. Numerical examples are original.

Previous: Antithetic variates Next: Anytime algorithm