Disjunctive Temporal Planning with Uncertainty

1 Introduction

For modelling and solving real-world planning and scheduling problems, quantitative temporal constraint networks in the form of the Simple Temporal Problem (STP) [Dechter et al., 1991] are widely known. The STP has been independently extended in two orthogonal directions.

First, since the STP formalism is unable to express concepts such as "event A occurs before or after event B", the Disjunctive Temporal Problem (DTP) [Stergiou and Koubarakis, 2000] admits more than one disjunct in a constraint. Thus DTP constraints are disjuncts of the form: Y1-X1 ∈ [ai1, b1]∨· · ·∨Yn-Xn ∈ [an, bn]. Note a variable may appear in more than one disjunct. A simple way to solve a DTP is to consider the component STPs obtained by selecting one disjunct from each constraint. The computational complexity of solving each component STP (deciding consistency and deriving the minimal network) is polynomial, while the worst-case complexity of solving a DTP is NP-hard [Stergiou and Koubarakis, 2000]; but in practice, efficient solving techniques have been developed (e.g. [Tsamardinos and Pollack, 2003]), and tractability results are known for some classes of DTPs [Satish Kumar, 2005].

Second, since the STP formalism assumes all time-points are under the complete control of the execution agent, the Simple Temporal Problem with Uncertainty (STPU) [Vidal and Fargier, 1999; Morris et al., 2001] divides the time-points into two classes, executable and contingent. Contingent timepoints are controlled by exogenous factors, often referred to as 'Nature', and consistency of an STP is replaced by varying notions of controllability.

Driven by planning problems that feature both disjunctive constraints and contingent events, in this poster we propose

Neil Yorke-Smith

Artificial Intelligence Center SRI International Menlo Park, CA 94025, USA

nysmith@ai.sri. co m

the Disjunctive Temporal Problem with Uncertainty (DTPU). Consider, for instance, planning the schedule of an elderly patient [Peintner and Pollack, 2004]. On the one hand, her schedule includes events, such as exercising and a relative's visit, that are not totally ordered by the problem requirements; on the other hand, while the patient has some idea when the relative will arrive, the precise time is not under her control.

2 Extending the DTP with Uncertainty

Following the STPU formalism [Vidal and Fargier, 1999], in a DTPU we divide the time-point variables into two classes: the controllable decision variables Vd and the uncontrollable parameters Vu. In an STPU, this induces a partition of the temporal relation constraints C into two types. A constraint Y -X ∈ [a, b], where Y ∈ Vu, is a contingent link. Intuitively, contingent links model tasks with uncertain durations. If a constraint is not contingent, it is an executable link; thus all other constraints (i.e. where Y ∈ Vd) are executable links.

In a DTPU, each constraint is a disjunction of links:

Definition 1 A DTPU is a tuple 〈Vd, Vu, Rd, Ru, C〉, where Vd, Vu are as above, Rd is the set of all executable links, and Ru is the set of all contingent links, and C is a finite set of disjunctive temporal constraints.

Thus in a DTPU, three types of constraints arise according to the contingent status of the included disjuncts. First, only Rd disjuncts; analogously with STPUs, the constraint is said to be executable. Second, only Ru disjuncts; analogously with STPUs, the constraint is said to be contingent. Third, both Rd and Ru disjuncts. Here, a situation which has no analogue in an STPU, the constraint can be satisfied by the satisfaction of either some executable link (a possibility under the agent's control), or of some contingent link (which is not); we say that it is semi-executable.

A constraint is satisfied if at least one of its disjuncts is satisfied. A solution to a DTPU is a complete assignment to all variables V = Vd∪Vu that satisfies all the constraints in C. A solution s can be partitioned into sd ∪ su, where sd and su are the set of temporal values assigned to elements of Vd and Vu respectively. sd is called a decision, and su is a realisation (or possible world, or scenario). We say a component STPU of a DTPU is the problem obtained by selecting one disjunct from each constraint.

Example 1 Consider further the example of an elderly patient's schedule [Peintner and Pollack, 2004]. The timepoints in a DTP model of the schedule include Es and Ee, and Vs and Ve, which describe the start and end of exercising and a visit respectively. One of the constraints is:

stating that "Exercise must finish at least 5 minutes before the visitor arrives or start anytime after the visitor leaves."

While the visitor has a scheduled arrival time of 4:30 p.m., his precise arrival is not under the control of the patient; thus Vs is a parameter. This means that the first disjunct of (1) is a contingent link. The second disjunct is an executable link, and so constraint (1) is semi-executable.

2.1 Controllability

For space reasons, we present informal definitions extending the notions of controllability to DTPUs. The important new possibility is of a semi-executable DTPU constraint.

Strong Controllability. A DTPU is strongly controllable (SC) if there exists a decision that, combined with any realisation, satisfies the constraints. In other words, there is a way to assign values to the decision variables such that, given any values for the parameters, at least one disjunct on each constraint is satisfied. Note this means that a DTPU is SC if some component STPU is SC. The converse is false, however, since in a SC decision, sd ∪ su may satisfy different disjuncts in different realisations.

DynamicControllability. ADTPU is dynamically controllable (DC) if there exists an incremental, online decision that, given knowledge of the values of all parameters that have occurred until now, can be dynamically extended to a decision in the future, whatever the values of the parameters that have not yet occurred. Note this means that a DTPU is DC if some component STPU is DC, provided the decision for the component STPU can be consistently extended to a decision to all decision variables in the complete DTPU. (A component STPU may involve a strict subset of Vd.) Again, the converse is false in general.

Weak Controllability. A DTPU is weakly controllable (WC) if for any realisation there exists a decision that, combined with that realisation, satisfies the constraints. That is, every realisation can be consistently extended to a decision. Once more, a DTPU is WC if some component STPU is WC, but the converse is false.

Trivial Controllability. The situation where every constraint is semi-executable brings the possibility that the agent could satisfy the DTPU without regard to the contingent links, by satisfying at least one executable link in each constraint. We say a component STPU of a DTPU is a component STP if it contains only executable links. A DTPU is trivially controllable (TC) if one or more of its component STPUs is a consistent component STP. Consistency of a component STP is required to prove that: every TC DTPU is SC.

Since SC =⇒ DC =⇒ WC (inherited from the STPU case), by testing whether a DTPU is trivially controllable, we have a sufficient but not necessary condition for all other types of controllability. Testing for this condition requires, in the worst case, checking the consistency of every component STP. While there may be exponentially-many such STPs to check, the consistency of each can be determined relatively quickly, compared to other inference tasks for DTPUs.

The other constraints of Example 1, not shown here, are all single-disjunct executable constraints. Thus, since a component STP arising with the second disjunct of (1) is consistent, the whole problem is trivially controllable. While so for this particularly simple example of a DTPU, more interesting DTPUs are not TC in general.

3 Future Work

As a step towards modelling real-world planning problems with disjunctive temporal constraints and contingent events, we have proposed the Disjunctive Temporal Problem with Uncertainty. While the DTPU extends previous work on the STPU, much future work is needed. On the theory side, our main task is to formally state and prove properties of DTPUs; on the practical side, our task is to develop algorithms to check the various controllability notions, and prove their complexity. Beyond this, we are interested to combine the DTPU framework with user preferences [Peintner and Pollack, 2004], in a similar manner to [Rossi et al., 2004].

Acknowledgments. We thank M. Pollack and T. Uribe for useful discussions, and the reviewers for their comments. This material is based upon work supported by the Defense Advanced Research Projects Agency, through the Department of the Interior, NBC, Acquisition Services Division, under Contract No. NBCHD030010.