Abstract
Temporal reasoning is a cornerstone of automated planning and scheduling. While the Simple Temporal Problem (STP) provides an efficient framework for basic constraints, real-world applications often require more expressive logic, such as strict inequalities and "not-equal" constraints. This paper introduces the Extended Simple Temporal Problem (ESTP) and a corresponding polynomial-time algorithm ($O(nm + h)$). By utilizing graph-based relaxation, rigid component identification, and a novel epsilon-shift technique, our approach scales to problems with 3 million variables, outperforming current state-of-the-art SMT solvers by orders of magnitude.
Introduction
In automated planning, temporal constraints are typically modeled using the Simple Temporal Problem (STP), which handles linear inequalities of the form $y - x \leq k$. However, many scenarios demand stricter requirements, such as "Task B must start strictly after Task A" ($B - A > 0$) or "Task A and Task B cannot be simultaneous" ($A - B \neq 0$). Previous attempts to incorporate these features often resulted in systems that were either too limited or computationally prohibitive.
The Extended Simple Temporal Problem (ESTP) pushes the "tractability frontier" by supporting standard inequalities, strict inequalities, and monotone Boolean formulas on "not-equal" inequations. This paper presents a robust, strongly polynomial algorithm to solve ESTPs efficiently.
Methodology: The ESTP Algorithm
The core of our approach involves transforming the ESTP into a graph-based consistency problem. The algorithm proceeds through several key stages:
- Relaxation and Red Arcs: Strict inequalities ($y - x < k$) are initially treated as non-strict ($y - x \leq k$) to construct a standard constraint graph. Edges derived from strict constraints are labeled as "red arcs." A critical theoretical insight is that any zero-weight cycle containing at least one red arc indicates inconsistency.
- Rigid Components: Using Strongly Connected Components (SCCs), the algorithm identifies "rigid components"—sets of variables whose relative temporal distances are fixed.
- Epsilon-Shift Technique: To satisfy strict and "not-equal" constraints simultaneously, the algorithm calculates a valid solution for the non-strict relaxation and then applies infinitesimal offsets ($\epsilon$). This ensures that variables within the same rigid component maintain their required distances while satisfying the strict logic of the ESTP.
Experimental Evaluation
We evaluated the algorithm against a suite of state-of-the-art Satisfiability Modulo Theory (SMT) solvers, including Yices2, CVC4, z3, and MathSAT5. Benchmarks were categorized into four classes to test various hardness profiles:
- H000: Consistent instances with deep shortest-path trees.
- H001 / H025: Inconsistent instances with single negative cycles of varying lengths.
- H100: Inconsistent instances containing a Hamiltonian negative cycle.
Results and Discussion
The experimental results highlight a significant performance gap between specialized graph algorithms and general-purpose SMT solvers. While SMT solvers like Yices2 perform adequately on small instances, they typically encounter timeouts or failures beyond 8,000 variables. In contrast, our algorithm demonstrates massive scalability, solving instances with up to 3 million variables in under 100 seconds.
The algorithm's strongly polynomial complexity ($O(nm + h)$) ensures that its runtime is independent of the weight values, making it exceptionally robust for large-scale temporal reasoning tasks.
Conclusion
The ESTP framework and its associated algorithm provide a powerful tool for complex temporal modeling. By bridging the gap between simple graph-based STP solvers and general-purpose SMT reasoning, we achieve unprecedented scalability for strict and disjunctive temporal constraints. Future work will focus on expanding the framework to include more complex Boolean logic and establishing a standardized benchmark suite for the community.
Summary updated