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

Abstract

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.