Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
SoCS Conference 2022 Conference Paper
The classic jeep problem concerns crossing a desert wider than the range of the jeep, by preplacing caches of fuel. The optimal strategy for a given distance is known, but we consider the case where we don
AAAI Conference 2022 Conference Paper
We present a new algorithm called A*+BFHS for solving problems with unit-cost operators where A* and IDA* fail due to memory limitations and/or the existence of many distinct paths between the same pair of nodes. A*+BFHS is based on A* and breadth-first heuristic search (BFHS). A*+BFHS combines advantages from both algorithms, namely A*’s node ordering, BFHS’s memory savings, and both algorithms’ duplicate detection. On easy problems, A*+BFHS behaves the same as A*. On hard problems, it is slower than A* but saves a large amount of memory. Compared to BFIDA*, A*+BFHS reduces the search time and/or memory requirement by several times on a variety of planning domains.
SoCS Conference 2022 Conference Paper
Breadth-first heuristic search (BFHS) is a classic algorithm for optimally solving heuristic search and planning problems. BFHS is slower than A* but requires less memory. However, BFHS only works on unit-cost domains. We propose a new algorithm that extends BFHS to domains with different edge costs, which we call uniform-cost heuristic search (UCHS). Experimental results show that the iterative-deepening version of UCHS, IDUCHS, is slower than A* but requires less memory on a variety of planning domains.
SoCS Conference 2021 Conference Paper
The diameter of a graph is the longest shortest path between two nodes. This paper presents an improved algorithm for finding the exact diameter of an undirected graph. Rather than performing complete breadth-first searches, these searches can be terminated early. The algorithm is readily parallelized, and is used to find the diameters of 4-peg Tower of Hanoi problem-space graphs with up to 18 discs. Performance improvements range from a factor of almost 2 to 5. 88 over the previous state of the art.
IJCAI Conference 2019 Conference Paper
We present a simple combination of A* and IDA*, which we call A*+IDA*. It runs A* until memory is almost exhausted, then runs IDA* below each frontier node without duplicate checking. It is widely believed that this algorithm is called MREC, but MREC is just IDA* with a transposition table. A*+IDA* is the first algorithm to run significantly faster than IDA* on the 24-Puzzle, by a factor of almost 5. A complex algorithm called dual search was reported to significantly outperform IDA* on the 24-Puzzle, but the original version does not. We made improvements to dual search and our version combined with A*+IDA* outperforms IDA* by a factor of 6. 7 on the 24-Puzzle. Our disk-based A*+IDA* shows further improvement on several hard 24-Puzzle instances. We also found optimal solutions to a subset of random 27 and 29-Puzzle problems. A*+IDA* does not outperform IDA* on Rubik’s Cube, for reasons we explain.
IJCAI Conference 2016 Conference Paper
We compare sorting and hashing for implicit graph search using disk storage. We first describe efficient pipelined implementations of both algorithms, which reduce disk I/O. We then compare the two algorithms and find that hashing is faster, but that sorting requires less disk storage. We also compare disk-based with in-memory search, and surprisingly find that there is little or no time overhead associated with disk-based search. We present experimental results on the sliding-tile puzzles, Rubik's Cube, and the 4-peg Towers of Hanoi.
SoCS Conference 2014 Conference Paper
Algorithm design and implementation are notoriously error-prone. As researchers, it is incumbent upon us to maximize the probability that our algorithms, their implementations, and the results we report are correct. In this position paper, I argue that the main technique for doing this is confirmation of results from multiple independent sources, and provide a number of concrete suggestions for how to achieve this in the context of combinatorial search algorithms.
IJCAI Conference 2013 Conference Paper
The bin-packing problem is to partition a multiset of n numbers into as few bins of capacity C as possible, such that the sum of the numbers in each bin does not exceed C. We compare two existing algorithms for solving this problem: bin completion (BC) and branch-and-cut-and-price (BCP). We show experimentally that the problem difficulty and dominant algorithm are a function of n, the precision of the input elements and the number of bins in an optimal solution. We describe three improvements to BC which result in a speedup of up to five orders of magnitude as compared to the original BC algorithm. While the current belief is that BCP is the dominant bin-packing algorithm, we show that improved BC is up to five orders of magnitude faster than a state-of-the-art BCP algorithm on problems with relatively few bins. We then explore a closely related problem, the number-partitioning problem, and show that an algorithm based on improved bin packing is up to three orders of magnitude faster than a BCP solver called DIMM which claims to be state of the art. Finally, we show how to use number partitioning to generate difficult binpacking instances.
ICAPS Conference 2013 Conference Paper
Given a set of n different jobs, each with an associated running time, and a set of k identical machines, our task is to assign each job to a machine to minimize the time to complete all jobs. In the OR literature, this is called identical parallel machine scheduling, while in AI it is called number partitioning. For eight or more machines, an OR approach based on bin packing appears best, while for fewer machines, a collection of AI search algorithms perform best. We focus here on scheduling up to seven machines, and make several new contributions. One is a new method that significantly reduces duplicate partitions for all values of k, including k = 2. Another is a new version of the Complete-Karmarkar-Karp (CKK) algorithm that minimizes the makespan. A surprising negative result is that dynamic programming is not competitive for this problem, even for k = 2. We also explore the effect of precision of values on the choice of the best algorithm. Despite the simplicity of this problem, a number of different algorithms have been proposed, and the most efficient algorithm depends on the number of jobs, the number of machines, and the precision of the running times.
IJCAI Conference 2011 Conference Paper
The number partitioning problem is to divide a given set of N positive integers into K subsets, so that the sum of the numbers in each subset are as nearly equal as possible. While effective algorithms for two-way partitioning exist, multi-way partitioning is much more challenging. We introduce an improved algorithm for optimal multi-way partitioning, by combining several existing algorithms with some new extensions. We test our algorithm for partitioning 31-bit integers from three to ten ways, and demonstrate orders of magnitude speedup over the previous state of the art.
SoCS Conference 2011 Conference Paper
The rectangle-packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our new benchmark includes rectangles of successively higher precision, a problem for the previous state-of-the-art, which enumerates all locations for placing rectangles. We instead limit these locations and bounding box dimensions to the set of subset sums of the rectangles
SoCS Conference 2010 Conference Paper
The number partitioning problem is to divide a set of integers into a collection of subsets, so that the sum of the numbers in each subset are as nearly equal as possible. There are at least three natural objective functions for number partitioning. One is to minimize the largest subset sum, another is to maximize the smallest subset sum, and the third is to minimize the difference between the largest and smallest subset sums. I show that contrary to my previous claims, no two of these objective functions are equivalent for partitioning numbers three or more ways. Minimizing the largest subset sum or maximizing the smallest subset sum correspond to different practical applications of number partitioning, and both allow a recursive strategy for finding optimal solutions that is very effective in practice. Finally, a completely new version of this recursive strategy appears to reduce the asymptotic complexity of the algorithm, and results in orders of magnitude improvement over the best previous results for multi-way partitioning.
IJCAI Conference 2009 Conference Paper
The rectangle packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our algorithm picks the x-coordinates of all the rectangles before picking any of the y-coordinates. For the x-coordinates, we present a dynamic variable ordering heuristic and an adaptation of a pruning algorithm used in previous solvers. We then transform the rectangle packing problem into a perfect packing problem that has no empty space, and present inference rules to reduce the instance size. For the y-coordinates we search a space that models empty positions as variables and rectangles as values. Our solver is over 19 times faster than the previous state-of-the-art on the largest problem solved to date, allowing us to extend the known solutions for a consecutive-square packing benchmark from N=27 to N=32.
IJCAI Conference 2009 Conference Paper
The number partitioning problem is to divide a given set of integers into a collection of subsets, so that the sum of the numbers in each subset are as nearly equal as possible. While a very efficient algorithm exists for optimal two-way partitioning, it is not nearly as effective for multi-way partitioning. We develop two new linear-space algorithms for multi-way partitioning, and demonstrate their performance on three, four, and five-way partitioning. In each case, our algorithms outperform the previous state of the art by orders of magnitude, in one case by over six orders of magnitude. Empirical analysis of the running times of our algorithms strongly suggest that their asymptotic growth is less than that of previous algorithms. The key insight behind both our new algorithms is that if an optimal k-way partition includes a particular subset, then optimally partitioning the numbers not in that set k−1 ways results in an optimal k-way partition.
IJCAI Conference 2009 Conference Paper
Depth-first search is effective at solving hard combinatorial problems, but if the problem space has a graph structure the same nodes may be searched many times. This can increase the size of the search exponentially. We explore two techniques that prevent this: duplicate detection and duplicate avoidance. We illustrate these techniques on the treewidth problem, a combinatorial optimization problem with applications to a variety of research areas. The bottleneck for previous treewidth algorithms is a large memory requirement. We develop a duplicate avoidance technique for treewidth and demonstrate that it significantly outperforms other algorithms when memory is limited. Additionally, we are able to find, for the first time, the treewidth of several hard benchmark graphs.
AAAI Conference 2008 Conference Paper
We present a breadth-first search algorithm, two-bit breadthfirst search (TBBFS), which requires only two bits for each state in the problem space. TBBFS can be parallelized in several ways, and can store its data on magnetic disk. Using TBBFS, we perform complete breadth-first searches of the original pancake problem with 14 and 15 pancakes, and the burned pancake problem with 11 and 12 pancakes, determining the diameter of these problem spaces for the first time. We also performed a complete breadth-first search of the subspace of Rubik’s Cube determined by the edge cubies.
IJCAI Conference 2007 Conference Paper
We integrate a number of new and recent advances in heuristic search, and apply them to the four-peg Towers of Hanoi problem. These include frontier search, disk-based search, parallel processing, multiple, compressed, disjoint, and additive pattern database heuristics, and breadth-first heuristic search. New ideas include pattern database heuristics based on multiple goal states, a method to reduce coordination among multiple parallel threads, and a method for reducing the number of heuristic calculations. We perform the first complete breadth-first searches of the 21 and 22-disc four-peg Towers of Hanoi problems, and extend the verification of "presumed optimal solutions" to this problem from 24 to 30 discs. Verification of the 31-disc problem is in progress.
AAAI Conference 2007 Conference Paper
We introduce a model for predicting the performance of IDA* using pattern database heuristics, as a function of the branching factor of the problem, the solution depth, and the size of the pattern databases. While it is known that the larger the pattern database, the more efficient the search, we provide a quantitative analysis of this relationship. In particular, we show that for a single goal state, the number of nodes expanded by IDA* is a fraction of (logb s + 1)/s of the nodes expanded by a brute-force search, where b is the branching factor, and s is the size of the pattern database. We also show that by taking the maximum of at least two pattern databases, the number of node expansions decreases linearly with s compared to a brute-force search. We compare our theoretical predictions with empirical performance data on Rubik’s Cube. Our model is conservative, and overestimates the actual number of node expansions.
AAAI Conference 2005 Conference Paper
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 1013 states.
AAAI Conference 2004 Conference Paper
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.
ICAPS Conference 2004 Conference Paper
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.
IJCAI Conference 2003 Conference Paper
Best-first search is limited by the memory needed to store nodes in order to detect duplicates. Disks can greatly expand the amount of storage available, but randomly accessing a disk is impractical. Rather than checking newlygenerated nodes as soon as they are generated, we append them to a disk file, then sort the file, and finally scan the sorted file in one pass to detect and remove duplicate nodes. This also speeds up such searches that fit entirely in memory, by improving cache performance. We implement this idea for breadth-first search, performing the first complete searches of the 2 x 7 sliding-tile puzzle, and the 18-disk, 4-peg Towers of Hanoi puzzle.
ICAPS Conference 2003 Conference Paper
Given a set of rectangles with fixed orientations, we want to find an enclosing rectangle of minimum area that contains them all with no overlap. Many simple scheduling tasks can be modelled by this NP-complete problem. We use an anytime branch-and-bound algorithm to solve the problem optimally. Our main contributions are a lower-bound on the amount of wasted space in a partial solution, based on a relaxation of the problem to one-dimensional bin packing, and a dominance condition that allows us to ignore many partial solutions. For our experiments, we choose a class of increasingly difficult square-packing problems as a simple and easily-specified benchmark. The square-packing problem of size N is to find the smallest rectangle that contains the 1x1, 2x2, etc. up to NxN square. We find optimal solutions to these problems up to size N=22. For comparison, we also find the best slicing solutions, a popular approximation algorithm. Our approach is rather general, and many of our techniques can be applied to packing non-rectangular shapes in non-rectangular enclosing regions, and higher-dimensional packing problems as well.
AAAI Conference 2002 Conference Paper
We consider the NP-complete problem of bin packing. Given a set of numbers, and a set of bins of fixed capacity, find the minimum number of bins needed to contain all the numbers, such that the sum of the numbers assigned to each bin does not exceed the bin capacity. We present a new algorithm for optimal bin packing. Rather than considering the different bins that each number can be placed into, we consider the different ways in which each bin can be packed. Our algorithm appears to be asymptotically faster than the best existing optimal algorithm, and runs more that a thousand times faster on problems with 60 numbers.
AIJ Journal 2002 Journal Article
We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases [J. Culberson, J. Schaeffer, Comput. Intelligence 14 (3) (1998) 318–334]. 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.
AIJ Journal 2001 Journal Article
AIJ Journal 2001 Journal Article
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.
AAAI Conference 2000 Conference Paper
We present a new algorithm that reduces the space complexity of heuristic search. It is most effective for problem spaces that grow polynomially with problem size, but contain large numbers of short cycles. For example, the problem of finding an optimal global alignment of several DNA or amino-acid sequences can be solved by finding a lowest-cost corner-tocorner path in a d-dimensional grid. A previous algorithm, called divide-and-conquer bidirectional search (Korf 1999), saves memory by storing only the Open lists and not the Closed lists. We show that this idea can be applied in a unidirectional search as well. This extends the technique to problems where bidirectional search is not applicable, and is more efficient in both time and space than the bidirectional version. If n is the length of the strings, and d is the number of strings, this algorithm can reduce the memory requirement from O(nd) to O(nd 1 ). While our current implementation of DCFS is somewhat slower than existing dynamic programming approaches for optimal alignment of multiple gene sequences, DCFS is a more general algorithm.
IJCAI Conference 1999 Conference Paper
We present a new algorithm to reduce the space complexity of heuristic search. It is most effective for problem spaces that grow polynomially with problem size, but contain large numbers of short cycles. For example, the problem of finding a lowest-cost corner-to-corner path in a d-dimensional grid has application to gene sequence alignment in computational biology. The main idea is to perform a bidirectional search, but saving only the Open lists and not the Closed lists. Once the search completes, we have one node on an optimal path, but don't have the solution path itself. The path is then reconstructed by recursively applying the same algorithm between the initial node and the intermediate node, and also between the intermediate node and the goal node. If n is the length of the grid in each dimension, and d is the number of dimensions, this algorithm reduces the memory requirement from to The time complexity only increases by a constant factor of in two dimensions, and 1. 8 in three dimensions.
AIJ Journal 1998 Journal Article
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.
AAAI Conference 1998 Conference Paper
Weanalyze the asymptotic time complexity of admissible heuristic search algorithms such as A*, IDA*, and depth-first branch-and-bound. Previous analyses relied on an abstract analytical model, and characterize the heuristic function in terms of its accuracy, but do not apply to real problems. In contrast, our analysis allows us to accurately predict the performance of these algorithms on problems such as the slidingtile puzzles and l~ubik’s Cube. Theheuristic function is characterized simply by the distribution of heuristic values in the problemspace. Contrary to conventional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the bruteforce branchingfactor, and that the effect of a heuristic function is to reduce the effective depth of search, rather than the effective branching factor.
AIJ Journal 1996 Journal Article
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 transition patterns by showing that the control parameter that determines the complexity is the number of distinct intercity distances.
AIJ Journal 1996 Journal Article
We describe a very simple selective search algorithm for two-player games, called best-first minimax. It always expands next the node at the end of the expected line of play, which determines the minimax value of the root. It uses the same information as alpha-beta minimax, and takes roughly the same time per node generation. We present an implementation of the algorithm that reduces its space complexity from exponential to linear in the search depth, but at significant time cost. Our actual implementation saves the subtree generated for one move that is still relevant after the player and opponent move, pruning subtrees below moves not chosen by either player. We also show how to efficiently generate a class of incremental random game trees. On uniform random game trees, best-first minimax outperforms alpha-beta, when both algorithms are given the same amount of computation. On random trees with random branching factors, best-first outperforms alpha-beta for shallow depths, but eventually loses at greater depths. We obtain similar results in the game of Othello. Finally, we present a hybrid best-first extension algorithm that combines alpha-beta with best-first minimax, and performs significantly better than alpha-beta in both domains, even at greater depths. In Othello, it beats alpha-beta in two out of three games.
AAAI Conference 1996 Conference Paper
We have found the first optimal solutions to random instances of the Twenty-Four Puzzle, the 5 x 5 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 finitestate machine. Finally, we observe that as heuristic search problems are scaled up, more powerful heuristic functions become both necessary and cost-effective. I I I I I IO 11 12 13 14
AAAI Conference 1996 Conference Paper
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((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.
AIJ Journal 1995 Journal Article
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 more 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 0 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 o < 1, at most O(d 4) when bp 0 = 1, and at most quadratic when bp 0 > 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.
AAAI Conference 1994 Conference Paper
We present a very simple selective search algorithm for two-player games. It always expands next the frontier 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. 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. In the game of Othello, using the evaluation function from BiIl (Lee & Mahajan 1990), bestfirst minimax outplays alpha-beta at moderate depths. A hybrid best-first extension algorithm, which combines alpha-beta and best-first minimax, performs significantly better than either pure algorithm even at greater depths. Similar results were also obtained for a class of random game trees.
ICAPS Conference 1994 Conference Paper
Wepropose incremental, real-time search as a general approach to real-time decision making. Wemodel real-time decision makingas incremental tree search with a limited numberof node expansions betweendecisions. Weshowthat the decision policy of moving towardthe best frontier node is not optimal, but nevertheless performsnearly as well as an expected-valuebased decision policy. Wealso showthat the real-time constraint causesdifficulties for traditional best-first search algorithms. Wethen present a new approach that uses a separate heuristic function for choosing where to explore and which decision to make. Empirical results for randomtrees showthat our newalgorithm outperformsthe traditional best-first search approach to real-time decision making, and that depthfirst branch-and-boundperforms nearly as well as the morecomplicatedbest-first variation.
AIJ Journal 1993 Journal Article
We present a parallel implementation of Iterative-Deepening-A∗, a depth-first heuristic search, on the single-instruction, multiple-data (SIMD) Connection Machine ★ ★ Connection Machine is a trademark of Thinking Machines Corporation. . 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 indicates that work only needs to increase as P log P 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.
AIJ Journal 1993 Journal Article
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.
AAAI Conference 1992 Conference Paper
Best-first search is a general search algorithm that, always expands next a frontier node of lowest cost. Its applicability, however, is limited by its exponential memory requirement. Iterative deepening, a previous approach to this problem, does not expand nodes in best-first, order if t’ he 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 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, a. t the cost of only a constant factor in time complexity in our expcriments.
AIJ Journal 1991 Journal Article
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 [2] to the maxn algorithm applied to vectors of n-tuples representing the evaluations for 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 + √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.
AIJ Journal 1990 Journal Article
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.
IJCAI Conference 1989 Conference Paper
We show how node ordering can be combined with parallel window search to quickly find a nearly optimal solution to single-agent problems. First, we show how node ordering by maximum g among nodes with equal / = g + h values can improve the performance of IDA*. We then consider a window search where different processes perform IDA* simultaneously on the same problem but with different cost thresholds. Finally, we combine the two ideas to produce a parallel window search algorithm in which node ordering information is shared among the different processes. Parallel window search can be used to find a nearly optimal solution quickly, improve the solution until it is optimal, and then finally guarantee optimality, depending on the amount of time available.
AIJ Journal 1987 Journal Article
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.
AAAI Conference 1987 Conference Paper
Existing heuristic search algorithms are not applicable to real-time applications because they cannot commit to a move before an entire solution is found. We present a special case of minimax lookahead search to handle this problem, and an analog of alpha-beta pruning that significantly improves the efficiency of the algorithm. In addition, we present a new algorithm, called Real-Time-A*, for searching when actions must actually be executed, as opposed to merely simulated. Finally, we examine the nature of the tradeoff between computation and execution cost.
AIJ Journal 1985 Journal Article
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.
AIJ Journal 1985 Journal Article
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 programs 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.
AAAI Conference 1983 Conference Paper
This paper describes a structural property of problems that allows an efficient strategy for solving a large number of problem instances to be based on a small amount of knowledge. Specifically, the property of operator decomposability is shown to be a sufficient condition for the effective application of the Macro Problem Solver, a method that represents its knowledge of a problem by a small number of operator sequences. Roughly, operator decomposability exists in a problem to the extent that the effect of an operator on each component of a state can be expressed as a function of only a subset of the components, independent of the remaining state components.
AAAI Conference 1982 Conference Paper
This paper describes a program which learns efficient strategies for solving problems such as Rubik’s cube and the eight puzzle. It uses a new general problem solving method based on macro-operators. The strategies learned by the program are equal to or superior to strategies used by humans on these problems, in terms of number of moves required for solution.
AIJ Journal 1980 Journal Article
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 transformations 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.