A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL\$^-\$ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is \$O(mn + k^2n + knlog n)\$, where \$n\$ is the number of time-points, \$m\$ is the number of constraints (equivalently, the number of edges in the STNU graph), and \$k\$ is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new implementation of the algorithm that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.

### A note on speeding up DC-checking for STNUs

#### Abstract

A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL\$^-\$ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is \$O(mn + k^2n + knlog n)\$, where \$n\$ is the number of time-points, \$m\$ is the number of constraints (equivalently, the number of edges in the STNU graph), and \$k\$ is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new implementation of the algorithm that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.
##### Scheda breve Scheda completa Scheda completa (DC) temporal constraints, simple temporal network with uncertainty, dynamic controllability, controllability check algorithm
File in questo prodotto:
File
fasterRUL_TECH_REPORT.pdf

accesso aperto

Descrizione: rapporto tecnico finale
Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 1.25 MB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/1045707`
• ND
• ND
• ND