Pubblicazioni

Autori:

Hunsberger, Luke; Posenato, Roberto

Titolo:

Canonical Form of Nested Diamond Structures

Anno:

2025

Tipologia prodotto:

Rapporti di ricerca

Tipologia ANVUR:

Altro

Lingua:

Inglese

Formato:

Elettronico

Parole chiave:

Temporal constraint networks, dispatchable networks, simple temporal networks with uncertainty, dynamic controllability C

Breve descrizione dei contenuti:

A Simple Temporal Network with Uncertainty (STNU) is a data structure for representing and reasoning about time in contexts where some actions may have uncertain, but bounded durations. An STNU is dynamically controllable (DC) if there exists a strategy for executing its controllable timepoints such that no matter how the uncertain durations turn out, within their known bounds, all relevant constraints in the network will necessarily be satisfied. Several polynomial-time DC-checking algorithms have been presented in the literature. A real-time execution strategy, called RTE^*, has been defined that preserves maximum flexibility while requiring minimal real-time computation; however, that strategy only guarantees a successful execution if: (1) the network is extended to accommodate conditional wait constraints; and (2) the network satisfies an additional property called dispatchability, that is stronger than dynamic controllability. This report presents a novel theory of the dispatchability of Extended STNUs (ESTNUs) that is based on the canonical form of nested diamond structures. Each such structure entails an ordinary constraint that must be satisfied by any dispatchable ESTNU. This theory provides an avenue through which to explore more efficient algorithms for finding equivalent dispatchable networks having a minimal number of edges, which is important for limiting the computational requirements during real-time execution.

Dipartimento:

Id prodotto:

146004

Handle IRIS:

11562/1163111

ultima modifica:

28 maggio 2025

Citazione bibliografica:

Hunsberger, Luke; Posenato, Roberto, Canonical Form of Nested Diamond Structures, Dipartimento Informatica,  N°  , 2025

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo