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

Massimo Cairo  PhD in Mathematics
Abstract:
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 wellstudied 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 timepoints (realvalued 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 timepoints.
Conditional Simple Temporal Networks extend STNs by introducing contingent conditions, observed during execution, that limit the applicability of timepoints 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