Forward Perimeter Search with Controlled Use of Memory

1 Introduction

Many heuristic search algorithms have been devised to find a shortest path in a graph. A* expands the fewest nodes, but its applicability is limited because it holds all expanded nodes in the main memory. IDA* in contrast, uses essentially no storage and is fast in terms of node expansions per second. However, it has four weaknesses: (1) Its iterative-deepening node expansion visits the same nodes multiple times, (2) it is not able to detect repeated nodes in a graph because it does not keep information on the visited nodes, (3) it uses a strict left-to-right traversal of the leaf nodes whereas A* maintains the frontier in a best-first order, and (4) it does not keep information from the preceeding iteration.

Breadth-first search with heuristic pruning has been proposed as a compromise between A* and IDA*. It needs less memory space than A* for storing the search front and is still able to detect repeated nodes in graphs, thereby solving weaknesses (2) and (3). Several variants have been proposed: breadth-first frontier search [Korf and Zhang, 2000], breadthfirst heuristic search [Zhou and Hansen, 2004], and breadthfirst iterative-deepening A* (BF-IDA*) [Zhou and Hansen, 2004].

Part of this work was supported by the EU project CONTRAIL 'Open Computing Infrastructures for Elastic Services'.

Forward Perimeter Search (FPS) allows to steer the memory consumption within certain limits and it does not suffer from IDA*'s weaknesses (2) to (4). FPS first generates a set of nodes (the perimeter P) around the root node and then performs heuristic breadth-first searches to test whether any perimeter node p ∈ P reaches a solution within a given threshold. When no solution has been found, the threshold is increased and the next iteration is begun. Before starting a new iteration, FPS checks whether a subtree of a perimeter node p exceeds a given size limit and, if this is the case, enlarges the perimeter at p. By this means, the perimeter is iteratively extended in the most promising direction, because the test subtrees grow in the direction of the expected goal. All perimeter nodes are kept in the main memory and their goal distance estimates are updated.

The adaptive decomposition of the search space allows FPS to solve large problems without exceeding the available memory. FPS' breadth-first expansion of the perimeter nodes avoids duplicate node expansions as far as possible (depending on the available memory) and its adaptively refined perimeter makes it likely to find a goal early in the last iteration. This perimeter refinement is the main reason for the 50% node savings with respect to BF-IDA* (Sec. 4).

FPS can be executed on massively parallel systems and on clusters. It provides two sources of parallelism. First, all perimeter nodes can be searched concurrently without incurring any communication overhead ('trivial parallelism'). Second, each perimeter node can be tested with the parallel BFIDA* algorithm [Sch¨utt et al., 2011] presented in Sec. 3.4. In fact, all empirical results in Sec. 4 were obtained on compute clusters of various sizes.

This paper begins with a brief review of related work. Thereafter, we introduce FPS and present empirical results on the 24-puzzle and 17-pancake problem. Finally, we present an instance of the 24-puzzle that is more difficult to solve than any previously published instance and we give upper and lower bounds (140 resp. 142 moves) on its solution length.

2 RelatedWork

The idea of perimeter search was invented almost twenty years ago. But in contrast to our approach, the previous algorithms [Dillenburg and Nelson, 1994; Manzini, 1995; Kaindl and Kainz, 1997] build a perimeter around the goal rather than the start node 1 . Hence, each newly expanded node must be checked against all perimeter nodes which only pays off in application domains with expensive operator costs.

Single-frontier bidirectional search [Felner et al., 2010] also builds a search front around the goal node, but it dynamically switches the search direction between forward and backward search. Several jumping policies (highest branching degree, smallest h-value) have been evaluated. Further improvements can be achieved by combining this method with multiple-goal pattern databases [Felner and Ofek, 2007] which are seeded with the states' values that are abstracted from the perimeter nodes.

Fringe search [Bj¨ornsson et al., 2005] stores the search frontier (fringe) in main memory. It searches the graph in an iterative-deepening fashion without re-expanding the nodes inside the fringe. The algorithm is beneficial when inaccurate heuristics would require many iterations, but it does not allow to control the memory consumption.

MREC [Sen and Bagchi, 1989] is a combination of A* and IDA*. It stores as much as possible of the explicit search graph in memory and searches the remaining nodes with IDA*. MREC is comparable to FPS, but instead of keeping the search space in memory, we only store a search frontier (the perimeter) and instead of using IDA* we use BF-IDA* to test the tip nodes. But more importantly, we incrementally extend the perimeter towards the goal with information from the previous iteration.

Bidirectional BF-IDA* [Barker and Korf, 2012] can find an optimal solution without performing the last (most costly) iteration in which the threshold is equal to the optimal solution cost. The potential node savings are high, but the algorithm does not allow to control the memory consumption.

3 Forward Perimeter Search (FPS)

We consider shortest path search in undirected graphs with non-negative edge costs. The graph is represented implicitly by a procedure for generating the successors of a node.

Forward Perimeter Search (FPS) has two phases: It first builds a perimeter around the start node s and then tests for each perimeter node whether it lies on a shortest path from s to the goal g. The testing can be done with a variety of search algorithms. We use BF-IDA*. Both phases are executed in an iterative-deepening manner. Before starting the next iteration with a deeper search depth, the perimeter is adjusted by taking information from the preceeding iteration into account. The perimeter nodes are sorted so that a goal is found early in the last iteration.

1 We therefore named our algorithm Forward Perimeter Search.

Algorithm 1 Computing a perimeter with radius r

per i ex t end pe r ime t e r ( per i P ; node s , p ; i n t r ){ P = P \ {p} ; C = c i r c l e ( p , r ) ; foreach ( node n ∈ C) i f ( d ( s , n ) == d ( s , p ) + r ) P = P ∪ n ; return P ; }

3.1 Perimeter

Let sp(x, y) be the set of all shortest paths between x and y and let d(x, y) be the length of the shortest path(s). A perimeter is a set of nodes around a start node s such that any shortest path from s to a goal node g passes through at least one node of the perimeter.

Definition 1 (Perimeter). A set of nodes P in a graph G = (V, E) is a perimeter around s for the shortest paths between s, g ∈ V , if ∀ path ∈ sp(s, g) : path ∩ P ̸= ∅.

A perimeter P can be incrementally built from a single start node P = {s}. The function extend perimeter (Alg. 1) does this by removing a node p from a perimeter P and inserting all descendants v into P which are r steps away from p and also d(s, p) + r steps away from the start s. The distance d(s, v) can be determined with a short backward BF-IDA* search from v to the start node s. It ensures that backwards lying nodes (dashed line in Fig. 1) will not be inserted into P .

This scheme will be used to incrementally enlarge the perimeter towards the expected goal. Before describing the FPS algorithm with an adaptive radius (Sec. 3.3), we present a simpler version which uses a perimeter with fixed radius.

3.2 FPS with Fixed Radius

The simple version of the FPS algorithm builds a perimeter with a fixed radius. This is done by expanding all nodes that are r steps away from the start s as shown in the function extend perimeter in Alg. 1. When the perimeter P has been built, the search process continues in an iterativedeepening fashion. In each iteration, it tests for each node p ∈ P whether there is a path of length thresh - r from p to the goal g. If yes, we terminate the search with a shortest path of length thresh. If not, we increase thresh by the least cost δ of all paths that exceeded thresh in the last iteration.

Note that all perimeter nodes are tested in each iteration except the last. In the last iteration, the search is stopped as soon as a solution is found. We therefore sort all nodes p ∈ P so that the most promising ones will be tested first. We experimented with several sorting schemes (Sec. 4.1) and found that simple schemes such as longest path first are already close to the optimum.

The testing can be done with a wide variety of node expansion strategies: breadth-first, best-first, depth-first or breadthfirst frontier search. We used the parallel variant [Sch¨utt et al., 2011] of breadth-first iterative deepening A* (BF-IDA*) [Zhou and Hansen, 2004]. It is efficient and it never revisits a node in the same iteration.

Algorithm 2 Forward Perimeter Search (FPS)

i n t FPS ( node s , goa l ; radius r ) { i n t t h r e s h = h ( s ) ; per i P = {s }; P = ex t end pe r ime t e r (P , s , s , r ) ; whi le ( true ) { s o r t ( P ) ; foreach ( node p ∈ P) i f ( t e s t ( p , goal , t h r e s h - d ( s , p ) ) ) return t h r e s h ; foreach ( node p ∈ P ) i f ( p . t r e e s i z e > l i m i t ) P = ex t end pe r ime t e r (P , s , p , r ) ; t h r e s h = t h r e s h + δ ; } }

The size of the radius is of crucial importance for the performance and the memory consumption of FPS. The memory needed to store the perimeter nodes must be carefully balanced with the memory requirements of the test function that is started at the perimeter nodes. As we will see in Sec. 4.1 larger radii contain more perimeters nodes and need more memory space, but their smaller subtrees are beneficial for quickly finding a solution in the last iteration. Smaller radii, on the other hand, spawn larger subtrees at the perimeter nodes, which allows to eliminate more duplicates.

3.3 FPS with Adaptive Radius

It is difficult to select a suitable fixed radius without knowing the properties of the search graph. The FPS variant with an adaptive radius uses information from the previous iteration to adaptively extend the perimeter. It starts with a small perimeter and extends it (using Alg. 1) at those perimeter nodes that spawned the biggest subtrees in the last iteration. This is done with the expectancy that these nodes are more likely to lie on a shortest path and, even more important, that the final iteration is speeded up by searching a small subtree (if the sorting was good). This adaptive perimeter refinement eliminates the major weakness of BF-IDA*, namely the large amount of node expansions in the last iteration.

Fig. 1 illustrates a scenario where an initial perimeter with radius r1 was built and later extended at node p by another radius r2 around p. Note that the nodes on the dashed line should not be included in the perimeter because they are redundant and the property in Def. 1 holds without them.

Alg. 2 shows the pseudo-code of FPS with adaptive radius.

void mapper ( node n , set<node> pred ) { foreach ( succ in g e t a d j a c e n t nod e s ( n ) ) i f ( ! pred . con t a i n s ( succ ) ) i f ( g + 1 + h ( succ ) <= t h r e s h ) / / pruning emit ( succ , n ) ; } void r educe r ( node n , l i s t <node> p r e d l s t ){ set<node> pr eds = {}; foreach ( p in p r e d l s t ) pr eds . add ( p ) ; / / merge pr edece s sor s so l ved = so l ved ∨ pos == goa l ; emit ( n , pr eds ) ; } bool t e s t ( node s , goa l ; i n t t h r e s h ) { f r o n t i e r = [ ( s , {} ) ] ; g = 0 ; so l ved = f a l s e ; whi le ( ! so l ved ∧ f r o n t i e r . s i z e ( ) != 0) { i n t e rme d i a t e = map ( f r o n t i e r , mapper ) ; f r o n t i e r = reduce ( i n t e rmed i a t e , r educe r ) ; g ++ ; }return so l ved ; }

The search is started by building an initial perimeter with radius r. FPS then performs three steps in a loop:

1. It orders the perimeter nodes p ∈ P according to the information gathered in the previous iteration so that the most promising nodes are tested first.
2. It iterates over all perimeter nodes and tests whether any of them lie on a shortest path between s and g within thresh. If this is true, the search is terminated with thresh as the solution length.
3. It checks for all subtrees spawned at perimeter nodes p whether they surpassed the given memory limit. If this is the case, the radius is enlarged at this node. The size of the new radius depends on the branching factor of the graph and thus is domain dependent.

In our implementation, we store for each perimeter node: the distance to the start node, the maximum path length towards the goal, the number of expanded nodes and the widest search front in the last iteration.

3.4 Testing the Perimeter Nodes with BF-IDA*

The test function in Alg. 2 spawns the subtrees from the perimeter nodes. Many different node expansion strategies can be used for the testing. We used the parallel BF-IDA* algorithm [Sch¨utt et al., 2011] which is based on [Zhou and Hansen, 2004]. It expands all nodes of a search frontier in parallel and eliminates duplicates on-the-fly.

The parallel BF-IDA* uses the MapReduce framework [Dean and Ghemawat, 2008] for orchestrating the concurrent process execution. Alg. 3 shows the program code of test. The search space is partitioned among all processes. In each step, the map processes apply the mapper function to all nodes in the current frontier. For each node the mapper expands the successors and emits them to the next stage. Backward moves are eliminated by keeping track of the nodes' predecessors.

A global function is then used to assign the generated nodes to the reduce processes. The function (partially) sorts the nodes so that duplicates are assigned to the same reduce process. This is done with a hash function, which also provides a good load balancing over all reduce processes.

For each unique node found in its local dataset, the reducer merges the predecessors into a single set and emits the node with the joined set of predecessors. This implements the delayed duplicate elimination described in [Korf and Schultze, 2005; Zhou and Hansen, 2006]. The output of the reducer is fed as input into the next map phase until there are no more data pairs to process or a solution is found.

The described algorithm is efficient and simple to implement. The MapReduce framework orchestrates the concurrent mapper and reducer processes which iteratively expand the graph without visiting duplicates.

3.5 Reconstructing the Solution Path

At the end of the search, FPS returns only the cost of the shortest path but not the path itself. The path can be determined in two steps. First we compute the shortest path from s to the perimeter node p. This is easy because of the shallow search. Second, we determine the path from p to g which is done by recursively applying FPS. This is easier than the original problem since we know that the goal is thresh - d(s, p) moves away from p. Hence the path can determined with a direct, i.e. non-iterative, FPS search.

4 Results

We first present empirical results on the 24-puzzle and thereafter on the 17-pancake problem. FPS was run on a cluster with 32 compute nodes, each of them with 2 quad-core AMD Opteron processors and 8 GB of main memory. BF-IDA* needed for the same problem instances a much larger system with more main memory. For the hardest problem we used 256 nodes, each equipped with 2 quad-core Intel Xeon processors and 48 GB of main memory. As a heuristic estimate function, we used the same 6-6-6-6 pattern database (PDB) with mirroring as in [Korf and Felner, 2002].

For a quick overview, Table 1 lists the node expansions and memory consumption on Korf's hardest problem instance of the 24-puzzle [Korf and Felner, 2002]. The performance of IDA* and BF-IDA* is given as a reference. As expected, IDA* expands the most nodes and requires the smallest memory space. BF-IDA* expands only one fourth of the IDA* nodes, but it keeps 50 billion nodes in the main memory, which is the widest search front in the final iteration. Note that it is not feasible to solve much larger problems with BFIDA* because of its excessive memory requirements.

FPS outperforms BF-IDA* in two ways: It expands only approximately half of the nodes and, even more important, it needs far less memory-up to three orders of magnitude in this example. In the first set of experiments (lines 3-7) we used perimeters with fixed radii r = 4 . . . 18. In the second set of experiments, we used FPS with an adaptively expanded perimeter. Here, FPS decides after each iteration for each perimeter node whether it should be extended so that the given memory limit is not overrun. The memory limits are given in terms of nodes, i.e. 1 · 106 , 2 · 106 , 35 · 106 and 188 · 106 nodes respectively. We extended the radius by at least r ≥ 3 moves, depending on how much the limit was overshot in the previous iteration.

Most impressive is that fact that FPS with adaptive radius was able to solve the given problem instance on a single computer with only 8 gigabytes of main memory. BF-IDA*, in contrast, needed 256 compute nodes with several terabytes of main memory-and still expanded more nodes.

4.1 Fixed Radius

Fig. 2 compares the performance of FPS with various fixed radii to BF-IDA*. We could only run the first 40 instances of Korf's random set, because the search trees spawned by FPS with fixed radii were too large and it ran out of memory on the largest 10 instances. The graphs indicate, that FPS expands for all radii on the average only half of the BF-IDA* nodes. Note the stable improvement over all radii.

Fig. 3 illustrates that increasing the radius r yields dramatic node savings in the last iteration (× ticks), especially for r ≤ 4. But unfortunately the node savings must be paid for by extra expansions in the second to last iteration (+ ticks). This is because larger radii contain more perimeter nodes which spawn overlapping subtrees in the testing. The perimeter nodes are tested separately, and hence duplicates cannot be eliminated. In the end these two effects compensate each other (see the ∗ ticks) and radii between 4 and 6 seem to be optimal. While this result was obtained from only a single problem instance (puzzle #17), it is in accordance with the larger test set shown in Fig. 4.

Fig. 4 shows the effect of sorting the perimeter nodes. The sort function uses information from the previous threshold:

• max tree sorts the perimeter nodes in decreasing order of their subtree sizes of the previous iteration.
• longest path + max tree favors the perimeter node with the longest path (i.e. max g). In case of ties, it takes the one with the bigger subtree.
• longest path + min tree is the same as above, but takes the smaller subtree in case of ties.
• optimal ordering shows the theoretical optimum that cannot be surpassed. It is achieved when the perimeter node leading to the goal is selected first.

Interestingly, all heuristics are close to the optimum. This indicates that further refinements probably do not pay off. We used longest path + min tree in all following experiments.

It can also be concluded from Fig. 4 that FPS expands 3.5 to 4 times more nodes than A*-but with much lower memory requirements. We obtained the A* performance by counting the nodes of BF-IDA* in the pre-final iteration, i.e. all nodes with f ≤ f ∗ - δ. These nodes are in A*'s Closed list just before A* finds a goal in the optimal case.

Compared to BF-IDA*, FPS saves almost half of the node expansions-again with less memory space. The leftmost tick at radius 0 shows the performance of BF-IDA*, which is equivalent to FPS with r = 0. IDA*, which is not plotted in the figure, expands approx. 32 times more nodes.

4.2 Adaptive Radius

Table 2: Node expansions on Korf's fifty 24-puzzle instances with a 6-6-6-6 PDB. (id: Korf's Id, d: depth, r1: BFIDA*/FPS, r2: IDA*/FPS)

Table 2 lists the performance of IDA*, BF-IDA* and FPS on the fifty random puzzles. We used the same 6-6-6-6 PDB with mirroring as a heuristic function. The perimeter was extended when the widest search front in a subtree exceeded 2 · 106 nodes.

The two rightmost columns r1 and r2 show the relative overhead of BF-IDA* and IDA* compared to FPS. FPS outperforms IDA* on the average by a factor of 10 and BF-IDA* by a factor of 2 in terms of node expansions. The benefits are more pronounced in the harder problem instances.

More important than the node savings are FPS' lower memory requirements. It allowed us to run all fifty instances on a single compute node with 8 GB of main memory whereas BF-IDA* needed a compute cluster with more than a terabyte to store the widest search front.

4.3 17-Pancake Problem

As a second benchmark we used the 17-pancake problem to evaluate the performance of FPS. An N-pancake problem is a stack of N pancakes of different size [Dweighter, 1975]. To solve the problem, the pancakes must be sorted by size. The only available operation is to reverse the order of a subset of pancakes at the top of the stack. Thus, a state has N - 1 successors.

We generated ten random instances with an average solution length of 15.2 and performed a shortest path search. A PDB of the 8 topmost pancakes was used to guide the search. The results are summarized in Table 3. Compared to BFIDA*, FPS reduces the number of node expansions by a factor of 2. Additionally the widest front and thus the memory consumption is reduced by a factor of 7.

5 AHard Problem of the 24-Puzzle

Korf's fifty random instances of the 24-puzzle [Korf and Schultze, 2005] are often used as a benchmark for assessing the performance of search algorithms. Unfortunately, this set does not contain any really hard problem. As is known from the 15-puzzle, the distribution of the solution lengths of all puzzle instances gives a bell curve and hard problems are therefore unlikely to occur in a random set. Note that the hardest puzzle in Korf's set requires only 114 moves while [Karlemo et al., 2000] presented a much higher upper bound of 210.

We constructed one problem instance of the 24-puzzle that is especially hard to solve (Fig. 5). Starting with the sorted puzzle on the left side in Fig. 5, we embed the hardest 15puzzle (80 moves) into the upper left corner. We then compute the worst-case configuration for the lower fringe with a breadth-first search. Thereafter, the same is done with the right fringe. Summing up the solution lengths gives an upper bound on the moves needed to solve this particular instance.

A direct solution of the hard problem in Fig. 5 is currently not possible. However, we can give a lower (140) and an upper bound (142) which are only two moves apart. The lower bound was computed by running FPS up to threshold 138 without finding a solution. This took three months.

Table 4 shows the node expansions of FPS with a memory limit of 5·108 . In our experiments, we found the standard 6-66-6 PDB to be insufficient for solving this problem instance. Hence, we built a more powerful 8-8-8 PDB [D¨obbelin et al., 2013] which requires 122 GB memory space compared to 0.5 GB for the 6-6-6-6 PDB. Table 4 shows that the 8-8-8 PDB expands one order of magnitude fewer nodes. Even so, we were only able to run FPS up to threshold 138 without finding a solution 2 .

We computed an upper bound by recursively calling FPS on the most promising perimeter nodes as illustrated in Fig. 6. From the first perimeter p0, we picked a position t at distance 8 which looked promising according to the node ordering (4,499,126,967,518 node expansions). Since we were not able to compute the shortest path between t and g either, we again approximated the distance with the same approach (4,861,328,174,120 node expansions). We picked u from the perimeter p1 and found an optimal path of length 119 from u to g (59,165,019,511 node expansions). Hence, the upper bound from s to g is 8 + 15 + 119 = 142. This is only two moves longer than the lower bound 140 and we conclude that the optimal solution has either 140 or 142 moves which is ≥ 26 moves longer than the hardest instance in Korf's random set.

2 IDA* could not be used either, because it expands approx. 10x more nodes. This extra effort is not compensated by IDA*'s faster node handling.

6 Conclusion

We presented a heuristic search algorithm (FPS) that expands fewer nodes and requires several orders of magnitude less memory space than BF-IDA* on the 24-puzzle. This is possible by using information from the previous iteration to expand the perimeter in the direction of the expected goal. With its reduced memory consumption, FPS can be used to solve very large problems. As an example we solved the hardest 24-puzzle of the standard random benchmark set with 8 CPU cores and just 8 GB of memory-an instance for which BFIDA* needs several terabytes.

FPS is flexible in two ways: It can dynamically trade the memory used for the perimeter with memory used by the test function, and it provides a template which can be used with various test functions. In the future we will experiment with better informed pattern databases [D¨obbelin et al., 2013] to further reduce the search effort of the test function.

We additionally presented a very hard problem instance of the 24-puzzle that can be used as a challenging benchmark for heuristic search algorithms. We applied FPS to this problem and established a lower and upper bound on the solution length which are only two moves apart.