Optimal Planning Modulo Theories

Francesco Leofante, Enrico Giunchiglia, Erika Ábrahám, Armando Tacchella

Abstract

This paper introduces OMTPLAN, a novel domain-independent planner that leverages Optimization Modulo Theories (OMT) to solve numeric planning problems. By combining Boolean abstraction with formal optimization, the authors provide a framework that guarantees cost-optimal plans even in complex scenarios where action costs change based on the current state—a challenge that often stymies traditional heuristic-based planners. Experimental results show that OMTPLAN excels in domains with state-dependent action costs and linear effects, outperforming both heuristic and MILP-based alternatives in these specific contexts.

Introduction

In Automated Planning, the goal is to find a sequence of actions that transitions a system from an initial state to a target goal. Numeric planning introduces additional complexity by incorporating variables such as fuel levels, distances, or budgets. While finding any valid plan is computationally difficult, finding the optimal (cheapest) plan is significantly harder.

Most existing cost-optimal planners rely on admissible heuristics. However, these mathematical shortcuts often fail when dealing with linear effects (where actions change variables by calculated amounts) or State-Dependent Action Costs (SDAC) (where costs depend on the current state, such as fuel price). OMTPLAN addresses this gap by providing a domain-independent solver capable of handling complex numeric constraints while guaranteeing global optimality.

Methods

OMTPLAN departs from traditional state-space search by treating planning as a Satisfiability (SAT) problem, specifically utilizing Optimization Modulo Theories (OMT). The core approach involves several key components:

  1. Bounded Encoding: The planning problem is represented as a logical formula for a fixed number of steps ($n$). A plan exists if the formula is satisfiable.
  2. Abstract Actions ($a^{abs}$): To ensure termination, the solver uses a "suffix" to the formula with abstract actions that ignore complex numeric constraints, providing a "relaxed reachability" check.
  3. Loop Formulas: Borrowed from Answer Set Programming (ASP), these formulas prevent circular dependencies in abstract reasoning.
  4. Optimality Guarantee: The authors prove that if the OMT solver finds a plan without relying on abstract actions, and the cost of those actions is set to a theoretical minimum, the resulting plan is globally optimal.

Evaluation and Results

The authors evaluated OMTPLAN against several benchmarks, including modified classic PDDL domains and a new Security Clearance domain designed to test SDAC.

Performance comparison in the Security Clearance domain showing CPU time vs. solved instances.

In the Security Clearance domain, OMTPLAN significantly outperformed traditional heuristic search ($h^{blind}$), solving 26 instances compared to the heuristic's 16. As shown in the performance plot above, OMTPLAN maintains much lower CPU times as the number of solved instances increases, demonstrating superior scalability in SDAC scenarios.

Comparison of OMTPlan against $h^{blind}$ and $C^{SC}$ across various linear numeric domains.

In domains with linear conditions, OMTPLAN solved 52 problems, more than doubling the 23 instances solved by the MILP-based competitor ($C^{SC}$), as detailed in the table above. While $C^{SC}$ remains more efficient in "simple" numeric domains with constant increments, OMTPLAN serves as the "heavy lifter" for more mathematically complex problems.

Discussion and Conclusion

OMTPLAN's primary strength lies in its ability to handle the marriage of logic and arithmetic seamlessly, a task where Mixed-Integer Linear Programming (MILP) often struggles due to complex if-then conditions. However, the approach is sensitive to the "horizon" length; as the required sequence of actions grows, the logical formula becomes massive, which can overwhelm the solver.

Future work aims to extend the framework to handle structured data types and integrate more advanced SMT/OMT features. Refining axioms to better handle different plan structures ("short and wide" vs. "long and narrow") also remains a key area for improvement.

Summary updated

Abstract

We consider the problem of planning with arithmetic theories, and focus on generating optimal plans for numeric domains with constant and state-dependent action costs. Solving these problems efficiently requires a seamless integration between propositional and numeric reasoning. We propose a novel approach that leverages Optimization Modulo Theories (OMT) solvers to implement a domain-independent optimal theory-planner. We present a new encoding for optimal planning in this setting and we evaluate our approach using well-known, as well as new, numeric benchmarks.
BibTeX
@inproceedings{leofante2020optimal,
  author = {Francesco Leofante and Enrico Giunchiglia and Erika Ábrahám and Armando Tacchella},
  title = {{Optimal Planning Modulo Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/571},
}
Figure