Exponential Deepening A* for Real-Time Agent-Centered Search

Proceedings of the International Symposium on Combinatorial Search, 7

Volume

Vol. 7 No. 1 (2014): Seventh Annual Symposium on Combinatorial Search

Extended Abstracts

This paper introduces Exponential Deepening A* (EDA*), an Iterative Deepening (ID) algorithm where the threshold between successive Depth-First calls is increased exponentially. EDA* can be viewed as a Real-Time Agent-Centered (RTACS) algorithm. Unlike most existing RTACS algorithms, EDA* is proven to hold a worst case bound that is linear in the state space. Experimental results demonstrate up to 5x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime. A full version of this paper appears in AAAI-14.

10.1609/socs.v5i1.18305