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

Abstract

In the Real-Time Agent-Centered Search (RTACS) problem,an agent has to arrive at a goal location while acting and reasoningin the physical world. Traditionally, RTACS problemsare solved by propagating and updating heuristic values ofstates visited by the agent. In existing RTACS algorithms theagent may revisit each state many times causing the entireprocedure to be quadratic in the state space. We study theIterative Deepening (ID) approach for solving RTACS andintroduce Exponential Deepening A* (EDA*), an RTACS algorithmwhere the threshold between successive Depth-Firstcalls is increased exponentially. EDA* is proven to hold aworst case bound that is linear in the state space. Experimentalresults supporting this bound are presented and demonstrateup to 10x reduction over existing RTACS solvers wrtdistance traveled, states expanded and CPU runtime.