Delayed Duplicate Detection: Extended Abstract

1 Introduction: The Problem

Best-first search algorithms, such as breadth-first search (BFS), Dijkstra's algorithm [Dijkstra, 1959], and A* [Hart, Nilsson, & Raphael, 1968], store every node that is generated, in either the Open list or the Closed list. One reason for doing this is to detect duplicate nodes, and avoid expanding a state more than once. As a result, these algorithms are limited by the available memory.

In some problems, this memory limitation can be avoided by depth-first searches (DFS) such as depth­ first iterative-deepening (DFID) or iterative-deepening­ A* (IDA*) [Korf, 1985], but DFS can generate ex­ ponentially more nodes than BFS. For example, in a rectangular-grid problem space, BFS will generate O(r 2 ) nodes within a radius of r, while DFID will generate 0(3r) nodes. While there are ways of detecting some duplicate nodes in a DFS[Taylor & Korf, 1993], they do not apply to all problem spaces.

2 Frontier Search

An algorithm called frontier search[Korf, 1999; Korf & Zhang, 2000] saves only the Open list of nodes at the frontier of the search, and not the Closed list of nodes that have been expanded, thus saving some memory.

With each node, it stores a used-operator bit for each op­ erator, to indicate whether the neighboring state reached by that operator has already been generated. For exam­ ple, the sliding-tile puzzles require four such bits for each state, one for each direction in which a tile could move. When a parent node is expanded, only children that are reached via unused operators are generated, and the par­ ent node is deleted from memory. In each child node, the operator that generates the parent is marked as used. When duplicate states are found in the Open list, only one copy is kept, and any operator that is marked as used in any copy is marked as used in the retained copy. Since the closed list is not stored, reconstructing the so­ lution path requires additional work. See [Korf, 1999; Korf & Zhang, 2000] for two ways to do this.

The memory required by frontier search is propor­ tional to the maximum size of the Open list, or the width of the problem space, rather than the size of the space. For example, in the grid space mentioned above, the width of the space grows only linearly with the search radius, while the entire space grows quadratically. As another example, the width of then-disk, 3-peg Towers of Hanoi space is only 2n states, while the entire space contains 3n states. Frontier search is still limited by the memory required to store the Open list, however.

3 Delayed Duplicate Detection (DDD)

Hard disks with hundreds of gigabytes of storage are available for less than a dollar per gigabyte, which is over a hundred times cheaper than memory. Because of high latency, however, a disk behaves more like a sequential device, such as a magnetic-tape drive, with large capac­ ity and high bandwidth, but only if it is accessed se­ quentially. To quickly detect duplicate states in a search algorithm, however, nodes are usually stored in a hash table, which is designed to be accessed randomly.

Our solution to this problem is rather than checking each newly-generated node for duplicates as soon as it is generated, we append each node to a disk file containing previously generated nodes. At some point later we sort the file, thereby bringing together nodes representing the same state. Then we scan the sorted list of nodes in one pass, merging any duplicate nodes.

3.1 Breadth-First Frontier Search

As a simple example, we describe breadth-first frontier search with delayed duplicate detection. BFS is normally implemented with a FIFO queue, which we implement with two disks files, an input file and an output file. Ini­ tially, the input file contains the initial state. As we read each node in the input file, we expand it, and write its children to the output file, with no duplicate checking. When the input file is exhausted, we delete it. At that point, the output file contains all the nodes at the next depth, including any duplicate nodes. We then sort the nodes in the output file by their state representations, which brings together any duplicate nodes representing the same state. Next, we linearly scan the output file, merging duplicate nodes and ORing their used operator bits, and write one copy of each state to a new input file, deleting the output file when we're done. This completes one level of the breadth-first search. The algorithm con­ tinues until expanding the nodes in the input file doesn't generate any more nodes in the output file.

3.2 Sorting the Disk Files

Algorithms for sorting disk files are well-known. See [Garcia-Molina, Ullman, & Widom, 2000), pp. 42-48. The basic algorithm is to read as much of the unsorted file as will fit into memory, sort it in memory using quick­ sort, for example, and write the sorted portion of the file to a new subfile. Continue until the entire original file has been read and written into a set of sorted sub­ files . Then, all the sorted subfiles are merged in one pass, storing the head of each file in memory, and writing the lowest record to a final sorted output file.

3.3 DDD in Memory

Surprisingly, delayed duplicate detection is useful even when all nodes fit in memory, resulting in reduced run­ ning time due to improved cache performance. In the standard implementation of breadth-first search in mem­ ory, the Open list is stored in a hash table. As each new node is generated, it is looked up in the hash table, which often results in a cache miss, since the hash func­ tion is designed to randomly scatter the nodes. A DDD implementation doesn't use a hash table, but a single FIFO queue in memory, reading nodes off the head of the queue, and appending them to the tail. Once a level of the search is completed, the queue is sorted in mem­ ory using an algorithm such as quicksort, and the sorted queue is scanned, merging duplicate nodes. The advan­ tage of this approach is that the queue is only accessed at the head and tail, or at two points in between during quicksort, and hence most memory references will reside in cache, reducing the running time.

4 Experiments

We implemented a breadth-first search on sliding-tile puzzles, and the 4-Peg Towers of Hanoi problem.

4.1 Sliding-Tile Puzzles

[Schofield, 1967] published a complete breadth-first search of the 3 x 3 Eight puzzle. We completed a BFS for all sliding-tile puzzles up to the 2 x 7 Thirteen Puzzle. Table 1 below shows the results. The first column gives the x and y dimensions of the puzzle, and the second column gives the number of moves needed to reach all solvable states, starting with the blank in a corner posi­ tion. This is also the worst-case optimal solution length, for a goal with the blank in a corner. The third column gives the number of solvable states, which is (xy)!/2, and the fourth column gives the width of the problem space, which is the maximum number of nodes at any depth.

The 3 x 4 and 2 x 6 Eleven Puzzles were the largest that we could solve in memory. We implemented both a standard BFS algorithm, using one bit of memory per state, and also breadth-first frontier search with delayed duplicate detection. The standard BFS required 17.5 minutes, while the frontier search with DDD required only 9.6 minutes, on a 440 Megahertz Sun Ultra 10 work­ station. This demonstrates that DDD frontier search is useful even for problems that fit in memory.

The 2 x 7 Fourteen Puzzle was the largest we could search exhaustively with our 120 gigabyte disk. At 8 bytes per state, this problem required about 15 gigabytes of disk storage, and ran for 51 hours, 13 minutes. The ratio of the problem size to the problem width is about 23.4, illustrating the advantage of frontier search.

4.2 Towers of Hanoi

For the standard 3-peg Towers of Hanoi problem, there is a simple algorithm that guarantees the shortest path between any pair of states. The 4-peg Towers of Hanoi puzzle, known as Reve's puzzle, is much more interest­ ing. There exists a algorithm for finding a solution, and a conjecture that it generates optimal solutions, but the conjecture remains unproven. [van de Liefvoort, 1992] contains a good bibliography for this problem. [Szegedy, 1999] gives bounds for the k-peg version, but they in­ clude an unspecified constant in the exponent.

For the sliding-tile puzzles, all paths between any pair of states have the same even-odd parity, and the algo­ rithm described in Section 3.1 works correctly. For the Towers of Hanoi, however, two states can have both even and odd length paths between them. In that case, fron­ tier search with delayed duplicate detection can fail by leaking into the interior of the search. One solution to this problem is to store two complete levels of the search at a time. See our full paper for the details [Korf, 2003] .

Using this algorithm, we were able to exhaustively search all problems through 18 disks, starting with all disks on one peg. Table 2 shows the results. The first column gives the number of disks, and the second col­ umn shows the minimum number of moves required to move all the disks from one peg to another. The third column gives the total number of states of the problem, which is 4n, where n is the number of disks. The fourth column shows the maximum width of the graph, starting from a state with all disks on one peg. In all cases, the optimal number of moves equals the conjectured mini­ mal number of moves. The 18-disk problem took almost 6 days to run, and at 8 bytes per state required about 30 gigabytes of disk space. Note that the ratio of the total number of states to the problem width for the 18-disk problem is almost 34.5.

5 Conclusions and Further Work

We showed that delaying the detection of duplicate nodes in a breadth-first search can effectively make use of very large capacity disk-storage systems. We also showed how to combine this idea with frontier search. In addition, we demonstrated that these ideas can also speed up a search that occurs entirely in memory. Using these algorithms, we completed breadth-first searches of sliding-tile puzzles with up to 43 billion nodes, and 4-peg Towers of Hanoi problems with up to 68 billion nodes. For the 4-peg Towers of Hanoi, we verified a conjecture regarding optimal solution lengths to 18 disks.

Current work is focussed on implementing these tech­ niques for more complex best-first search algorithms such as Dijkstra's algorithm [Dijkstra, 1959] and A* [Hart, Nilsson, & Raphael, 1968].

6 Acknowledgments

Larry Taylor brought the 4-Peg Towers of Hanoi problem to my attention, and also used disk storage in a breadth­ first search to find duplicate operator strings [Taylor & Korf, 1993]. Thanks to Jianming He for verifying the Towers of Hanoi results. This research was supported by NSF under grant No. EIA-0113313, by NASA and JPL under contract No. 1229784, and by the State of California MICRO grant No. 01-044.

References

[Dijkstra, 1959] Dijkstra, E. 1959. A note on two prob­ lems in connexion with graphs. Numerische Mathe­ matik 1:269- 271.

[Garcia-Molina, Ullman, & Widom, 2000] Garcia-Molina, H.; Ullman, J. D.; and Widom, J. 2000. Database System Implementation. Upper Saddle River, N.J.: Prentice-Hall.

[Hart, Nilsson, & Raphael, 1968] Hart, P.; Nilsson, N.; and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Science and Cybernetics SSC-4(2):100-107.

[Korf & Zhang, 2000] Korf, R., and Zhang, W. 2000. Divide-and-conquer frontier search applied to opti­ mal sequence alignment . In Proceedings of the Na­ tional Conference on Artificial Intelligence (AAAI2000}, 910-916.

[Korf, 1985] Korf, R. 1985. Depth-first iterativedeepening: An optimal admissible tree search. Ar­ tificial Intelligence 27(1):97-109.

• [Korf, 1999] Korf, R. 1999. Divide-and-conquer bidi­ rectional search: First results. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99 ), 1184-1189.

[Korf, 2003] Korf, R. 2003. Delayed duplicate detection: initial results. In Proceedings of the IJCAI-03 Work­ shop on Model Checking and Artificial Intelligence.

[Schofield, 1967] Schofield, P. 1967. Complete solution of the eight puzzle. In Meltzer, B., and Michie, D., eds., Machine Intelligence 3. New York: American El­ sevier. 125-133.

[Szegedy, 1999] Szegedy, M. 1999. In how many steps the k peg version of the towers of hanoi game can be solved? In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STAGS '99}, LNCS 1563. Trier, Germany: Springer-Verlag.

[Taylor & Korf, 1993] Taylor, L., and Korf, R. 1993. Pruning duplicate nodes in depth-first search. In Pro­ ceedings of the National Conference on Artificial In­ telligence (AAAI-93}, 756- 761.

[van de Liefvoort, 1992] van de Liefvoort, A. 1992. An iterative algorithm for the reve's puzzle. The Com­ puter Journal35(1):91-92.

A Portfolio Approach to Algorithm Selection

Kevin Leyton-Brown and Eugene Nudelman and Galen Andrew and Jim McFadden and Yoav Shoham {kevinlb;eugnud;galand;jmcf;shoham}@cs.stanford.edu, Stanford University, Stanford CA 94305

1 Introduction

Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, it is often the case that different algorithms perform well on dif­ ferent problem instances. Not surprisingly, this phenomenon is most pronounced among algorithms for solving NP-Hard problems, because runtimes for these algorithms are often highly variable from instance to instance. When algorithms exhibit high runtime variance, one is faced with the problem of deciding which algorithm to use; in 1976 Rice dubbed this the "algorithm selection problem" [8]. In the nearly three decades that have followed, the issue of algorithm selection has failed to receive widespread attention, though of course some excellent work does exist. By far, the most common approach to algorithm selection has been to measure different algorithms' performance on a given problem distribution, and then to use only the algorithm having the lowest average run­ time. This "winner-take-all" approach has driven recent ad­ vances in algorithm design and refinement, but has resulted in the neglect of many algorithms that, while uncompetitive on average, may offer excellent performance on particular prob­ lem instances. Our consideration of the algorithm selection literature, and our dissatisfaction with the winner-take-all ap­ proach, has led us to ask the following two questions. First, what general techniques can we use to perform per-instance (rather than per-distribution) algorithm selection? Second, once we have rejected the notion of winner-take-all algorithm evaluation, how ought novel algorithms to be evaluated? We offer the following answers:

1. Algorithms with high average running times can be com­ bined to form an algorithm portfolio with low average running time when the algorithms' easy inputs are suffi­ ciently uncorrelated.
2. New algorithm design should focus on problems on which the current algorithm portfolio performs poorly.

Readers familiar with the boosting paradigm in machine learning [9] will recognize that boosting uses similar ideas: combining weak classifiers into a much stronger ensemble by iteratively training new classifiers on data on which the ensemble performs poorly.

2 Algorithm Portfolios

In our previous work [6] we demonstrated that statistical re­ gression can be used to learn surprisingly accurate algorithm­ specific models of the empirical hardness of given distribu­ tions of problem instances. In short, the method proposed in that work is:

Figure 3: Selected

1. Use domain knowledge to select features of problem in­ stances that might be indicative of runtime.
2. Generate a set of problem instances from the given dis­ tribution, and collect runtime data for the algorithm on each instance.
3. Use regression to learn a real-valued function of the fea­ tures that predicts runtime.

Given this existing technique for predicting runtime, we now propose building portfolios of multiple algorithms as fol­ lows:

1. Train a model for each algorithm, as described above.
2. Given an instance:
3. (a) Compute feature values
4. (b) Predict each algorithm's running time
5. (c) Run the algorithm predicted to be fastest

2.1 WDP Case Study: Past Work

Our case study is based on the data collected in our previous work [6]. In that work we have constructed models for pre­ dicting the running time of the CPLEX solver on the winner determination problem (WDP), which is an NP-Complete combinatorial optimization problem formally equivalent to weighted set-packing. We have also created models for two other WDP algorithms: GL (Gonen-Lehmann) [3], a simple branch-and-bound algorithm with CPLEX's LP solver as its heuristic, and CASS [!], a more complex branch-and-bound algorithm with a non-LP heuristic. The data set consists of 4500 instances of a fixed size (256 goods and 1000 non­ dominated bids), sampled uniformly from CATS [7] instance generator. Since our methodology relies on machine learning, we split the data into training, validation, and test sets. We re­ port our portfolio runtimes only on the test set that was never used to train or evaluate models. Runtime data was collected on 550 MHz Pentium Xeons, running Linux 2.2.

2.2 WDP Case Study: Portfolios

We now describe new results. Fig. 1 compares the average runtimes of our three algorithms to that of the portfolio. Note that CPLEX would be chosen under winner-take-all algo­ rithm selection. The "optimal" bar shows the performance of an ideal portfolio where algorithm selection is performed per­ fectly and with no overhead. The portfolio bar shows the time taken to compute features (light portion) and the time taken to run the selected algorithm (dark portion). Despite the fact that CASS and GL are much slower than CPLEX on average, the portfolio outperforms CPLEX by more than a factor of 3. Further, neglecting the cost of computing features, our port­ folio's selections take only 5% longer to run than the optimal selections. Figs. 2 and 3 show the frequency with which each algorithm is selected in the ideal portfolio and in our portfo­ lio. They illustrate the quality of our algorithm selection and the relative value of the three algorithms. While our portfo­ lio does not always make the right choice, most of the mis­ takes occur when algorithms have very similar running times. These mistakes are not very costly, which explains why our portfolio's choices have a running time so close to optimal. These results show that our portfolio methodology can work very well even with a small number of algorithms, and even when one algorithm has superior average performance.

3 Focused Algorithm Design

Once it has been decided to select algorithms from a portfo­ lio on a per-instance basis, it is necessary to reexamine the way we design and evaluate algorithms. Since the purpose of designing new algorithms is to reduce the time that it will take to solve problems, designers should aim to produce new algorithms that complement an existing portfolio given a dis­ tribution D reflecting problems that will be encountered in practice. The instances with the greatest potential for im­ provement will be hard for the portfolio, common in D, or both. The full version of this paper describes a technique for using rejection sampling to automatically generate such in­ stances. In Figures 4 and 5 we show how our techniques are able to automatically skew two of the easiest CATS instance distributions towards harder regions. In fact, for these two distributions we generated instances that were (respectively) I 00 and 50 times harder than anything we had previously seen! Moreover, the average runtime for the new distribu­ tions was greater than the observed maximum running time on the original distribution.

Figure 5: Scheduling

4 Conclusions

Learned runtime models may be used to create algorithm portfolios that outperform their constituent algorithms. These models can also be used to induce harder benchmark distri­ butions for use in the development and evaluation of new al­ gorithms. Our case study on combinatorial auctions demon­ strates that a portfolio composed of CPLEX and two older­ and generally much slower-algorithms outperforms CPLEX alone by about a factor of 3. In the full version of this paper we describe our methodology in more detail, and also:

• Show how to reduce the time spent computing features without substantially degrading portfolio performance;
• Demonstrate ways of using response variable transfor­ mations to focus portfolios on metrics other than average running time;
• Explain how to induce distributions with characteristics other than hardness (e.g. realism);
• Compare our approach to previous work that executes algorithms in parallel [2]; uses classification instead of regression [4]; or considers the problem as an MDP [5] .