Cartesian abstractions can flexibly approximate planning tasks to generate admissible heuristic functions. Constrained abstractions use state constraints, such as mutexes, to eliminate parts of the abstraction that cannot belong to solutions for the original problem. While this has been successfully applied to simple forms of abstraction, no previous work has explored how to do this for Cartesian abstractions. We introduce constrained Cartesian abstractions, which leverage state constraints in multiple ways: to prune spurious transitions and to simplify or even remove abstract states. Moreover, we also use disambiguation to better guide the counterexample-guided process used to generate the abstractions. Our experimental results show that the resulting constrained Cartesian abstractions induce more informed heuristics than their non-constrained counterpart.

Anytime heuristic search algorithms try to find a (potentially suboptimal) solution as quickly as possible and then work to find better and better solutions until an optimal solution is obtained or time is exhausted. The most widely-known anytime search algorithms are based on best-first search. In this paper, we propose a new algorithm, rectangle search, that is instead based on beam search, a variant of breadth-first search. It repeatedly explores alternatives at all depth levels and is thus best-suited to problems featuring deep local minima. Experiments using a variety of popular search benchmarks suggest that rectangle search is competitive with fixed-width beam search and often performs better than the previous best anytime search algorithms.

Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost- optimal planning. The core idea is to iteratively refine the abstraction, finding a flaw of the current optimal abstract plan. All existing approaches find these flaws by executing the abstract plan using progression in the original state space. Instead, we propose to do backward refinements by using regression from the goals. This results in a new type of flaw, that can identify invalid plan suffixes. The resulting abstractions are less focused on the initial state, but more informative on average, significantly improving the performance of current CEGAR-based techniques. Furthermore, they can be combined with forward refinements in several bidirectional strategies that provide the benefits of both methods.

The problem of finding the shortest path in a graph G(V, E) has been widely studied. However, in many applications it is necessary to compute an arbitrary number of them, κ. Even though the problem has raised a lot of interest from different research communities and many applications of it are known, it has not been addressed to the same extent as the single shortest path problem. The best algorithm known for efficiently solving this task has a time complexity of O (|E| + |V|log|V|+κ|V|) when computing paths in explicit form, and is based on best-first search. This paper introduces a new search algorithm with the same time complexity, which results from a natural evolution of A* thus, it preserves all its interesting properties, making it widely applicable to many different domains. Experiments in various testbeds show a significant improvement in performance over the state of the art, often by one or two orders of magnitude.

Counterexample-Guided Abstraction Refinement (CEGAR) is a prominent technique to generate Cartesian abstractions for guiding search in cost-optimal planning. The core idea is to iteratively refine the abstraction, by finding a flaw in the current optimal abstract plan. Previous works find only a single flaw, by executing the abstract plan in the concrete state space and stopping when such execution cannot be continued. We show, however, that many flaws can be identified on a single plan. To that end, we introduce sequence flaws, which execute the plan in a Cartesian relaxation of the task to characterize issues beyond the first flaw found along its execution. This greatly increases the flexibility of CEGAR regarding how to refine the abstraction. Our experiments show that a high number of sequence flaws exist in most abstract plans across existing benchmarks. We observe that the selected flaw has a high impact on the resulting heuristic, opening new research opportunities for better selection strategies.

Recently there has been renewed interest in bidirectional heuristic search. New algorithms, e.g., MM, MMe, and NBS, have been introduced which seem much closer to refuting the accepted wisdom that "any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search". However, MM and MMe can still be dominated by their bidirectional brute-force versions, i.e., they can show a "hump-in-the-middle". We introduce a novel general breadth-first heuristic search algorithm, GBFHS, that unifies both unidirectional and bidirectional search into a single algorithm. It uses knowledge of the edge cost in unit cost domains to stop on first-collision in unidirectional search and in bidirectional search, unlike MM, MMe, and NBS. With no heuristic it expands fewer nodes bidirectionally than Nicholson's blind bidirectional search algorithm. GBFHS expands substantially fewer nodes than MM0, MM, MMe, and NBS. Additionally, GBFHS does not show a "hump-in-the-middle". GBFHS run bidirectionally is not dominated by bidirectional brute-force search, likewise, GBFHS run unidirectionally is not dominated by A*.

The Heuristic Search community has been concentrating much effort during the last decades in solving more and more efficiently the SHORTEST PATH problem (SPP). As a result, a valuable body of scientific results has been produced, mostly in the form of heuristics and search algorithms. However, not much attention has been given to other problems even if they result from slight variations of the typical problems addressed by the community. Furthermore, other communities attempt at solving hard combinatorial problems which might be well solved with heuristic search. In this paper, an attempt is presented to introduce a preliminary selection of relevant problems that goes well beyond the classical SPP.

The International Planning Competition is organized in the context of the International Conference on Automated Planning and Scheduling (ICAPS) and it is considered a reference source for the planning and scheduling community. The competition is typically organized every two years and deals with relevant issues for the community such as the definition of evaluation standards, the publication of benchmarks and the collection and dissemination of data about state-of-the-art planners. This paper focuses on the deterministic part, the longest-running part of the International Planning Competition. The paper describes its format, the participants, the selection of benchmarks and the generated results accompanied with analysis from different perspectives. The paper also examines the results of a brand new track created to explore the potential of planners that exploit the power of multi-core processors. Overall, the results of the competition indicate significant progress with respect to previous competitions, but they also reveal that some issues remain open and need further research, such as the coverage of temporal planners when concurrency is required and the performance in the multi-core track. As a novelty, all the data and the software generated for running the competition have been made publicly available allowing researchers to reproduce the competition and to carry out different analysis of the results.

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value, T. This problem has been previously addressed: first, for directed acyclic graphs; second, for general graphs under the assumption that nodes can be revisited given that the same edge can not be traversed twice. In this work we focus on a more restrictive variant of the same problem where nodes can not be revisited. We prove that this variant is NP-complete and discuss novel theoretical properties and provide empirical results to solve this problem optimally.

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value T. This problem has been previously addressed only for directed acyclic graphs. In this work we develop the theory required to solve this problem optimally for any type of graphs. We modify traditional heuristic search algorithms for this setting, and propose a novel bidirectional search algorithm that is specifically suited for TVS. The benefits of this bidirectional search algorithm are discussed both theoretically and experimentally on several domains. A longer version of this work was accepted to IJCAI-2013 (Linares Lopez et al. 2013)

In recent years the concept of sequential portfolio has become an important topic to improve the performance of modern problem solvers, such as SAT engines or planners. The PbP planner and more recently Fast Downward Stone Soup are successful approaches in Automated Planning that follow this trend. However, neither a theoretical analysis nor formal definitions about sequential portfolios have been described. In this paper, we focus on studying how to evaluate the performance of planners defining a baseline for a set of problems. We present a general method based on Mixed-Integer Programming to define the baseline for a training data set. In addition to prior work, we also introduce a short empirical analysis of the utility of training problems to configure sequential portfolios.

This paper describes BubbleDragon, an entry in the 2012 Grid-based Path-Planning Competition. We aim to solve path-finding problems in the minimum time possible by precomputing paths from states in a region to its frontiers. Experimental results show that suboptimal paths for 1024x1024 grids can be retrieved in less than 1ms on average.

The Pancake problem has become a classical combinatorial problem. Different attempts have been made to optimally solve it and/or to derive tighter bounds on the diameter of its state space for a different number of discs. Until very recently, the most successful technique for solving different instances optimally was based on Pattern Databases. Although different approaches have been tried, solutions with Pattern Databases on Pancakes with more than 19 discs have never been reported. In this work, a new technique is introduced which allows the definition of Additive Pattern Databases for solving Pancakes of an arbitrary length. As a result, this technique solves Pancake problems with twice as many discs as the largest ones solved nowadays with other techniques based on Pattern Databases saving up to two orders of magnitude of space.

In this work, a new approach for creating Pattern Databases (PDBs) is suggested that induces non-consistent heuristic functions just by recognizing feasible (yet admissible) heuristic values. This approach serves to generalize even further the BPMX propagation rule, that will work now even in directed graphs. Experiments in different state spaces show a noticeable improvement over the Scalar Pattern Databases.

In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.

Pattern Databases were a major breakthrough in heuristic search by solving hard combinatorial problems various orders of magnitude faster than state-of-the-art techniques at that time. Since then, they have received a lot of attention. Moreover, pattern databases are also researched in conjunction with other domain-independent techniques for solving planning tasks. However, they are not the only technique for improving heuristic estimates. Although more modest, perimeter search can also lead to significant improvements in the number of generated nodes and overall running time. Therefore, whether they can be combined or not is a natural and interesting issue. While other researchers have recently proven that a joint application of both ideas (termed as multiple goal) leads to no progress at all, it is shown here that there are other alternatives for putting both techniques together—denoted here as multi-valued. This paper shows that multi-valued pattern databases can still improve the performance of standard (or single-valued) pattern databases in practice. It also examines how to enhance memory usage when comparing multi-valued pattern databases in contraposition to various single-valued standard pattern databases.