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

Authors

  • Guni Sharon Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Nathan Sturtevant University of Denver

Keywords:

Real-time, Agent-centered, Heuristic 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.

Downloads

Published

2021-09-01