King's College London

Research portal

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

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish
Number of pages41
JournalINFORMATION AND COMPUTATION
Accepted/In press29 Sep 2020

Documents

King's Authors

Abstract

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.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454