These are some quick notes listing papers related to A* itself and variants. In particular, here I’m interested in papers that update \(h\) during the A* search, as a background for pruning.
Specifically, our version of pruning increases \(h\) during a single A* search, and in fact the heuristic becomes in-admissible after pruning.
Changing \(h\)
The original A* paper has a proof of optimality. Later papers consider this also with heuristics that change their value over time.
Original A* paper (Hart, Nilsson, and Raphael 1968) does not consider a changing heuristic.
- A later addendum (NO_ITEM_DATA:astar-correction-hart72) removes the need for the heuristic to be consistent in the optimality proof, but does not otherwise change things.
Gelperin (1977) considers that \(h\) may depend on the A* state. Notation: \(\hat h(n, m)\): the value of \(h\) in \(n\) just before closing (expanding) \(m\), and \(\hat h(n, \overline m)\), the value of \(h\) in \(n\) just after closing \(m\). State: \(\Sigma(m)\) resp. \(\Sigma(\overline m)\). Second argument may be omitted:
When is it neither necessary nor helpful to use this new notation, we will use the older notation with search-state dependence understood.
Dechter and Pearl (1983) comment on and extend the proof of (Gelperin 1977), but are not specific about \(h\) depending on the state.
Somewhat unrelated, a nice paper going over some tricky details regarding A* is Holte (2010).
Multiple-path pruning is the technique from (Poole and Mackworth 2017) to remove paths going through expanded nodes to which an optimal path has been found.
Variants
There are some variants of A* for repeated searches that do incremental updates of \(h\) between iterations. Note that \(h\) is assumed to be admissible, and usually also consistent. Incremental A* refers to the entire class of versions of A* that reuse information between runs.
The Wikipedia page on incremental heuristic search has more information.
- D* (Dynamic A*) (Stentz 1997, 1995)
- Setting: a robot is
navigating and discovers new obstacles along the way. This leads to increasing
(or possibly decreasing) edge weights. They keep
OPEN,RAISE, andLOWERlists. \(h\) is assumed to the distance to the end in the so-far explored graph. - Adaptive A* (Koenig and Likhachev 2005)
- Setting: repeatedly find
shortest path to a fixed set of goal states, but varying start states. Input:
a consistent heuristic \(h\). (I’m not sure where/why consistency is needed.)
Intuitively, it uses that after making a search from \(s\), we know that all states close to \(s\) must have a distance that is not much smaller than the distance from \(s\).
The main insight of Adaptive A* is this: after running one iteration from \(s\) to \(t\), let the distance from \(s\) to \(t\) be \(h^*(s)\), and let \(g(u)\) be the shortest distance from \(s\) to \(u\) found so far. Write \(g^*\) for the distance from \(s\), \(h^*\) for the distance to \(t\), and \(f^*\) for their sum. By the triangle inequality, \(h^*(s) \leq f^*(u)\). We get
\begin{equation} h^*(s) \leq f^*(u) = g^*(u) + h^*(u) \leq g(u) + h^*(u). \end{equation}
Rewriting gives \(h^*(u) \geq h^*(s) - g(u)\), which we can use as a new value for \(h\) that is possibly better than the user provided value.
Edge weights may increase over time.
- Real-Time Adaptive A* (RTAA*) (Koenig and Likhachev 2006)
- Same setting
as Adaptive A*, but now the model is a robot searching the grid. There is a
limit on the lookahead and movements it may make.
After increasing edge weights, they show that the heuristic remains consistent.
- Generalized Adaptive A* (GAA*) (Sun, Koenig, and Yeoh 2008)
- Can additionally handle decrements in edge weights and changes of goal state. Input: a consistent heuristic \(H(s, t)\) for any pair of states, that additionally satisfies the more general triangle inequality.
- D* Lite (Koenig and Likhachev 2002)
- Again models a robot moving around.
Conclusion
While there are many methods that (implicitly) modify \(h\), their setting is usually in that of changing surroundings, repeated searches, or constrained to a single moving robot. All these are different from our case, where we are able to increase \(h\) during a single search for a single shortest path. Further, most variants keep a more complicated state to handle the updates than that of a single A*.