Anytime Dynamic A*: The Proofs
Maxim Likhachev, Dave Ferguson, Geof f Gordon,
Anthony Stentz and Sebastian Thrun
a
April 2005
CMU-RI-TR-05-12
a S. Thrun is af f i liated with Stanford University,
all other authors are af f i liated with Carnegie Mellon University.
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
Abstract
This paper presents a thorough theoretical analysis of a recently developed
anytime incremental planning algorithm called Anytime Dynamic A* (AD*).
The analysis includes proofs for the correctness of the algorithm and as well
as the proofs for several properties of the algorithm related to its ef f i ciency.