AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Additive Heuristic for Four-Connected Gridworlds
Kenneth Anderson

Last modified: 2010-08-25


Memory-based heuristic techniques have been used to effectively reduce search times in implicit graphs. Recently, these techniques have been applied to improving search times in explicit graphs. This paper presents a new memory-based, additive heuristic that can be used on a type of explicit graph: the four-connected gridworld. The heuristic reduces the number of expanded nodes by up to five times, reduces execution time by up to 29 times, and can efficiently accommodate graph changes.

Full Text: PDF