Exponential deepening a* for real-time agent-centered search (extended abstract), full version has been accepted to aaai-2014

摘要: 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. Full version of this paper appears in AAAI-14.