Checking dynamic consistency of conditional hyper temporal networks via mean payoff games: Hardness and (pseudo) singly-exponential time algorithm

Abstract : Conditional Simple Temporal Network (CSTN) is a constraint-based graph-formalism for conditional temporal planning. It offers a more flexible formalism than the equivalent CSTP model of Tsamardinos et al. (2003), from which it was derived mainly as a sound formalization. Three notions of consistency arise for CSTNs: weak, strong, and dynamic. Dynamic consistency is the most interesting notion, but it is also the most challenging and it was conjectured to be hard to assess. Tsamardinos et al. (2003) gave a doubly-exponential time algorithm for checking dynamic consistency in CSTNs and to produce an exponentially sized dynamic execution strategy whenever the input CSTN is dynamically-consistent. CSTNs may be viewed as an extension of Simple Temporal Networks (STNs) (Dechter et al., 1991), directed weighted graphs where nodes represent events to be scheduled in time and arcs represent temporal distance constraints between pairs of events. Recently, STNs have been generalized into Hyper Temporal Networks (HyTNs), by considering weighted directed hypergraphs where each hyperarc models a disjunctive temporal constraint named hyperconstraint; being directed, the hyperarcs can be either multi-head or multi-tail. The computational equivalence between checking consistency in HyTNs and determining winning regions in Mean Payoff Games (MPGs) was also pointed out; MPGs are a family of 2-player infinite pebble games played on finite graphs, which is well known for having applications in model-checking and formal verification. In this work we introduce the Conditional Hyper Temporal Network (CHyTN) model, a natural extension and generalization of both the CSTN and the HyTN model which is obtained by blending them together. We show that deciding whether a given CSTN or CHyTN is dynamically-consistent is coNP-hard; and that deciding whether a given CHyTN is dynamically-consistent is PSPACE-hard, provided that the input instances are allowed to include both multi-head and multi-tail hyperarcs. In light of this, we continue our study by focusing on CHyTNs that allow only multi-head hyperarcs, and we offer the first deterministic (pseudo) singly-exponential time algorithm for the problem of checking the dynamic consistency of such CHyTNs, also producing a dynamic execution strategy whenever the input CHyTN is dynamically-consistent. Since CSTNs are a special case of CHyTNs, as a byproduct this provides the first sound-and-complete (pseudo) singly-exponential time algorithm for checking dynamic consistency in CSTNs. The proposed algorithm is based on a novel connection between CHyTNs and MPGs; due to the existence of efficient pseudo-polynomial time algorithms for MPGs, it is quite promising to be competitive in practice. The presentation of such connection is mediated by the HyTN model. In order to analyze the time complexity of the algorithm, we introduce a refined notion of dynamic consistency, named-dynamic consistency, and present a sharp lower bounding analysis on the critical value of the reaction timê ε where a CHyTN transits from being, to not being, dynamically-consistent. The proof technique introduced in this analysis ofˆεofˆ ofˆε is applicable more generally when dealing with linear difference constraints which include strict inequalities.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01719175
Contributor : Admin Upem <>
Submitted on : Wednesday, February 28, 2018 - 8:10:27 AM
Last modification on : Thursday, August 9, 2018 - 4:09:06 PM
Long-term archiving on : Monday, May 28, 2018 - 1:37:34 PM

File

conditional-temporal-networks1...
Files produced by the author(s)

Identifiers

Citation

Carlo Comin, Romeo Rizzi. Checking dynamic consistency of conditional hyper temporal networks via mean payoff games: Hardness and (pseudo) singly-exponential time algorithm. Information and Computation, Elsevier, 2018, 259 (3), pp.348-374. ⟨10.1016/j.ic.2017.08.008⟩. ⟨hal-01719175⟩

Share

Metrics

Record views

102

Files downloads

77