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.

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

Comin, Carlo;Rizzi, Romeo
2018-01-01

Abstract

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.
2018
Conditional temporal networks; Dynamic consistency; Mean payoff games; Simple temporal networks; Hyper temporal networks; Singly-exponential time; Reaction time
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/988557
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact