Temporal Reasoning with Preferences and Uncertainty

1 Motivation and Background

Research on temporal reasoning, once exposed to the difficul­ ties of real-life problems, can be found lacking both expres­ siveness and flexibility. Planning and scheduling for satel­ lite observations, for instance, involves not only quantitative temporal constraints between events and qualitative tempo­ ral ordering of events, but also soft temporal preferences and contingent events over which the agent has no control. For example, on one hand, slewing and scanning activities should not overlap, but may if necessary. On the other hand, the du­ ration of failure recovery procedures is not under the direct control of the satellite executive. To address the lack of ex­ pressiveness, preferences can be added to the framework; to address the lack of flexibility to contingency, handling of un­ certainty can be added. Some real-world problems, however, have need for both. It is this requirement that motivates us.

In a temporal constraint problem, as defined in Dechter et a!. [ 1991 ], variables denote timepoints and constraints rep­ resent the possible temporal relations between them. Such constraints are quantitative, describing restrictions on either durations or distances of events, in terms of intervals over the timeline. In general such problems are NP-complete. How­ ever, if each temporal constraint has just one interval- hence the constraints have form l;j ::; x j - x; ::; U;j, where X; de­ note the timepoints - then we have a Simple Temporal Prob­ lem (STP) that can be solved in polynomial time.

*Partially supported by the EPSRC under grant GR/N64373/0l.

tpartially funded by the Italian MIUR projects NAPOLI and COVER, and the ASI (Italian Space Agency) project ARISCOM.

K. B. Venable and F. Rossi

Dept. of Mathematics University of Padova Padova, Italy

{kvenable,frossi}@math.unipd.itt

To address the lack of expressiveness in standard STPs, the Simple Temporal Problems with Preferences (STPP) frame­ work merge STPs with semiring-based soft constraints [Rossi et al., 2002]. Soft temporal constraints are specified by means of a preference function on the constraint interval, f : [l ij, Uij] -+ A, where A is a set of preference val­ ues. The set A is part of a semiring. In general, STPPs are NP-complete. However, if the preference functions are semi-convex (that is, they have at most one peak), the con­ straints are combined via an idempotent operation (like max or min), and the preference values are totally ordered, then finding an optimal solution of a STPP is a polynomial prob­ lem. Two solvers for STPPs with the features above are pre­ sented by Rossi et al. [2002]. The first, Path-solver, enforces path consistency in the constraint network, then takes the sub­ interval on each constraint corresponding to the best prefer­ ence level. This gives a standard STP, which is then solved for the first solution by backtrack-free search. The second solver, Chop-solver, is less general but more efficient. It finds the maximum level y at which the preference functions can be 'chopped', i.e. reduced to the set { x : x E I , f(x) 2 y } . This set is a simple interval for each I. Hence we obtain a standard STP, STP y· By binary search, the solver finds the maximal y for which STP y is consistent. The solutions of this STP are the optimal solutions of the original STPP.

To address the lack of flexibility in execution of standard STPs, Vidal and Fargier [ 1999] introduced Simple Temporal Problems under Uncertainty (STPUs). Here, again as in a STP, the activities have durations given by intervals. The timepoints, however, fall into two classes: requirement and contingent. The former, as in a STP, are decided by the agent, but the latter are decided by 'nature': the agent has no con­ trol over when the activity will end; he observes rather than executes. The only information known prior to observation is that nature will respect the interval on the duration. Control­ lability of a STPU is the analogue of consistency of a STP. Controllable implies the agent has a means to execute the timepoints under his control, subject to all constraints. Three notions are proposed. A STPU is strongly controllable if there is a fixed execution strategy that works in all realisations (that is, an observation of all contingent timepoints). Check­ ing strong controllability is in P [Vidal and Fargier, 1999]. A STPU is dynamically controllable if there is a online execu­ tion strategy that depends only on observed timepoints in the past and that can always be extended to a complete sched­ ule whatever may happen in the future. Checking dynamic controllability is also in P [Morris et a!., 200 1]. A STPU is weakly controllable ifthere exists at least one execution strat­ egy for every realisation. Checking weak controllability is co-NP [Vidal and Fargier, 1999]. The three notions are or­ dered by their strength: strong =? dynamic =? weak.

In this paper we introduce a framework which allows one to handle both preferences and uncertainty in temporal prob­ lems. This is done by just merging the two pre-existing mod­ els of STPPs and STPUs. We also adopt the notion of con­ trollability, to be used instead of consistency because of the presence of uncertainty, and we adapt it to handle preferences. We then investigate the complexity of checking such notions of controllability, and we develop algorithms to perform such checks. The main results are for strong and weak controlla­ bility, which we show to maintain the same complexity as in STPUs under the same hypothesis that make STPPs polyno­ mially solvable. As future work, we plan to study dynamic controllability, and to implement our algorithms to compare their performance experimentally.

2 Simple Temporal Problems with Preferences and Uncertainty (STPPU)

A STPPU is a STPP with timepoints partitioned into two classes, requirement and contingent, just as in a STPU. Since some timepoints are not controllable by the agent, the no­ tion of consistency of a STP(P) is replaced by controllabil­ ity, just as in a STPU, with the three notions suitably ex­ tended. While all three notions of controllability used for STPUs can be adapted to STPPUs, for this short paper we will focus on just weak and strong controllability. A STPPU is optimally strongly controllable if there is a fixed execution strategy that works in all realisations and is optimal in each of them. Rather than optimality, one could be interested in just reaching a certain quality level: a STPPU is a-strongly controllable, where a is a preference level, if there is a fixed execution strategy that works in all realisations and is above a in each of them. A STPPU is optimally (resp. a-) weakly controllable if there exists at least one optimal (resp., above a) execution strategy for every realisation.

3 Checking Optimal and a Strong Controllability

It can be proved that checking either optimal or a strong controllability is in P. The method we propose relies on two known algorithms. The first is Path-solver, which en­ forces path consistency on a STPP. The second is Strong­ Controllability(STPU) [Vidal and Fargier, 1999], which checks if a STPU is strongly controllable. The main idea is to ap­ ply Strong-Controllability(STPU) to a special STPU, which we will call Papt. that can be constructed starting from the STPP P' obtained by applying Path-solver to a STPPU P. More precisely, the algorithm takes as input a STPPU P and performs the following steps: (I) forgetting the uncertainty, treat P as a STPP and apply Path-solver to it, obtaining the STPP P'; (2) collapse the non-contingent intervals of P' to those parts which have the highest preference level, and then neglect the preferences, obtaining a STPU Papt; (3) apply Strong-Controllability to Papt. Theoretical results that we have proven, but omit for lack of space, show the correctness of the algorithm: ( 1) If a STPPU is optimally strong controllable, then the STPU obtained by neglecting preferences is strongly controllable; (2) A STPPU P is optimally strong controllable if and only if the STPU Papt is strongly controllable.

We have also generated a different algorithm by combining Strong-Controllability with Chop-solver. This algorithm is less general but more efficient. Both algorithms we propose are polynomial, with a time complexity O(n 3 x R x l), where n is the problem size, R is the range of the largest interval, and lis the number of preference levels.

For a-strong controllability, we rely on theoretical results similar to those above, and we propose two algorithms. Given a, the first one checks a-SC by: cutting the intervals to those parts whose preference is above a, and applying strong con· trollability checking to the resulting STPU. The time com­ plexity is O(n 3 x R). The second algorithm finds the highest a at which P is a -SC, by performing a binary search for the highest a, checking strong controllability at each step. Its time complexity is O(p x n 3 x R), where pis proportional to the precision we want in returning the result.

4 Checking Optimal and a Weak Controllability

Optimal weak controllability of a STPPU is equivalent to weak controllability of the corresponding preference-stripped STPU. Thus we can use the existing STPU algorithms for checking weak controllability. For checking a-weak con­ trollability, we propose two approaches. The first chops the STPPU at level a by considering only those parts of its inter­ vals which have preference level above a (semi-convexivity guarantees that the result is always a single interval), and then applies Weak-Controllability to the STPU so obtained. The second approach generates the realisations that arise by con­ sidering the contingent intervals reduced to just their upper or lower bound (other realisations need not be considered) [Vi­ dal and Fargier, 1999]), and checks the consistency of all such realisations. Both algorithms are exponential in the number of contingent constraints.