Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertainty (Extended Abstract)

Nikhil Bhargava, Brian C. WilliamsIJCAI 2019 · DOI

TL;DR

This paper tackles the computational complexity of checking whether a plan can be executed given temporal constraints, especially when those constraints involve conditions, choices (disjunctions), and unpredictable events (uncertainty). The authors provide tight complexity bounds, remarkably showing that all these complex controllability problems can be solved within PSPACE, a significant improvement over previous, looser bounds.

What Problem Does This Paper Address?

In temporal planning, we often model real-world scenarios using temporal networks. These networks define events (timepoints) and the relationships between them (constraints). The core challenge is determining "controllability": can we always find a valid schedule that satisfies all constraints, even when faced with uncertainty or choices?

While simpler temporal networks have well-understood computational complexities, adding features like:

  • Conditions: Actions that are only relevant under certain circumstances.
  • Disjunctions: Choices between different ways an event can occur (e.g., "eat lunch either 30 minutes before swimming or immediately after").
  • Uncertainty: Events outside the scheduler's control (e.g., traffic delays).

makes controllability checking much harder. Previous research had established that some of these problems were at least EXPTIME-hard, and some even EXPSPACE-hard, with very loose upper bounds. This left a significant gap in our understanding of the true computational cost of using these more expressive, yet complex, temporal models. This paper aims to close that gap by providing tight complexity bounds for controllability checking across various combinations of these features.

Methods

The authors' approach involves two main steps: establishing lower bounds (hardness) and then proving upper bounds (completeness) for the controllability decision problems.

  1. Hardness Results: They leverage existing hardness results for simpler temporal networks and extend them. For more complex networks involving disjunctions and uncertainty, they provide tighter analyses by reducing known hard problems (like 3SAT and TQBF) to their temporal network problems. This demonstrates that these problems are inherently difficult.
  2. Completeness Results: The core of their novel contribution lies here. They develop a general technique to map temporal network constraints to a system of conditional linear inequalities. By carefully quantifying over variables representing scheduler choices and nature's uncertainty, they can encode the different types of controllability (strong, weak, and dynamic) as problems in quantified linear systems. The order and type of quantifiers (existential/universal) directly correspond to the type of controllability being checked. They also introduce a recursive algorithm (Algorithm 1) specifically for checking dynamic controllability, which forms the basis for their PSPACE-completeness proofs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Remarkable PSPACE Bound: The most striking finding is that all the considered controllability problems (strong, weak, and dynamic) for temporal networks with conditions, disjunctions, and uncertainty are solvable in PSPACE. This is a unified and surprisingly tight bound, suggesting that these complex problems are not as computationally intractable as previously feared.
  • Subtle Differences in Disjunctions: The paper highlights a difference in the complexity of strong controllability between TCSPUs and DTNUs. While both have similar complexities for weak and dynamic controllability, DTNUs (which allow disjunctions to span multiple links) are harder for strong controllability than TCSPUs (which have simpler disjunctions). This suggests that the structure of disjunctions matters.
  • Uncertainty's Low Cost for Strong Controllability: Adding uncertainty to conditional temporal networks (CSTNUs) doesn't increase the complexity of checking strong controllability, which remains in P. This is a practical insight for modelers.
  • Dynamic Controllability is the Bottleneck: For most network types, dynamic controllability is PSPACE-complete. This is a significant jump from the polynomial-time solvability of dynamic controllability for simple temporal networks with uncertainty (STNUs). This implies that if dynamic controllability is crucial, simplifying the temporal model to an STNU might be highly beneficial, even if it sacrifices expressiveness.

Key Results

The paper provides tight complexity bounds for various temporal network types:

  • Strong Controllability (SC):
    • CSTNU: P
    • TCSPU: NP-complete
    • CDTNU: Σ₂-complete
    • DTNU: Σ₂-complete
  • Weak Controllability (WC):
    • CSTNU: coNP-complete
    • TCSPU: Π₂-complete
    • CDTNU: Π₂-complete
    • DTNU: Π₂-complete
  • Dynamic Controllability (DC):
    • CSTNU, TCSPU, DTNU, CDTNU: All PSPACE-complete

The paper's main quantitative result is the establishment of these tight bounds, particularly the PSPACE completeness for dynamic controllability across many complex network types.

Limitations and Future Work

  • Algorithm Practicality: While the paper establishes PSPACE bounds, the proofs often rely on recursive enumeration of certificates, which might be impractical for real-world applications. The authors explicitly state that developing novel, practical algorithms that respect these polynomial bounds is a key area for future research.
  • Specific Network Types: The paper focuses on specific combinations of features. Further work could explore other combinations or more complex temporal constraint types.
  • Algorithmic Development: The primary limitation acknowledged is the lack of efficient algorithms. The theoretical bounds are established, but translating them into efficient solvers remains an open challenge.

Summary updated

BibTeX
@inproceedings{bhargava2019complexity,
  author = {Nikhil Bhargava and Brian C. Williams},
  title = {{Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertainty (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/886},
}
Figure