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.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.