Simple Temporal Networks with Partially Shrinkable Uncertainty [original]

Simple Temporal Networks with Partially Shrinkable Uncertainty∗

Andreas Lanz1, Roberto Posenato2, Carlo Combi2, Manfred Reichert1

1Institute of Databases and Information Systems, University of Ulm, Germany

2Department of Computer Science, University of Verona, Italy

Keywords: Simple Temporal Constraint Network with Uncertainty, STNU, Controllability, Guarded Constraints

Abstract:

The Simple Temporal Network with Uncertainty (STNU) model focuses on the representation and evaluation of

temporal constraints on time-point variables (timepoints), of which some (i.e., contingent timepoints) cannot be

assigned (i.e., executed by the system), but only be observed. Moreover, a temporal constraint is expressed as an

admissible range of delays between two timepoints. Regarding the STNU model, it is interesting to determine

whether it is possible to execute all the timepoints under the control of the system, while still satisfying all given

constraints, no matter when the contingent timepoints happen within the given time ranges (controllability

check). Existing approaches assume that the original contingent time range cannot be modified during execution.

In real world, however, the allowed time range may change within certain boundaries, but cannot be completely

shrunk. To represent such possibility more properly, we propose Simple Temporal Network with Partially

Shrinkable Uncertainty (STNPSU) as an extension of STNU. In particular, STNPSUs allow representing a

contingent range in a way that can be shrunk during run time as long as shrinking does not go beyond a given

threshold. We further show that STNPSUs allow representing STNUs as a special case, while maintaining the

same efficiency for both controllability checks and execution.

1 INTRODUCTION

For more than a decade, the temporal constraint com-

munity has focused on the concept of controllabil-

ity (Morris et al., 2001). Given a set of temporal

constraints, of which each is expressed as an admissi-

ble range of delays between two time-point variables

(timepoints for short), we distinguish two types of

constraints: contingent and requirement constraints.

The latter represent the standard temporal constraints,

where both timepoints are under control of the system

that “executes” the timepoints according to the as-

signed constraints (i.e., the system fixes the timepoints

on the time line). This means that, during execution,

the range admissible for some timepoints could be re-

stricted by the system as it depends on the execution

of already executed timepoints. In turn, contingent

constraints are related to pairs of timepoints of which

one (i.e., the contingent timepoint) is not under control

of the system. Contingent timepoints are either given

by the environment (Morris et al., 2001), i.e., they are

related to uncontrollable, but expected, events, or by

an external agent (i.e., human or software) who may

decide autonomously when to execute the contingent

timepoint. Considering this scenario, the attention of

∗

This paper is a short version. A more complete version

is described in a technical report (Lanz et al., 2014).

the temporal constraint community has moved from

the problem of consistency, which consists of deter-

mining whether there exists an execution of all time-

points satisfying all given constraints (Dechter et al.,

1991), to the problem of controllability; i.e., to deter-

mine whether it is possible to execute all timepoints

under the control of the system, while satisfying all

given constraints, no matter when the contingent time-

points happen within their given time ranges (Morris

et al., 2001).

Most contributions from literature assume that the

original time range of a contingent constraint cannot

be modified during execution. Thus there is no dif-

ference between contingent timepoints given by the

environment and the ones executed by external agents.

In the real world, however, it is quite common that

during execution the allowed time range may change,

although it cannot be completely shrunk. To repre-

sent the behavior of external agents more properly, we

may assume that an agent accepts certain reductions

(i.e., modifications) of the initial execution range, as

long as these do not go beyond a given threshold. In

other words, there is an unshrinkable range of execu-

tion time the agent can always use. Further, this range

is included into a larger one, the system may shrink

during execution. The basic idea of our approach is to

represent the fact that both the agent and the system

T1 Biking

[5,20]

T2 Stretching

[10,40]

[1,5]

[25,50]

(a) Rigid temporal ranges

T1 Biking

[5,20]

T2 Stretching

[10,[15,20],40]

[1,5]

[25,50]

(b) Flexible temporal ranges

Figure 1: A simple physiotherapy. Range

[x,y]

represents

the minimum and maximum allowed duration (in minutes)

for the corresponding activity.

are aware that some timepoints of the larger time range

may be removed before starting the agent’s activity.

For example, consider a physiotherapy (cf. Fig. 1)

consisting of two subsequent activities, namely Biking

and Stretching, with one overall temporal constraint.

The first activity has an allowed duration range, while

its actual duration is decided by the physiotherapist

according to the patient’s state. The second activity,

i.e., the stretching exercise, is performed by the pa-

tient over a time period, which is decided by another

therapist who considers both the state of the patient

and the goal of the therapy. Let us assume that the

given ranges are as depicted in Fig. 1 (a): activities are

visualized as rounded boxes and subsequent activities

are linked to their predecessor through a directed arc.

Temporal constraints are represented through arcs to-

gether with their related ranges. Activities Biking and

Stretching have possible durations within ranges

[5,20]

and

[10,40]

, respectively, which are autonomously de-

cided by therapists. However, the overall therapy must

be within range

[25,50]

, assuming that it may take

between 1 and 5 time units to start Stretching after end-

ing Biking. Note that for this scenario it can be easily

verified that the corresponding temporal network is

not controllable, as there is no way to ask the second

activity to have a duration depending on the actual

duration of the first activity.

As more realistic representation of this scenario,

the second therapist may accept that the allowed dura-

tion range may be shrunk during execution, while guar-

anteeing that the “core” range

[15,20]

can be always

applied when executing Stretching. This scenario is

depicted in Fig. 1 (b) where the range is represented as

[10,[15,20],40]

, highlighting the non-shrinkable part.

One can easily observe that in this case the network can

be executed in a way satisfying all constraints, while

still allowing the therapists to autonomously choose

the durations of the involved activities.

This paper discusses how to represent and deal with

the described extension of contingent constraints in

simple temporal constraint networks with uncertainty

(STNUs), i.e., temporal networks that allow represent-

ing both requirement and contingent constraints (Mor-

ris et al., 2001). In addition to dynamic controllability,

we discuss that there are no alternative representations

of such shrinkable contingent constraints based on

compositions of standard requirement and contingent

constraints. Moreover, we generalize shrinkable con-

straints to represent time ranges having certain “guards”

on their possible lower and upper bounds.

2 BACKGROUND AND RELATED

WORK

A Simple Temporal Network (STN) (Dechter et al.,

1991) is a directed weighted graph where a node repre-

sents a time-point variable (timepoint), usually corre-

sponding to the start or end of activities, and an edge

represents a lower and an upper bound constraint on

the distance between the two timepoints it connects.

Each STN is associated with a distance graph, derived

from the upper and lower bound constraints, where

a constraint between a pair of timepoints

and

represented as two edges:

→Y

, representing the

constraint

Y≤X+v

, and

X−u

←Y

, which stands for

Y≥X+u

u,v∈R

. An STN is denoted as consistent

if it is possible to execute each node, i.e., to assign

a real value to each timepoint such that all temporal

constraints are satisfied. The consistency property can

be verified by searching for negative loops in the graph.

It is well known that consistency checking as well as

determining the earliest/latest value of each timepoint

can be done in polynomial time (Dechter et al., 1991).

To represent events that cannot be executed,

but only observed, (Morris et al., 2001) intro-

duced Simple Temporal Networks with Uncertainty

(STNUs). STNUs augment Simple Temporal Net-

works (STN) (Dechter et al., 1991) with contingent

timepoints representing timepoints whose value is de-

cided by the environment. Each contingent timepoint

has one incoming edge, called contingent link, which

is labeled by a time range. Therefore, any contingent

timepoint may assume a value from a bounded range,

but the exact value is decided by the environment at run

time. (Morris et al., 2001) provided a formal seman-

tics for the dynamic controllability, which is discussed

in detail in Sect. 2.1. Moreover, (Morris et al., 2001)

presented a pseudo-polynomial-time algorithm, called

DC-checking algorithm, that determines whether a

given STNU is dynamically controllable (DC). Fur-

ther, (Morris and Muscettola, 2005) proposed the first

polynomial DC-checking algorithm, which operates

O(n5)

time, where

is the number of timepoints.

In this paper, we denote this algorithm as MM5. In

turn, (Morris, 2006) and (Morris, 2014) presented two

interesting optimizations of the MM5 algorithm not

further discussed in this paper.

(Lanz et al., 2013) showed how Conditional Sim-

ple Temporal Networks with Uncertainty (CSTNUs),

an extension of STNU considering alternative execu-

tion paths, can be applied in the context of time-aware

business processes in order to verify their controllabil-

ity at both design and run time. Concerning temporal

aspects of a business process, it is emphasized that ac-

tivity durations usually represent worst case estimates,

which are either based on the experience of a domain

expert or extracted from process logs; further, the ex-

ecution times of most activities can be shortened if

required. Accordingly, one may assume that an ac-

tivity has a flexible maximum duration

MaxDF

that

may be restricted up to a contingent minimum and

maximum duration range

[MinDC,MaxDC]

. In other

words, they proposed and analyzed a mapping of time-

aware business processes to CSTNU in which activity

durations are expressed in terms of shrinkable time

intervals [[MinDC,MaxDC]MaxDF].

For a more extensive discussion of the related work

please refer to our technical report (Lanz et al., 2014).

2.1 Dynamic Controllability of STNUs

As proposed by (Morris et al., 2001), an STNU is a set

of time-point variables (timepoints) and temporal con-

straints together with a set of contingent links. Each

contingent link has the form

(A,x,y,C)

, where

and

are timepoints and

0<x<y<∞

holds.

is called the

activation timepoint and

the contingent timepoint.

Once

is executed,

is guaranteed to be executed

such that

C−A∈[x,y]

holds. However, the particular

time at which

is executed is uncontrollable since

it is decided by the environment; i.e., it can be only

observed when it happens.

Let

S= (T,C,L)

be an STNU, with

being a

set of timepoints,

a set of constraints, and

a set of

contingent links. The corresponding graph for

has

the form

(T,E,E`,Eu)

. Thereby, each timepoint in

serves as a node in the graph;

is a set of ordinary

edges;

is a set of lower-case and

a set of upper-

case edges (Morris and Muscettola, 2005):

•

Each ordinary edge has the form

XvY

, represent-

ing the constraint Y−X≤v.

•

Each lower-case edge has the form

Ac:xC

, repre-

senting the possibility that the contingent duration,

C−A, might take on its minimum value x.

•

Each upper-case edge

CC:−yA

, represents the

possibility that the contingent duration,

C−A

might take on its maximum value y.

An STNU is dynamically controllable if there ex-

ists a strategy for executing its timepoints, in a way

guaranteeing that all constraints in the network can be

satisfied, no matter how the durations of the contin-

gent links actually turn out. The strategy is dynamic

since its execution decisions can react to observations

of contingent links that have already been completed,

while excluding those not completed yet.

This section presents preliminary notions and in-

troduces the dynamic controllability of an STNU as

defined in (Morris et al., 2001) and subsequently fixed

in (Hunsberger, 2009).

For an STNU, a situation specifies fixed durations

for all contingent links.

Definition 1

(Situations)

Let

be an STNU

comprising

contingent links,

(A1,x1,y1,C1),...,

(Ak,xk,yk,Ck)

, with corresponding duration ranges

[x1,y1],...,[xk,yk]

. Then:

ΩS= [x1,y1]×... ×[xk,yk]

is called the space of situations for

. Any

ω=

(d1,...,dk)∈ΩS

is called a situation. Where possible,

we may write Ωinstead of ΩS.

The concept of schedule formalizes the execution

of timepoints.

Definition 2

(Schedule)

Aschedule for an STNU is

a mapping

ψ:T→R

that assigns a real number to

each timepoint in T.

Given a situation

for an STNU, the replacement

of its contingent links by the durations specified in

determines a projection of the STNU onto situation

Definition 3

(Situation Projection for an STNU)

Sup-

pose

S= (T,C,L)

is an STNU and

ω= (d1,...,dk)

a situation. The projection of

onto

—denoted as

sitPrj(S,ω)—is the STN (T,C0)with:

C0=C∪{(di≤Ci−Ai≤di)|1≤i≤k}

Given an STNU, multiple schedules may exist. We

are interested in finding a strategy that determines

schedules that satisfy all constraints in any situation.

Definition 4

(Execution Strategy for an STNU)

Let

S= (T,C,L)

be an STNU. An execution strategy for

is a mapping

σ:Ω→ψ

such that for each situa-

tion

ω∈Ω

σ(ω)

is a (complete) schedule for the

timepoints in

. Furthermore, if for each situation

schedule

σ(ω)

is a solution for the situation projec-

tion

sitPrj(S,ω)

, then

is called viable. In any case,

the execution time of timepoint

in schedule

σ(ω)

denoted as [σ(ω)]X.

A situation history for an STNU specifies the du-

rations of all contingent links that have finished their

execution prior to a time tin schedule σ(ω).

Table 1: Edge-generation rules of the MM5 algorithm.

Dashed edges are the generated ones.

No Case:

u+v

Upper Case:

uR:v

R:u+v

Lower Case: QT

s:uv

u+v

Applicable if: v<0∨(v=0∧S6≡ T)

Cross Case: QT

s:uR:v

R:u+v

Applicable if: R6≡ S∧(v<0∨(v=0∧S6≡ T))

Label Removal:

R:v

Applicable if: v≥ −x,xis the lower

bound for the contingent link from Tto R

Definition 5

(Situation History for an STNU)

Let

S= (T,C,L)

be any STNU,

any execution strategy

for

any situation, and

any real number. The

history of

in situation

for strategy

—denoted as

sitHst(t,ω,σ)—is defined as follows:

sitHst(t,ω,σ) = {(A,C,[σ(ω)]C−[σ(ω)]A)|

∃x,y such that (A,x,y,C)∈L∧[σ(ω)]C<t}

Definition 6

(Dynamic Execution Strategy for an

STNU)

An execution strategy

for an STNU is called

dynamic if for any situations,

ω1

and

ω2

, and any non-

contingent timepoint X, it holds:

sitHst([σ(ω1)]X,ω1,σ) = sitHst([σ(ω1)]X,ω2,σ)

⇒[σ(ω1)]X= [σ(ω2)]X.

Definition 7

(Dynamic Controllability of an STNU)

An STNU

is called dynamically controllable (DC)

if there exists an execution strategy for

that is both

viable and dynamic.

In order to determine whether an STNU is dynami-

cally controllable, (Morris and Muscettola, 2005) pro-

posed a polynomial-time checking algorithm, MM5,

which works by recursively generating new edges in

the STNU graph according to the rules from Table 1

and checking whether newly added edges determine

negative loops in the graph. For each rule, existing

edges are represented as solid arrows and newly ones

as dashed arrows. Each of the first four rules takes two

existing edges as input and generates a single edge as

output. Finally, notation

R6≡ S

expresses that

and

Procedure MM5-DC-Check(G)

Input:G= (T,C,L): STNU graph instance to analyze.

Output: the controllability of G.

for 1to |T|2+|T||L|+|L|do

if (AllMax matrix inconsistent) then return false;

Generate new edges using rules from Table 1;

if (no edges generated) then return true;

return false;

must be distinct time-point variables, and does not

represent a constraint on the values of those variables.

We observe that the edge-generation rules from Ta-

ble 1 only generate ordinary or upper-case edges. The

upper-case edges generated by respective rules repre-

sent conditional constraints, called waits (Morris et al.,

2001). In particular, an upper-case edge

BC:−vA

represents the following constraint: as long as con-

tingent timepoint

remains unexecuted, timepoint

must wait at least

units after the execution of

, the

activation timepoint for C.

Procedure MM5-DC-Check shows the pseudocode

of the MM5 DC-checking algorithm. Its time com-

plexity is O(n5)(Morris and Muscettola, 2005).

2.2 Alternative Characterization of an

Execution Strategy

As observed in (Hunsberger, 2009), the original defini-

tion of dynamic execution strategy (DES) obscures the

real-time features of typical execution scenarios and

the kinds of execution decisions an execution system

may make. Therefore, (Hunsberger, 2009) proposed

an alternative characterization of a DES to not only rep-

resent the conditions under which a system must make

real-time execution decisions, but also the outcomes of

those decisions. Two kinds of real-time execution de-

cisions (RTEDs) are defined: WAIT and

(τ,χ)

, which

can be described as: “Wait until some contingent dura-

tion completes” or “If nothing happens before

, then

execute the (executable) timepoints in

.” The out-

come of a RTED depends on the situation and is repre-

sented by a partial schedule that specifies the execution

of one or more additional timepoints. The outcome

of a WAIT decision solely involves the execution of

contingent timepoints, whereas the outcome of a

(τ,χ)

decision may involve the execution of contingent as

well as non-contingent timepoints. An RTED-based

strategy is defined as a mapping from partial sched-

ules to real-time execution decisions. (Hunsberger,

2009) proved that RTED-based strategies correspond

one-to-one to DESs.

In more detail, given an STNU and a partial sched-

ule

ψ:T→R

(i.e., the domain of

may be a subset of

), we denote by

µ(ψ) = max{ψ(t)|t∈Dom(ψ)}

the

maximum execution time of timepoints appearing in

, by

U(ψ) = {x|x6∈ Dom(ψ)}

the set of unexecuted

timepoints in

, by

Ux(ψ)⊆U(ψ)

the set of non-

contingent unexecuted timepoints, by

Uc(ψ)⊆U(ψ)

the set of contingent unexecuted timepoints, and by

Ua(ψ)⊆Uc(ψ)

the set of contingent activated unexe-

cuted timepoints, respectively.

Let

be a partial schedule for an STNU

and

ω= (ω1,...,ωq)

a situation for

respects

if for

each contingent link

(Ai,x,y,Ci)

one of the following

conditions holds: (1) neither

nor

appear in

; (2) only

appears in

, and

ψ(Ai) + ωi>µ(ψ)

;

or (3) both

and

appear in

, and

ψ(Ai) + ωi=

ψ(Ci)

is called respectful if it respects at least one

situation. If

is both respectful and partial, it is called

a respectful, partial schedule (RPS). A strategy

respectful if for each ω,σ(ω)respects ω.

Let us recall the definition of WAIT and

(τ,χ)

de-

cisions.

WAIT Decision

. Let

be some RPS for

such that

Ua(ψ)

is non-empty. Then WAIT is an admissible

RTED.

Outcome of a WAIT Decision

. If

Ua(ψ)6=/

and

is a situation respected by

, then the time at which

the next contingent timepoint will execute is defined

tnc(ψ,ω) = min{ψ(Ai) + ωi|Ci∈Ua(ψ)}

. With

χa(ψ,ω) = {Ci∈Ua(ψ)|ψ(Ai) + ωi=tnc(ψ,ω)}

we denote the non-empty set of contingent timepoints

that will be executed at time

tnc(ψ,ω)

. Then, the out-

come of the WAIT decision for

in situation

defined to be the execution of contingent timepoints at

time tnc(ψ,ω):ψ∪{(Ci,tnc(ψ,ω)) |Ci∈χa(ψ,ω)}.

(τ,χ)Decision

. Let

be some RPS for

such that

Ux(ψ)6=/

. If

τ>µ(ψ)

and

is a non-empty subset

of Ux(ψ), then (τ,χ)is an admissible RTED for ψ.

Outcome of a (τ,χ)Decision

. Let

be a situation

respected by

. The outcome of a

(τ,χ)

decision de-

pends on the relationship between

tnc(ψ,ω)

and in-

stant

. For the sake of simplicity, let

τc=tnc(ψ,ω)

and

χa=χa(ψ,ω)

Ua(ψ)6=/

; otherwise, let

τc=∞

τc<τ

, the outcome solely involves the execution

of the contingent timepoints in

χa

. In turn, if

τ<τc

the outcome solely involves the execution of the non-

contingent timepoints in

. Finally, for

τc=τ

, the

outcome involves the execution of the timepoints in

both χaand χ.

(Hunsberger, 2009) proved that the original dy-

namic execution strategy can be described in terms of

RTEDs as shown in procedure RTEDExecutionStrat-

egy. Thereby, function RTExecutionDecision is used

to determine the next RTED. For the sake of brevity,

the RTED WAIT is represented as

(τ,χ)

decision with

τ:=∞and χ:=/

0in the given context.

Function RTExecutionDecision(S,ψ)

Input:S: STNU. ψ; partial schedule

Output:δ(ψ): real-time execution decision

if (Ux(ψ) = /

0)then // WAIT RTED!

δ(ψ):= (τx,χ), where τx:=∞and χ:=/

else // (τ,χ)RTED!

foreach (x∈Ux(ψ)) do

[m(x),M(x)] = current time-window for x;

W(x):=−∞;

foreach ((Ai,Ci)|Ci∈Ua(ψ)∧xCi:−wi

−→ Ai)do

W(x):=max{W(x),ψ(Ai)+wi};

f loor(x):=max{m(x),W(x)};

go(x):=min{f loor(x),M(x)};

δ(ψ):= (τx,χ), where τx:=min{go(x)|x∈Ux(ψ)}

and χ:={x∈Ux(ψ)|τx=go(x)};

return δ(ψ);

Procedure RTEDExecutionStrategy(S)

Input:S: STNU.

ψ={(Z,0)};// initial partial schedule

while (U(ψ)6=/

0)do

(τx,χ) = RTExecutionDecision(S,ψ);

if (nothing happens before time τx)then

Execute the timepoints in χ;

else

Observe the contingent timepoints executed at

some τc<τx;

Update ψto include the executed events;

Update Sto include the corresponding constraints;

Starting with a partial schedule

ψ={(Z,0)}

which only fixes the initial timepoint

, proce-

dure

RTEDExecutionStrategy

iteratively determines

an RTED

δ(ψ)

, considering two possibilities (cf. func-

tion RTExecutionDecision). If all executable time-

points have already been executed,

δ(ψ) = (∞,/

holds (i.e., RTED WAIT); otherwise,

δ(ψ) = (τx,χ)

with the values of

τx

and

being computed by con-

sidering all unexecuted timepoints and using an all-

pairs, shortest-path algorithm.

f loor(x)

corresponds

to the earliest time, timepoint

may be executed with-

out violating its lower bound

m(x)

or any of its rele-

vant waits.

go(x)

is the same, except that it enforces

the constraint that

does not violate its upper bound

M(x)

. It is noteworthy that Morris and Muscettola

showed that a conflict between

f loor(x)

and

M(x)

not possible for an STNU accepted by their algorithm.

After determining the RTED

δ(ψ) = (τx,χ)

, proce-

dure

RTEDExecutionStrategy

waits for the outcome

δ(ψ)

and then updates

and

accordingly. If there

are still unexecuted timepoints, the procedure iterates,

otherwise it terminates.

3 GUARDED TEMPORAL

CONSTRAINTS

Regarding an STNU, the execution of a contingent

timepoint can be thought of as being completely out

of the control of the system that executes the network.

Typically, a system activates a contingent link

(A,x,

y,C)

by executing its activation timepoint

. After-

wards, the execution of

is out of the system’s control.

However, the contingent timepoint

is guaranteed to

execute such that C−A∈[x,y]holds.

As motivated in Sect. 1, for real-world problems

this is often too strict. In many cases, the system may

exercise some control over the execution of the con-

tingent timepoint. As example consider a case where,

at an activation timepoint, the system transfers control

to an external agent. The agent is then responsible for

executing the corresponding contingent timepoint. In

turn, the system waits for the agent to complete its

task (i.e., to execute the contingent timepoint). When

transferring the control to the agent, the system may

inform the agent about the temporal constraints to be

met. The agent then adapts its plan in order to com-

ply with the additional constraints. At the same time,

the system must guarantee that it is able to meet the

commitment made, i.e., it needs to ensure that it can

deal with any decision the agent makes for executing

timepoint Cbased on the given constraints.

In many cases, the agent responsible for executing

timepoint

cannot completely control the execution of

either (e.g., in case the agent is executing a network

itself). Particularly, he might only be able to provide a

preferred duration range

[x,y]

as well as bounds

xmax

and

ymin

to which

may be increased or

may be

decreased (i.e.,

x≤xmax

and

y≥ymin

). In turn, the

system executing the network must ensure that, when

executing timepoint

(i.e., when activating the con-

straint between

and

), the agent responsible for

executing timepoint

has at least

ymin

time units and

is not required to take more than

xmax

time units to

execute

. We denote

xmax

(

ymin

) as the guard of

(

Note that this example addresses a common sce-

nario, i.e., to transfer execution control at run time to

another agent, which is responsible for executing a

complex task (e.g., another network).

The need to model constraints of this type requires

an extension of the STNU formalism, we denote as

Simple Temporal Network with Partially Shrinkable

Uncertainty (STNPSU). In particular, STNPSU ex-

tends contingent links of STNU to guarded links.

Definition 8

(STNPSU)

ASimple Temporal Network

with Partially Shrinkable Uncertainty (STNPSU) is a

triple (T,C,G), where:

•Tis a set of timepoints;

•C

is a set of requirement constraints

X[u,v]

−→ Y

(i.e.,

STN constraints); and

•G

is a set of guarded links each having the form

(A,[x,xmax],[ymin,y],C)

where

and

are time-

points, and

0≤x≤y<∞

x≤xmax

0≤ymin ≤y

•

(A1,[x1,x1max],[y1min,y1],C1)

as well as

(A2,

[x2,x2max],[y2min,y2],C2)

are distinct guarded

links in G, then C1and C2are distinct timepoints.

Informally, we denote an STNPSU as dynamically

controllable if it is possible to execute it such that, no

matter how the execution of any guarded link turns

out, for any other guarded link

(A,[x,xmax],[ymin,y],

the lower bound

never must be increased beyond

its guard

xmax

and the upper bound

never must be

decreased below its guard

ymin

in order to ensure con-

trollability of the network.

The execution semantics of STNPSU can be sum-

marized as follows: The basic execution semantics is

the same as for an STNU. However, when executing an

STNPSU, the outer bounds

[x,y]

of a guarded link

(A,

[x,xmax],[ymin,y],C)

may be restricted to

[x0,y0]

with

x≤x0≤xmax

ymin ≤y0≤y

, and

x0≤y0

in order to en-

sure controllability of the remaining network. In turn,

when executing the activation timepoint

of a guarded

link

(A,[x,xmax],[ymin,y],C)

, the latter is activated and

its current bounds

[x0,y0]

are fixed. Particularly, the

guarded link

(A,[x,xmax],[ymin,y],C)

is replaced by the

strict guarded link

(A,[x0,x0],[y0,y0],C)

. The latter is

equivalent to a contingent link of STNU. As we will

show in Sect. 3.3, this change does not affect control-

lability of the network.

It is noteworthy that guarded links of STNPSU may

be used to represent two different types of constraints

Type 1:

xmax <ymin

holds, a guarded link repre-

sents a partially contingent constraint. Particularly,

the guarded link represents a temporal constraint

x≤C−A≤y

with a contingent (i.e., unshrinkable)

core

[xmax,ymin]⊆[x,y]

. This represents an exten-

sion of the classical contingent links of STNU.

Moreover, if

x=xmax ∧y=ymin

hold, the guarded

link is equivalent to a contingent link of STNU.

We call this a strict guarded link.

Type 2:

xmax ≥ymin

holds, a guarded link represents

apartially shrinkable constraint with a guarded

core

[ymin,xmax]

. In detail, this represents a tempo-

ral constraint

x≤C−A≤y

whose bounds cannot

be shrunk beyond a certain point (i.e.,

xmax

and

ymin

, respectively). As opposed to a contingent

link,

may be restricted to be greater than

ymin

and

to be lower than

xmax

. This represents an

extension of the classical requirement constraints.

Please refer to our technical report (Lanz et al., 2014)

for a more detailed discussion.

As example of a Type 1 guarded link consider

guarded link

(A,[10,15],[20,40],C)

, which represents

the duration of activity Stretching (cf. Fig. 1 (b)). Dur-

ing execution, the outer bounds

[10,40]

of this guarded

link may be shrunk in order to ensure controllability

of the remaining network. In the given case, for ex-

ample, they may be shrunk to

(A,[7,15],[20,23],C)

(A,[5,15],[20,20],C)

. However, the outer bounds

may at most be shrunk to the contingent core of the

guarded link, i.e., the above guarded link may at most

be shrunk to (A,[15,15],[20,20],C).

In turn, an example of a Type 2 guarded link is

given by

(A,[5,20],[10,25],C)

. In this case, the lower

bound of the guarded link may at most be increased to

20 and the upper bound may at most be decreased to

10. Thus,

(A,[15,20],[10,20],C)

(A,[20,20],[10,23],

, and

(A,[5,20],[10,10],C)

are possible values this

guarded link may be shrunk to. Note that a Type 2

guarded link may also be shrunk to a single value, e.g.,

(A,[15,20],[10,15],C)

. However, a Type 2 guarded

link must always allow for at least one value within its

guarded core [ymin,xmax](i.e., [10,20]).

During execution, when activating a guarded link

of Type 1 or 2 (i.e., when executing its activation time-

point), the current outer bounds of the guarded link

are fixed. This is to ensure that the outer bounds of

the guarded link cannot be modified while it is active.

Therefore, the current outer bounds of the guarded link

are set to be strict. For example, when executing time-

point

, the Type 2 guarded link

(A,[15,20],[10,20],

is replaced by a strict guarded link

(A,[15,15],

[20,20],C)

. The latter is equivalent to a contingent

link

(A,15,20,C)

of STNU and ensures that the agent

responsible for executing timepoint

may now choose

any time in range [15,20]to execute timepoint C.

3.1 Dynamic Controllability of STNPSU

This section presents preliminary definitions of basic

concepts required for the definition of dynamic con-

trollability of a STNPSU.

The set of core situations specifies the contingent

core of all guarded links of Type 1 (partially contingent

guarded links), while the set of core settings specifies

the guarded core of all guarded links of Type 2 (par-

tially shrinkable guarded links).

Definition 9

(Core Situations and Core Settings)

Sup-

pose

S= (T,C,G)

is an STNPSU. Let

Gc={g∈

G|g= (A,[x,xmax],[ymin,y],C)∧xmax <ymin}

be the

set of guarded links for which the guard

xmax

of the

lower bound is lower than the guard

ymin

of the upper

bound (i.e., Type 1). Further, let

Gr=G\Gc

be the

set of guarded links for which

ymin ≤xmax

holds (i.e.,

Type 2).

contains

guarded links,

(A1,[x1,x1max],

[y1min,y1],C1),...,(Ak,[xk,xkmax],[ykmin,yk],Ck)

, then

Ωc

S= [x1max,y1min]×... ×[xkmax,ykmin]

is called the

space of core situations for

. Any

ωc= (d1,...dk)∈

Ωc

Sis called a core situation.

Further, if

contains

guarded links,

(A1,

[x1,x1max],[y1min,y1],C1),...,(Am,[xm,xmmax],

[ymmin,ym],Cm)

, then

Ωr

S= [y1min,x1max]×... ×

[ymmin,xmmax]

is called the space of core settings

for S.

Given the space of core situations

Ωc

and the space

of core settings

Ωr

of an STNPSU, a projection of

the STNPSU onto an STNU can be obtained as fol-

lows: First, each guarded link in

is replaced by a

contingent link for the range specified in

Ωc

. Second,

each guarded link in

is replaced by a requirement

constraint for the range in Ωr.

Definition 10

(Core STNU of an STNPSU)

Let

(T,C,G)be an STNPSU.

Then: The projection of

onto its space of

core situations

Ωc

and its space of core settings

Ωr

—denoted as

stnuPrj(S,Ωc,Ωr)

—corresponds to an

STNU (T,C00,L00)with:

C00 =C∪{(yimin ≤Ci−Ai≤ximax)|1≤i≤m,

Ωr=[y1min,x1max]×... ×[ymmin,xmmax]}

L00 ={(Ai,ximax,yimin,Ci)|1≤i≤k,

Ωc=[x1max,y1min]×... ×[xkmax,ykmin]}

We denote the respective STNU as the core STNU of

STNPSU S.

Finally, this leads us to the dynamic controllabil-

ity of an STNPSU. We provide a formalization of the

dynamic controllability of an STNPSU based on the

dynamic controllability of an STNU. We choose this

approach since the formalization of dynamic control-

lability of STNU is robust and verified in literature.

Theorem 1

(Dynamic Controllability of STNPSU)

An STNPSU

S= (T,C,G)

is dynamically control-

lable (DC), if the core STNU that results from the

STNU Projection

stnuPrj(S,Ωc,Ωr)

of the STNPSU is

dynamically controllable.

Proof. ⇒

It is a matter of definitions to show that, if

the core STNU is DC (cf. Sect. 2.1), the corresponding

STNPSU is DC as well: each schedule being a solution

of the core STNU is also a solution of the STNPSU.

Indeed, it is always possible to restrict the STNPSU to

its core situations. Thus, for each core situation of the

STNPSU, a dynamic execution strategy (DES), which

is a viable DES for the STNU, is also a viable DES

for the STNPSU regarding its core situations. Hence,

if the core STNU is DC, the STNPSU will be DC as

well.

BSBESSSE

20; bE:5

−5; BE:−20

−1

40; bE:15

−10; BE:−20

−25

BS= Start of Biking; BE= End of Biking;

SS= Start of Stretching; SE= End of Stretching

Figure 2: STNPSU corresponding to the activity sequences

from Fig. 1 (b)

⇐

If the core STNU is not DC (i.e., no viable DES

exists), at least one core situation

ωc

of the STNPSU

exists for which no DES exists within the core set-

tings. Hence, for core situation

ωc

, one of the partially

shrinkable guarded links must be restricted beyond its

guards to find a DES which returns a solution. As this

is not possible, the STNPSU is not DC either.

3.2 DC-Checking for Guarded

Constraints

This section shows how the dynamic controllability of

an STNPSU may be checked without need to restrict

the respective STNPSU to its core STNU. First, we

emphasize the close relationship between dynamic

controllability of STNU and the one of STNPSU (cf.

Theorem 1). In turn, this fosters the following graph-

based representation of an STNPSU, which is similar

to the one of an STNU.

Definition 11

(Graph of a STNPSU)

The graph for

an STNPSU

has the form

(T,E,E`,Eu)

, where each

timepoint in

corresponds to a node in the graph;

is a set of ordinary edges,

is a set of lower-case

edges, and Euis a set of upper-case edges:

•

Each requirement constraint

X[u,v]

−→ Y

is repre-

sented by two ordinary edges

−→ Y

and

Y−u

−→

•

Each guarded link

(A,[x,xmax],[ymin,y],C)

is rep-

resented by

–two ordinary edges A y

−→ C and C −x

−→ A,

–one lower-case edge A c:xmax

−→ C, and

–one upper-case edge C C:−ymin

−→ A.

As example of this graph-based representation of

an STNPSU, consider the graph depicted in Fig. 2.

It shows the STNPSU corresponding to the activity

sequence depicted in Fig. 1 (b). If multiple edges exist

between two nodes (e.g., an ordinary and an upper-

case edge), for the sake of readability, we draw only

one arrow between the nodes and annotate it with the

values of the respective edges. Further, we use bold

arrows to highlight edges representing a guarded link.

y;s:xmax

−x;S:−ymin

Figure 3: Guarded Link

At this point, we want to emphasize important dif-

ferences between the graph of an STNU and the one

of an STNPSU:

•

In an STNU, the value of any lower-case edge

Ac:xmax

−→ C

always corresponds to the negative value

of the ordinary edge

C−x

−→ A

pointing in the op-

posite direction (i.e.,

x=xmax)

. Similarly, the

value of any upper-case edge

CC:−ymin

−→ A

always

corresponds to the negative value of ordinary edge

−→C

(i.e.,

y=ymin

). For an STNPSU, this does

not apply. Particularly, we only require

x≤xmax

and y≥ymin.

•

In an STNU, the value of a lower-case edge

Ac:xmax

−→

always is lower than the negative value of the

upper-case edge

CC:−ymin

−→ A

pointing in the oppo-

site direction (i.e.,

xmax <ymin

). Note that for an

STNPSU this is not required.

In our technical report (Lanz et al., 2014), we show

that, except one minor change regarding one of the

edge generation rules (cf. Table 1), procedure MM5-

DC-Check may be reused in order to check dynamic

controllability of a STNPSU. Particularly, we ana-

lyze all possible combinations of edges between three

nodes of an STNPSU graph (i.e., all possible trian-

gles). Based on this, it can be shown that the resulting

distance graph of the STNPSU has no negative loops

if and only if the distance graph of the core STNU has

no negative loops as well.

Consider the single guarded link depicted in Fig. 3.

It comprises two triangles

and

. Note that

it is a matter of applying the edge-generation rules

to these two triangles (i.e., the No Case rule to

and the No Case, Upper Case, Lower Case, and

Label Removal rules to

) to ascertain that a valid

guarded link does not contain a negative loop. In

case of a partially shrinkable guarded link (Type 2),

in addition, the Label Removal (cf. Table 1) rule may

be applied to the upper-case edge between

and

replacing it with a requirement edge. This poses no

problem for checking dynamic controllability, but it is

undesired as it obscures some of the properties of the

guarded link. Thus, we restrict the Label Removal rule

R6≡ S

to prevent this. Note that this change does

not influence the applicability of the rule to an STNU.

Regarding an STNU, for

R≡S

it holds that

v<−x

(i.e.,

xmax <ymin

; cf. Table 1), i.e., for an STNU, the

Procedure ExRTEDExecutionStrategy(S)

Input:S: STNPSU.

1ψ={(Z,0)};// initial partial schedule

2while (U(ψ)6=/

0)do

3(τx,χ) = RTExecutionDecision(S,ψ);

4if (nothing happens before time τx)then

5execute the time-points in χ;

6else

observe the contingent timepoints executed at some

τc<τx;

8χ= set of executed contingent timepoints;

9Update ψto include the execution events in χ;

10 Update Sto include the corresponding constraints;

11 foreach (Ai∈χ)do // Activate guarded links

12 foreach ((Ai,[x,xmax],[ymin,y],Ci)∈G)do

13 [x0,y0]

= current outer bounds of guarded

AiCi

;

14 repeat // Prepare the guarded link for execution

// Determine its maximum controllable range

15 range(Ai,Ci) = min{v−u|a∈U(ψ)!∧

−→ Ci∧v≥0∧(Ci−u

−→ a∨Ci

Cj:−u

−→ a)};

// Update its bounds to observe max. controll. range

16 y0=min{y0

,max{ymin,x0+range(Ai,Ci)}};

// x0is update only if the update y0is not sufficient

17 x0=max{x0,y0−range(Ai,Ci)};

18 if x0or y0is modified then

19 Update Sto include the modified

outer bounds of the guarded link;

20 until neither x0nor y0is modified;

// Consider the max possible wait constraint for Ci

21 W(Ai,Ci):=−∞;

22 foreach((Ai,Cj)|Cj∈Ua(ψ)∧Ci

Cj:−wj

−→ Ai)do

23 W(Ai,Ci):=max{W(Ai,Ci),wj};

24 f loor(Ai,Ci):=max{x0,W(Ai,Ci)};

25 x0:=min{f loor(Ai,Ci),y0};

26 Transform the guarded link to the strict

guarded link (Ai,[x0,x0],[y0,y0],Ci);

27 Update Sto include the new constraint;

rule will never be applied if R≡Sholds.

3.3 Executing STNPSUs

This section shows how an STNPSU may be executed

by means of an appropriate extension of procedure RT-

EDExecutionStrategy (cf. Sect. 2.2).

Consider procedure ExRTEDExecutionStrategy.

The first part of the procedure executes the same

actions as procedure RTEDExecutionStrategy (cf.

Sect. 2.2). The second part activates all guarded links

(Ai,[x,xmax],[ymin,y],Ci)

whose activation timepoint

has just been executed. The guarded link semantics

requires to allow each of them, once it is activated, to

use any possible value in the range defined by the cur-

rent outer bounds, i.e.,

[x,y]

. By construction and due

to the fact that the network is DC, for a Type 1 guarded

link the possibility of using any possible value in the

range is guaranteed only for the core range

[xmax,ymin]

while for a Type 2 guarded link only the possibility

of using at least one value in the range

[ymin,xmax]

guaranteed. Particularly, the execution of some other

timepoints before the occurrence of

may modify the

bounds of these guarded links making the network not

controllable. Therefore, the procedure has to suitably

update the bounds of the guarded links (lines 14–20)

before transforming them into strict ones (lines 21–27).

Finally, the execution goes back to the first part until

there are no more unexecuted timepoints.

The key point of the procedure consists in the exe-

cution of timepoints subjected to guarded links as con-

tingent timepoints with suitable ranges; this allows for

the exploitation of the correctness proof of RTEDExe-

cutionStrategy (Hunsberger, 2009). In order to show

that this transformation preserves the controllability

of the network, it is sufficient to show that the trans-

formation of any guarded link—during runtime—into

a strict one with a suitable range is always possible

and preserves the dynamic controllability of the rest

of network (i.e., the unexecuted subnetwork).

Theorem 2.

Suppose

is a dynamically controllable

STNPSU,

is a respectful, partial schedule, and

(A,

[x,xmax],[ymin,y],C)

is a guarded link of

. Let us

assume that

has just been executed and that the

outer bounds

and

of the guarded link

have

been updated as described in lines 13–25 of proce-

dure RTEDExecutionStrategy to the values

and

Then: The new values

and

satisfy

x0≤xmax

and

ymin ≤y0

and the STNPSU

resulting after the trans-

formation of the guarded link

(A,[x0,xmax],[ymin,y0],C)

into the strict one

(A,[x0,x0],[y0,y0],C)

is dynamically

controllable as well.

Sketch of the proof.

Due to the lack of space, we only

give a outline of the complete proof.

Let us assume that, before the execution of lines

13–25, the guarded link

is given as

(A,[x,xmax],

[ymin,y],C)

. Instructions of lines 13–25 update the

outer bounds

[x,y]

[x0,y0]

. Let us assume that the

guarded link is of Type 1.

Since the network is

DC before line 13 and the core range

[xmax,ymin]

a contingent range, the update made in lines 13–25

cannot reduce

[x,y]

[x0,y0]

such that

x0>xmax

y0<ymin

holds. Hence, the updated range

[x0,y0]

con-

tains (possibly in a weak way) the core range of

(A,

[x,xmax],[ymin,y],C)

. Thus, there are 4 possible cases:

(1)

x0=xmax ∧y0=ymin

, (2)

x0=xmax ∧y0>ymin

, (3)

The case of a guarded link of Type 2 can be discussed

in a similar way.

x0<xmax ∧y0=ymin

, and (4)

x0<xmax ∧y0>ymin

. In

case (1) the guarded link is already strict and, hence,

it is not changed by the procedure. Case (4) is a com-

bination of cases (2) and (3).

Hence, let us consider case (2) and (3). In case

(2), by contradiction, suppose that the changing of

the guarded link

(A,[xmax,xmax],[ymin,y0],C)

into the

strict one (A,[xmax,xmax],[y0,y0],C)makes the remain-

ing network not dynamically controllable. This means

that there exists at least one negative loop involving

timepoints

, and some

, where

has not yet

executed (i.e., it has to occur after

), but has to be

executed before

. All other timepoints, i.e., unexe-

cuted ones that have to be executed after

, cannot

contribute to form a negative loop since each of them—

by definition of controllability—must have at least one

possible execution time for each possible execution

time of Cin the range [ψ(A)+xmax,ψ(A)+y0].

Now, instead of considering the distance graph and

negative loops in it, let us reason in term of ranges

and their spans

. Given the dynamic controllabil-

ity of the network before the transformation, it is a

fact that

has at least one possible execution time

for each possible execution time of

in the range

[ψ(A)+xmax,ψ(A)+ymin]

, i.e., with such range there

is no negative loop involving

, and

. Equivalently,

the span of the constraint between

and

is greater

or equal to the span

ymin −xmax +1

of the contingent

core of the guarded link between

and

. There-

fore, a negative loop can only emerge when the new

bound

is considered, or, equivalent, when the span

of the constraint between

and

is less than the span

y0−xmax +1

of the outer bounds of the guarded link

between Aand C.

However, when preparing the guarded link for ex-

ecution,

is determined such that the span of range

[xmax,y0]

of the link between

and

is lower than or

equal to the span of the constraint between

and

Thus, there cannot exist any negative loop involving

B, and C.

Case (3) can be shown in a similar way taking

also into account any possible wait constraint that may

increase the value of x0.

4 ON THE EXPRESSIVENESS OF

GUARDED CONSTRAINTS

This section informally discusses the expressiveness of

STNPSUs. Further, we show that most guarded links

cannot be represented in STNUs by other solutions.

Consider again the physiotherapy session scenario

3The span of a range [a,b]is b−a+1.

ASACAE

yC;ac:xC

−xC;AC:−yC

−xF

Figure 4: STNU pattern representing a shrinkable duration

range

[xF,[xC+f,yC],yF](0≤xC≤xF≤xC+f∧xC≤yC≤yF≤

yC+f).

from Fig. 1 (b): Activity Stretching has a duration

range of

[10,40]

, which may be shrunk to a core dura-

tion range of

[15,20]

during run time according to the

actual duration of activity Biking. Fig. 2 depicts the

temporal aspects of the session in terms of an STNPSU:

each of the two activities is represented through a pair

of timepoints, of which one represents the starting

instant of the activity and the other one the ending

instant. The allowed duration of activity Stretching is

represented as guarded link

(SS,[10,15],[20,40],SE)

while the contingent duration of activity Biking is rep-

resented as strict guarded link

(BS,[5,5],[20,20],BE)

Based on the results from Sect. 3 one can easily verify

that the STNPSU is dynamically controllable, i.e., for

each possible execution time of activity Biking, the sys-

tem is able to determine a suitable duration range for

activity Stretching containing the core range

[15,20]

such that each possible execution time in this range

satisfies the overall duration constraint [25,50].

Let us discuss some of the limitations that arise

when representing the temporal aspects of the phys-

iotherapy session in terms of an STNU. The main

problem is how to represent the temporal constraints

of activity Stretching. One option to be considered is

the pattern depicted in Fig. 4. It constitutes a general-

ization of the pattern proposed by (Lanz et al., 2013).

This pattern is composed of three timepoints

and

connected by a contingent link and two re-

quirement constraints. More precisely, timepoints

and

represent the starting and ending timepoint

of the respective activity. In turn,

is an internal

timepoint that is only used for checking dynamic con-

trollability of the STNU, but is not considered when

executing the activity. The values of the three con-

straints guarantee that the overall duration range of the

pattern lies in range

[xF,yF]

and the upper bound

can be shrunk to

at run time. Moreover, the lower

bound

may be shrunk to

xC+f

as well. Hence,

the overall constraint represented by this pattern is