AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
Online Detection of Dead States in Real-Time Agent-Centered Search
Guni Sharon, Nathan Sturtevant, Ariel Felner

Last modified: 2013-06-19


In this paper we introduce techniques for state pruning atruntime in a priori unknown domains. We describe how toidentify states that can be deleted from the state-space whenlooking for both optimal and suboptimal solutions. We discussgeneral graphs and special cases like 8-connected grids.Experimental results show a speed up of up to an order ofmagnitude when applying our techniques on real-time agentcenteredsearch problems.


Heuristic search; Real-time; State pruning

Full Text: PDF