Additive Heuristic for Four-Connected Gridworlds

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Oral Presentations

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.

10.1609/socs.v1i1.18162