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 (Hart, Nilsson, and Raphael 1972) 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`

, and`LOWER`

lists. \(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*.

## References

*Artificial Intelligence*8 (1): 69–76. https://doi.org/10.1016/0004-3702(77)90005-4.

*Acm Sigart Bulletin*, no. 37 (December): 28–29. https://doi.org/10.1145/1056777.1056779.

*Ieee Transactions on Systems Science and Cybernetics*4 (2): 100–107. https://doi.org/10.1109/tssc.1968.300136.

*Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, Usa, July 8-10, 2010*, edited by Ariel Felner and Nathan R. Sturtevant. AAAI Press. http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2073.

*Eighteenth National Conference on Artificial Intelligence*, 476–83. Edmonton, Alberta, Canada: American Association for Artificial Intelligence.

*Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems - Aamas ’05*. https://doi.org/10.1145/1082473.1082748.

*Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems - Aamas ’06*. https://doi.org/10.1145/1160633.1160682.

*Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2*, 1652–59. Ijcai’95. Montreal, Quebec, Canada: Morgan Kaufmann Publishers Inc.

*Intelligent Unmanned Ground Vehicles*, 203–20. https://doi.org/10.1007/978-1-4615-6325-9_11.