Strong Controllability of Temporal Networks with Decisions

A number of extensions of simple temporal networks have been proposed over the last years to face several sources of uncertainty, either in isolation or simultaneously. This paper focuses on a hierarchy of simple temporal networks where the top-level formalism is that of conditional simple temporal networks with uncertainty and decisions (CSTNUDs), a formalism dealing with controllable and uncontrollable durations and controllable and uncontrollable conditional constraints simultaneously. We propose an algorithm to check strong controllability of CSTNUDs. We prove that strong controllability of temporal networks in this hierarchy is NP-complete if controllable conditional constraints are considered.