Abstract
Automated planning and scheduling often rely on Simple Temporal Problems (STPs) for efficiency, yet these models lack the expressiveness to handle complex preferences or disjunctions. Conversely, Disjunctive Temporal Problems (DTPs) offer high expressiveness at the cost of NP-hard complexity. This paper introduces a polynomial-time algorithm for Extended Simple Temporal Problems (ESTPs) featuring piecewise constant preference functions. By reducing the scheduling problem to finding the largest weighted anti-chain in a partially ordered set (POSET) and subsequently to a Max-Flow problem, the authors demonstrate that optimal schedules can be found efficiently without the exponential overhead of traditional disjunctive reasoning.
Introduction: Bridging the Gap in Temporal Reasoning
In the field of automated planning, researchers face a trade-off between the simplicity of Simple Temporal Problems (STPs) and the expressiveness of Disjunctive Temporal Problems (DTPs). STPs represent constraints as simple intervals (e.g., "Task B must start 10–20 minutes after Task A ends") and are solvable in polynomial time using shortest-path algorithms. However, they cannot represent "either/or" choices or varying levels of preference for different time windows.
Extended Simple Temporal Problems (ESTPs) occupy a middle ground. They allow for piecewise constant preference functions—enabling users to specify that certain time intervals for an event are more desirable than others—and limited forms of disjunctions.
The primary challenge addressed in this research is proving that these more expressive problems can still be solved in polynomial time, avoiding the "exponential trap" typically associated with disjunctive constraints.
Methodology: Reduction to Max-Flow
The authors propose a novel reduction strategy that transforms the ESTP into a graph-theoretic optimization problem. The core of this approach is finding the Largest Weighted Anti-Chain in a Partially Ordered Set (POSET).
The algorithm follows four key steps:
- Interval Decomposition: The time domain for each event is partitioned into intervals where the preference value remains constant.
- Conflict Identification: The system identifies conflicts between these intervals. A "Size-1" conflict occurs if an interval is globally impossible, while a "Size-2" conflict occurs if two specific intervals for different events are mutually exclusive.
- POSET Construction: These conflicts and temporal dependencies are used to build a directed graph where nodes represent time intervals and edges represent precedence or conflict relationships.
- Max-Flow Reduction: The problem of selecting the optimal set of non-conflicting intervals is mapped to a standard Maximum Flow / Minimum Cut algorithm on a bipartite version of the graph.
By adjusting node weights using a sufficiently large constant $M$, the algorithm guarantees it will select exactly one valid time interval for every event in the system, maximizing the total preference sum.
Key Insights: The "Size-2" Breakthrough
The mathematical foundation of this polynomial-time guarantee lies in Lemma 6. The authors prove that within this framework, minimal conflicts involve at most two intervals. This "Size-2" property is critical; if conflicts required three or more intervals to trigger, the problem would likely escalate to NP-hard complexity. This insight allows preferences to be treated as a structured form of disjunction that remains computationally tractable.
Results and Complexity
The paper successfully establishes that ESTPs can be solved in polynomial time, with complexity proportional to the number of events and the number of steps in the preference functions. Beyond finding a valid schedule, the algorithm is guaranteed to find the optimal schedule that maximizes the sum of preferences across all variables. Furthermore, the algorithm serves as a consistency checker: if the resulting anti-chain does not include one interval for every variable, the constraints are mathematically inconsistent.
Limitations and Future Directions
While a significant step forward, the algorithm has specific constraints:
- Stepwise Functions: It is strictly limited to piecewise constant (stepwise) functions. Sloped preferences (e.g., "the earlier the better") must be approximated by multiple steps, increasing graph size.
- Domain-Only Disjunctions: Disjunctions are restricted to the domains of individual variables. Relative disjunctions (e.g., "Either A is 5 mins after B, OR A is 20 mins after C") still require NP-hard DTP solvers.
- Concave Functions: Optimizing the sum of preferences for concave functions remains an open challenge in this specific temporal context.
Summary updated