Exponential Deepening A* for Real-Time Agent-Centered Search Academic Article uri icon

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.

published proceedings

  • Proceedings of the International Symposium on Combinatorial Search

author list (cited authors)

  • Sharon, G., Felner, A., & Sturtevant, N.

citation count

  • 0

complete list of authors

  • Sharon, Guni||Felner, Ariel||Sturtevant, Nathan

publication date

  • January 2021