Online Detection of Dead States in Real-Time Agent-Centered Search
- Guni Sharon
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
In this paper we introduce techniques for state pruning at runtime in a priori unknown domains. We describe how to identify states that can be deleted from the state-space when looking for both optimal and suboptimal solutions. We discuss general graphs and special cases like 8-connected grids. Experimental results show a speed up of up to an order of magnitude when applying our techniques on real-time agent-centered search problems.
Citation
G. Sharon, N. Sturtevant, A. Felner. "Online Detection of Dead States in Real-Time Agent-Centered Search". Symposium on Combinatorial Search, (ed: Malte Helmert, Gabriele Röger), pp 167-174, July 2013.| Keywords: | Heuristic search, Real-time, State pruning |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sharon+al:SoCS13,
author = {Guni Sharon and Nathan R. Sturtevant and Ariel Felner},
title = {Online Detection of Dead States in Real-Time Agent-Centered Search},
Editor = {Malte Helmert, Gabriele Röger},
Pages = {167-174},
booktitle = {Symposium on Combinatorial Search},
year = 2013,
}Last Updated: July 09, 2020Submitted by Sabina P
