Resource Temporal Networks: Definition and Complexity

Philippe LaborieIJCAI 2003

Abstract

Resource Temporal Networks (RTNs) provide a unified framework for AI Planning and Scheduling by integrating absolute and relative state changes with numerical temporal constraints. This paper explores the computational complexity of RTNs, demonstrating that while finding a valid schedule is NP-Complete, checking the Necessary Truth Criterion (NTC)—determining if a condition must hold across all possible timings—is polynomial. This finding enables the development of more efficient solvers through powerful constraint propagation.

Introduction: Bridging Planning and Scheduling

Historically, the AI community has treated planning and scheduling as distinct domains. Planning focuses on "what" to do, dealing with absolute state changes and logical preconditions. Scheduling focuses on "when" to do it, managing relative resource consumption and numerical time constraints. As real-world applications, such as satellite power management, become increasingly complex, a unified formalism is required. Resource Temporal Networks (RTNs) address this need by merging absolute changes, relative changes, and numerical time into a single expressive framework.

The RTN Framework

An RTN tracks a numerical "fluent" (a value that changes over time) through four primary statement types:

  1. Absolute Changes ($A$): Setting the resource to a specific value $q$ at time $t$.
  2. Relative Changes ($R$): Increasing or decreasing the resource by $q$ at time $t$.
  3. Lower-than Conditions ($L$): Ensuring the level stays below $q$ for a specific duration.
  4. Greater-than Conditions ($G$): Ensuring the level stays above $q$ for a specific duration.

Timing relationships between these events are managed using Simple Temporal Networks (STNs). This structure allows RTNs to represent a wide array of problems, including STRIPS operators and PDDL 2.1 durative actions.

An RTN graph illustrating events (nodes) with resource changes and the temporal constraints (edges) between them.

Complexity and the Necessary Truth Criterion

The paper maps various RTN fragments to classic combinatorial problems like Subset Sum and Bin Packing to establish complexity bounds. A key finding is the "Complexity Split": while finding any valid solution for a general RTN is NP-Complete due to the hard combinatorial choices involved in task ordering, reasoning about the necessity of conditions is much more efficient.

The Necessary Truth Criterion (NTC) determines if a resource constraint will definitely be violated regardless of how task timings are adjusted within their allowed bounds. The author proves that computing the NTC is polynomial, specifically solvable in $O(\text{maxflow}(n, m))$ time. This is a significant result for the field, as it allows solvers to prune large parts of the search space efficiently.

A step function graph showing how discrete resource changes at specific time points result in a fluctuating resource level profile.

Conclusion and Future Directions

While RTNs offer a powerful unifying theory, several areas remain for future exploration. The current framework primarily addresses discrete, instantaneous changes; extending these complexity results to continuous resource changes (e.g., gradual battery drain) is a logical next step. Additionally, while the NTC is theoretically efficient, practical implementation within branching schemes and empirical benchmarking on multi-resource problems will be essential to realize the framework's full potential in real-world planning and scheduling systems.

Summary updated

BibTeX
@inproceedings{laborie2003resource,
  author = {Philippe Laborie},
  title = {{Resource Temporal Networks: Definition and Complexity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure