Checking the Dynamic Consistency of Conditional Simple Temporal Networks with Bounded Reaction Times. .
abstract   bibtex   
A Conditional Simple Temporal Network (CSTN) includes not only time-points and temporal constraints, but also observation time-points whose execution yields information during run-time. This incrementally revealed information eventually determines a complete scenario. Different time-points and temporal constraints may apply in different scenarios. The most important property of a CSTN is whether it is dynamically consistent (DC)�that is, whether there exists a strategy for executing its time-points such that all applicable constraints are guaranteed to be satisfied no matter which scenario is incrementally revealed during execution. The definition of dynamic consistency allows an execution strategy to react to observations after any positive delay, no matter how small. An alternative definition allows instantaneous reactions. Recent work defined ?-dynamic consistency, which requires all reaction times to be bounded below by a fixed ? > 0. An exponential algorithm for checking the ?-DC property has been presented, but not empirically evaluated. This paper presents an ?-DC-checking algorithm that is based on the propagation of labeled constraints. The algorithm is an extension of an existing DC-checking algorithm for CSTNs. The new algorithm is proven to be sound and complete; and an empirical evaluation using networks drawn from real-world ex- amples demonstrates its scalability. This is the first empirical evaluation of any ?-DC-checking algorithm for CSTNs
@inproceeduings {icaps16-104,
  track={Main Track},
  title={Checking the Dynamic Consistency of Conditional Simple Temporal Networks with Bounded Reaction Times},
  authors={Luke Hunsberger, Roberto Posenato},
  abstract={A Conditional Simple Temporal Network (CSTN) includes not only time-points and temporal constraints, but also observation time-points whose execution yields information during run-time. This incrementally revealed information eventually determines a complete scenario. Different time-points and temporal constraints may apply in different scenarios.
The most important property of a CSTN is whether it is dynamically consistent (DC)�that is, whether there exists a strategy for executing its time-points such that all applicable constraints are guaranteed to be satisfied no matter which scenario is incrementally revealed during execution.
The definition of dynamic consistency allows an execution strategy to react to observations after any positive delay, no matter how small. An alternative definition allows instantaneous reactions. Recent work defined ?-dynamic consistency, which requires all reaction times to be bounded below by a fixed ? > 0. An exponential algorithm for checking the ?-DC property has been presented, but not empirically evaluated.
This paper presents an ?-DC-checking algorithm that is based on the propagation of labeled constraints. The algorithm is an extension of an existing DC-checking algorithm for CSTNs. The new algorithm is proven to be sound and complete; and an empirical evaluation using networks drawn from real-world ex- amples demonstrates its scalability. This is the first empirical evaluation of any ?-DC-checking algorithm for CSTNs},
  keywords={Scheduling,Temporal planning}
}

Downloads: 0