Dynamic Controllability of Temporal Constraint Networks: Analytical and Computational Improvements

Cycle 31th Oral Defence of the Phd Thesis

21 October 2019
Versione stampabile

Venue: Seminar Room “-1” – Department of Mathematics – Via Sommarive, 14 Povo - Trento
Time: 3.00 p.m.

  • Massimo Cairo - PhD in Mathematics


Dynamic controllability (called dynamic consistency in some contexts) is the ability of a planning agent to schedule the execution of some tasks on the time line, satisfying some given temporal constraints, in the presence of contingent parameters revealed to the agent during execution.
Many models have been presented to specify the nature of constraints and contingent parameters, which we refer to as “temporal constraint networks”.
This talk presents some contributions related to the dynamic controllability in two well-studied models of temporal constraint networks: Simple Temporal Networks with Uncertainty and Conditional Simple Temporal Networks.
Both Simple Temporal Networks with Uncertainty and Conditional Simple Temporal Networks are extensions of Simple Temporal Networks (STNs), which comprise a set of time-points (real-valued variables representing execution times) and binary difference constraints among them.
Simple Temporal Networks with Uncertainty extend STNs by introducing uncertainty on the execution time of some of the time-points.
Conditional Simple Temporal Networks extend STNs by introducing contingent conditions, observed during execution, that limit the applicability of time-points and constraints.
The main results presented are of two kinds: analytical and computational.
Analytical results comprise new approaches, simplified and/or more general, for proving analytical properties of temporal constraint networks.
Computational results comprise new algorithms, with improved asymptotic complexity, and new conditional lower bounds on the complexity, for computational problems related to temporal constraint networks, including checking their dynamic controllability.

Supervisor: Romeo Rizzi