Introduction
Temporal planning represents the intersection of planning and scheduling, requiring an AI to determine not only which actions to execute but also their precise timing and duration in continuous time. While finding a valid plan (satisficing) is well-studied, finding the optimal plan—minimizing either total duration (makespan) or cumulative action costs—is notoriously difficult due to the massive search space of overlapping actions. This paper introduces OMTPlan, the first framework for optimal temporal planning using Optimization Modulo Theory (OMT).
Methodology: OMTPlan and the Abstract Step
The authors leverage OMT, an extension of Satisfiability Modulo Theories (SMT) that handles logic formulas alongside optimization objectives over continuous and discrete variables. The core of their approach is an incremental algorithm based on a bounded encoding. Unlike traditional SAT-based planning, these discrete steps do not represent fixed time increments but rather "events" (the start or end of actions) in continuous time.
To prove optimality, the authors introduced a novel abstract step following the final concrete step $h$. This step uses "modification variables" ($mod_f$) to over-approximate all possible future states. If the OMT solver finds a plan using only concrete steps and confirms that no better cost is possible even with the abstract over-approximation, the plan is mathematically guaranteed to be optimal. This allows the system to "prove the negative"—that no plan better than the current one can ever exist.
Experimental Evaluation
The tool, ANML-OMT, was evaluated across five distinct domains: MAJSP and PAINTER (industrial makespan), MATCH-MS (classic makespan), MATCH-AC (action costs), and OVERSUB (synthetic oversubscription). The researchers compared ANML-OMT against OPTIC, the only other publicly available planner capable of proving optimality for these expressive temporal problems.
Key Results
The experiments demonstrated that the OMT-based approach is significantly more robust than traditional heuristic-based planners when dealing with complex, highly concurrent constraints.
As shown in the results table, the best configuration of the OMT planner (ANML-OMT-INC) solved 110 out of 200 instances, whereas OPTIC solved only 41. In domains like OVERSUB and PAINTER, the OMT approach was consistently faster, often by orders of magnitude. However, OPTIC performed exceptionally well on the MATCH-MS domain, solving all 30 instances. This highlights a specific trade-off: while OMT excels at concurrency, it struggles with long, purely sequential plans where the number of required steps ($h$) becomes very large.
Insights and Future Work
By treating time as a first-class continuous variable via Quantifier-Free Linear Real Arithmetic (QF_LRA), the planner avoids the precision loss and scaling issues inherent in discrete-time models. The use of an incremental OMT solver (specifically the OMSAT engine) provided a significant performance boost by allowing the solver to retain information from previous steps.
Current limitations include a restriction on "action self-overlapping" (starting a second instance of an action before the first finishes) and performance degradation in high-horizon sequential problems. Future research may explore hybridizing this OMT approach with heuristic searches or clock-based encodings to better handle long-horizon sequential planning tasks.
Summary updated