TL;DR
This paper introduces a novel encoding for "Planning as SMT" (Satisfiability Modulo Theories) that allows for more parallelism in action execution, leading to significantly shorter plans. They achieve this by relaxing the constraints on how actions can be executed concurrently, and then efficiently remove redundant actions using a MaxSMT post-processing step.
What Problem Does This Paper Address?
Traditional AI planning often assumes actions are executed sequentially. However, in many real-world scenarios, multiple actions can happen simultaneously. This parallelism can drastically reduce the time needed to achieve a goal. Existing approaches to parallel planning, especially those using Satisfiability Modulo Theories (SMT) for planning with complex numeric domains, have limitations on how actions can be grouped into "time steps." Specifically, some semantics require that all actions within a time step must be executable in any order, or that their effects must be consistent. This paper tackles the challenge of enabling maximum parallelism in SMT-based planning by introducing a more relaxed semantics, called "relaxed relaxed ∃-step" (R²∃-step), and developing an efficient encoding for it.
Methods
The core contribution is a new SMT encoding for planning that adheres to the R²∃-step semantics. This semantics is more permissive than previous ones, allowing actions to be executed in parallel even if their preconditions aren't all met at the start of the time step, and relaxing consistency requirements between their effects. The key technical innovation lies in how they model the state transitions. They introduce auxiliary variables for each state variable at each time step, allowing for the modeling of "chains of assignments" that capture the effects of potentially many actions within a single time step. This is crucial for handling non-commutative effects and achieving greater parallelism.
To address the potential issue of redundant actions introduced by this high degree of parallelism, they propose a post-processing step using a MaxSMT solver. This step penalizes the inclusion of actions in the plan, forcing the solver to find a plan with the minimum number of actions while still achieving the goal.
Datasets
The paper evaluates their approach on several benchmark domains from the International Planning Competition (IPC), specifically those with numeric fluents and without quantified preconditions. These include Zenotravel, Driverlog, Depots, Rovers, Petrobras, and Planes. They do not introduce new benchmarks.
Key Insights and Ideas
- R²∃-step Semantics is Key to Parallelism: By relaxing the strict ordering and consistency requirements of previous parallel planning semantics, the R²∃-step semantics allows for significantly more actions to be grouped into a single time step.
- Chained Variables for Complex Effects: The introduction of auxiliary "chained" variables is a clever way to model the cumulative and potentially non-commutative effects of multiple actions within a single time step, which is essential for the R²∃-step semantics.
- MaxSMT for Plan Optimization: Using MaxSMT as a post-processing step is an efficient way to prune redundant actions from highly parallel plans, improving plan quality without significantly increasing computation time.
- Ordering Matters: The choice of ordering for actions within a time step can significantly impact the efficiency of the encoding. Informing the ordering with a plan derived from a relaxed version of the problem proved to be particularly effective.
Key Results
The proposed R²Chained encoding significantly outperforms existing SMT-based planners (SEM+C, Springroll, SMTPlan) in terms of the number of problem instances solved across various numeric domains. For instance, in the Depots and Rovers domains, the R²Chained approach solved substantially more instances than its closest competitor. The R²Chained approach also achieved a dramatic decrease in the number of time steps required to find a solution, often needing less than half the steps of other planners for commonly solved instances. The MaxSMT-based redundant action removal step (R²O) was found to be very efficient, typically taking less than two seconds, and resulted in notable reductions in the number of actions in the plans.
Limitations and Future Work
- Ordering Heuristics: While they found that informing the ordering with a relaxed plan was beneficial, designing optimal orderings remains a challenge. They suggest that designing better orderings and heuristics is a direction for future work.
- Constraint Impact: The authors mention studying the effects of adding or removing implied constraints (like constraint (5) in the paper) as a future research direction.
- MaxSMT Plan Quality: While the MaxSMT step reduces redundant actions, the resulting plan is not guaranteed to be makespan-optimal, though it is usually significantly shorter.
Summary updated