Solving Time-Dependent Planning Problems

1 Introduction

We are interested in the problem of controlling an au­ tonomous agent embedded in the real world ( i.e., a robot) . In order to act effectively in a complex envi­ ronment, the agent will most likely need to reason about sequences of predicted events, ·some corresponding to its own actions, some the result of other processes. We call this reasoning process planning. In some situations, the time required to plan may be considerable. Predicted events may provide constraints on the amount of time available or otherwise affect the cost of time spent plan­ ning. We say that a planning problem is time-dependent if the time spent planning has a cost ( i.e., affects the utility of the agent's performance).

In [Dean and Boddy, 1988], we define a framework for constructing solutions to time-dependent planning prob­ lems that we call expectation-driven iterative refinement. This framework is intended to restrict the form of the so­ lutions generated, in order to make their analysis easier. Planning using expectation-driven iterative refinement is accomplished using a set of decision procedures known as anytime algorithms. Anytime algorithms are defined as algorithms that return some answer for any alloca­ tion of computation time, and are expected to return better answers when given more time. A solution to a time-dependent planning problem using expectation­ driven iterative refinement will consist of a set of anytime algorithms for planning, and a deliberation-scheduling al­ gorithm that allocates computational resources to the set of anytime algorithms based on expectations regarding their performance.

·This work was supported by an IBM graduate fellowship, by the National Science Foundation under grant IRI-8612644, and by the Advanced Research Projects Agency of the De­ partment of Defense and was monitored by the Air Force Office of Scientific Research under Contract No. F49620-88C-0132.

In this paper, we take the first steps in developing a methodology for applying expectation-driven iterative refinement to time-dependent planning problems. As an example of what such a methodology should consist of, consider the use of divide-and-conquer as a strategy for solving combinatorial problems. Divide-and-conquer is a useful strategy for problems that can be decom­ posed, such that the resulting subproblems have sub­ stantially easier solutions. The literature offers a great deal of advice on how to go about decomposing a par­ ticular problem ( e.g., keeping the size of the subprob­ lems approximately equal [Aho et a/., 1974]). Problems that are not completely decomposable may have approx­ imate divide-and-conquer solutions based on the intro­ duction of appropriate assumptions ( e.g., Karp's par­ tition for TSP [1977]). Analogously, a methodology for expectation-driven iterative refinement will require some way of identifying planning problems as likely candidates for expectation-driven iterative refinement, and a set of methods for generating solutions.

We proceed with the development of a methodology for expectation-driven iterative refinement by applying it to a moderately complex robot planning problem. The process of constructing a solution provides some insight into what a methodology for expectation-driven iterative refinement will look like. It also helps validate our claim that the framework itself is useful in that we construct a useful solution without appealing to luck or extraordi­ nary inspiration . In the next section, we present a robot planning problem, and discuss how to break the problem down into pieces suitable for implementation as anytime algorithms. The rest of the paper describes our solution in detail.

2 The robot courier

Suppose that we are in charge of designing the control program for a new model of robot courier for a deliv­ ery service in Manhattan. The function of these couriers is to pick up small parcels and deliver them to speci­ fied locations. Assuming that a courier completes all of its assigned deliveries, the main factor in evaluating the courier's performance will be the speed with which it ac­ complishes this task. The faster deliveries are made, the more deliveries a courier can make, and the more income it will generate.

In any world where the robot does not have complete information, the exact utility of a particular course of action cannot be determined a priori. If we can formu­ late expectations regarding the exact state of the world (possibly conditioned upon information that the robot has some way of obtaining) then it is possible to calcu­ late the expected utility of a -proposed course of action. This is the metric on the robot's performance that we seek to maximize. The utility of the robot's performance we define in terms of the time required to complete the entire set of deliveries (i.e., the less time, the better).

How might a robot courier plan, in order to do its job better? The robot must fix upon a tour that visits all of locations on its current list of deliveries. We refer to this as tour improvement planning. Choosing a tour may have considerable impact on the length of time re­ quired to visit all the locations. Once the robot has an ordering for the locations, it may spend time determin­ ing how to get from one to another of them. We refer to this as path planning. We assume that path planning is accomplished by constructing an ordered set of tar­ get points between the two locations. Planning in any greater detail we ignore. Arguably, the tasks involved in navigating between target points are sufficiently routine that "planning" is not normally required. 1 In addition, whatever work is done on achieving tasks at lower lev­ els will be local in scope (determining which door to go in, avoiding bumping into things, etc.) and should not greatly affect the expected utility of tour improvement or path planning. 2

The benefit to be expected from either tour improve­ ment or path planning will depend on the current situa­ tion. Finding a tour that avoids the area around the Lincoln Thnnel at rush hour is most likely time well spent. On the other hand, if the next location to visit is straight down 5th Avenue from the robot's current po­ sition, there may be only a minor benefit to refining a path to get there. In either case, time spent planning may hurt more than it helps if it causes the robot to delay too long. Deliberation scheduling for the robot courier consists of allocating time to algorithms for tour improvement and path planning based on the expected improvement in the robot's performance. An optimal deliberation schedule for a given situation is a deliberation schedule that maximizes the expected utility of the robot's performance in that situation. An optimal deliberation scheduling algorithm always generates the optimal schedule for the current situation. All the de­ liberation scheduling algorithms discussed in this paper are optimal.

1 See, for example, [Brooks, 1985].

2 We are not ignoring the possibility that the robot may fail at low-level tasks so as to require additional planning. The possibility of failure is included in the expected utility of the plans generated.

In the next section, we describe an experimental do­ main within which we have implemented a solution to the robot courier problem.

3 The gridworld

One of the salient characteristics of solutions using expectation-driven iterative refinement is their reliance on expectations to support deliberation scheduling. Us­ ing expectations is necessary because we have no way of determining the precise behavior of the planning al­ gorithms employed by the robot, apart from actually running them. Accordingly, an important part of con­ structing a solution to the robot-courier problem consists of gathering statistics on which to base expectations re­ garding the anytime algorithms for path planning and tour improvement. For the purposes of this exercise we have designed a simulated world in which the required statistics can be gathered . easily. We call this simulated world the gridworld. The gridworld consists of a rectan­ gular subset of the integer plane (Z 2 ), where each point is a location that may be occupied by the robot, or by something else, but not both. The robot can move onto any of the 4 neighbors of the point it currently occupies, provided that neighbor is not already occupied. We de­ fine the distance between adjacent locations to be one unit. The robot has a map of the world, and is capa­ ble of finding its way from one point to another with­ out a planned path, by keeping track of the heading of the destination as it performs a form of obstacle avoid­ ance. Path planning helps because a planned path may be more direct.

The statistics we needed were gathered over randomly­ generated instances of the gridworld with a predeter­ mined size and a fixed probability that any given loca­ tion is occupied (.2). We will refer to these instances as standard gridworlds.

4 Anytime algorithms

In this section, we present and analyze anytime algo­ rithms for path planning and tour improvement in the gridworld. Before proceeding with our analysis, we in­ troduce some terminology and notation:

• C is a set of locations, defined as points in the integer plane (Z 2 ) .
• S = (It, /2, ... , lm} is a tour; an ordered sequence of locations in C.
• d; ,j is the distance between locations l; and lj. In the gridworld, d; ,i equals the sum of the difference in x and y coordinates between l; and lj.
• 1Js is the length of the tourS (1Js = 2:~~ 1 d; ,i+t).
• v is the mean speed of the robot, moving without incident or obstacle. We assume that the time re-

quired to attain this speed is small compared to the time the robot spends traveling between locations.

• 71,;(6) is the expected amount of time required to go from /; to I;, given an amount of time 6 spent planning a path.
• 71,; = 71,;(0) is the expected amount of time required to go from I; to I;, without a path.

4.1 Path planning

The robot plans a path from one location to another by constructing an ordered set of adjacent locations (target points), starting at the initial location and working to­ ward the destination. The algorithm used is a heuristic search similar to an algorithm described in [Korf, 1987].3 In the gridworld, the algorithm when run to completion produces a path whose length averages 1.07 * the dis­ tance between the begin and end points, and examines a number of locations averaging 1.1 * the distance from one location to the other. Since it proceeds by searching from the initial point towards the destination, it can be interrupted at any time to return a partial path whose expected length is a linear function of the time spent planning, as is the expected distance remaining to the destination.

The robot can traverse a path at speed v, so that the expected time required to go from h to /2 given a completely defined path is a* (d1,2/v), where a = 1.07. The mean time required to move from one location to another without a path ( i.e., working around obstacles as they are encountered) turns out to be a linear function of the distance between them. For standard grid worlds, the constant involved is approximately 3. Thus 71,; = hd;,;/v, where b:::::: 3. In the interests of simplifying the analysis in the rest of this paper, we assume that a = 1 and b = 3.

We define J.'(6) to be T;,j -71,j(6), the expected time saved by a partially defined path generated usin~ an al­ location of deliberation time 6. Then 1'(6) = - 6 , up _ Tpttl to 6 = Tptdi,i, where Tpt equals the expected amount of time required to add another target point to an existing path. 4 Figure 1 shows how the expected savings in travel time varies with the time spent planning. We call such a function a performance profile for the anytime algorithm. The dependent variable for a performance profile may be any characteristic of the result of an algorithm that we find significant. One anytime algorithm could have sev­ eral performance profiles tracking different attributes of the results it returns.

3 Basically A ·, using the distance to the goal as a heuristic evaluation function.

·we assume that the robot can work on a path between two locations only before it starts moving between them. This is a stronger assumption than we might like, but it can be relaxed fairly easily at the cost of complicating the de-

4.2 Tour improvement

We assume that the cost of a tour equals the total dis­ tance traversed. Though we make the assumption, it is not apparent that a minimum-distance tour will take minimal time to traverse, including planning time. In fact, it is possible to construct two tours such that the longer one is expected to take less time to traverse. How­ ever, our expectations regarding the result of tour im­ provement are in terms of the length of the entire tour, not the distribution of the distances between individ­ ual locations. Thus we can make no better assump­ tion about the individual distances than that they are all equal. Given two tours of different lengths, both assumed to have all individual distances equal, the ex­ pected time to traverse the longer tour will be greater.

To construct a useful anytime algorithm, we need an initial answer whose cost is known, and some measure of how that cost is expected to improve with deliberation time. For tour improvement planning, the initial cost is the length of the initial tour (choose one at random, if necessary), and the optimal cost is the length of the opti­ mal tour. The length of the optimal t~r for n gridw~ld locations can be approximated by 1.2d(n)· 58 , where dis the mean distance between the points on the tour, with a standard deviation of about 10% for tours of between 10 and 15 locations.

The next step is to find an anytime algorithm for tour improvement plannine;. Edge-exchange algorithms [Lin and Kernighan, 1973j produce tours that are progres­ sively closer to optimal by exchanging small sets of edges (typically 2 or 3) such that the length of the overall tour decreases. It has been shown empirically that for large (100 city) tours, these algorithms average within about 8% of the optimal tour length when run to com­ pletion [Lawler et a/., 1985]. In the gridworld, a tour­ improvement algorithm that looks for pairs of edges to exchange averages within 2% of optimal when run to completion on considerably smaller tours (between 10 and 15 points) . The mean number of exchanges neces­ sary to obtain an almost-optimal tour for between 10 and 30 locations is approximately (.61n- 2)1.1, with a mean error of less than 1% and a standard deviation of about 10%. The mean improvement in tour length af­ ter k exchanges as a fraction of the maximum possible improvement can be approximated by a function of the form f(k) = 1- e->.k, where A is a function of the size of the tour. For tours of 24 locations, a value for A of 0.29 results in a mean error and standard deviation both under 1%. Figure 2 gives a performance profile for tour improvement, showing the expected improvement in tour length as a fraction of the maximum possible, given an allocation of deliberation time 6. Because the algorithm always looks for the best pairs of edges to exchange, the time required for any exchange is roughly constant for a given tour size.

liberation scheduling algorithm (reschedule, breaking up the area to be traversed into planned and unplanned segments) .

Figure 2 is not a graph of the expected tour length over deliberation time. Given an initial tour length 1) s, an estimated optimal tour length 1J s· , and an average length of time t, to make one exchange, the expected tour length as a function of time is g(t) = Ds· + e->.tft·(1Js -1Js· ). Given the assumption that the minimum-length tour will take the least time to plan for and traverse, minimizing expected tour length max­ imizes expected utility.

5 Deliberation scheduling

In this section, we discuss deliberation scheduling for three restricted versions of the robot-courier problem:

• Pr-1. Deliberation scheduling for path planning for a fixed sequence of locations.
• Pr-11. Deliberation scheduling for tour improvement followed by path planning for the improved tour.
• Pr-111. Deliberation scheduling for a limited interleav­ ing of tour improvement and path planning.

5.1 Pr-1

Assume a tourS= (/o, /1 , . .. , /1:), where /o is the robot's current location. Let 8; be the amount of time allocated to deliberating about the path from /;_1 to I;, for 1 ::; i ::; k. Let begin(/;) and end(/;) be the begin and end points, respectively, of the period of time over which the robot is traveling from /;_1 to I;. This defines a time line with the following constraints:

• VI; : 1::; i::; k, begin(/;)= end(/;_!)
• VI; : 1::; i::; k, end(/;)= begin(/;)+ 11-1,;(6;)

We will also use the following definitions:

• Let o; = Tptdi-1,i - max. useful 8; .
• Let c = - 2 - Tpt'V -slope of J.L(6;),0 < 8; < o;.
• Using the results of Section 4.1:

The procedure given in Figure 3 is optimal in exactly the sense defined in Section 1. In other words, the algo­ rithm generates a deliberation schedule for S such that

Procedure: Sched-1( S) begin t := end(l~~:) forj = kto1,step-1 begin ift > begin(lj), then gap:= max(c6j, t- begin(lj)) t = begin(lj) else gap:= 0 6j := min(6j, t- begin(h), c!l (t- begin(l!)+ gap)) end t := t - 6j gap := max(O, gap - c6i) ift = begin(l1), goto exit end exit:: if c > 1 and gap > 0, then t::. := min(6j- 6j, ~·gap) 6j := 6j + t::. 6; := 0, 1 :5 i < j end return t::. + 2:: (1i-I,;(6;))

there is no other schedule for which the robot is expected to complete the tour in less time. The procedure works backward from the last path to be traversed, ensuring that each path is allocated the maximum useful amount of time. There may be times where the robot is pre­ dicted to be traversing a path and all later paths have already been allocated as much time as will produce any improvement . The length of the earliest such predicted idle time is the value of the variable gap. The algorithm is simplified considerably by the fact that c is the same for any path ( i.e., as long as 6; < o;' it doesn't mat­ ter which 6; gets allocated, for 1 < i < k). That c is a constant is a property of the gridworld, not an assump­ tion we make. Figure 4 shows a deliberation schedule constructed for an example tour. The shaded regions represent time allocated for deliberation.

5.2 Pr-11

Fr-11 extends Pr-1 by allowing S to be reordered, but only before any path planning gets done. In other words, if the initial tour is far from optimal, we expend some effort improving it before doing path planning. GivenS, we can generate a deliberation schedule for path plan­ ning using Sched-1. Sched-1 returns the expected time to complete S, including path planning time. We also know the expected length of the tour S' resulting from a given amount of time allocated to tour improvement. To calculate the expected utility of tour improvement, we need the expected time required, including path plan­ ning time, to complete S'. We have no better informa­ tion than the assumption that all the distances between locations in S' are equal. So the path planning problem involves k paths, all of length d = Vs' fk.

In this case, the expected time to complete the tour given an optimal deliberation schedule can be expressed as a linear function of d (and thus of Vs' ). There are four cases, depending on the value of c. The cases are distinguished by differing values of c and k. In the first case, the expected benefit from path planning is so high that each path is allocated the maximum deliberation time. In the second case, the expected benefit is slightly less, so that setting 81 to 8* might make the tour take longer. In the third case, the expected benefit of path planning is low enough that any value of 81 > 0 has a negative utility, and that only 8k is automatically allo­ cated the maximum amount of time. In the last case, the improvement to be expected is so small that only the last path in the tour is worth planning for, and that only while traveling among the other locations. 5

For a particular domain, c and v are constants. k is fixed for a given set of locations. Let f(d) be the ap­ propriate linear function of d, which we will write as ad. Let g(S, 8') be the expected length of the tour returned by the anytime algorithm for tour improvement, allo­ cated 8' units of time. Then the following procedure is an optimal deliberation scheduling algorithm.

Procedure: Sched-2( S) begin Choose 6' s.t. T = 6' +(a* g( S, 6')/k) is minimized. if Sched-1( S) < T, then 6' = 0. return 6'

end

Once the tour improvement algorithm has been run, we run Sched-1 on the resulting tour. That the required minimization can be done easily is guaranteed by the fact that g' is always negative and g" is always positive (see Section 4.2); there are no local minima.

5.3 Pr-Ill

Interleaving tour improvement and path planning arbi­ trarily can be complex; there are an exponential number of ways in which a given tour might be subdivided into pieces on which to run the tour improvement algorithm. There is a useful special case, however, for which we can construCt a deliberation scheduling algorithm whose complexity is O(n 2 ) in the number of locations. We define the scheduling problem Pr-Ill to consist of de­ termining some number of locations Ia, .. . , 1;, for which we plan paths first, followed by the remaining locations , which are treated as an instance of problem Pr-11. An optimal scheduling algorithm for Pr-Ill is given in the longer paper.

5 The exact form of the relation between distance and ex­ pected completion time for each of these cases is given in [Boddy and Dean, 1989], an extended version of this paper.

The algorithm works by assuming initially that all the travel time for the locations Ia, ... , 1; will be used to deliberate about finding an improved tour for 1;, ... , lk. Using a procedure almost identical to Sched-1, the algo­ rithm then sweeps back from begin(/;), determining for each increment of time whether spending time on tour improvement or path planning is expected to save more time in the final schedule.

6 Related work

There is a growing interest in applying decision theory to AI problems. [Horvitz et al., 1988] sketches the current state of this effort, and points out some areas where fur­ ther research might be most fruitful. In addition to our work on planning, the application of decision theory to the control of resource-bounded reasoning is currently being pursued in at least the areas of medical diagno­ sis [Horvitz, 1987], heuristic search [Hanson and Meyer, 1988], [Russell and Wefald, 1989], and computer vision [Levitt et al., 1988]. Breese and Fehling [1988] provide an abstract characterization for the decision-theoretic con­ trol of an autonomous agent, including reasoning about tradeoffs among planning, acting, and gathering infor­ mation.

There is also some interesting work in other areas. In building his ping-pong playing robot, Andersson [1988] solves special cases of exactly the kind of problems we are interested in. It is not clear to what extent his techniques will generalize, but they are obviously quite successful for one particular domain. Wellman [1988] provides an extended analysis of the use of uncertain knowledge in planning, which is a problem that the control system for any reasonably complex agent must address. The work in [Ow et al., 1988] deals with the problem of re­ source bounds by using the analysis of a specific domain to guide the construction of strategies for controlling rea­ soning in that domain.

7 Conclusions

Accounting for the time required for planning or other complex computations is a necessary part of construct­ ing systems for controlling robots. In [Dean and Boddy, 1988], we define a framework for solutions to time­ dependent planning problems called expectation-driven iterative refinement. This framework is intended to re­ strict the form of those solutions to facilitate decision­ theoretic analysis. In the current paper, we are inter­ ested in a methodology for applying expectation-driven iterative refinement. Specifically, we want a way to iden­ tify problems as likely candidates and a body of tech­ niques for generating solutions. We detail the process of solving a time-dependent planning problem involving a mobile robot courier, as a way of investigating such a methodology.

There are several lessons to be taken from this paper on how to go about solving a time-dependent planning problem. For one, we do not "solve" either of the plan­ ning problems facing the robot. We provide approximate solutions, and some measure of the errors to be expected. A problem where a precise answer is critical would probably use different algorithms. An interesting point that arises in the generation of performance profiles is that we need a fast estimate of how good an answer is obtain­ able. This estimation will of necessity introduce some error (otherwise the anytime algorithm would be super­ fluous) and we should know how much. Assuming that the anytime algorithms can be represented by continu­ ous performance profiles does not for this problem intro­ duce any large error-the increments in which planning is done are small enough that the approximation is a reasonable one. The form of the solution we provide is strongly determined by the structure of the environ­ ment within which the robot operates. The environment determines the performance profiles of the anytime algo­ rithms the robot employs for planning, and to a lesser extent the algorithms themselves.

The process of generating a solution provides some indication of the characteristics-of the methodology we are developing. Good candidates for solution using expectation-driven iterative refinement will be problems that can be decomposed into subproblems that can be solved using anytime algorithms for which we can gener­ ate useful expectations in the form of performance pro­ files . There is an additional restriction, which is that the problem must be decomposed in such a way that we know how to combine the profiles for the subproblems so as to produce a performance profile for time spent on the problem as a whole.

Solving even a moderately complex time-dependent planning problem requires combining the results of sev­ eral processes. In some problems, there may be several unrelated subproblems competing for processor time. For the robot courier, this would correspond to allocat­ ing planning time for the individual paths on a tour. Also, most useful anytime algorithms we know of ap­ ply to sufficiently simple problems that any interesting planning problem will require combining the results of several anytime algorithms. In order to plan for a tour, our robot courier needs to combine the results of path planning and tour improvement . These are not sepa­ rate competing processes. The expected utility of time spent path planning depends on the result of tour im­ provement. In our example, combining expectations for the two planning algorithms is straightforward: they can be composed, given an assumption that is justified by the information available to the robot . Other problems and other decompositions will require combining expec­ tations in different ways.

In this and earlier papers, we have analyzed a few special cases of time-dependent planning problems. In future work, we hope to provide a more general clas­ sification of time-dependent planning problems, and to analyze the various classes in terms of their solution us­ ing expectation-driven iterative refinement.