One popular and efficient scheme for solving exactly combinatorial optimization problems over graphical models is depth-first Branch and Bound. However, when the algorithm exploits problem decomposition using AND/OR search spaces, its anytime behavior breaks down. This paper 1) analyzes and demonstrates this inherent conflict between effective exploitation of problem decomposition (through AND/OR search spaces) and the anytime behavior of depth-first search (DFS), 2) presents a first scheme to address this issue while maintaining desirable DFS memory properties, 3) analyzes and demonstrates its effectiveness. Our work is applicable to any problem that can be cast as search over an AND/OR search space.

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given cost bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the ``discretization effect''. Second, we disprove the intuitively appealing idea that a ``more informed'' prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in several of our experiments the more informed system makes poorer predictions. Our third contribution is a method, called ``$\epsilon$-truncation'', which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments $\epsilon$-truncation rarely degraded predictions; in the vast majority of cases it improved predictions, often substantially.

Classical heuristic search algorithms find the solution cost of a problem while finding the path from the start state to a goal state. However, there are applications in which finding the path is not needed. In this paper we propose an algorithm that accurately and efficiently predicts the solution cost of a problem without finding the actual solution. We show empirically that our predictor makes more accurate predictions when compared to the bootstrapped heuristic, which is known to be a very accurate inadmissible heuristic. In addition, we show how our prediction algorithm can be used to enhance heuristic search algorithms. Namely, we use our predictor to calculate a bound for a bounded best-first search algorithm and to tune the w-value of Weighted IDA*. In both cases major search speedups were observed.

In problem domains for which an informed admissible heuristic function is not available, one attractive approach is hierarchical search. Hierarchical search uses search in an abstracted version of the problem to dynamically generate heuristic values. This paper makes two contributions to hierarchical search. First, we propose a simple modification to the state-of-the-art algorithm Switchback that reduces the number of expansions (and hence the running time) by approximately half, while maintaining its guarantee of optimality. Second, we propose a new algorithm for suboptimal hierarchical search, called Switch. Empirical results suggest that Switch yields faster search than straightforward modifications of Switchback, such as weighting the heuristic or greedy search. The success of Switch illustrates the potential for further research on specifically suboptimal hierarchical search.

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

Search-based planning is widely used for mobile robot motion planning because of its guarantees of optimality and completeness. In continuous state-spaces, however, most existing approaches have significant limitations in terms of optimality and completeness because of the underlying grid used. We propose an approach that eliminates the dependency on grids by using more general equivalence classes to quickly find an initial solution and instead of pruning states that fall within an equivalence class and have higher cost, we use an inflated heuristic to lower the priority of these states in the search. In further iterations, we reduce the inflated heuristic in a principled way, thus providing fast solutions with provable suboptimality bounds that can be improved as time allows. The proposed approach produces smooth paths with the resolution dictated by the action set. Finer action sets produce higher resolution paths that are more computationally intensive to calculate and coarser action sets produce lower resolution paths that are faster to compute. To the best of our knowledge, this is the first algorithm that is able to plan in continuous state-spaces with provable guarantees on completeness and bounds on suboptimality for a given action set. Experimental results on 3D (x,y,theta) path planning show that, on average, this approach is able to find paths in less than two seconds that are within 2% of the optimal path cost in worlds of up to 1000x1000 m with a minimum step size of one meter.

Dijkstra's single-source shortest-path algorithm (DA) is one of the well-known, fundamental algorithms in computer science and related fields. DA is commonly taught in undergraduate courses. Uniform-cost search (UCS) is a simple version of the best-first search scheme which is logically equivalent to DA. In this paper I compare the two algorithms and show their similarities and differences. I claim that UCS is superior to DA in almost all aspects. It is easier to understand and implement. Its time and memory needs are also smaller. The reason that DA is taught in universities and classes around the world is probably only historical. I encourage people to stop using and teaching DA, and focus on UCS only.

In many applications of heuristic search, insufficient time isavailable to find provably optimal solutions. We consider thecontract search problem: finding the best solution possible within agiven time limit. The conventional approach to this problem is to usean interruptible anytime algorithm. Such algorithms return a sequenceof improving solutions until interuppted and do not consider theapproaching deadline during the course of the search. We propose anew approach, Deadline Aware Search, that explicitly takes the deadlineinto account and attempts to use all available time to find a singlehigh-quality solution. This algorithm is simple and fully general: itmodifies best-first search with on-line pruning. Empirical results onvariants of gridworld navigation, the sliding tile puzzle, and dynamicrobot navigation show that our method can surpass the leading anytimealgorithms across a wide variety of deadlines.

Move pruning is a low-overhead technique for reducing the size of a depth first search tree. The existing algorithm for automatically discovering move pruning information is restricted to games where all moves can be applied to every state. This paper demonstrates an algorithm which handles a general class of single player games. It gives experimental results for our technique, demonstrating both the applicability to a range of games, and the reduction in search tree size. We also provide some conditions under which move pruning is safe, and when it may interfere with other search reduction techniques.

Social networks play an increasingly important role in today's society. Special characteristics of these networks make them challenging domains for the search community. In particular, social networks of users can be viewed as search graphs of nodes, where the cost of obtaining information about a node can be very high. This paper addresses the search problem of identifying the degree of separation between two users. New search techniques are introduced to provide optimal or near-optimal solutions. The experiments are performed using Twitter, and they show an improvement of several orders of magnitude over greedy approaches. Our optimal algorithm finds an average degree of separation of 3.43 between two random Twitter users, requiring an average of only 67 requests for information over the Internet to Twitter. A near-optimal solution of length 3.88 can be found by making an average of 13.3 requests.