Checking dynamic consistency of conditional hyper temporal networks via mean payoff games

Conditional Simple Temporal Network(CSTN) is a constraint-based graph formalism for conditional temporal planning, which may be viewed as an extension of Simple Temporal Networks. Recently, STNshave been generalized into Hyper Temporal Networks(HyTNs), by considering weighted directed hypergraphs where each hyperarc models a disjunctive temporal constraint. We introduce the Conditional Hyper Temporal Network(CHyTN) model, a natural extension and generalization of both CSTNs and HyTNs, obtained by blending them together. We show that deciding whether a given CSTN is dynamically-consistent is coNP-hard, and that deciding whether a given CHyTN is dynamically-consistent is PSPACE-hard. Next, we offer the first deterministic (pseudo) singly-exponential time algorithm for checking DC in CHyTNs and CSTNs. To analyze the computational complexity of the proposed algorithm, we introduce a refined notion of DC, named epsilon-DC, presenting a sharp lower bounding analysis on the critical value of the reaction time where a conditional temporal network transits from being, to not being, dynamically-consistent. (c) 2017 Elsevier Inc. All rights reserved.