Temporal networks are expressive formalisms employed in AI to model, validate, and execute temporal plans. The core parts of a temporal network are a finite set of real variables called time points and a finite set of constraints bounding the minimal and/or maximal temporal distance between pairs of time points. When uncontrollable choices are considered, a problem of interest is determining whether or not a network is dynamically controllable. That is, whether there exists a strategy that, based only on the values already assigned to uncontrollable variables, progressively assigns the controllable variables with their final values in such a way that all constraints will be met in the end. Current single-strategy synthesis approaches are mainly based on constraint propagation or controller synthesis for timed game automata. In this paper we show how to model a temporal network as a Discrete Event System (DES) so as to leverage on Supervisory Control Theory to synthesize all dynamic integer strategies within a finite time horizon.

Dynamic Controllability of Temporal Networks via Supervisory Control

Matteo Zavatteri
;
Romeo Rizzi;Tiziano Villa
2022

Abstract

Temporal networks are expressive formalisms employed in AI to model, validate, and execute temporal plans. The core parts of a temporal network are a finite set of real variables called time points and a finite set of constraints bounding the minimal and/or maximal temporal distance between pairs of time points. When uncontrollable choices are considered, a problem of interest is determining whether or not a network is dynamically controllable. That is, whether there exists a strategy that, based only on the values already assigned to uncontrollable variables, progressively assigns the controllable variables with their final values in such a way that all constraints will be met in the end. Current single-strategy synthesis approaches are mainly based on constraint propagation or controller synthesis for timed game automata. In this paper we show how to model a temporal network as a Discrete Event System (DES) so as to leverage on Supervisory Control Theory to synthesize all dynamic integer strategies within a finite time horizon.
AI, formal methods, temporal network, discrete event system, supervisory control
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1077648
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact