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.


single-agent search; pattern databases; heuristic; pathfinding

Full Text: PDF