In this paper we study the k goal search problem (kGS), which is the problem of solving k shortest path problems that share the same start state. Two fundamental heuristic search approaches are analyzed: searching for the k goals one at a time, or searching for all k goals together in a single pass. Key theoretical properties are established and a preliminary experimental evaluation is performed.

The game of Sokoban is an interesting platform for algorithm research. It is hard for humans and computers alike. Even small levels can take a lot of computation for all known algorithms. In this paper we will describe how a search based Sokoban solver can be structured and which algorithms can be used to realize each critical part. We implement a variety of those, construct a number of different solvers and combine them into an algorithm portfolio. The solver we construct this way can outperform existing solvers when run in parallel, that is, our solver with 16 processors outperforms the previous sequential solvers.

The efficiency of heuristic search depends dramatically on the quality of the heuristic function. For an optimal heuristic search, heuristics that estimate cost-to-goal better typically lead to faster searches. For a sub-optimal heuristic search such as weighted A*, the search speed depends more on the correlation between the heuristic and the true cost-to-goal. In this extended abstract, we discuss our preliminary work on computing heuristic functions that exploit this fact. In particular, we introduce a many-to-one mapping from an original search space to a conservative abstract space. Edges in the abstract space capture reachability among all corresponding nodes in the original space. We compute a heuristic in the conservative abstract space which when used by the search in the original space reduces the number of searched nodes. Our preliminary results on 3D navigation show that in more complex scenarios the speedup can be dramatic.

Admissible heuristics are essential for optimal planning in the context of search algorithms like A*, and they can also be used in the context of suboptimal planning in order to find quality-bounded solutions. In satisfacing planning, on the other hand, admissible heuristics are not exploited by the best-first search algorithms of existing planners even when a time window is available for improving the first solution found. For example, in the well-know planner LAMA, better solutions within such a time window are sought by restarting a Weighted-A* search guided by inadmissible heuristics, each time a better solution is found. In this paper, we investigate the use of admissible heuristics in the context of LAMA for pruning nodes that cannot lead to better solutions. The revised search of LAMA is experimentally evaluated using two alternative admissible heuristics for pruning and three types of problems: planning with soft goals, planning with action costs, and planning with both action costs and soft goals. Soft goals are compiled into hard goals following the approach of Keyder and Geffner. The empirical results show that the use of admissible heuristics in LAMA can be of great help to improve the planner performance.

We investigate GPU-based parallelization of Iterative-Deepening A* (IDA*). We show that straightforward thread-based parallelization techniques which were previously proposed for massively parallel SIMD processors perform poorly due to warp divergence and load imbalance. We propose Block-Parallel IDA* (BPIDA*), which assigns the search of a subtree to a block (a group of threads with access to fast shared memory) rather than a thread. On the 15-puzzle, BP-IDA* on a NVIDIA GRID K520 with 1536 CUDA cores achieves a speedup of 4.98 compared to a highly optimized sequential IDA* implementation on a Xeon E5-2670 core.

Pattern databases are among the strongest known heuristics for many classical search benchmarks such as sliding-tile puzzles, the 4-peg Towers of Hanoi puzzles, Rubik's Cube, and TopSpin. Min-compression is a generally applicable technique for augmenting pattern database heuristics that has led to marked experimental improvements in some settings, while being ineffective in others. We provide a theoretical explanation for these experimental phenomena by studying the interaction between the ranking function used to order abstract states in a pattern database, the compression scheme used to abstract states, and the dependencies between state variables in the problem representation.

Star-Topology Decoupled Search has recently been introduced in classical planning. It splits the planning task into a set of components whose dependencies take a star structure, where one center component interacts with possibly many leaf components. Here we address a weakness of decoupled search, namely large leaf components, whose state space is enumerated explicitly. We propose a symbolic representation of the leaf state spaces via decision diagrams, which can be dramatically smaller, and also more runtime efficient. We further introduce a symbolic version of the LM-cut heuristic, that nicely connects to our new leaf representation. We show empirically that the symbolic representation indeed pays off when the leaf components are large.

Dynamic Potential Search (DPS) is a recently introduced search algorithm that returns a bounded-suboptimal cost solution. DPS orders nodes in the open-list based on their potential which is a combination of both the g - and h -values of a node. In this paper we study the behavior of DPS on weighted graphs. In particular, we develop a new variant of DPS, called DPSU which calculates the potential by counting one for each edge regardless of its costs. We develop an eager version and a restrained version of DPSU. We then compare all these algorithms on a number of weighted graphs and study the pros and cons of each of them.

The pancake puzzle is a standard benchmark domain used to test search algorithms, and the gap heuristic is the state-of-the-art heuristic function most often used in such tests. In this work, we analyze the accuracy of this heuristic and identify ways to enhance it. We begin by showing that in the worst-case, the amount that the gap heuristic underestimates the optimal cost of a pancake puzzle state can be linear in the number of pancakes in the stack. However, empirical analysis suggests that it is extremely rare that the gap heuristic underestimates the optimal cost by more than two. We then identify several simple methods that can be used to generate large sets of problems on which the gap heuristic underestimates the optimal cost by a larger amount than it typically does on random permutations. In doing so, we provide new pancake puzzle test sets that can be used to evaluate how search algorithms behave when the heuristic is inaccurate. We also formally characterize states according to the size of the heuristic plateaus around them. This characterization allows us to efficiently compute a two-step look ahead of the gap heuristic on any state, which we can use alongside a state's dual to further improve heuristic accuracy. These enhancements substantially improve the performance of an IDA*-based pancake problem solver on both the existing benchmarks and the new ones proposed in this paper.

A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search but, no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical param-eterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.