Abstract: This paper addresses the challenge of creating reliable schedules in automated planning under temporal uncertainty. By formalizing timeline-based planning and encoding it into Satisfiability Modulo Theories (SMT), the authors present a complete algorithm for generating "strongly controllable" plans. Their incremental SMT approach demonstrates significant performance gains in time and memory efficiency across various complex domains, including satellite operations and industrial machinery.
What Problem Does This Paper Address?
In high-stakes domains like aerospace (e.g., NASA’s Europa mission) or industrial manufacturing, planning is often "timeline-based." Instead of a simple sequence of actions, a plan consists of parallel timelines describing the state of various components over time.
Traditional timeline frameworks assume the "plan executor" has total control over the duration of every activity. In reality, many factors are uncontrollable: a satellite’s visibility window might last between 10 and 12 hours, or a data transmission might take anywhere from 5 to 7 minutes. If a plan is "brittle," a slight delay in an uncontrollable task can cause the entire mission to fail.
The authors tackle the Strong Controllability problem: finding a fixed schedule of start times for controllable actions that is robust against any valid duration the environment might "choose" for the uncontrollable ones. As shown in the Satellite domain example above, states like "Hidden" or "Visible" have uncertain durations (e.g., [10, 12]), requiring a planner that can account for these ranges.
Methods
The researchers bridge the gap between temporal logic and modern constraint solving through several key steps:
- Formalization: They extend "Allen’s Algebra" (a standard way of describing how time intervals relate, like during, before, or overlaps) to include quantitative bounds and uncertainty annotations.
- CU-Annotations: They introduce a system to flag specific states or synchronizations as either Controllable (decided by the planner) or Uncontrollable (decided by nature).
- SMT Encoding: The core innovation is translating the planning problem into a First-Order Logic formula using the theory of Linear Real Arithmetic (LRA) to represent time as a continuous (dense) value.
- Algorithms: They propose two ways to solve these formulas:
- Monolithic: Encoding the entire problem up to a fixed time horizon ($H$) into one large formula and using a quantifier-elimination procedure to handle the "for all possible uncertain durations" requirement.
- Incremental (Lazy): Starting with a small number of possible intervals and gradually increasing complexity only if a solution isn't found, leveraging the incremental features of modern SMT solvers like MathSAT5.
Key Results
The experimental results demonstrate that the Incremental SMT approach makes timeline planning with uncertainty computationally feasible across three distinct domains: Satellite, Machinery, and Meeting.
As detailed in the performance table, the Incremental approach offers substantial benefits:
- Speedup: In the "Meeting" domain, the Incremental approach found a solution in roughly 182 seconds, while the Monolithic approach timed out (TO) or ran out of memory (MO).
- Memory Efficiency: For the "Satellite" domain, the Incremental solver used only 31.9 MB of memory compared to the Monolithic solver’s 111.5 MB.
- Completeness: Unlike previous heuristic methods, this algorithm is complete—if a robust plan exists within the given time horizon, the algorithm is guaranteed to find it.
Limitations and Future Work
While this framework provides a robust foundation, several areas remain for future exploration:
- Bounded Horizon: The current algorithm requires a pre-defined time horizon ($H$) and cannot yet prove that a plan works for "infinite" time.
- Fixed Time-Triggered Plans: The paper focuses on "strong" controllability (fixing all times upfront). It does not yet address "dynamic" controllability, where the executor can adjust the plan in real-time based on observed durations.
- Resource Constraints: The model currently only handles time. Future work aims to include "consumable" resources, such as battery power or fuel levels, which are critical for real-world robotics and space applications.
Summary updated