Abstract: The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.
Abstract: Recently, best-first search algorithms have been introduced that store their nodes on disk, to avoid their inherent memory limitation. We introduce several improvements to the best of these, including parallel processing, to reduce their storage and time requirements. We also present a linear-time algorithm for bijectively mapping permutations to integers in lexicographic order. We use breadth-first searches of sliding-tile puzzles as testbeds. On the 3x5 Fourteen Puzzle, we reduce both the storage and time needed by a factor of 3.5 on two processors. We also performed the first complete breadth-first search of the 4x4 Fifteen Puzzle, with over 10^(13)$ states.
Abstract: Best-first search is limited by the memory needed to store the Open and Closed lists, primarily to detect duplicate nodes. Magnetic disks provide vastly more storage, but random access of a disk is extremely slow. Instead of checking generated nodes immediately against existing nodes in a hash table, delayed duplicate detection (DDD) appends them to a file, then periodically removes the duplicate nodes using only sequential disk accesses. Frontier search saves storage in a best-first search by storing only the Open list and not the Closed list. The main contributions of this paper are to provide a scalable implementation of DDD, to combine it with frontier search, and to extend it to more general best-first searches such as A*. We illustrate these ideas by performing complete breadth-first searches of sliding-tile puzzles up to the 3x5 Fourteen Puzzle. For the 4-peg Towers of Hanoi problem, we perform complete searches with up to 20 disks, searching a space of over a trillion nodes, and discover a surprising anomaly concerning the problem-space diameter of the 15 and 20-disk problems. We also verify the presumed optimal solution lengths for up to 24 disks. In addition, we implement A* with DDD on the Fifteen Puzzle. Finally, we present a scalable implementation of DDD based on hashing rather than sorting.
Abstract: We present new results on the problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. Many simple scheduling tasks can be modelled by this NP-complete problem. We present a new lower bound on the amount of wasted space in a partial solution, a new dominance condition that prunes many partial solutions, and extend our algorithms to packing unoriented rectangles. For our experiments, we consider the set of squares of size 1x1, 2x2,...,NxN, and find the smallest rectangle that can contain them for a given value of N. While previously we solved this problem up to N=22, we extend this to N=25. Overall, our new program is over an order of magnitude faster than our previous program running on the same machine. We also show that for the larger problems, our optimal algorithm is faster than one that finds the best slicing solution, a popular approximation algorithm. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24x24 in a square of size 70x70.
Abstract: Given a set of numbers, and a set of bins of fixed capacity, the NP-complete problem of bin packing is to find the minimum number of bins needed to contain the numbers, such that the sum of the numbers assigned to each bin does not exceed the bin capacity. We present two improvements to our previous bin-completion algorithm. The first speeds up the constant factor per node generation, and the second prunes redundant parts of the search tree. The resulting algorithm appears to be asymptotically faster than our original algorithm. On problems with 90 elements, it runs over 14 times faster. Furthermore, the ratios of node generations and running times both increase with increasing problem size.
Abstract: We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.
Abstract: We analyze the time complexity of iterative-deepening-A* (IDA*). We first show how to calculate the exact number of nodes at a given depth of a regular search tree, and the asymptotic brute-force branching factor. We then use this result to analyze IDA* with a consistent, admissible heuristic function. Previous analyses relied on an abstract analytic model, and characterized the heuristic function in terms of its accuracy, but do not apply to concrete problems. In contrast, our analysis allows us to accurately predict the performance of IDA* on actual problems such as the sliding-tile puzzles and Rubik's Cube. The heuristic function is characterized by the distribution of heuristic values over the problem space. Contrary to conventional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the brute-force branching factor. Thus, the effect of a heuristic function is to reduce the effective depth of search by a constant, relative to a brute-force search, rather than reducing the effective branching factor.
Abstract: Given a set of numbers, the two-way number partitioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible. The problem is NP-complete. Based on a polynomial-time heuristic due to Karmarkar and Karp, we present a new algorithm, called Complete Karmarkar Karp (CKK), that optimally solves the general number-partitioning problem, and significantly outperforms the best previously-known algorithms for large problem instances. For numbers with twelve significant digits or less, CKK can optimally solve two-way partitioning problems of arbitrary size in practice. For numbers with greater precision, CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Over seven orders of magnitude improvement in solution quality is obtained in less than an hour of running time. Rather than building a single solution one element at a time, or modifying a complete solution, CKK constructs subsolutions, and combines them together in all possible ways. This approach may be effective for other NP-hard problems as well.
Abstract: We have found the first optimal solutions to random instances of Rubik's Cube. The median optimal solution length appears to be 18 moves. The algorithm used is iterative-deepening-A* (IDA*), with a lower-bound heuristic function based on large memory-based lookup tables, or ``pattern databases'' (Culberson and Schaeffer 1996). These tables store the exact number of moves required to solve various subgoals of the problem, in this case subsets of the individual movable cubies. We characterize the effectiveness of an admissible heuristic function by its expected value, and hypothesize that the overall performance of the program obeys a relation in which the product of the time and space used equals the size of the state space. Thus, the speed of the program increases linearly with the amount of memory available. As computer memories become larger and cheaper, we believe that this approach will become increasingly cost-effective.
Abstract: We have found the first optimal solutions to random instances of the Twenty-Four Puzzle, the 5x5 version of the well-known sliding-tile puzzles. Our new contribution to this problem is a more powerful admissible heuristic function. We present a general theory for the automatic discovery of such heuristics, which is based on considering multiple subgoals simultaneously. In addition, we apply a technique for pruning duplicate nodes in depth-first search using a finite-state machine. Finally, we observe that as heuristic search problems are scaled up, more powerful heuristic functions become both necessary and cost-effective.
Abstract: We present an improvement to Harvey and Ginsberg's limited discrepancy search algorithm, which eliminates much of the redundancy in the original, by generating each path from the root to the maximum search depth only once. For a complete binary tree of depth $d$, this reduces the asymptotic complexity from $O(\frac{d+2}{2}2^d)$ to $O(2^d)$. The savings is much less in a partial tree search, or in a heavily pruned tree. The overhead of the improved algorithm on a complete $b$-ary tree is only a factor of $b/(b-1)$ compared to depth-first search. While this constant factor is greater on a heavily pruned tree, this improvement makes limited discrepancy search a viable alternative to depth-first search, whenever the entire tree may not be searched. Finally, we present both positive and negative empirical results on the utility of limited discrepancy search, for the problem of number partitioning.
Abstract: We present a simple selective minimax search algorithm for two-player games. It always expands next the node at the end of the current best line of play, which is the node that determines the minimax value of the root. The algorithm requires no information other than a static evaluation function, and its time overhead per node is similar to that of alpha-beta minimax. On random game trees, best-first minimax outperforms alpha-beta, giving both the same amount of computation. In the game of Othello, using the evaluation function from Bill, one of the world's best programs, best-first minimax also outplays alpha-beta. We also present an implementation of the algorithm that reduces its space complexity from exponential to linear in the search depth, at the cost of increased time complexity. Finally, we present a hybrid best-first extension algorithm that combines alpha-beta and best-first minimax, and performs significantly better than either pure algorithm in both domains.
Abstract: The traveling salesman problem (TSP) is one of the best-known combinatorial optimization problems. Branch-and-Bound (BnB) is the best method for finding an optimal solution of the TSP. Previous research has shown that there exists a transition in the average computational complexity of BnB on random trees. We show experimentally that when the intercity distances of the asymmetric TSP are drawn uniformly from {0,1,2,...,r}, the complexity of BnB experiences an easy-hard transition as r increases. We also observe easy-hard-easy complexity transitions when asymmetric intercity distances are chosen from a log-normal distribution. This transition pattern is similar to one previously observed on the symmetric TSP. We then explain these different trnasition patterns by showing that the control parameter that determines the complexity is the number of distinct intercity distances.
Abstract: Search algorithms that use space linear in the search depth are widely employed in practice to solve difficult problems optimally, such as planning and scheduling. In this paper, we study the average-case performance of linear-space search algorithms, including depth-first branch-and-bound (DFBnB), iterative-deepening (ID), and recursive best-first search (RBFS). To facilitate our analyses, we use a random tree T(b,d) that has mean branching factor b, depth d, and node costs that are the sum of the costs of the edges from the root to the nodes. We prove that the expected number of nodes expanded by DFBnB on a random tree is no mmore than bd times the expected number of nodes expanded by best-first search (BFS) on the same tree, which usually requires space that is exponential in depth d. We also show that DFBnB is asymptotically optimal when BFS runs in exponential time, and ID and RBFS are asymptotically optimal when the edge costs of T(b,d) are integers. If bp is the expected number of children of a node whose costs are the same as that of their parent, then the expected number of nodes expanded by these three linear-space algorithms is exponential when bp<1, at most O(d^4) when pb=1, and at mnost quadratic when bp>1. In addition, we study the heuristic branching factor of T(b,d) and the effective branching factor of BFS, DFBnB, ID, and RBFS on T(b,d). Furthermore, we use our analytic results to explain a surprising anomaly in the performance of these algorithms, and to predict the existence of a complexity transition in the asymmetric traveling salesman problem.
Abstract: We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, involve an adversarial relationship between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired.
Abstract: We consider the case of heuristic search where the goal may change during the course of the search. For example, the goal may be a target that actively avoids the problem solver. We present a moving-target search algorithm (MTS) to solve this problem. We prove that if the average speed of the target is slower than that of the problem solver, then the problem solver is guaranteed to eventually reach the target in a connected problem space. The original MTS algorithm was constructed with the minimum operations necessary to guarantee its completeness, and hence is not very efficient. To improve its efficiency, we introduce ideas from the area of resource-bounded planning into MTS, including (1) \em commitment to goals, and (2) deliberation for selecting plans. Experimental results demonstrate that the improved MTS is 10 to 20 times more efficient than the original MTS in uncertain situations.
Abstract: Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, Dijkstra's single-source shortest-path algorithm, and the A* algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do not expand nodes in best-first order if the cost function can decrease along a path. We present a linear-space best-first search algorithm (RBFS) that always explores new nodes in best-first order, regardless of the cost function, and expands fewer nodes than iterative deepening with a nondecreasing cost function. On the sliding-tile puzzles, RBFS with a nonmonotonic weighted evaluation function dramatically reduces computation time with only a small penalty in solution cost. In general, RBFS reduces the space complexity of best-first search from exponential to linear, at the cost of only a constant factor in time complexity in our experiments.
Abstract: We present a parallel implementation of Iterative-Deepening-A*, a depth-first heuristic search, on the single-instruction, multiple-data (SIMD) Connection Machine. Heuristic search of an irregular tree represents a new application of SIMD machines. The main technical challenge is load balancing, and we explore three different techniques in combination. We also use a simple method for dynamically determining when to stop searching and start load balancing. We achieve an efficiency of 69%, for a speedup of 5685 on 8K processors, an efficiency of 64%, for a speedup of 10,435 on 16K processors, and an efficiency of 53%, for a speedup of 17,300 on 32K processors on the Fifteen Puzzle. On hard problem instances, we achieved efficiencies as high as 80%, for a speedup of 26,215 on 32K processors. Our analysis shows that work only needs to increase as PlogP to maintain constant efficiency, where P is the number of processors. This high degree of scalability was confirmed empirically for the range of 16 to 32,768 (32K) processors.
Abstract: We present a simple solution to a class of pursuit games that have become popular domains for the study of cooperative behavior in distributed artificial intelligence (DAI). In these games, a group of predators tries to surround and capture a prey. In our solution, each predator independently tries to minimize its distance to the prey, and maximize its distance to the nearest other predator. We use this example to argue that problems that appear to require complex cooperation may be solvable with much simpler approaches. In general, we view coordination as a property that emerges out of the interaction of simple agents greedily optimizing their utility functions subject to environmental constraints.
Abstract: We apply parallel window search to single-agent problems by having different processes simultaneously perform iterations of Iterative-Deepening-A* (IDA*) on the same problem but with different cost thresholds. This approeach is limited by teh time to perform the goal iteration. To overcome this disadvantage, we then consider node ordering. We discuss how global node ordering by minimum h among nodes wiht equal f=g+h values can reduce the time complexity of serial IDA* by reducing the time of the goal iteration. This approach is limited by the time to performe the iterations prior to the goal iteration. Finally, we combine the two ideas of parallel window search and node ordering to eliminate the weaknesses of each approach while retaining the strengths. The resulting approach, which we call simply parallel window search, can be used to find a near-optimal solution quickly, improve the solution until it is optimal, and then finally guarantee optimality, depending on the amount of time available.
Abstract: We consider the generalization of minimax search with alpha-beta pruning to non-cooperative, perfect-information games with more than two players. The minimax algorithm was generalized in 1986 by Luckhardt and Irani to the maxn algorithm applied to vectors of n-tuples representing the evaluations of each of the players. If we assume an upper bound on the sum of the evaluations for each player, and a lower bound on each individual evaluation, then shallow alpha-beta pruning is possible, but not deep pruning. In the best-case, the asymptotic branching factor is reduced to (1+sqrt(4b-3))/2. In the average case, however, pruning does not reduce the asymptotic branching factor. Thus alpha-beta pruning is found to be effective only in the special case of two-player games. In addition, we show that it is an optimal directional algorithm for two players.
Abstract: We propose depth-limited heuristic search as a general paradigm for real-time problem solving in a dynamic environment. When combined with iterative-deepening, it provides the ability to commit to an action almost instantaneously, but allows the quality of that decision to improve as long as time is available. Once a deadline is reached, the best decision arrived at is executed. We illustrate the paradigm in three different settings, corresponding to single-agent search, two-player games, and multi-agent problem solving. First we review two-player minimax search with alpha-beta pruning. Minimax can be extended to the {\it maxn} algorithm for more than two players, which admits a much weaker form of alpha-beta pruning. Finally, we explore real-time search algorithms for single-agent problems. Minimax is specialized to {\it minimin}, which allows a very powerful {\it alpha pruning} algorithm. In addition, {\it real-time-A*} allows backtracking while still guaranteeing a solution and making locally optimal decisions.
Abstract: We apply the two-player game assumptions of limited search horizon and commitment to moves in constant time, to single-agent heuristic search problems. We present a variation of minimax lookahead search, and an analog to alpha-beta pruning that significantly improves the efficiency of the algorithm. Paradoxically, the search horizon reachable with this algorithm increases with increasing branching factor. In addition, we present a new algorithm, called Real-Time-A*, for interleaving planning and execution. We prove that the algorithm makes locally optimal decisions and is guaranteed to find a solution. We also present a learning version of this algorithm that improves its performance over successive problem solving trials by learning more accurate heuristic values, and prove that the learned values converge to their exact values along every optimal path. These algorithms effectively solve significantly larger problems than have previously been solvable using heuristic evaluation functions.
Abstract: We propose a parallel tree search algorithm based on the idea of tree-decomposition in which different processors search different parts of the tree. This generic algorithm effectively searches irregular trees using an arbitrary number of processors without shared memory or centralized control. The algorithm is independent of the particular type of tree search, such as single-agent or two-player game, and independent of any particular processor allocation strategy. Uniprocessor depth-first and breadth-first search are special cases of this generic algorithm. The algorithm has been implemented for alpha-beta search in the game of Othello on a 32-node Hypercube multiprocessor. The number of node evaluations grows approximately linearly with the number of processors $P$, resulting in an overall speedup for alpha-beta with random node ordering of $P^{.75}$. Furthermore we present a novel processor allocation strategy, called Bound-and-Branch, for parallel alpha-beta search that achieves linear speedup in the case of perfect node ordering. Using this strategy, an actual speedup of 12 is obtained with 32 processors.
Abstract: We present the thesis that planning can be viewed as problem solving search using subgoals, macro-operators, and abstraction as knowledge sources. Our goal is to quantify problem solving performance using these sources of knowledge. New results include the identification of subgoal distance as a fundamental measure of problem difficulty, a multiplicative time-space tradeoff for macro-operators, and an analysis of abstraction which concludes that abstraction hierarchies can reduce exponential problems to linear complexity.
Abstract: The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.
Abstract: This article explores the idea of learning efficient strategies for solving problems by searching for macro-operators. A macro-operator, or macro for short, is simply a sequence of operators chosen from the primitive operators of a problem. The technique is particularly useful for problems with non-serializable subgoals, such as Rubik's Cube, for which other weak methods fail. Both a problem-solving program and a learning program are described in detail. The performance of these program is analyzed in terms of the number of macros required to solve all problem instances, the length of the resulting solutions (expressed as the number of primitive moves), and the amount of time necessary to learn the macros. In addition, a theory of why the method works, and a characterization of the range of problems for which it is useful are presented. The theory introduces a new type of problem structure called operator decomposability. Finally, it is concluded that the macro technique is a new kind of weak method, a method for learning as opposed to problem solving.
Abstract: A technique is presented for taking a program written in pure LISP and automatically deriving a program which computes the inverse function of the given program. The scheme is based on a set of rules for inverting the primitive functions plus a method of solving for variables introduced by non-invertible functions. As an example, a program to reverse a list is inverted.
Abstract: This paper presents the first steps in the development of a computer model of the process of changing representations in problem solving. The task of discovering representations that yield efficient solution strategies for problems is viewed as heuristic search in the space of representations. Two dimensions of this representation space are information structure and information quantity. Changes of representation are characterized as isomorphisms and homomorphisms, corresponding to changes of information structure and information quantity, respectively. A language for expressing representations is given. Also, a language for describing representation transformation and an interpreter for applying the transformations to representations has been developed. In addition, transformations can be automatically inverted and composed to generate new transformations. Among the example problems used to illustrate and support this model are tic-tac-toe, integer arithmetic, the Tower of Hanoi problem, the arrow puzzle, the five puzzle, the mutilated checkerboard problem, and floor plan design. The system has also been used to generate some new NP-complete problems.
Abstract: A theory of space allocation in architectural design is presented. The theory is completely independent of the shapes of the spaces. The problem is broken down into four hierarchical levels of abstraction. The top level is the number of spaces. The second level consists of the adjacencies between the spaces, represented as abstract graphs. The third level is concerned with the different planar embeddings or geometries of the adjacency graphs. The bottom level is represented by labelled bubble diagrams. At each level, the number of design alternatives is finite and it is shown how they can be systematically enumerated.