A Simple Temporal Network with Uncertainty (STNU) in- cludes real-valued variables, called time-points; binary differ- ence constraints on those time-points; and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web-service composition, and business processes. 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 + k2n + kn log n), where n is the number of time-points, m is the number of constraints, 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 algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.

Speeding Up the RUL¯ Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty

Luke Hunsberger;Roberto Posenato
2022

Abstract

A Simple Temporal Network with Uncertainty (STNU) in- cludes real-valued variables, called time-points; binary differ- ence constraints on those time-points; and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web-service composition, and business processes. 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 + k2n + kn log n), where n is the number of time-points, m is the number of constraints, 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 algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.
temporal constraint networks, dynamic controllability, checking algorithm, simple temporal netwok with uncertainty
File in questo prodotto:
File Dimensione Formato  
fastenRUL_Conference_PubblisherVersion.pdf

accesso aperto

Tipologia: Versione dell'editore
Licenza: Dominio pubblico
Dimensione 287.2 kB
Formato Adobe PDF
287.2 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/1072066
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact