TL;DR
This paper carves out new "islands of tractability" for cost-optimal AI planning problems, specifically for those with propositional state variables and simple (unary-effect) actions. By analyzing the structure of the problem's causal graph, the authors identify specific conditions under which finding the cheapest plan is computationally feasible, effectively drawing a line between tractable and intractable planning scenarios.
What Problem Does This Paper Address?
AI planning, the task of finding a sequence of actions to achieve a goal from an initial state, is notoriously difficult. Even for simplified versions of planning (like propositional state variables and unary-effect actions), finding any plan is PSPACE-complete, and finding the optimal (lowest cost) plan is even harder. While researchers have identified some specific problem structures (fragments) that make planning tractable, the landscape of tractable cost-optimal planning is particularly sparse. This paper aims to expand this landscape by identifying new, non-trivial fragments of cost-optimal planning that are computationally tractable, and to provide a clearer understanding of what makes these problems hard or easy.
Methods
The core of the paper's methodology involves relating the complexity of cost-optimal planning to the structural properties of the problem's causal graph. The causal graph represents dependencies between state variables, where an edge from variable $v$ to $v'$ means $v$ can influence $v'$. The authors focus on specific graph topologies like trees, polytrees, and directed-path singly connected graphs, and also consider constraints on the in-degree of nodes (how many variables directly influence a given variable).
A key technique employed is a "planning-to-constraint-optimization" (COP) compilation. This involves transforming a planning problem into an equivalent constraint optimization problem. By leveraging existing efficient algorithms for solving certain types of constraint optimization problems (specifically, those with tree-structured constraint networks), the authors can then solve the original planning problem efficiently. The tractability results are largely based on showing that specific planning fragments can be compiled into COPs with bounded tree-width, a property that allows for polynomial-time solutions.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity analysis and the identification of tractable problem fragments, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Causal Graph Topology Matters: The structure of the causal graph is a critical determinant of planning complexity. Polytrees (graphs without undirected cycles) with bounded in-degrees are particularly amenable to tractable cost-optimal planning.
- Planning-to-COP Compilation is Powerful: The technique of compiling planning problems into constraint optimization problems is a robust and versatile tool for proving tractability. It allows leveraging existing efficient solvers for COPs.
- "Islands of Tractability" are Discoverable: Despite the general intractability of planning, there are specific, structured sub-problems where efficient cost-optimal planning is achievable. The paper systematically identifies and characterizes these "islands."
- k-Dependence as a Tractability Frontier: The concept of "k-dependence" (limiting the number of unaffected variables an action can depend on) plays a role, with 1-dependence showing promise for tractability in certain graph structures, but also highlighting limitations in others.
Key Results
The paper establishes several key results regarding the tractability of cost-optimal planning for propositional state variables and unary-effect actions:
- Tractability for $P_b$: Cost-optimal planning is tractable for problems whose causal graphs are polytrees with $O(1)$-bounded in-degrees. This is achieved through a planning-to-COP compilation where the COP's cost network has a bounded tree-width.
- Tractability for $P(1)$ (Uniform Cost): Cost-optimal planning is tractable for 1-dependent problems with polytree causal graphs and uniform-cost actions. This relies on a specialized planning-to-COP compilation that exploits properties of post-unique plans.
- Tractability for $P(1)$ (General Cost): Cost-optimal planning is also tractable for 1-dependent problems with polytree causal graphs and general action costs. This uses a more complex planning-to-COP compilation based on "post-3/2" plans.
- Hardness for $S(1)$: Cost-optimal planning is NP-complete for 1-dependent problems with directed-path singly connected causal graphs (even with bounded in/out-degrees). This demonstrates a boundary where tractability breaks down.
Limitations and Future Work
- Complexity of $P(k)$: The complexity of cost-optimal planning for $P(k)$ problems (where $k$ is $O(1)$) remains an open question, particularly for causal graphs that are more complex than polytrees.
- Complexity of $S(1)$ (Satisficing): The complexity of satisficing (non-optimal) planning for $S(1)$ problems is also an open question.
- Practical Efficiency: While the algorithms presented are polynomial-time in theory, their complexity can be high (e.g., exponential in the in-degree of the causal graph). Future work could focus on improving practical efficiency and developing more specialized algorithms for specific tractable fragments.
- Multi-valued State Variables: The current work focuses on propositional (binary-valued) state variables. Extending these results to planning problems with multi-valued state variables is a promising direction for future research.
Summary updated