Dynamic Controllability of Parameterized CSTNUs
Journal
Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing
Type
conference contribution
Date Issued
2023-03
Author(s)
Abstract
A Conditional Simple Temporal Network with Uncertainty (CSTNU) models temporal constraint satisfaction problems in which the environment sets uncontrollable timepoints and conditions. The executor observes and reacts to such uncontrollable assignments as time advances with the CSTNU execution. However, there exist scenarios in which the occurrence of some future timepoints must be fixed as soon as the execution starts. We call these timepoints parameters. For a correct execution, parameters must assume values that guarantee the possibility of satisfying all temporal constraints, whatever the environment decides the execution time for uncontrollable timepoints and the truth value of conditions, i.e., dynamic controllability (DC). Here, we formalize the extension of the CSTNU with parameters. Furthermore, we define a set of rules to check the DC of such extended CSTNU. These rules additionally solve the problem inverse to checking DC: computing restrictions on parameter values that yield DC guarantees. The proposed rules can be composed into a sound and complete procedure.
Keywords
Temporal Constraint Network
Conditional
Uncertainty
Constraintpropagation
Dynamic controllability
File(s)![Thumbnail Image]()
Name
2023DynamicControllabilityOfParameterizedCSTNUs.pdf
Size
2.15 MB
Format
Adobe PDF
Checksum (MD5)
ea0fe9b9e1727228f96ca91d0be711c6