Introduction: The Gap in Temporal Reasoning
In AI planning and scheduling, reasoning about the timing of events is a fundamental challenge. Traditionally, researchers have relied on two main frameworks:
- Simple Temporal Problems (STPs): These handle basic constraints like "Task B must start 5 to 10 minutes after Task A." They are computationally efficient (polynomial time) but lack the ability to handle disjunctive "either/or" logic.
- Disjunctive Temporal Problems (DTPs): These offer high expressiveness, allowing for complex logic (e.g., "Task B must happen either in the morning or after Task A finishes"). However, they are NP-complete, leading to exponential search times as problem size increases.
The critical gap lies in modeling non-monotonic relationships—scenarios where the available window for one task shifts based on when another task is performed due to external factors like battery life or environmental conditions. This paper introduces "domain rules" to bridge this gap, offering a way to model realistic constraints without the computational explosion of DTPs.
Methods: Domain Rules and CRC Constraints
The proposed framework centers on Domain Rules, which take the conditional form: If event $X_i$ happens during interval $[a, b]$, then event $X_j$ must happen during interval $[c, d]$.
To solve these problems efficiently, the paper leverages two key theoretical concepts:
- Smoothness: A property where local search is guaranteed to move toward a solution. The author proves that while a single domain rule may not be "smooth," a set of rules describing a connected feasible region is.
- Connected Row-Convex (CRC) Constraints: By mapping the temporal problem onto a meta-level Constraint Satisfaction Problem (CSP), the author proves that the relationships between domain rules satisfy the CRC property. This allows for polynomial-time solutions using standard path-consistency algorithms.
The resulting SOLVE-STP-DOMAIN-RULES algorithm extends standard STP techniques (like distance graphs and negative cycle detection) to handle this conditional logic.
Illustrative Scenarios
As a theoretical work, the paper demonstrates its utility through high-complexity illustrative scenarios rather than empirical datasets:
- The Rover Scenario: Models a Mars rover where task timing depends on the interplay between non-monotonic battery power and solar energy availability.
- The Daily Schedule: A complex human planning problem involving travel options (e.g., bus vs. train) that change based on departure times and traffic.
Key Insights and Results
The most significant insight is that tractability is fundamentally linked to the geometry of the feasible region. If the valid times for two events form a single "connected" shape in a 2D plane, the problem remains easy to solve, even if the shape is non-linear or complex.
Key Results include: * Complexity Breakthrough: Proof that temporal problems with domain rules and connected feasible regions can be solved in polynomial time. * Algorithm Versatility: Provision of both deterministic (path-consistency) and randomized (random walk) algorithms. * Expressiveness: Successful modeling of non-monotonic behaviors common in physical systems (like resource depletion) that STPs cannot capture.
Limitations and Future Work
The primary limitation is the connectedness requirement. If a constraint forces a task into disconnected "islands" of valid time (e.g., "either very early or very late"), the problem reverts to a hard DTP. Future research may extend this "smoothness" approach to spatial reasoning or integrate user preferences into the tractable framework.
Summary updated