Consistency Checking of STNs with Decisions: Managing Temporal and Access-Control Constraints in a Seamless Way

Matteo Zavatteri, Carlo Combi, Romeo Rizzi, Luca Viganò

Research output: Contribution to journalArticlepeer-review

138 Downloads (Pure)


A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN by adding decision time points to model temporal plans with decisions. A decision time point is a special kind of time point that once executed allows for deciding a truth value for an associated Boolean proposition. Furthermore, STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i.e., complete truth value assignments to the propositions) they are relevant. In this paper, we deal with the use of STNDs for modeling and synthesizing execution strategies on real world planning problems, by considering some motivating scenarios from the area of healthcare processes. More precisely, we focus on the issue of checking the consistency of STNDs and propose an incremental hybrid SAT-based consistency checking algorithm for STNDs that (i) is faster than the one previously proposed and (ii) allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). We employ STNDs to model and reason about both temporal and access-control constraints. We carry out an experimental evaluation with Kappa, a tool that we developed for STNDs. Finally, as a last contribution from the theoretical side, since consistency of STNDs is equivalent to consistency of disjunctive temporal networks (DTNs), as for both formalisms consistency is NP-complete, we show how any STND can be easily translated into a DTN and vice versa.
Original languageEnglish
Number of pages41
Publication statusAccepted/In press - 29 Sept 2020


Dive into the research topics of 'Consistency Checking of STNs with Decisions: Managing Temporal and Access-Control Constraints in a Seamless Way'. Together they form a unique fingerprint.

Cite this