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

abstract

  • 2014 AAAI press. All Rights Reserved. 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.

published proceedings

  • Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014

author list (cited authors)

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

complete list of authors

  • Sharon, G||Felner, A||Sturtevant, NR

publication date

  • January 2014