Real-Time Problem-Solving with Contract Algorithms

1 Introduction

Since the mid 1980's, the AI community has produced a large body of work on anytime algorithms for solving such problems as real-time search, constraint satisfac­ tion, planning and scheduling, and diagnosis (see, for example, the collection of papers in [Horvitz and Zil­ berstein, 1996]). Much of this work has focused on the meta-level control problem posed by anytime algorithms, that is, the problem of deciding when to stop delibera­ tion and act on the best available solution. The result­ ing techniques have proved useful in addressing the high computational complexity of AI problems and the in­ herent uncertainty associated with AI problem-solving techniques.

Contract algorithms are a special type of anytime al­ gorithms that require the amount of run-time to be de­ termined prior to their activation. In other words, con­ tract algorithms offer a tradeoff between computation time and quality of results, but they are not interrupt­ ible. Once activated with a particular contract time, a contract algorithm may not produce any useful result before the end of the contract.

Contract algorithms are easier to construct because they do not have to continually generate solutions of increasing quality. In fact, many existing AI problem­ solving techniques produce contract rather than inter­ ruptible anytime algorithms. Examples include depthbounded search or cost-bounded search techniques, design-to-time [Gravey and Lesser, 1993], approximate evaluation of relational database queries, and schedul­ ing [Gallone and Charpillet, 1997]. What is common to these algorithms is that for any given contract time they select a set of parameters that limit the amount of search or computation so as to guarantee returning a solution within the available time. Another important class of systems that yields contract rather than inter­ ruptible algorithms includes systems composed of several interruptible or contract algorithms. Composition, even simple sequencing, destroyf'i interruptibility; the result­ ing system is therefore a contract algorithm. Zilberstein [1995] shows how to divide the contract time among the components so as to maximize the overall quality of the solution for a given contract.

This paper addresses the problem of building an inter­ ruptible real-time system using contract algorithms. The key question is how to use prior knowledge about the per­ formance of the algorithm and the deadline in order to produce an optimal sequence of solutions with a contract algorithm. This is done by activating the contract algo­ rithm multiple times with different contracts. Section 2 provides a formal definition of the contract sequenc­ ing problem. Section 3 describes an optimal solution to the problem when no information is available about the deadline. Section 4 shows how to handle quality un­ certainty and stochastic deadlines. Section 5 provides an optimal solution to the sequencing problem when a time­ dependent utility function is given instead of a strict deadline. We conclude with a summary of the contribu­ tion of this work.

2 Using contract algorithms in interruptible domains

Suppose that a contract algorithm, A, is used in an in­ terruptible domain in which the amount of time avail­ able for problem solving is unknown in advance. At a particular time, the system receives a deadline signal in­ dicating that the computation must be terminated and the best available result must be returned. Examples of interruptible domains include a diagnosis system in an intensive care unit; a data visualization program that may be interrupted by its user; and a scheduling program that may need to return a new schedule once processors are ready to accept new tasks.

We use in this paper prior information about the per­ formance of the contract algorithm. We begin with a simple form of performance profile [Dean and Boddy, 1988] and generalize it in Section 4.

Definition 1 A performance profile, QA(t), of a contract algorithm A, denotes the output quality as a function of contract time t.

The performance profile is .assumed to be a monotone increasing and continuous function of time.

Monotonicity is a standard property of anytime algo­ rithms that can be guaranteed if the best result rather than the most recently generated one is returned. Strict monotonicity and continuity are assumed in order to sim­ plify the analysis in Section 3.

If the amount of time available for computation is known in advance, the best strategy to maximize the quality of the result is to run the contract algorithm once giving it all the available time. What happens when we have no information (or only stochastic information) about the deadline? The contract algorithm should be activated with some contract time x1 . If the algorithm completes its execution before the deadline, it should be reactivated with a new contract x2 and so on. Because of the monotonicity of QA, it is never beneficial to use a short contract following a longer one. Therefore, we get the following sequence of contracts:

Suppose that an interruptible anytime algorithm B is constructed using A with the sequence of contracts X = (x1 , x2 , ... ). Whenever B is interrupted, it should return the result obtained by the most recently completed con­ tract. No solution is available before the termination of the first contract (which is arbitrarily small). Therefore, the performance profile of the interruptible algorithm, B, is as follows.

What is the sequence of contracts that produces the best anytime algorithm? To answer this question we must first formalize the notion of "best" . If the dead­ line, d, is known in advance, the best quality QA(d) can be guaranteed. Suppose now that an interruptible algo­ rithm is created by a sequence of contracts. We want the interruptible algorithm to guarantee the same qual­ ity as the contract algorithm, if it runs on a processor that is accelerated by a factor of r 2: 1. This definition follows the notion of bounded optimality defined by Rus­ sell, Subramanian and Parr [1993]. In fact, the results presented in Section 3 can be interpreted as the construc­ tion of a bounded-optimal interruptible algorithm from the contract one. Moreover, we prove that the minimal acceleration needed by any interruptible algorithm that matches the quality of A is 4. The acceleration ratio is defined as follows .

Definition 2 Let A be a contract algorithm and B an interruptible algorithm produced by the sequence of con­ tracts X = ( x1 , x2 , . .. ) , then the acceleration ratio of X, r 2: 1, is the smallest constant c for which:

The acceleration ratio is the minimal acceleration that guarantees that the interruptible algorithm will always have a solution ready from the previous contract that is at least as good as the one produced by the contract algorithm without acceleration. The condition t 2: 7 is needed because no solution is available before the termi­ nation of the first contract. Note that the acceleration ratio does not imply that the application must utilize a faster processor; it is only a performance measure of a sequence of contracts.

3 Optimal sequencing of contracts

Zilberstein and Russell [1996] show that a particular se­ quence of contracts requires an acceleration ratio of 4. The sequence of contracts is a geometric series with run­ time being doubled at each activation. They prove the following theorem.

Theorem 1 For any contract algorithm A, an in­ terruptible algorithm B can be constructed such that Ql3(4t) 2: QA(t).

In this section, we prove that the acceleration ratio of 4 is the best possible over any sequence of contracts. We also generalize the result to the case of multiple problem instances.

3.1 Solving a single problem instance

We first show that the construction proposed by Zither­ stein and Russell is in fact optimal in the sense that it requires the minimal acceleration ratio. In general, the acceleration ratio must hold in the worst possible case: when the interruptible algorithm is stopped just before the end of the current contract xi+1 and it must return the result produced by the previous run (with contract time x;). This leads to the following property.

Lemma 1 Equation (2) is equivalent to

Proof: We first show that (2) => (3). Consider some i 2: 1 and let

Let t ---* x_ denote the fact that t approaches x from below. Given that Condition (2) holds in particular for t---* s(i + 1)_, we get:

From (1) we know that for any t, s(i) :=:; t < s(i + 1):

Therefore we obtain:

Finally, by the continuity of QA:

that is:

The converse, (3) => (2), is straightforward. Consider any t, s(i) :=:; t < s(i + 1), we have

To summarize, in order to show that a particular se­ quence of contracts is optimal, it is sufficient to show that its acceleration ratio is the smallest required to sat­ isfy Equation (3).

Theorem 2 The minimal acceleration ratio needed to construct an interruptible algorithm from a given con­ tract algorithm is r = 4.

Proof: From Lemma 1 we know that for any sequence of contracts, X = ( x1 , x2 , ... ) , r must satisfy:

From the strict monotonicity of Q A we get:

Similarly,

The difference between the last two equations gives:

The sequence ( x1 , x2, ... ) is an increasing sequence of positive numbers. Let p be defined as follows.

It is clear that p ~ 1. From Equation 4 we obtain:

and thus, for any i ~ 1 we have

Because {Vi x; ~ a} => {inf; x; ~ a}, we conclude that

Equivalently, because p > 1, we get

2 The function f(p) = -;St has a minimum of 4 (when p = 2) over the interval (1, +oo) . Therefore, r ~ 4. D

3.2 Solving multiple problem instances

We now generalize the above result to the case in which a contract (or interruptible) anytime algorithm with per­ formance profile QA is used to solve m independent prob­ lem instances. The goal is to maximize the minimal solution quality over all problem instances. When the deadline d is known in advance, the best strategy is to divide all the available time equally among the problem instances guaranteeing a minimal quality of Q A ( ~). The question is how to construct the best interruptible any­ time algorithm when the deadline is unknown. As with a single task, we want to find the minimal acceleration needed to match the performance of the contract algo­ rithm with a known deadline.

There are many situations in which multiple instances of a problem must be solved in real-time. Examples include search problems with multiple possible start­ ing states; optimizing the code of several tasks to be executed on a parallel machine; and compression of a file divided into m blocks to be transmitted through m equivalent communication channels. In all these exam­ ples the objective is to maximize the minimal quality over all problem instances by the deadline. Another ap­ plication is the continual computation model developed by Horvitz [1997] in which an interactive system uses idle time in order to solve possible future problems. When the user interrupts the computation by making a spe­ cific choice, the system responds using the best available solution for that choice.

For a given sequence of contracts X = (x1 , x2 , ... ) , the performance profile of the interruptible algorithm solving m problem instances is as follows.

This is due to the fact that the first (and shortest) among the last m contracts defines the overall quality.

We want to find the minimal acceleration ratio c such that QB(ct) delivers a result at least as good as the one returned by A when the deadline is known (i.e., QA(rk)).

Lemma 2 For any c ~ 1 the condition:

holds if and only if:

Proof: This is a straightforward generalization of Lemma 1. The complete proof is omitted.

Theorem 3 The minimal acceleration ratio needed to construct an interruptible algorithm to solve m prob­ lem instances with a given contract algorithm is r = (m~l )m+l.

Proof: The proof is similar to the proof of Theo­ rem 2 and is given in Appendix A. Note that the ratio ( mrrt"l )m+l is obtained by a sequence of contracts defined by a geometric series with run-times being multiplied by a factor of mrrt"l. In other words:

Therefore, the construction described in Zilberstein and Russell [1996] is the solution for the special case in which m=l.

4 Handling quality uncertainty and stochastic deadlines

In this section we generalize the problem of sequencing contract algorithms to situations in which some infor­ mation about the deadline is available. We assume that there is uncertainty about both the deadline and the quality produced by the cont.ract algorithm. It is not surprising that there is no closed-form solution to the sequencing problem in this case. Instead, the optimal sequence of contracts is determined using dynamic pro­ gramming. To be able to apply dynamic programming, the problem is formalized using a discrete representa­ tion oftime (as opposed to the continuous representation used in the previous sections).

Definition 3 A stochastic deadline is a probability distribution, Pv ( t) , of the deadline over time.

A stochastic deadline is the prior probability that the deadline will occur at time t measured relative to the activation time of the contract algorithm. The represen­ tation of performance profiles is generalized as follows.

Definition 4 A stochastic performance profile, PA ( qlt) of a contract algorithm, A, denotes the proba­ bility of getting solution of quality q with contract time t.

We assume that the quality of the result is observable. That is, once the contract algorithm completes its exe­ cution, the actual quality of the solution produced by the algorithm can be determined. The quality of a plan, for example, is observable if it is measured by the sum of the costs of the operators. However, when solution qual­ ity is defined as the approximation ratio with respect to the optimal solution it may not be observable. Hansen and Zilberstein [1996] have studied situations in which solution quality is partially observable. Their approach to the problem could be used to augment the framework presented in this paper.

Definition 5 A utility function, U(q), is the value of a solution of quality q produced by the contract algorithm.

The contract sequencing problem in this case is defined as follows. Given a contract algorithm, its stochastic performance profile, a stochastic deadline and an arbi­ trary utility function, find an optimal policy to activate a sequence of contracts. An optimal policy is one that maximizes the expected utility of the available solution at the deadline.

We approach the problem by defining a corresponding Markov decision process (MDP) and finding an optimal policy by solving it. The states of the MDP are (q, t) in­ dicating the availability of solution of quality q at time t. In addition, there is a terminal state associated with each solution quality q, indicating reaching the deadline with that quality. The action or decision taken at each non-terminal state is to activate the contract algorithm with a new contract time T. The outcomes of these ac­ tions depend on the stochastic performance profile and the likelihood of reaching the deadline, both of which satisfy the Markov assumption (they are independent of previous states, given the current state of the computa­ tion) .

Definition 6 Let Pv(mln) be the probability distribu­ tion of the deadline occurring at time m (m > n) given that it has not occurred so far and the current time is n.

Note that Pv(mln) can be easily computed from the prior probability Pv(t) as follows.

This can be easily obtained by observing that n stands for the proposition that the deadline did not occur at time points { 1, ... , n} and by applying Bayes' rule.

Definition 7 The completion probability of a con­ tract T starting in state (q, t) is

The completion probability is the probability that the contract algorithm will terminate before the deadline oc­ curs.

We now define the following value function over states:

The value of a contract T at state (q, t) depends on whether the deadline occurs during the contract or not. If the contract algorithm completes its execution (with probability c(t, r)), then the value depends on the new quality and time. Note that if the new quality is lower than the current solution quality, the better solution is used rather than the most recent one. If the deadline occurs, a final state is reached with a reward that de­ pends on the quality of the existing solution. The value function is defined based on the best action T in each state.

Theorem 4 The contracts that maximize the value function defined in Equation (6) provide an optimal so­ lution to the contract sequencing problem for a given stochastic deadline.

Proof: Because of the one-to-one correspondence be­ tween the sequencing problem and the MDP and because the stochastic performance profile and the deadline sat­ isfy the Markov assumption, it is obvious that an optimal policy for the MDP provides an optimal solution to the sequencing problem. D

Many existing algorithms can be used to solve Equa­ tion (6). Because this is a finite-horizon MDP with no cycles (time always moves forward), dynamic program­ ming can be used to determine the best action for each state in one sweep of the state space. The policy can be constructed off-line once for a given deadline distri­ bution, offering efficient reactive meta-level control. The selection of a time unit affects the size and complexity of the policy. We are confident that a coarse time unit and a compact policy are sufficient in practice for making good meta-level decisions.

5 Optimal sequencing with no strict deadline

In this section we consider the case in which there is no strict deadline. Instead, the value of the solution de­ creases over time as specified by a time-dependent utility function [Dean and Boddy, 1988].

Definition 8 A time-dependent utility function, U(q, t), is the value of a solution of quality q produced by the contract algorithm and returned at time t.

The contract sequencing problem in this case is defined as follows. Given a contract algorithm, its stochastic per­ formance profile and an arbitrary time-dependent utility function, find the best policy to activate a sequence of contracts. As in the previous section, an optimal policy maximizes the expected utility of the returned solution. Note that in this case the meta-level control problem is not only to determining the next contract, but also when to stop the computation and return the current best result.

Similar to the previous section, we approach the prob­ lem by defining a corresponding MDP with states repre­ senting the current quality and time. The action taken at each state, however, is either to terminate the com­ putation and return the current solution of quality q or activate the algorithm with a particular contract r. We define the following value function over states.

(7)

When a new contract is activated, the value is defined by the distribution of output quality and the contract time. If the computation is terminated, the value is the utility of returning a result of quality q at time t.

Theorem 5 The policy that maximizes the value func­ tion defined in Equation (7) provides an optimal solu­ tion to the contract sequencing problem for a given time­ dependent utility function.

Proof: Again, this is an immediate result of the one­ to-one correspondence between the optimal sequencing problem and the above MDP and because the stochastic performance profile satisfies the Markov assumption. D

Using dynamic programming, the optimal policy can be constructed off-line once for a given time-dependent utility function, offering an efficient, reactive meta-level control.

6 Conclusion

We have analyzed the problem of optimal sequencing of contract algorithms. The problem arises when there is uncertainty about the amount of time available for problem-solving with contract algorithms. When no prior information is available about the deadline, the best sequence can match the performance of the contract algorithm when it runs on a processor that is 4 times faster. No slower acceleration can guarantee that per­ formance. This result is generalized to the case in which an interruptible system must solve multiple problem in­ stances. When stochastic information is available about the deadline and about the performance of the contract algorithm, the optimal sequence of contracts can be con­ structed using dynamic programming. Finally, we solve the case in which no deadline is specified but the utility function is time-dependent.

Section 3 was inspired by the work of Baeza-Yates et al. [1993] on searching in the plane. The analogy between the two problems is not obvious, but once for­ malized, they present similar mathematical questions. In particular, Lemmas 1 and 2 in this paper provide a foundation to solving the problem of searching in the plane. Furthermore, the analytical work reported here offers a dramatic simplification of the proofs presented in [Baeza-Yates et al., 1993].

Sections 4 and 5 build on a large body of work on meta-level control of computation by Dean and Boddy [1988), Horvitz [1988), Russell and Wefald [1991] and others. By and large, existing meta-level control mech­ anisms are myopic; the computation is terminated once no single computational step has positive value. One exception is the technique developed by Russell, Sub­ ramanian, and Parr [1993] for sequencing a set of rules given a stochastic deadline. Similar to their dynamic programming approach, our solution provides a globally optimal policy, taking into account future computations.

To summarize, we show how to optimally sequence contract algorithms so as to maximize their utility in in­ terruptible domains. These results provide useful guid­ ance for embedding contract algorithms in a wide range of practical applications.

Acknowledgments

This work was supported in part by the National Sci­ ence Foundation under grants No. IRI-9624992 and IRI-9634938, by an NSF /INRIA Cooperative Research grant, and by the LIRE Cooperative Program at INRIA.

Appendix A: Proof of Theorem 3

From Lemma 2, for any sequence of contracts X= (x1 ,xz,oo.), r must satisfy:

From the strict monotonicity of QA we get:

Similarly:

The difference between the last two equations gives:

The sequence ( x1 , x2 , .. . ) is an increasing sequence of positive numbers. As before, let p be defined as:

It is clear that p ~ 1. From Equation 8 we obtain:

Therefore, We conclude that:

Equivalently, because p > 1, we get:

~+I The function p --+ %=T reaches its minimum on the interval (1, +oo) when p = nt" 1 , therefore r ~ ( nt" 1 )m+l.

The ratio ( m+l )m+l can be obtained by a sequence of contracts defined by a geometric series with run-times being multiplied by a factor of m~l. Thus the best pos­ sible acceleration ratio is r = ( m~l )m+l. 0