In many sectors of realworld industry, it is necessary to plan and schedule tasks allocated to agents participating in complex processes. Temporal planning aims to schedule tasks while respecting temporal constraints such as release times, maximum durations, and deadlines, which requires quantitative temporal reasoning. Over the years, several major application developers have highlighted the need for the explicit representation of actions with uncertain durations; efficient algorithms for determining whether plans involving such actions are controllable; and efficient algorithms for converting such plans into forms that enable them to be executed in real time with minimal computation, while preserving maximum flexibility. A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is a triple (𝒯, 𝒞, ℒ) where 𝒯 is a set of realvalued variables called timepoints, 𝒞 is a set of constraints of the form YX ≤ δ, where X, Y ∈ 𝒯 and δ ∈ 𝐑, and ℒ is a set of contingent links of the form (A,x,y,C), where A,C ∈ 𝒯 and 0 < x < y < ∞. A contingent link (A,x,y,C) represents an uncertain duration where A is the activation timepoint, C is the contingent timepoint, and yx is the uncertainty in the duration CA. Typically, an executor controls the execution of A, but only observes the execution of C in real time. Although uncontrollable, the duration is guaranteed to satisfy CA ∈ [x,y]. We let n = 𝒯, m = 𝒞 and k = ℒ. An STNU graph is a pair (𝒯, ℰ), where the timepoints in 𝒯 serve as nodes in the graph, and the edges in ℰ correspond to the constraints in 𝒞 and contingent links in ℒ. For each YX ≤ δ in 𝒞, ℰ contains an ordinary edge Xδ>Y. For each (A,x,y,C) ∈ ℒ, ℰ contains a lowercase (LC) edge, Ac:y>C, and an uppercase (UC) edge, CC:y>A, representing the respective possibilities that CA might take its minimum or maximum value. The LOedges are the LC or ordinary edges; the OUedges are the ordinary or UC edges. For any STNU, it is important to determine whether it is dynamically controllable (DC) (i.e., whether it is possible, in real time, to schedule its noncontingent timepoints such that all constraints will necessarily be satisfied no matter what durations turn out for the contingent links). Polynomialtime algorithms are available to solve this DCchecking problem. Each uses rules to generate new edges aiming to bypass certain kinds of edges in the STNU graph. Morris' O(n⁴)time DCchecking algorithm [Paul Morris, 2006] starts from LC edges, propagating forward along OUedges, looking for opportunities to generate new OUedges that bypass the LC edges. Morris' O(n³)time algorithm [Morris, 2014] starts from negative OUedges, propagating backward along LOedges, aiming to bypass negative edges with nonnegative edges. The O(mn+k²n + knlog n)time RUL¯ algorithm [Massimo Cairo et al., 2018] starts from UC edges, propagating backward along LOedges, aiming to bypass UC edges with ordinary edges. After propagating, each algorithm checks for certain kinds of negative cycles to decide DCvs.nonDC. However, being DC only asserts the existence of a dynamic scheduler. It is also crucial to be able to execute a DC STNU efficiently in real time. For maximum flexibility and minimal space and time requirements, a dynamic scheduler for an STNU is typically computed incrementally, in real time, so that it can react to observations of contingent executions as they occur. An efficient dynamic scheduler can be realized by first transforming an STNU into an equivalent dispatchable form [Muscettola et al., 1998; Ioannis Tsamardinos et al., 1998]. Then, to execute the dispatchable STNU, it suffices to maintain timewindows for each timepoint and, as each timepoint X is executed, only updating timewindows for neighbors of X in the graph. Dispatchable STNUs are very important in applications that demand quick responses to observations of contingent events. Of the existing DCchecking algorithms, only Morris' O(n³)time algorithm necessarily generates a dispatchable STNU for DC inputs. This abstract describes a faster, O(mn + kn² + n² log n)time algorithm for converting DC STNUs into dispatchable form. (The full journal article is available elsewhere [Luke Hunsberger and Roberto Posenato, 2023].) This improvement is significant for applications (e.g., modeling business processes) where networks are typically sparse. For example, if m = O(n log n) and k = O(log n), then our algorithm runs in O(n²log n) ≪ O(n³) time. Our new Fast Dispatch algorithm, FD_STNU, has three phases. The first phase is similar to the RUL¯ DCchecking algorithm, but generates an orderofmagnitude fewer edges overall, while also generating new UC edges that correspond to wait constraints. The second phase is a version of Morris' 2006 algorithm that propagates forward from LC edges, but only along LOedges, aiming to generate ordinary bypass edges. The third phase focuses on the subgraph of ordinary edges, which comprise a Simple Temporal Network (STN). It uses an existing dispatchability algorithm for STNs [Ioannis Tsamardinos et al., 1998] to convert that ordinary subgraph into a dispatchable STN. After completing the three phases, the STNU is guaranteed to be dispatchable. We provide the source code of a Java implementation of the considered algorithms (Morris, RUL¯, and FD_STNU) [Posenato, 2022] and the benchmarks used to compare their performances.
Converting Simple Temporal Networks with Uncertainty into Dispatchable Form  Faster (Extended Abstract)
Luke Hunsberger;Roberto Posenato^{}
20230101
Abstract
In many sectors of realworld industry, it is necessary to plan and schedule tasks allocated to agents participating in complex processes. Temporal planning aims to schedule tasks while respecting temporal constraints such as release times, maximum durations, and deadlines, which requires quantitative temporal reasoning. Over the years, several major application developers have highlighted the need for the explicit representation of actions with uncertain durations; efficient algorithms for determining whether plans involving such actions are controllable; and efficient algorithms for converting such plans into forms that enable them to be executed in real time with minimal computation, while preserving maximum flexibility. A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is a triple (𝒯, 𝒞, ℒ) where 𝒯 is a set of realvalued variables called timepoints, 𝒞 is a set of constraints of the form YX ≤ δ, where X, Y ∈ 𝒯 and δ ∈ 𝐑, and ℒ is a set of contingent links of the form (A,x,y,C), where A,C ∈ 𝒯 and 0 < x < y < ∞. A contingent link (A,x,y,C) represents an uncertain duration where A is the activation timepoint, C is the contingent timepoint, and yx is the uncertainty in the duration CA. Typically, an executor controls the execution of A, but only observes the execution of C in real time. Although uncontrollable, the duration is guaranteed to satisfy CA ∈ [x,y]. We let n = 𝒯, m = 𝒞 and k = ℒ. An STNU graph is a pair (𝒯, ℰ), where the timepoints in 𝒯 serve as nodes in the graph, and the edges in ℰ correspond to the constraints in 𝒞 and contingent links in ℒ. For each YX ≤ δ in 𝒞, ℰ contains an ordinary edge Xδ>Y. For each (A,x,y,C) ∈ ℒ, ℰ contains a lowercase (LC) edge, Ac:y>C, and an uppercase (UC) edge, CC:y>A, representing the respective possibilities that CA might take its minimum or maximum value. The LOedges are the LC or ordinary edges; the OUedges are the ordinary or UC edges. For any STNU, it is important to determine whether it is dynamically controllable (DC) (i.e., whether it is possible, in real time, to schedule its noncontingent timepoints such that all constraints will necessarily be satisfied no matter what durations turn out for the contingent links). Polynomialtime algorithms are available to solve this DCchecking problem. Each uses rules to generate new edges aiming to bypass certain kinds of edges in the STNU graph. Morris' O(n⁴)time DCchecking algorithm [Paul Morris, 2006] starts from LC edges, propagating forward along OUedges, looking for opportunities to generate new OUedges that bypass the LC edges. Morris' O(n³)time algorithm [Morris, 2014] starts from negative OUedges, propagating backward along LOedges, aiming to bypass negative edges with nonnegative edges. The O(mn+k²n + knlog n)time RUL¯ algorithm [Massimo Cairo et al., 2018] starts from UC edges, propagating backward along LOedges, aiming to bypass UC edges with ordinary edges. After propagating, each algorithm checks for certain kinds of negative cycles to decide DCvs.nonDC. However, being DC only asserts the existence of a dynamic scheduler. It is also crucial to be able to execute a DC STNU efficiently in real time. For maximum flexibility and minimal space and time requirements, a dynamic scheduler for an STNU is typically computed incrementally, in real time, so that it can react to observations of contingent executions as they occur. An efficient dynamic scheduler can be realized by first transforming an STNU into an equivalent dispatchable form [Muscettola et al., 1998; Ioannis Tsamardinos et al., 1998]. Then, to execute the dispatchable STNU, it suffices to maintain timewindows for each timepoint and, as each timepoint X is executed, only updating timewindows for neighbors of X in the graph. Dispatchable STNUs are very important in applications that demand quick responses to observations of contingent events. Of the existing DCchecking algorithms, only Morris' O(n³)time algorithm necessarily generates a dispatchable STNU for DC inputs. This abstract describes a faster, O(mn + kn² + n² log n)time algorithm for converting DC STNUs into dispatchable form. (The full journal article is available elsewhere [Luke Hunsberger and Roberto Posenato, 2023].) This improvement is significant for applications (e.g., modeling business processes) where networks are typically sparse. For example, if m = O(n log n) and k = O(log n), then our algorithm runs in O(n²log n) ≪ O(n³) time. Our new Fast Dispatch algorithm, FD_STNU, has three phases. The first phase is similar to the RUL¯ DCchecking algorithm, but generates an orderofmagnitude fewer edges overall, while also generating new UC edges that correspond to wait constraints. The second phase is a version of Morris' 2006 algorithm that propagates forward from LC edges, but only along LOedges, aiming to generate ordinary bypass edges. The third phase focuses on the subgraph of ordinary edges, which comprise a Simple Temporal Network (STN). It uses an existing dispatchability algorithm for STNs [Ioannis Tsamardinos et al., 1998] to convert that ordinary subgraph into a dispatchable STN. After completing the three phases, the STNU is guaranteed to be dispatchable. We provide the source code of a Java implementation of the considered algorithms (Morris, RUL¯, and FD_STNU) [Posenato, 2022] and the benchmarks used to compare their performances.File  Dimensione  Formato  

LIPIcsTIME202320.pdf
accesso aperto
Descrizione: Extended abstract
Tipologia:
Versione dell'editore
Licenza:
Creative commons
Dimensione
469.2 kB
Formato
Adobe PDF

469.2 kB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.