---
title: "Forward Perimeter Search with Controlled Use of Memory"
authors:
  - "Thorsten Schütt"
  - "Robert Döbbelin"
  - "Alexander Reinefeld"
doi: ""
url: "https://ijcai.org/proceedings/2013/104"
pdf: "https://ijcai.org/proceedings/2013/0104.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "659-664"
track: ""
keywords:
---

# Forward Perimeter Search with Controlled Use of Memory

Thorsten Schütt, Robert Döbbelin, Alexander Reinefeld

*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.