Faster and Better Simple Temporal Problems

Dario Ostuni, Alice Raffaele, Romeo Rizzi, Matteo ZavatteriAAAI 2021 · DOI

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:

  1. 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.
  2. Rigid Components: Using Strongly Connected Components (SCCs), the algorithm identifies "rigid components"—sets of variables whose relative temporal distances are fixed.
  3. 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.
The epsilon-shift technique applied to rigid components (shaded areas) to satisfy strict constraints.

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.

Performance comparison across H000, H001, H025, and H100 benchmarks, showing the scalability of the proposed algorithms (OUR_*) versus SMT solvers.

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

BibTeX
@inproceedings{ostuni2021faster,
  author = {Dario Ostuni and Alice Raffaele and Romeo Rizzi and Matteo Zavatteri},
  title = {{Faster and Better Simple Temporal Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17415},
}

Loading related content...

Figure