Forward Perimeter Search with Controlled Use of Memory
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 659-664.
Abstract
There are many hard shortest-path search problems that cannot be solved, because best-first search runs out of memory space and depth-first search runs out of time. We propose Forward Perimeter Search (FPS), a heuristic search with controlled use of memory. It builds a perimeter around the root node and tests each perimeter node for a shortest path to the goal. The perimeter is adaptively extended towards the goal during the search process. We show that FPS expands in random 24-puzzles 50% fewer nodes than BF-IDA* while requiring several orders of magnitude less memory. Additionally, we present a hard problem instance of the 24-puzzle that needs at least 140 moves to solve; i.e. 26 more moves than the previously published hardest instance.
@inproceedings{ijcai2013p104,
title = {Forward Perimeter Search with Controlled Use of Memory},
author = {Schütt, Thorsten and Döbbelin, Robert and Reinefeld, Alexander},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {659--664},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/104},
}
TY - CPAPER TI - Forward Perimeter Search with Controlled Use of Memory AU - Schütt, Thorsten AU - Döbbelin, Robert AU - Reinefeld, Alexander T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 659 EP - 664 UR - https://ijcai.org/proceedings/2013/104 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
