A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about temporal constraints on activities, including those with uncertain durations. An STNU is dispatchable if it can be flexibly and efficiently executed in real time while guaranteeing that all relevant constraints are satisfied. The number of edges in a dispatchable network affects the computational work that must be done during real-time execution. Recent work presented an O(k n³)-time algorithm for converting a dispatchable STNU into an equivalent dispatchable network having a minimal number of edges, where n is the number of timepoints and k is the number of actions with uncertain durations. This paper presents a modification of that algorithm, making it an order of magnitude faster, down to O(n³). Given that in typical applications k = O(n), this represents an effective order-of-magnitude reduction from O(n⁴) to O(n³).

Faster Algorithm for Converting an STNU into Minimal Dispatchable Form

Roberto Posenato
2024-01-01

Abstract

A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about temporal constraints on activities, including those with uncertain durations. An STNU is dispatchable if it can be flexibly and efficiently executed in real time while guaranteeing that all relevant constraints are satisfied. The number of edges in a dispatchable network affects the computational work that must be done during real-time execution. Recent work presented an O(k n³)-time algorithm for converting a dispatchable STNU into an equivalent dispatchable network having a minimal number of edges, where n is the number of timepoints and k is the number of actions with uncertain durations. This paper presents a modification of that algorithm, making it an order of magnitude faster, down to O(n³). Given that in typical applications k = O(n), this represents an effective order-of-magnitude reduction from O(n⁴) to O(n³).
2024
978-3-95977-349-2
Temporal constraint networks, dispatchable networks
File in questo prodotto:
File Dimensione Formato  
LIPIcs.TIME.2024.11.pdf

accesso aperto

Descrizione: articolo
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 836.46 kB
Formato Adobe PDF
836.46 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/1143937
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact