We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.

Welcome to the Third International Symposium on a long line of research that was carried out in the Combinatorial Search (SoCS)! This is an important past decade by him and others about the important year for SoCS as we have established archival proceedings topic of search in nondeterministic environments. These proceedings are the Finally, we scheduled an important panel discussion result of hard work by many, from researchers to reviewers about the differences and mutual influence of domain and the publisher. Every submitted search for planning environments. Wheeler Ruml paper was assigned to three anonymous reviewers; moderates the panel, which includes three experts all experts in the topic of the paper.

Anytime search is a pragmatic approach for trading solution cost and solving time. It can also be used for solving problems within a time bound. Three frameworks for constructing anytime algorithms from bounded suboptimal search have been proposed: continuing search, repairing search, and restarting search, but what combination of suboptimal search and anytime framework performs best? An extensive empirical evaluation results in several novel algorithms and reveals that the relative performance of frameworks is essentially fixed, with the repairing framework having the strongest overall performance. As part of our study, we present two enhancements to Anytime Window A* that allow it to solve a wider range of problems and hastens its convergance on optimal solutions.

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space.  This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks.  We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

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.

In various domains, such as computer games, robotics, and transportation networks, shortest paths may need to be found quickly. Search time can be significantly reduced if it is known which parts of the graph include "swamps" - areas that cannot lie on the only available shortest path, and can thus safely be pruned during search. We introduce an algorithm for detecting hierarchies of swamps, and exploiting them. Experiments support our claims of improved efficiency, showing significant reduction in search time.

Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to ≈ 8% longer than the shortest paths in the continuous environment. Theta* typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short “any-angle” paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be ≈ 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta* can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta* which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta* finds paths faster than Theta* on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length.

This paper examines the following statements about heuristic search, which are commonly held to be true: More accurate heuristics result in fewer node expansions by A* and IDA*. A* does fewer node expansions than any other equally informed algorithm that finds optimal solutions.  Any admissible heuristic can be turned into a consistent heuristic by a simple technique called pathmax. In search spaces whose operators all have the same cost A* with the heuristic function h(s)=0 for all states, s, is the same as breadth-first search. Bidirectional A* stops when the forward and backward search frontiers meet. The paper demonstrates that all these statements are false and provides alternative statements that are true.

A ubiquitous feature of planning problems — problems involving the automatic generation of action sequences for attaining a given goal — is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.

Our approach is conceptually simple: we perform a the search algorithm. In video game pathfinding and robot standard dynamic search but interrupt it periodically to move motion planning, the search is often required to be real-time, the agent according to a real-time search. In this paper, we that is, return the next move for the agent within a strict time use D* Lite (Koenig and Likhachev 2002) or Anytime D* bound, so that the agent can continue acting in the world. To (Likhachev et al. 2005) as the dynamic search algorithm and accommodate this constraint, real-time search algorithms interleave LRTA* (Korf 1990) or LSS-LRTA* (Koenig and Sun 2009) planning and moving. Because the agent must make as the real-time search algorithm. D* Lite and Anytime D* a choice of which move to execute next before finding a perform a global search backwards from the goal, trying to complete path to a goal, real-time search algorithms achieve reach the agent's current location. LRTA* and LSS-LRTA* fast response times at the cost of sub-optimality of the resulting perform a local search forward from the agent's current location, trajectories. There has been much research on real-time trying to reach the goal. Therefore, RTD* is a form of search algorithms, starting with LRTA* (Korf 1990).