Exponential Deepening A* for Real-Time Agent-Centered Search
- Guni Sharon
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Nathan R. Sturtevant
In the Real-Time Agent-Centered Search (RTACS) problem, an agent has to arrive at a goal location while acting and reasoning in the physical world. Traditionally, RTACS problems are solved by propagating and updating heuristic values of states visited by the agent. In existing RTACS algorithms the agent may revisit each state many times causing the entire procedure to be quadratic in the state space. We study the Iterative Deepening (ID) approach for solving RTACS and introduce Exponential Deepening A* (EDA*), an RTACS algorithm where the threshold between successive Depth-First calls is increased exponentially. EDA* is proven to hold a worst case bound that is linear in the state space. Experimental results supporting this bound are presented and demonstrate up to 10x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime.
Citation
G. Sharon, A. Felner, N. Sturtevant. "Exponential Deepening A* for Real-Time Agent-Centered Search". National Conference on Artificial Intelligence (AAAI), (ed: Carla E. Brodley, Peter Stone), pp 871-877, July 2014.| Keywords: | Real-time, Agent-centered, Heuristic search |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sharon+al:AAAI14,
author = {Guni Sharon and Ariel Felner and Nathan R. Sturtevant},
title = {Exponential Deepening A* for Real-Time Agent-Centered Search},
Editor = {Carla E. Brodley, Peter Stone},
Pages = {871-877},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2014,
}Last Updated: July 07, 2020Submitted by Sabina P
