Vivek Nigam, Timed Collaborative Systems
Timed Collaborative Systems
Time often plays a key role when specifying the rules and requirements of a collaboration. For instance, policies and regulations, such as those regulating pharmaceutical trials on human subjects, contain specific time requirements, such as deadlines, which have to be obeyed by a collaboration. This paper introduces a model based on multiset rewriting that allows for the specification of policies and systems with explicit time. Time is discrete and is specified by timestamps attached to facts. Actions, goal and critical states may be constrained by means of relative time constraints. Moreover, actions may have non-deterministic effects, ie, they may have different outcomes whenever applied. We investigate the complexity of the plan compliance problem, which is of finding a plan that leads from an initial state to a desired goal state without reaching any undesired critical state. We consider all actions to be balanced, ie, their pre and post-conditions have the same number of facts. We then show that the plan compliance problem is PSPACE-complete for balanced systems containing only actions with deterministic effects and is EXPTIME-complete for balanced systems possibly containing actions with non-deterministic effects. For these results, there are no bounds on time nor on the number of nonces used in a plan. We also consider the same problem for progressing systems where actions can only be applied at most once at a given time. We show that the plan compliance problem is NP-complete for balanced progressing systems given appropriate bounds.
This is joint work with Max Kanovich, Andre Scedrov, Carolyn Talcott, Tajana Bar Kirigin and Ranko Perovic.