Classical planning asks for a sequence of operators reaching a given goal. While the most common case is to compute a plan, many scenarios require more than that. However, quantitative reasoning on the plan space remains mostly unexplored. A fundamental problem is to count plans, which relates to the conditional probability on the plan space. Indeed, qualitative and quantitative approaches are well-established in various other areas of automated reasoning. We present the first study to quantitative and qualitative reasoning on the plan space. In particular, we focus on polynomially bounded plans. On the theoretical side, we study its complexity, which gives rise to rich reasoning modes. Since counting is hard in general, we introduce the easier notion of facets, which enables understanding the significance of operators. On the practical side, we implement quantitative reasoning for planning. Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans. This framework scales well to large plan spaces, while enabling rich reasoning capabilities such as learning pruning functions and explainable planning.

We show that standard symbolic search algorithms for classical planning can incur exponential overhead compared to explicit blind search in the presence of complex conditions and effects. To address this problem, we explore conjunctive partitioning in classical planning and present fully automated, domain-independent methods for representing actions and goal conditions in a partitioned form. We show that one of our methods, based on the Tseitin transformation, yields a symbolic search algorithm that in the worst case incurs only a polynomial overhead and in the best case can be exponentially more efficient than its explicit counterpart. Finally, our empirical evaluation shows that our theoretical findings carry over into practice: our algorithms solve planning problems previously intractable for symbolic search, and perform favorably overall compared to traditional symbolic search, explicit blind search, and other state-of-the-art planners.

Building a single Cartesian abstraction is usually not enough to obtain an informative heuristic for classical planning. Therefore, state-of-the-art methods decompose the original task into subtasks—for example, one per goal atom—and compute an abstraction for each individual subtask. However, building a single abstraction suffers from diminishing returns, while building multiple abstractions loses information about how to achieve the associated subtasks jointly. We interpolate between these two extremes by first considering subtasks individually and then merging some of the resulting abstractions. We introduce an efficient algorithm for merging pairs of Cartesian abstractions using their refinement hierarchies and show that it yields more informative abstractions in less time than a naive approach. Furthermore, we prove that adding merged abstractions can only improve a cost-partitioned heuristic based on saturated post-hoc optimization and that for maximal heuristic values, we need to keep the individual abstractions. Our experiments show that merging abstractions drastically improves the resulting heuristics.

Classical planning provides a framework for solving sequential decision-making problems, i.e., finding a sequence of actions that transforms the current state of the world into a state that satisfies a desired goal condition. Planning tasks are modeled in a logic that describes the environment and its dynamics. It is well known that the specific problem formulation can significantly affect the performance of planning systems solving problems like the Rubik's Cube or finding algorithms for matrix multiplication. In this work, we propose a domain-general problem reformulation that embodies decoupled search, a search-reduction technique from classical planning and model checking. Decoupled search decomposes a given problem to exploit its structure, achieving exponential reductions over other search techniques. We show that decoupled search can be captured exactly as a task reformulation and that, on many benchmark domains, it performs as good and sometimes even better than a native decoupled-search implementation.

Many planning applications require not only a single solution but benefit substantially from having a set of possible plans from which users can select, for example, when explaining plans. For decades, research in classical AI planning has primarily focused on quickly finding single plans. Only recently researchers have started to investigate preferences, enumerate plans by top-k planning, or count plans to reason about the plan space. Unfortunately, reasoning about the plan space is computationally extremely hard and feeding many similar plans to the user is hardly practical. To circumvent computational shortcomings while still being able to reason about variability in plans, faceted actions have been introduced very recently. These are meaningful actions that can be used by some plan but are not required by all plans. Enforcing or forbidding such facets allows for navigating even large plan spaces while ensuring desired properties quickly and step by step. In this paper, we illustrate an industrial challenge, the Beluga logistics problem of Airbus, where reasoning with facets enables targeted plan space navigation. We present an approach to handle large plan spaces iteratively and interactively and present a tool that we call PlanPilot.

Saturated cost partitioning (SCP) is one of the strongest methods for admissibly combining heuristics for optimal classical planning. The quality of an SCP heuristic depends heavily on the order in which its component heuristics are considered. For high accuracy, it is essential to maximize over multiple SCP heuristics computed using different component orders. However, for n component heuristics, even enumerating all n! orders is usually infeasible. Consequently, previous work resorted to using greedy algorithms and local optimization. In contrast, we present the first practical method for computing the perfect SCP heuristic that is equivalent to considering all component orders. We show that a set of SCP heuristics forms an additive disjunctive heuristic, which allows us to concisely represent component orders as a directed acyclic graph. Furthermore, once certain components have been considered, the order of the remaining components often becomes irrelevant. By exploiting this characteristic, we can reduce the size of the heuristic representation by several orders of magnitude in practice. Finally, our work makes it possible to compare the quality of existing SCP methods with that of the perfect SCP heuristic, revealing that existing approximations are nearly optimal for standard benchmarks.

In classical planning, the task is to derive a sequence of deterministic actions that changes the current fully-observable world state into one that satisfies a set of goal criteria. Algorithms for classical planning are domain-independent, i.e., they are not limited to a particular application and instead can be used to solve different types of reasoning problems. The main language for modeling such problems is the Planning Domain Definition Language (PDDL). Even though it provides many language features for expressing a wide range of planning tasks, most of today’s classical planners, especially optimal ones, support only a small subset of its features. The most widely supported fragment is lifted STRIPS plus types and action costs. While this fragment suffices to model some interesting planning tasks, using it to model more realistic problems often incurs a much higher modeling effort. Even if modeling is possible at all, solving the resulting tasks is often infeasible in practice, as the required encoding size increases exponentially. To address these issues, we show how to support more expressive modeling languages natively in optimal classical planning algorithms. Specifically, we focus on symbolic search, a state-of-the-art search algorithm that operates on sets of world states. We show how to extend symbolic search to support classical planning with conditional effects, axioms, and state-dependent action costs. All of these modeling features are expressive in the sense that compiling them away incurs a significant blow-up, so is it often necessary to support them natively. Except for blind (non-symbolic) search, our new symbolic search is the first optimal classical planning algorithm that supports these three modeling extensions in combination, and it even compares favorably to other state-of-the-art approaches that only support a subset of the extensions.

Automated problem reformulation is a common technique in classical planning to identify and exploit problem structures. Decoupled search is an approach that automatically decomposes planning tasks based on their causal structure, often significantly reducing the search effort. However, its broad applicability is limited by the need for specialized algorithms. In this paper, we present an approach that embodies decoupled search for non-optimal planning through a novel task transformation. Specifically, given a task and a decomposition, we create a transformed task such that the state space of the transformed task is isomorphic to that of decoupled search on the original task. This eliminates the need for specialized algorithms and allows the use of various planning technology in the decoupled-search framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

Saturated post-hoc optimization is a powerful method for computing admissible heuristics for optimal classical planning. The approach solves a linear program (LP) for each state encountered during the search, which is computationally demanding. In this paper, we theoretically and empirically analyze to which extent we can reuse an LP solution of one state for another. We introduce a novel sensitivity analysis that can exactly characterize the set of states for which a unique LP solution is optimal. Furthermore, we identify two properties of the underlying LPs that affect reusability. Finally, we introduce an algorithm that optimizes LP solutions to generalize well to other states. Our new algorithms significantly reduce the number of necessary LP computations.

Combinatorial reconfiguration is the problem of transforming one solution of a combinatorial problem into another, where each transformation may only apply small changes to a solution and may not leave the solution space. An important example is the independent set reconfiguration (ISR) problem, where an independent set of a graph (a subset of its vertices without edges between them) has to be transformed into another by a sequence of transformations that can replace a vertex in the current subset such that the new subset is still an independent set. The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) was a competition focused on the ISR problem. The PARIS team successfully participated with two solvers that model the ISR problem as a planning task and employ different planning techniques for solving it. In this work, we describe these models and solvers. For a fair comparison to competing ISR approaches, we re-run the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a cross-fertilization of the two research fields.

Cost partitioning is the foundation of today’s strongest heuristics for optimal classical planning. However, computing a cost partitioning for each evaluated state is prohibitively expensive in practice. Thus, existing approaches make an approximation and compute a cost partitioning only for a set of sampled states, and then reuse the resulting heuristics for all other states evaluated during the search. In this paper, we present exact methods for cost partitioning heuristics based on linear programming that fully preserve heuristic accuracy while minimizing computational cost. Specifically, we focus on saturated post-hoc optimization and establish several sufficient conditions for when reusing a cost partitioning computed for one state preserves the estimates for other states, mainly based on a sensitivity analysis of the underlying linear program. Our experiments demonstrate that our theoretical results transfer into practice, and that our exact cost partitioning algorithms are competitive with the strongest approximations currently available, while usually requiring fewer linear program evaluations.

Heuristic search is a successful approach to cost-optimal planning. Bidirectional heuristic search algorithms have been around for a long time, but only recent advances have led to algorithms like BAE* that have the potential to outperform unidirectional heuristic search algorithms like A* in practice. In this work, we analyze BAE* for classical planning and the challenges associated with the underlying assumption of an explicit state representation. We show that it is crucial to use mutexes and reachability analysis to reduce the potentially exponential number of goal states, which makes it possible to create an explicit representation of a reversed planning task that can be used for the backward search of BAE*. Our empirical evaluation shows that BAE* solves more instances than A* in multiple domains with significantly fewer node expansions, demonstrating the usefulness of BAE* in planning.

The objective of optimal oversubscription planning is to find a plan that yields an end state with a maximum utility while keeping plan cost under a certain bound. In practice, the situation occurs whenever a large number of possible, often competing goals of varying value exist, or the resources are not sufficient to achieve all goals. In this paper, we investigate the use of symbolic search for optimal oversubscription planning. Specifically, we show how to apply symbolic forward search to oversubscription planning tasks and prove that our approach is sound, complete and optimal. An empirical analysis shows that our symbolic approach favorably competes with explicit state-space heuristic search, the current state of the art for oversubscription planning.

Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.

The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called sym-k, which is based on symbolic search, and prove that sym-k is sound and complete. Our empirical analysis shows that sym-k exceeds the current state of the art for both small and large k.

MDPs with factored action spaces, i.e., where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the Trial-based Heuristic Tree Search (THTS) framework, such as AO* or UCT. To be able to reason over factored action spaces, we propose a generalization of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.