Weighted, Anytime & Real-Time Search
Trading optimality for speed with guarantees.
A robot arm, a game character and a delivery planner share a deadline problem: an optimal plan that arrives late is worth less than a good plan that arrives now. Bounded-suboptimal search promises "within 10% of optimal", anytime search improves its answer until time runs out, and real-time search commits to every move after a fixed amount of thinking, yet still learns to act optimally.
What you’ll learn
- Prove that weighted A* is -admissible, including without reopening when the heuristic is consistent.
- Explain how focal search uses inadmissible estimates for guidance while an admissible certifies the bound.
- Run anytime weighted A* and compute its suboptimality certificate at any moment.
- Prove that LRTA* reaches the goal in every trial, keeps admissible and converges to optimal behavior, with moves per trial in unit-cost spaces.
Bounded suboptimality
Invariant: every closed state has . Suppose it holds so far and is popped. Let be the first state on a cheapest path to that is not closed, and its predecessor there, closed with . Expanding gave the value
Consistency makes nondecreasing along a cheapest path, and was popped before :
Cancel : the invariant holds for . The same chain along a cheapest path to an optimal goal, where , bounds the first goal popped:
Raising often cuts expansions by orders of magnitude, but not always. Wilt and Ruml (2012) found that weighted A* thrives when tracks the number of steps to the goal and can expand more nodes as grows when it does not, for example when costs vary widely between actions.
Guidance without losing the bound: focal search
Weighted A* uses one inflated both to bound and to guide. Focal search separates the two roles. A* (Pearl & Kim, 1982) keeps the usual open list ordered by with an admissible , and a sublist of nodes whose is within the factor of the smallest:
It expands from FOCAL by any secondary criterion, typically an inadmissible estimate of the number of steps to go. With reopening, the frontier lemma gives at every moment, so a goal taken from FOCAL costs .
Explicit Estimation Search (Thayer & Ruml, 2011) adds an inadmissible cost estimate and expands the node that looks best by whenever the admissible bound allows. These algorithms let a learned or hand-tuned estimate drive the search, while the guarantee rests on an admissible alone.
Focal search with and an admissible : the smallest on the open list is 50, and FOCAL holds a goal with . If that goal is returned now, what is certified?
- Nothing yet: the bound applies only when the search ends
- The solution is optimal, since it was in FOCAL
- , so the solution is within of optimal
Show the answer
C. , so the solution is within of optimal
By the frontier lemma, , so and , inside the promised factor . The open list's minimum is a running lower bound on the optimum, which is what makes focal and anytime search certifiable at every moment.
Anytime search
An anytime algorithm returns a solution early and keeps improving it, with a certificate that tightens toward 1. Anytime weighted A* (Hansen & Zhou, 2007) simply keeps running the weighted search after its first solution, using the incumbent's cost to prune:
function ANYTIME-WEIGHTED-A*(problem, h, w):
U ← ∞; incumbent ← none # best solution so far
OPEN ← {start}, ordered by f_w(n) = g(n) + w·h(n)
while OPEN is not empty and time remains:
n ← POP-MIN(OPEN)
if g(n) + h(n) ≥ U: continue # cannot beat the incumbent
for each successor n' of n with step cost c:
g' ← g(n) + c
if g' + h(n') ≥ U: continue # prune
if n' is a goal: U ← g'; incumbent ← path to n'
else if n' is new or g' < g(n'): # reopen if reached more cheaply
g(n') ← g'; insert n' into OPEN
report incumbent, bound U / min(U, min{ g(m) + h(m) : m in OPEN })
return incumbent # optimal if OPEN emptiedThe order of expansion follows , but pruning and the certificate use the admissible .
An anytime search holds a solution of cost 120, and the smallest on its open list is 96. At most how many percent above the optimum can the incumbent be?
Show the answer
25 %
, so : at most 25% above optimal. As the search continues, falls and the open list's minimum rises, and the certificate tightens toward 1.
ARA* (Likhachev, Gordon & Thrun, 2003) runs a sequence of weighted searches with decreasing , say , reusing -values between them and never re-expanding a state within one search. With a consistent , each search is -admissible by the theorem above, and the certificate is the smaller of and the open-list bound. It became a standard tool in robot motion planning. Restarting weighted A* (Richter, Thayer & Ruml, 2010) instead restarts each search from the root, keeping only the incumbent and cached heuristic values, which helps when early commitments were poor; it powers the LAMA planner.
Real-time search: act, then learn
An agent that must act before planning is finished, such as a game character with a per-frame budget or a robot in unknown terrain, interleaves search with execution: look ahead a bounded amount, move, repeat. Without memory such an agent can oscillate forever in a heuristic depression, a region where underestimates badly. LRTA* (Korf, 1990) fixes this by learning: before leaving a state, it raises there to the best one-step lookahead value.
function LRTA*-TRIAL(start, h): # h: a table, initialized admissibly
s ← start
while s is not a goal:
s* ← argmin over successors s' of [ c(s, s') + h(s') ]
h(s) ← max( h(s), c(s, s*) + h(s*) ) # learn: s is at least this far
s ← s* # act: one moveLookahead depth 1. Deeper lookahead and larger learning neighborhoods (as in LSS-LRTA*) trade more thinking per move for fewer moves.
Admissibility is preserved. If before the update at , the new value is at most :
Each move spends potential. Let be on arrival and the increase learned there. After the update , and is unchanged until the agent arrives:
Sum over a trial of moves. Values only rise and never exceed , so the total learning is bounded:
With unit costs and , each of the nongoal states has . With integer costs, every trial that learns raises by at least 1, so learning stops; in a trial without learning, at every step, and summing shows that the path costs at most :
Key takeaways
- Weighted A* returns cost at most for admissible with reopening, and for consistent even without it, through the invariant .
- Focal search and explicit estimation decouple guidance (inadmissible estimates) from the bound: any goal taken from FOCAL costs at most .
- Anytime search certifies its incumbent at every moment by and is optimal when the open list empties; ARA* and restarting weighted A* lower while reusing work.
- LRTA* acts after a bounded lookahead and learns : stays admissible, each trial ends, using moves with unit costs, and repeated trials converge to optimal paths.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Weighted A* with and a consistent heuristic never re-expands a state. What is guaranteed?
- An optimal solution
- A solution of cost at most
- A solution of cost at most
- Nothing, since bounds need reopening
Show the answer
B. A solution of cost at most
With a consistent , every closed state satisfies , so the first goal popped costs at most , with or without reopening.
Why is greedy best-first search not -admissible for any ?
- Because it uses an inadmissible heuristic
- Because it is incomplete in finite graphs
- Because it never reopens states
- Because it ignores : it can follow a deceptively low into a detour of arbitrary cost
Show the answer
D. Because it ignores : it can follow a deceptively low into a detour of arbitrary cost
Ordering by alone ignores how much a path has already cost, so a family of instances with ever longer detours toward low- states defeats any fixed factor. Weighted A* keeps in its key, which is exactly what its bound uses.
Anytime weighted A* prunes nodes with , where is the incumbent's cost. What does it mean when its open list becomes empty?
- The incumbent is proven optimal
- The search failed and must restart with a smaller
- The incumbent is -optimal, but no better
- The heuristic was inconsistent
Show the answer
A. The incumbent is proven optimal
A node is discarded only if , which proves that nothing through it beats . When no node remains, every path that could improve on the incumbent has been ruled out, so , and the certificate has reached 1.
Why does LRTA* raise to before leaving ?
- To make consistent everywhere
- To guarantee that the first trial follows an optimal path
- To escape heuristic depressions: learned values bound the moves per trial, and they never exceed
- To save memory by forgetting the old value
Show the answer
C. To escape heuristic depressions: learned values bound the moves per trial, and they never exceed
Without learning, an agent can oscillate forever inside a depression of . Each update raises by an amount that the potential argument charges against the moves, and because the new value is a one-step lookahead bound, stays admissible, so total learning is finite.
Further reading
- M. Likhachev, G. Gordon & S. Thrun, "ARA*: Anytime A* with provable bounds on sub-optimality," Advances in Neural Information Processing Systems 16 (2003).
- E. A. Hansen & R. Zhou, "Anytime heuristic search," Journal of Artificial Intelligence Research 28 (2007), 267–297.
- R. E. Korf, "Real-time heuristic search," Artificial Intelligence 42 (1990), 189–211.
- J. Pearl & J. H. Kim, "Studies in semi-admissible heuristics," IEEE Transactions on Pattern Analysis and Machine Intelligence 4(4) (1982), 392–399.
- J. T. Thayer & W. Ruml, "Bounded suboptimal search: A direct approach using inadmissible estimates," Proceedings of IJCAI (2011).