Simple Temporal Networks (STNs) are a widely used formalism for representing and reasoning about tem- poral constraints on activities. The dispatchability of an STN was originally defined as a guarantee that a specific real-time execution algorithm would necessarily satisfy all of the STN’s constraints while preserv- ing maximum flexibility but requiring minimal computation. A Simple Temporal Network with Uncertainty (STNU) augments an STN to accommodate actions with uncertain durations. However, the dispatchability of an STNU was defined differently: in terms of the dispatchability of its so-called STN projections. It was then argued informally that this definition provided a similar real-time execution guarantee, but without specifying the execution algorithm. This paper formally defines a real-time execution algorithm for STNUs that similarly preserves maximum flexibility while requiring minimal computation. It then proves that an STNU is dispatch- able if and only if every run of that real-time execution algorithm necessarily satisfies the STNU’s constraints no matter how the uncertain durations play out. By formally connecting STNU dispatchability to an explicit real-time execution algorithm, the paper fills in important elements of the foundations of the dispatchability of STNUs.

Foundations of Dispatchability for Simple Temporal Networks with Uncertainty

Hunsberger, Luke;Posenato, Roberto
2024-01-01

Abstract

Simple Temporal Networks (STNs) are a widely used formalism for representing and reasoning about tem- poral constraints on activities. The dispatchability of an STN was originally defined as a guarantee that a specific real-time execution algorithm would necessarily satisfy all of the STN’s constraints while preserv- ing maximum flexibility but requiring minimal computation. A Simple Temporal Network with Uncertainty (STNU) augments an STN to accommodate actions with uncertain durations. However, the dispatchability of an STNU was defined differently: in terms of the dispatchability of its so-called STN projections. It was then argued informally that this definition provided a similar real-time execution guarantee, but without specifying the execution algorithm. This paper formally defines a real-time execution algorithm for STNUs that similarly preserves maximum flexibility while requiring minimal computation. It then proves that an STNU is dispatch- able if and only if every run of that real-time execution algorithm necessarily satisfies the STNU’s constraints no matter how the uncertain durations play out. By formally connecting STNU dispatchability to an explicit real-time execution algorithm, the paper fills in important elements of the foundations of the dispatchability of STNUs.
2024
978-989-758-680-4
dispatchability, temporal constraint networks, uncertainty
File in questo prodotto:
File Dimensione Formato  
123600.pdf

accesso aperto

Descrizione: articolo versione editor
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 302.47 kB
Formato Adobe PDF
302.47 kB Adobe PDF Visualizza/Apri

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/1119986
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact