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