Planning with Qualitative Action-Trajectory Constraints in PDDL

Luigi Bonassi, Alfonso Emilio Gerevini, Enrico ScalaIJCAI 2022 · DOI

TL;DR

This paper introduces a new way to express constraints on the sequence of actions in a plan, rather than just the states visited. They propose a compilation method to translate these "action-trajectory constraints" into a format that standard AI planners can understand, significantly improving their performance and plan quality in experiments.

What Problem Does This Paper Address?

Automated planning systems aim to find a sequence of actions to achieve a goal. Often, we want to guide the planner not just to reach any goal state, but to do so in a specific way, or to avoid certain action sequences. Traditional methods in PDDL3 use "state-trajectory constraints" (like LTLf formulas) to specify properties of the states a plan visits. However, these are often insufficient for expressing desired action sequences. For example, you might want to ensure a specific truck drives from city A to city B, which is hard to express by only looking at the truck's location (state). This paper addresses this gap by proposing a formalism for action-level constraints and a practical way to use them with existing planners.

Methods

The core contribution is a new formalism for "action-trajectory constraints" that extends PDDL3's temporal modal operators with two new ones: "always-next" and "pattern." These constraints directly refer to the labels of actions in a plan.

To make these constraints usable by standard planners, the authors developed a compilation schema called PAC-C. This schema transforms a planning problem with action constraints into an equivalent classical planning problem without them. The compilation works in three phases:

  1. Atom Creation: Introduces new "helper" atoms to track the satisfaction of constraints.
  2. Action Revision: Modifies the preconditions and effects of existing actions. This includes pruning actions that would violate "prevent constraints" (like "at-most-once") and adding effects to ensure "request constraints" (like "sometime") are met.
  3. Goal Revision: Updates the goal of the planning problem to enforce the satisfaction of all "request constraints."

The key idea is that PAC-C generates a compiled problem whose solutions have the same length as the original problem's solutions, which is an advantage over some existing methods.

Datasets

The authors generated a new benchmark suite for evaluating their approach. This suite is based on problems from the 5th International Planning Competition, covering domains like Trucks, Storage, TPP, Openstack, and Rover. For each domain, they designed action constraints specifically to either boost problem coverage or improve plan quality. They also created equivalent PDDL3 and LTLf formulations of these constraints for comparison.

Key Insights and Ideas

  • Action-level constraints are more expressive: The paper demonstrates that certain desired plan properties, like specific action sequences, are difficult or impossible to express using only state-based constraints. Action-trajectory constraints offer a more direct and natural way to capture this knowledge.
  • Compilation is key for practical use: By developing the PAC-C compilation schema, the authors make their novel constraints accessible to existing, off-the-shelf classical planners. This avoids the need for specialized planners that natively support these constraints.
  • Action constraints can significantly boost performance: The experimental results show that using action constraints, compiled via PAC-C, can dramatically improve a planner's ability to solve problems (coverage) and find shorter, better plans (quality).
  • PAC-C outperforms state-constraint compilation: In their experiments, compiling action constraints into state-trajectory constraints (using TCORE and LTL-C) was less effective than using PAC-C for action constraints directly.

Key Results

  • Coverage Improvement: PAC-C solved more instances than the baseline planner (LAMA without constraints) across all domains. Notably, in Storage, PAC-C solved all instances where the baseline failed on 10. In Trucks, it solved 7 more instances.
  • Plan Quality Improvement: For domains like Rover, TPP, and Openstack, PAC-C significantly improved plan quality, finding shorter plans on average. For example, in TPP, plans were, on average, 40 actions shorter.
  • Comparison to State-Constraint Methods: PAC-C generally outperformed LTL-C and TCORE in terms of coverage and plan quality improvements. LTL-C even worsened performance in some cases.
  • Efficiency: The compilation process itself is polynomial, and the resulting compiled problems maintain the same plan length as the original problem.

Limitations and Future Work

  • Limited Expressiveness of State Constraints: The paper highlights that state-trajectory constraints are less expressive than action-trajectory constraints for certain types of knowledge.
  • Future Work: The authors suggest exploring trajectory constraints that combine both actions and states, investigating preferences over action constraints, and conducting further experiments with numeric planning domains. They also mention that a deeper comparison with LPP (a language for temporal logic constraints) is left for future work.

Summary updated

BibTeX
@inproceedings{bonassi2022planning,
  author = {Luigi Bonassi and Alfonso Emilio Gerevini and Enrico Scala},
  title = {{Planning with Qualitative Action-Trajectory Constraints in PDDL}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/639},
}
Figure