In the field of automated planning, finding an optimal solution—the fastest or most cost-effective sequence of actions—is a significant challenge. A recent paper from AAAI-24, "Abstract Action Scheduling for Optimal Temporal Planning via OMT," introduces a novel approach to accelerate this search by refining the "abstract" component of the search space.
The Challenge of Optimal Temporal Planning
Temporal planning involves scheduling actions with specific durations and complex dependencies. For instance, a package cannot be unloaded before the transport vehicle arrives. Optimal Temporal Planning (OTP) seeks to minimize the total time (makespan) or total cost.
Modern techniques often reduce this problem to a series of queries for an Optimization Modulo Theory (OMT) solver. The solver examines a "bounded" version of the problem (e.g., "Can we solve this in $h$ steps?"). To ensure optimality, researchers use an abstract step—a mathematical over-approximation of all possible future actions beyond the current bound.
However, previous abstractions were often too permissive. They allowed for "spurious models" where actions could logically enable themselves in circular loops (e.g., a robot simultaneously loading and unloading a package to "create" it). These loose abstractions forced solvers to explore unnecessarily deep search trees to prove optimality.
Methods: Abstract Action Scheduling
The authors, Stefan Panjkovic and Andrea Micheli, propose a refined encoding called Abstract Action Scheduling. This method tightens the abstraction by enforcing a logical timeline on abstract actions.
- Symbolic Timelines: Instead of treating the abstract step as an unordered set of effects, every abstract action is assigned a symbolic start time ($t^a_h$).
- Causal Ordering: Constraints ($\phi^{SCHED}_h$) require that if an action's precondition is not met by the end of the concrete plan, it must be preceded by an abstract effect that satisfies it.
- Loop Breaking: By enforcing that effects must occur strictly before the conditions they satisfy, the encoding mathematically forbids circular self-enabling loops.
- Improved Objective Function: A new variable, $t_{obj}$, calculates the makespan by considering the end times of both concrete and abstract actions, providing a more accurate lower bound.
Experimental Evaluation
The approach was evaluated using standard benchmarks from the 2014 International Planning Competition (e.g., Driverlog, Satellite) and industrial benchmarks (e.g., Majsp, Painter). The new encoding ($Z3^{OUR}$) was compared against the previous state-of-the-art OMT encoder ($Z3^{PM}$) and the heuristic-search-based OPTIC planner.
Key Results and Insights
The results demonstrate a significant advancement over existing methods. The core insight is treating the abstract step as a symbolic version of an admissible heuristic. Just as a better heuristic aids A* search, a tighter abstract encoding helps the OMT solver terminate earlier.
- Coverage: The new approach solved 148 instances optimally, nearly doubling the 78 instances solved by the previous OMT-based state-of-the-art.
- Speedup: In domains like Majsp and Match, the solver reached the optimal bound at a much lower step ($h$), leading to orders-of-magnitude faster solving times.
- Efficiency: As shown in the performance plots, the $Z3^{OUR}$ variants consistently outperform both previous OMT encoders and the OPTIC planner.
Conclusion and Future Work
While the new abstraction is significantly tighter, it remains an over-approximation. It captures causal and temporal dependencies but does not yet account for all constraints, such as resource capacity, in the abstract step.
Future research directions include integrating this precise abstract encoding as a heuristic within traditional search-based planners and comparing OMT solvers against Mixed Integer Linear Programming (MILP) solvers using this scheduling encoding.
Summary updated