Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems

1 Introduction

In this paper, we demonstrate a connection between two prob­ lems that initially seem umelated. The first involves comput­ ing solutions to multiple problems, under the condition that a solution to any one of the problems can be requested at any time. Challenges of this type arise in the design of intelligent user interfaces, information prefetching systems, and medi­ cal diagnosis systems. The second problem involves multiple robots searching an unknown environment for a goal. Prob­ lems of this nature arise in robotics and space exploration. In the following paragraphs we describe the problems, along with our contribution, in more detail.

The first problem concerns anytime algorithms [Horvitz, 1987; Dean and Boddy, 1988; Russell and Zilberstein, 1991], which produce solutions of different qualities depending on available computation time. More specifically, we focus on

Shlomo Zilberstein

Dept. of Computer Science University of Massachusetts Amherst, MA 01 003 shlomo@cs. umass.edu

contract algorithms, which are anytime algorithms that re­ quire the deadline as input prior to the start of execution. With contract algorithms, no assumptions can be made about re­ sults produced before the given deadline. This is in contrast to the familiar interruptible algorithms, which can be queried at any point during execution. Although less flexible than inter­ ruptible algorithms, contract algorithms typically use simpler data structures, making them easier to implement and main­ tain. An example in AI is game playing programs based on heuristic search. For these programs, the allowed deliberation time is usually known in advance, and is used to set internal parameters. Another example is planning algorithms that per­ form state-space abstraction. With these algorithms, the run time can be controlled by setting the abstraction level at the start of execution.

Our problem can be stated as follows. We are given n instances of an optimization problem, along with a contract algorithm for the problem, and we have an m-processor ma­ chine on which to run the algorithm. An interruption can oc­ cur at any time, and a solution can be requested for any one of the problem instances. Given these constraints, we want a good general strategy for scheduling runs of the algorithm on the processors.

In the case of one problem instance and one processor, Russell and Zilberstein [1991] suggested iteratively doubling the contract lengths. With this schedule, for any interruption time t, the last contract completed (if one exists) is always of length at least t /4. This factor of four is the acceleration ratio of the schedule, a worst-case measure of its efficiency. Zilberstein et al. [1999] showed that no schedule can achieve an acceleration ratio less than four.

The generalization to multiple problem instances has been considered [Zilberstein et al., 1999], as has the generaliza­ tion to scheduling contracts on parallel processors [Bernstein et al., 2002]. Optimal acceleration ratios have been derived in both cases. The more general multi-processor, multi-instance case has not previously been studied. In this paper, we pro­ vide a schedule for this case, and we prove that this schedule is optimal among a restricted, though still interesting, class of schedules. The optimality proof is a nontrivial extension of the previous proofs, and contains as a lemma a generalization of the monotone convergence principle.

This work is most closely related to Horvitz's continual computation framework [Horvitz, 2001]. In his framework, as in ours, computation is performed with limited knowledge about the deadline or desired result. However, the assump­ tions underlying the two frameworks are different. In the con­ tinual computation framework, the limited knowledge comes in the form of probability distributions. In contrast, our use of acceleration ratio does not require probabilistic information. Furthermore, contract algorithms and parallel processing are both not considered in continual computation.

Our contract scheduling results can be directly applied to a robot search problem. In this problem, m robots search for a goal that is located on one of p intersecting rays. The aim is to minimize the time-competitive ratio, which is the worst­ case ratio of the total time spent searching to the time for a single robot to traverse directly to the goal. The optimal ratio for the one-robot case was derived previously [Baeza-Yates et al., 1993].

We address the general multi-robot case, for which search strategies are formally equivalent to contract schedules. For our class of schedules, we derive a formula relating the accel­ eration ratio of a schedule to the time-competitive ratio of the corresponding search strategy. The optimal time-competitive ratio is derived as a corollary.

This work is the first to draw a precise connection between contract scheduling and multi-robot search, and the first to provide nontrivial results for the multi-robot case. Kao et a!. [ 1998] studied the multi-robot problem, but used a dif­ ferent performance measure. They minimized the distance­ competitive ratio, which is the worst-case ratio of the total distance traveled during the search to the distance between the origin and the goal.

2 Scheduling a Contract Algorithm

2.1 Problem Description

An anytime algorithm A, when applied to an optimization problem instance i for time t, produces a solution of some real-valued quality QA (t , i) . The function QA is called A's performance profile. In general, one does not know an al­ gorithm's performance profile. Nevertheless the concept of a performance profile is useful in reasoning about anytime algorithms. We assume that the performance profile of an anytime algorithm on any problem instance is defined for all t ~ 0 and is a nondecreasing function oft.

The distinctions among different types of anytime algo­ rithms arise from different assumptions about which param­ eters are known prior to execution. When both t and i are known in advance, the algorithm is called contract. When only i is known in advance, the algorithm is called interrupt­ ible. For the case where both are unknown, we will say that the algorithm is multi-interruptible, because it acts like mul­ tiple interruptible algorithms running in parallel.

Suppose we have a contract algorithm A, which we can run on a machine with m processors. At some unknown deadline, a solution to one of n problem instances will be requested. This setup requires a multi-interruptible algorithm, which we can create by scheduling contracts in such a way that progress is continually made on each problem instance. Upon inter­ ruption and query, the result returned is that of the longest completed contract dedicated to the desired problem instance.

The multi-interruptible algorithm's performance profile de­ pends on A's profile and the schedule, in a way to be formal­ ized shortly. A particular schedule for the case of m = 3 and n = 2 is illustrated in Figure 1.

Formally, a schedule is a triple X= ({Pk}, {h}, {Lk}), where Pk E { 0, .. . , m - 1} is the processor of contract k, h E { 0, .. . , n - 1} is the problem instance worked on by contract k, and Lk E JR.+ is the length of contract k. The contract index will be assumed to start at zero. A schedule must satisfy some minor conditions, which require a couple more definitions to state. First, let J be defined as

Next, for a given schedule X, the completion time of the kth contract is defined as

Note that although G depends on X, we omit the subscript. Dependence on the schedule will be made implicit through­ out the paper for ease of notation. For every schedule, the index ordering must correspond to the completion time or­ dering. Furthermore, no two contracts may complete at the exact same time. The formal statement of these two condi­ tions is that k < l is equivalent to Gk < G1 for all k, l. Also, a schedule must have h = k for 0 :::; k :::; n - 1. This ensures that after timet = Gn_1 , a solution is available for each problem instance.

To compare schedules, we use a worst-case metric called acceleration ratio. The acceleration ratio tells us how much faster our constructed algorithm would need to run in order to ensure the same quality as if the query time and problem were known, and a dedicated processor was assigned to producing a result. Intuitively, it measures how well a schedule handles the uncertainty about the problem instance and interruption time.

Before formally defining acceleration ratio, we must state some more technical details of the problem and present some more definitions. First, we take the view that when a contract completes at time t, its solution is available to be returned upon interruption at any timeT > t. Second, we assume that no interruptions occur until after time t = Gn- 1, so that there is always at least one result available.

The length of the longest contract for instance ito complete before some time t > Gn- 1 is

The performance profile for the multi-interruptible algorithm B(A, X) is defined for all i and all t > Gn_ 1 as

We can now give a precise definition of acceleration ratio.

Definition 1 The acceleration ratio, Rm,n(X). is the small­ est constant r for which Q B(A,X) (t, i) 2: QA (tjr, i) for all contract algorithms A. all problem instances i, and all times t > Gn- 1·

In the next section, we provide a schedule that is optimal within a restricted, though still interesting, class of schedules. We state below in precise terms the properties that delineate the class of schedules under consideration. Schedules having the three properties below will be called cyclic schedules.

The first property states that problem instances are com­ pleted in a round-robin manner. This seems sensible, as the desired problem instance is unknown. However, we cannot yet prove that for every non-problem-round-robin schedule, there is an equally good problem-round-robin schedule.

Property 1 (Problem-round-robin) h = k mod n for all k.

The next property states that the lengths of contracts for each problem instance must increase with time. Given that performance profiles are nondecreasing, it seems that it would never be beneficial to use a schedule that doesn't satisfy this property. However, as with the first property, we cannot yet prove this. One difficulty lies in having to satisfy the problem-round-robin property mentioned above. We would like to be able to "remove" useless contracts from a schedule, but we have not found a way to do this while guaranteeing that the resulting schedule will be problem-round-robin.

Property 2 (Length-increasing) For all k, l, if h = It and k < l, then Lk < Lt .

The final property states that processors return results in a round-robin manner. This property does not play a part in our lower bound derivation, but it is used in drawing a connection to the robot search problem. We introduce it at this point only for ease of exposition.

Property 3 (Processor-round-robin) Pk = k mod m for all k.

We can prove a lemma that allows us to cast acceleration ratio in simpler terms when we are considering only cyclic schedules. In the proof, the following facts are established: acceleration ratio can be stated without reference to perfor­ mance profiles; the only interruption times that need to be considered are completion times; and upon interruption, the result returned is from the contract with index exactly n less than index of the current contract.

Lemma 1 For all cyclic schedules X,

Proof: We first argue that

From the definitions given above, we have

for all i and t > Gn_ 1 . Since this holds for any algorithm A, we can suppose an algorithm A with perforn1ance profile QA(t , i) = t for all i. Thus s(i, t) 2: t j Rm,n(X), and hence Rm,n(X) 2: tjs(i, t) for all i and t > Gn- 1 . This implies that

To show that equality holds, assume the contrary and derive a contradiction with the fact that Rm,n (X) is defined as the smallest constant enforcing the inequality between QB(A,X) and QA.

Next we show that

For each i, s(i, t) is left-continuous everywhere and piece­ wise constant, with the pieces delimited by time points Gk. So for all i, tjs(i, t) is left-continuous and piecewise linear and increasing. Thus, the local maxima of t j s( i, t) occur at the points Gk; no other times may play a role in the supre­ mum.

Finally,

follows from the problem-round-robin and length-increasing properties, and the fact that no two contracts can finish at the exact same time. 0

To conclude this section, we define the minimal accelera­ tion ratio form processors and n problems to be

where the infimum is taken over the set of cyclic schedules. In the following sections, we provide tight bounds for this ratio.

2.2 An Exponential Schedule

A simple approach to scheduling contract algorithms is to have the contract lengths increase exponentially. We consider the schedule

It is easily verified that this is a cyclic schedule. The follow­ ing theorem gives an expression for this schedule's accelera­ tion ratio.

Theorem 1 The acceleration ratio for the exponential schedule is

Proof: Let b = ((m + n)jn) 1 fm. The following is true for all k:

Note that this expression is nondecreasing with k. Thus

D

There are a few things to note about the ratio we just de­ rived. As the number of processors approaches infinity, it tends to one. This is intuitive; by adding processors, we can get arbitrarily close to the omniscient algorithm. As the num­ ber of problems approaches infinity, the ratio tends to infinity. Finally, the ratio depends only on the ratio of problems to pro­ cessors, and not on the absolute numbers.

We turn now to showing that no cyclic schedule can achieve a smaller ratio.

2.3 Lower Bound

We define a function to represent the sum of the lengths of all the contracts finishing no later than contract k finishes:

We can derive an inequality involving only the acceleration ratio and {Hk}.

Lemma 2 For all cyclic schedules X and all k,

Proof: Consider the contract with index k+m+n. We define the set U such that u E U if and only if u is the index of the last contract on some processor to finish no later than contract k + m + n finishes. It follows that H k+m+n = Z:uEU Cu. Note that U contains at most m distinct integers, each be­ tween 1 and k + m + n. Since G is increasing,

Using Lemma 1, we get

D

To derive our lower bound, we also need the following lemma, which is a generalization of the monotone conver­ gence principle. Its proof is deferred to the appendix.

Lemma 3 Let m and n be relatively prime, and let {Pk} be a sequence of real numbers that is bounded from below by f . If (Pk · · · Pk+m-1)nfm ~ Pk+m · · · Pk+m+n-1 is satisfied for all k, then {Pk} converges.

We can now prove our lower bound theorem.

Theorem 2 The optimal acceleration ratio form processors and n problems is

Proof: Consider an arbitrary cyclic schedule X. From Lemma 2, we have

and thus

for all k.

Now let v = gcd(m, n). We define m' = mjv and n' = njv. Note that m' and n' are relatively prime. Further, let Pk = Hv(k+l)/ Hvk· Note that Pk > 1 for all k. Then for all k,

This implies that for all k,

There are two cases to consider.

Case 1: There exists some k' such that

Then we have

We are interested in how small Rm,n(X) can be. Let d = Pk' · · · Pk' +m' - 1. Then

The valued = ( m + n) /n minimizes the right-hand side over the region d > 1. Substituting into the previous inequality, we find

Case 2: The inequality

holds for all k.

Because n/m = n' / m', we can apply Lemma 3 to show that {Pk} converges, and hence limk-.oo Pk is well defined. Then we have

We can proceed as in the previous case but with d limk-.oo Pk· This gives

As in the previous case, we find that

Combining this inequality with Theorem 1, we get the desired result. 0

3 Multi-Robot Search on Rays

The results from the previous section can be directly ap­ plied to a formally similar problem involving multiple robots searching for a goal. The problem is described as follows. Initially, m robots stand at the intersection of p rays (with m < p) . The robots, all moving in a continuous fashion and at the same speed, search for a goal at an unknown location on one of the rays (see Figure 2). The search ends as soon as one of the robots finds the goal. Because there are not enough robots to cover all of the rays, finding a good search strategy is nontrivial. At this level of detail, the search problem may seem very different from the contract scheduling problem. Below we provide a more precise description of the search problem and show how the contract scheduling results can be applied.

A search is an infinite sequence of search extents, or return trips departing from the origin. Formally, a search strategy is a tripleX= ({Pk} , {h},{Lk}),wherePk E {O, . .. ,m1} is the robot executing search extent k, h E {0, . .. , p -1} is the ray on which search extent k takes place, and Lk E JR+ is the length of search extent k. By adding the same con­ ditions as in the contract scheduling case, we get an exact correspondence between schedules and search strategies. A cyclic search strategy is defined in the same way as a cyclic schedule.

A natural metric for the efficiency of a search strategy is the time-competitive ratio, the worst-case ratio of the total time spent searching to the time required for a single robot to traverse directly to the goal. We assume that the goal is not considered discovered until a robot actually moves beyond it. We assume also that the location of the goal is such that it cannot be found on the first search extent on any of the rays. This means that for each ray a, we consider only locations t ~La.

Before formally defining time-competitive ratio, we need to introduce a new function and explain its use in the defini­ tion. Let us defines( a, t) to be the index of the first search ex­ tent that goes past point ton ray a. This means that if the goal is located at point ton ray a, then it is found during search ex­ tent s(a, t). The total search time up through extent s(a, t) is 2G s(a,t). (The factor of two results from search extents going out and back on rays.) However, since the search ends as soon as the goal is found, the last extent does not go to completion, and thus we must subtract out 2Ls(a ,t) - t. This leads us to the following formal definition for time-competitive ratio.

Definition 2 The time-competitive ratio,

We can now give a formula for the relationship between acceleration ratio and time-competitive ratio for cyclic sched­ ules and search strategies.

Theorem 3 For all cyclic search strategies (schedules) X,

where X' is the same as X. but with h = k mod (p - m ).

Proof: Because of the length-increasing and problem-round­ robin properties, we know that the first search extent to pass a point on a ray comes p extents after the last extent on that same ray. Formally, we have that for all a and all t 2: La,

Thus we have

The last equation above expresses the intuitive notion that the worst place for the goal to be is just out of reach of one of the robots.

Now we have

The last equation requires some explanation. Because of the processor-round-robin property, the robot that performs search extent k + p does so immediately after completing search extent k + p- m. Thus Gk+p = Gk+p-m + Lk+p· Finally,

0

We define the minimal time-competitive ratio form robots and prays as

where the infimum is taken over the set of cyclic search strate­ gies. This has the following immediate consequence.

4 Conclusion

In this paper, we addressed two apparently different schedul­ ing problems, one involving contract algorithms, and the other involving robots searching on rays. For the contract scheduling problem, we provided a schedule and proved its optimality among the class of cyclic schedules. We further showed how contract scheduling results can be applied to the robot search problem, thus unifying the two problems.

A natural direction for future research is to study less re­ stricted classes of schedules and search strategies. One in­ triguing question is whether lower acceleration ratios can be achieved with schedules that are not problem-round-robin or length-increasing. It would also be interesting to know whether the contract scheduling and robot search problems have similarities beyond those that result from using cyclic schedules and search strategies.

Acknowledgments

We thank William Hesse and Laszlo Babai for providing key insights into the proof of Lemma 3. We also thank Theodore Perkins and Charles Sutton for comments on earlier drafts. Support for this work was provided in part by the NSF un­ der grant IIS-0219606 and by NASA under grants NAG-21394 and NAG-2-1463. Daniel Bernstein was supported by a NASA GSRP Fellowship. Any opinions, findings, and con­ clusions or recommendations expressed in this material are those of the authors and do not reflect the views of the NSF or NASA.

A Proof of Lemma 3

This section contains a proof of the central lemma used for our lower bound result. It is repeated below.

Lemma 3 Let m and n be relatively prime, and let {Pk} be a sequence of real numbers that is bounded from below by 1. If (Pk · · · Pk+m-1)nfm 2: Pk+m · · · Pk+m+n-1 is satisfied for all k, then {pk} converges.

Proof: We first define Qk = lnpk. Since the convergence of { Qk} implies the convergence of {Pk} , we can hereafter focus our attention on { Qk}.

We have

Let us define

Note that rk 2: 0 for all k. Now let

A simple calculation shows that for all k, rk = sk - sk+1. Because the rk are all nonnegative, we have Sk 2: sk+1 for all k. Since {pk} is bounded below by 1, { qk} is bounded from below, and hence { sk} is bounded below. By the monotone convergence principle, { sk} converges.

Thus we have

where v = limk_,oo Sk and limk_,oo Ek = 0. This equa­ tion is a linear nonhomogeneous difference equation [Mick­ ens, 1987]. The behavior of { qk} depends on the roots of the characteristic polynomial,

We know that { qk} is bounded below, and since { sk} con­ verges, { qk} is also bounded above. Thus to demonstrate convergence, it suffices to show that f has no roots on the unit circle.

Consider the polynomial

Clearly z = 1 is a root of g but not of f. To show that f has no roots on the unit circle, we will show that g has no roots on the unit circle other than z = 1.

We must show that for all z, if g(z ) = 0 and lzl = 1, then z = 1. If g(z) = 0, then

Adding the assumption that lz l = 1, we get

In order for the first and last expressions to be equal, we must have zm+n = 1. Substituting back into the original equality, we get

which implies that zn = 1. It is a basic property of complex numbers that if zm+n = zn = 1 and gcd(m, n) = 1, then z = 1.

We have thus shown that { qk} converges, and hence {pk} converges. D