Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 ww-admissible, including without reopening when the heuristic is consistent.
  • Explain how focal search uses inadmissible estimates for guidance while an admissible ff 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 hh admissible and converges to optimal behavior, with O(n2)\order{n^2} moves per trial in unit-cost spaces.

Bounded suboptimality

DerivationProof of the no-reopening case
  1. g(m) ≤ g(p)+c(p,m) ≤ w g∗(p)+c(p,m) ≤ w g∗(m)g(m)\ \le\ g(p)+c(p,m)\ \le\ w\,g^*(p)+c(p,m)\ \le\ w\,g^*(m)

    Invariant: every closed state ss has g(s)≤w g∗(s)g(s)\le w\,g^*(s). Suppose it holds so far and ss is popped. Let mm be the first state on a cheapest path to ss that is not closed, and pp its predecessor there, closed with g(p)≤w g∗(p)g(p)\le w\,g^*(p). Expanding pp gave mm the value

  2. g(s)+w h(s) ≤ g(m)+w h(m) ≤ w(g∗(m)+h(m)) ≤ w(g∗(s)+h(s))g(s)+w\,h(s)\ \le\ g(m)+w\,h(m)\ \le\ w\big(g^*(m)+h(m)\big)\ \le\ w\big(g^*(s)+h(s)\big)

    Consistency makes g∗+hg^*+h nondecreasing along a cheapest path, and ss was popped before mm:

  3. g(s) ≤ w g∗(s)andg(G)=fw(G) ≤ w C∗g(s)\ \le\ w\,g^*(s)\qquad\text{and}\qquad g(G)=f_w(G)\ \le\ w\,C^*

    Cancel w h(s)w\,h(s): the invariant holds for ss. The same chain along a cheapest path to an optimal goal, where g∗+h≤C∗g^*+h\le C^*, bounds the first goal GG popped:

Raising ww often cuts expansions by orders of magnitude, but not always. Wilt and Ruml (2012) found that weighted A* thrives when hh tracks the number of steps to the goal and can expand more nodes as ww 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 hh both to bound and to guide. Focal search separates the two roles. A*ε_\varepsilon (Pearl & Kim, 1982) keeps the usual open list ordered by f=g+hf=g+h with an admissible hh, and a sublist of nodes whose ff is within the factor ww of the smallest:

FOCAL={ n∈OPEN: f(n)≤w⋅min⁡m∈OPENf(m) }.\mathrm{FOCAL}=\Big\{\,n\in\mathrm{OPEN}:\ f(n)\le w\cdot\min_{m\in\mathrm{OPEN}}f(m)\,\Big\}.

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 min⁡OPENf≤C∗\min_{\mathrm{OPEN}}f\le C^* at every moment, so a goal taken from FOCAL costs g=f≤w C∗g=f\le w\,C^*.

Explicit Estimation Search (Thayer & Ruml, 2011) adds an inadmissible cost estimate h^\hat h and expands the node that looks best by g+h^g+\hat h whenever the admissible bound allows. These algorithms let a learned or hand-tuned estimate drive the search, while the guarantee rests on an admissible hh alone.

Check your understanding

Focal search with w=1.2w=1.2 and an admissible hh: the smallest ff on the open list is 50, and FOCAL holds a goal with g=58g=58. If that goal is returned now, what is certified?

  1. Nothing yet: the bound applies only when the search ends
  2. The solution is optimal, since it was in FOCAL
  3. C∗≥50C^*\ge50, so the solution is within 58/50=1.1658/50=1.16 of optimal
  4. C∗=58C^*=58
Show the answer

C. C∗≥50C^*\ge50, so the solution is within 58/50=1.1658/50=1.16 of optimal

By the frontier lemma, min⁡OPENf≤C∗\min_{\mathrm{OPEN}}f\le C^*, so C∗≥50C^*\ge50 and 58≤1.16 C∗58\le1.16\,C^*, inside the promised factor 1.21.2. 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 UU to prune:

text
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 emptied

The order of expansion follows fwf_w, but pruning and the certificate use the admissible g+hg+h.

Predict before you look

An anytime search holds a solution of cost 120, and the smallest g+hg+h on its open list is 96. At most how many percent above the optimum can the incumbent be?

Show the answer

25 %

C∗≥96C^*\ge96, so 120/C∗≤120/96=1.25120/C^*\le120/96=1.25: at most 25% above optimal. As the search continues, UU 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 ww, say 2.5,2,1.5,12.5, 2, 1.5, 1, reusing gg-values between them and never re-expanding a state within one search. With a consistent hh, each search is ww-admissible by the theorem above, and the certificate is the smaller of ww 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 hh underestimates badly. LRTA* (Korf, 1990) fixes this by learning: before leaving a state, it raises hh there to the best one-step lookahead value.

text
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 move

Lookahead depth 1. Deeper lookahead and larger learning neighborhoods (as in LSS-LRTA*) trade more thinking per move for fewer moves.

DerivationProof: a potential argument
  1. c(s,s⋆)+h(s⋆)=min⁡s′[c(s,s′)+h(s′)] ≤ min⁡s′[c(s,s′)+h∗(s′)]=h∗(s)c(s,s^\star)+h(s^\star)=\min_{s'}\big[c(s,s')+h(s')\big]\ \le\ \min_{s'}\big[c(s,s')+h^*(s')\big]=h^*(s)

    Admissibility is preserved. If h≤h∗h\le h^* before the update at ss, the new value is at most h∗(s)h^*(s):

  2. at+1 ≤ at+δt−εa_{t+1}\ \le\ a_t+\delta_t-\varepsilon

    Each move spends potential. Let ata_t be h(st)h(s_t) on arrival and δt≥0\delta_t\ge0 the increase learned there. After the update h(st)≥c(st,st+1)+h(st+1)h(s_t)\ge c(s_t,s_{t+1})+h(s_{t+1}), and h(st+1)h(s_{t+1}) is unchanged until the agent arrives:

  3. Tε ≤ a0+∑tδt ≤ h(s0)+∑x∈S(h∗(x)−h0(x))T\varepsilon\ \le\ a_0+\sum_t\delta_t\ \le\ h(s_0)+\sum_{x\in S}\big(h^*(x)-h_0(x)\big)

    Sum over a trial of TT moves. Values only rise and never exceed h∗h^*, so the total learning is bounded:

  4. T ≤ ∑xh∗(x) ≤ (n−1)2,cost of a learning-free trial ≤ h(s0) ≤ h∗(s0)T\ \le\ \sum_x h^*(x)\ \le\ (n-1)^2,\qquad \text{cost of a learning-free trial}\ \le\ h(s_0)\ \le\ h^*(s_0)

    With unit costs and h0≡0h_0\equiv0, each of the n−1n-1 nongoal states has h∗≤n−1h^*\le n-1. With integer costs, every trial that learns raises ∑xh(x)\sum_xh(x) by at least 1, so learning stops; in a trial without learning, h(st)≥c(st,st+1)+h(st+1)h(s_t)\ge c(s_t,s_{t+1})+h(s_{t+1}) at every step, and summing shows that the path costs at most h(s0)≤h∗(s0)h(s_0)\le h^*(s_0):

Key takeaways

  • Weighted A* returns cost at most w C∗w\,C^* for admissible hh with reopening, and for consistent hh even without it, through the invariant g≤w g∗g\le w\,g^*.
  • Focal search and explicit estimation decouple guidance (inadmissible estimates) from the bound: any goal taken from FOCAL costs at most wmin⁡OPENf≤w C∗w\min_{\mathrm{OPEN}}f\le w\,C^*.
  • Anytime search certifies its incumbent at every moment by U/min⁡{U,min⁡OPEN(g+h)}U/\min\{U,\min_{\mathrm{OPEN}}(g+h)\} and is optimal when the open list empties; ARA* and restarting weighted A* lower ww while reusing work.
  • LRTA* acts after a bounded lookahead and learns h(s)←max⁡(h(s), c(s,s⋆)+h(s⋆))h(s)\leftarrow\max\big(h(s),\,c(s,s^\star)+h(s^\star)\big): hh stays admissible, each trial ends, using O(n2)\order{n^2} 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.

Question 1

Weighted A* with w=2w=2 and a consistent heuristic never re-expands a state. What is guaranteed?

  1. An optimal solution
  2. A solution of cost at most 2C∗2C^*
  3. A solution of cost at most 4C∗4C^*
  4. Nothing, since bounds need reopening
Show the answer

B. A solution of cost at most 2C∗2C^*

With a consistent hh, every closed state satisfies g≤w g∗g\le w\,g^*, so the first goal popped costs at most w C∗=2C∗w\,C^*=2C^*, with or without reopening.

Question 2

Why is greedy best-first search not ww-admissible for any ww?

  1. Because it uses an inadmissible heuristic
  2. Because it is incomplete in finite graphs
  3. Because it never reopens states
  4. Because it ignores gg: it can follow a deceptively low hh into a detour of arbitrary cost
Show the answer

D. Because it ignores gg: it can follow a deceptively low hh into a detour of arbitrary cost

Ordering by hh alone ignores how much a path has already cost, so a family of instances with ever longer detours toward low-hh states defeats any fixed factor. Weighted A* keeps gg in its key, which is exactly what its bound uses.

Question 3

Anytime weighted A* prunes nodes with g+h≥Ug+h\ge U, where UU is the incumbent's cost. What does it mean when its open list becomes empty?

  1. The incumbent is proven optimal
  2. The search failed and must restart with a smaller ww
  3. The incumbent is ww-optimal, but no better
  4. The heuristic was inconsistent
Show the answer

A. The incumbent is proven optimal

A node is discarded only if g+h≥Ug+h\ge U, which proves that nothing through it beats UU. When no node remains, every path that could improve on the incumbent has been ruled out, so U=C∗U=C^*, and the certificate U/min⁡{U,min⁡OPEN(g+h)}U/\min\{U,\min_{\mathrm{OPEN}}(g+h)\} has reached 1.

Question 4

Why does LRTA* raise h(s)h(s) to c(s,s⋆)+h(s⋆)c(s,s^\star)+h(s^\star) before leaving ss?

  1. To make hh consistent everywhere
  2. To guarantee that the first trial follows an optimal path
  3. To escape heuristic depressions: learned values bound the moves per trial, and they never exceed h∗h^*
  4. 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 h∗h^*

Without learning, an agent can oscillate forever inside a depression of hh. Each update raises hh by an amount that the potential argument charges against the moves, and because the new value is a one-step lookahead bound, hh 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).