Reaction-First Search

1 Introduction

Most general-purpose planning algorithms cannot be used incrementally. Since initial steps in a partial plan are not necessarily part of a solution, planning algo­ rithms generally do not produce any plan for execu­ tion until a complete plan has been found. Such non­ incremental algorithms fail to address the needs of an agent that must act before a complete plan is available.

This paper presents a general-purpose planning algo­ rithm that is incremental. The algorithm, Reaction­ First Search (RFs), generates partial plans in service of a given goal. RFS is used by a situated planner to pro­ vide guidance to an independently competent reactive system. Without a plan, the reactive system executes a human-provided program, and by so doing, stands some chance of producing a behavior that satisfies a given goal. The partial plans found by RFS help the reactive system handle difficult situations that were not foreseen by the programmer. RFS reasons about the reactive system's behavior, giving it plans to help satisfy the goal. We cannot guarantee that the single plan found by RFS af­ ter an arbitrary amount of computation increases the reactive system's chances of satisfying the goal. How­ ever, averaged over a number of trials, we can guarantee that RFS monotonically increases the reactive system's goal satisfaction probability as a function . of computa­ tion time. Thus, the expected performance of RFS is to monotonically improve the reactive system's goal sat­ isfaction probability - it is this expected improvement property that makes RFS usefully incremental.

2 Background

A situated agent often needs to take action within bounded time. To facilitate this, we suggest that when­ ever possible, a prior reactive competence should be hand-coded by a programmer. This approach avoids ex­ pensive automatic planning whenever the prior compe­ tence is capable of solving a given problem. Our general architecture is based on this idea and includes two con­ nected components: a planner and a reactor. For details see Bresina and Drummond (1990], Drummond, et al. (1991], and Bresina, et al., [in press].

Bresina and Drummond (1990] introduced the princi­ ple of independent competence to ensure that the reactor is able to take action with or without a plan. When the reactor is told to act, it executes the currently available plan and then falls back on a reactive program defined by the programmer. If a complete plan is available then the execution of that plan will cause the reactor to solve the problem. If absolutely no plan is available then the reactor executes only the programmer-provided reactive program. When there is a partial plan available, the plan takes the reactor part of the way, and the reactive program takes over at the plan's end.

These intermediate cases lead to the following prob­ lem. If the reactor executes a partial plan before that plan is known to lead to a solution, how can we be sure that this will not impair the reactor's performance? In­ deed, the entire reason that search is an essential part of problem-solving is that there is no purely "local" way to guarantee that any given partial plan can be extended to a solution. This is the problem that RFS solves. The ex­ pected performance of RFS is to monotonically improve the goal satisfaction probability of the reactor, no mat­ ter how much time is spent searching. RFS accomplishes this by reasoning about possible behaviors of the reac­ tor and constraining them as appropriate. RFS can be used incrementally, releasing partial plans computed in the time available.

3 Basic definitions

This section defines the terms used throughout the rest of the paper. Most of these terms are reasonably stan­ dard. The planner is covered first, the reactor second.

The planner

Briefly, a state is a structure that describes a situa­ tion in the application domain. An operator describes an executable action and is considered enabled in a state when the action denoted by the operator can be exe­ cuted in the corresponding situation. An operator can be applied to a state in which it is enabled, producing a successor state that describes the effects of the action denoted by the operator. The STRIPS operator language [Fikes and Nilsson, 1971] is an example of this but is actually a special case; more general languages are pos­ sible. A trajectory is a sequence of operator applications, and any given trajectory models one possible behavior of the reactor.

A search tree is a tree of trajectories rooted at a com­ mon state. A level in a search tree is a set of states that are the same distance from the root. A goal is a function 1 that maps a trajectory into the set {t, !}. If the goal function returns t for a given trajectory, then the trajectory satisfies the goal. A problem is a specific initial state, a set of operators (defined in terms of oper­ ator enablement and application functions), and a goal.

A prefix partial plan (or just prefix plan) for a given problem is a trajectory constructed. from the problem's operators, rooted in the problem's initial state. Such a plan is a "prefix" since it specifies the first few actions in a trajectory which may or may not lead to the eventual satisfaction of the problem's goal. A solution plan for a given problem is a trajectory that satisfies the goal.

The reactor

A policy is a function that maps a state into a set of enabled operators and is provided by a programmer to specify how the reactor should behave in a given set of situations. Thus, a policy defines a prior reactive com­ petence for the reactor. For each possible stateS and for a given policy po, if I po ( S) I ~ 1, we say that the pol­ icy is deterministic; otherwise, if there exists a possible state S for which I po (S) I > 1, we say that the policy is nondeterministic. Since a policy is used to define the re­ actor's prior competence, it is largely counterproductive to allow the policy to encode a general purpose problem solving mechanism (a planner, for instance). Thus, we insist that any given policy be computable within time and space that are bounded by constants.

A policy is .executed by the reactor as follows. First, a state S is created to describe the agent's current situation. Next, the policy is evaluated on S, pro­ ducing a disjunctive set of recommended operators, {01,02 , ··· ,0n}· If this set is empty then the reactor halts. Otherwise, one particular Oi is randomly selected and executed.

In terms of the planner's search space, the subtree defined by the policy from a state S is the tree rooted at S defined by recursive application of all policy­ recommended operators. Thus, the states reachable from S under the policy are a subset of all possible states reachable from S. A policy state is simply a state for which the policy returns a non-empty set of operators.

1 We disallow goal functions that permit the growth of infinite length trajectories.

We measure the reactor's prior competence for a given problem instance as the probability that the reactor can satisfy the goal using only the programmer-defined pol­ icy. This probability can be explicitly measured, for ex­ ample, by repeatedly placing the reactor in the problem's initial state and allowing it to attempt to satisfy the goal by executing its policy. The number of samples required to obtain high statistical confidence is a function of the nondeterminism in the policy. If the policy is determin­ istic then a single run suffices. If there is a large degree of nondeterminism in the policy, then a large number of runs might be required.

The plan execution model of the reactor is as follows. At each point in time there is a prefix plan defined by the trajectory that terminates in the planner's "current" search state. If the reactor is told to act, it first executes this prefix plan and then executes its policy until the goal is satisfied or until the policy returns the empty set. If the current prefix plan causes the reactor to produce a behavior that satisfies the goal, then the policy is not executed. If the current prefix plan is null, then the policy is executed immediately.

This paper makes some assumptions regarding the ex­ ecution environment. We assume that no errors occur during plan execution, and we also assume that sens­ ing is free and provides enough information to define a search tree that includes a solution (if one exists). These assumptions merely simplify the discussion; they are eas­ ily relaxed, but space precludes a detailed discussion. Finally, note that RFS does not address the question of how long to plan- it simply uses whatever computation time is available.

4 The problem and a solution

Assume that a timer, t, is started when a problem is pre­ sented to the planner and reactor. At t = 0, the reactor can be told to run and, by executing its policy, stands some chance of solving the problem. If the reactor were to sit idle until the planner released a prefix plan for exe­ cution at t = 1, how would the reactor's performance be affected? Again, what if the reactor were to sit idle until the planner released a prefix plan at t = 2? RFS guaran­ tees that whenever the planner is stopped, t = 1, 2, 3, .. ., the expected performance of the reactor is never worse than its performance at t = 0. Indeed, as we show below, the reactor's performance can be significantly improved.

The three principles of Reaction-First Search

RFS is a randomized search algorithm that requires the planner to first reason about what the reactor would do without a plan. RFS uses the policy to define a search­ space bias, exploring the policy-defined subtree before any other part of the search space is examined. The policy defines a set of possible reactor behaviors. The planner, guided by the policy, searches through the set of trajectories that model those behaviors, looking for one that satisfies the given goal.

There are three principles that differentiate RFS from traditional state-space search. These principles, together with a definition of state-space search, constitute a defi­ nition of RFS. The three principles of RFS are:

1. All states in the policy-defined subtree must be ex­ panded before all other states in the search space;
2. After selecting a level in the search tree by any means, a policy state in that level must be randomly chosen for expansion;
3. In any given policy state, policy-recommended op­ erators must be randomly chosen for application.

These three principles are all that is required by RFS; any state-space search procedure that follows them faith­ fully implements our algorithm and consequently has expected performance that guarantees monotonic im­ provement of the reactor's goal satisfaction probability. The proof of monotonic improvement [Drummond, et al., 1992] hinges on the observation that the probabil­ ity of goal satisfaction at each level of the policy-defined subtree is the same. RFS samples from these levels in a randomized manner, and this ensures that the proba­ bility of goal satisfaction obtained at each point in time is, on average, always greater or equal to that obtained by the policy at time zero. 2 The incrementality of RFS comes from the fact that it can be stopped whenever it is about to expand a state: the trajectory that connects the root to this current state defines a plan that can be executed by the reactor.

The three principles of RFS are not as restrictive as they might first appear. In fact, it is easy to implement RFS so that it explores the policy subtree in a variety of ways. We have experimented with standard depth-first and breadth-first search, as well as iterative sampling [Minton, et al., 1992; Langley, 1992]. Other implemen­ tations are also possible; for instance, iterative deepen­ ing [Korf, 1985] and iterative broadening [Ginsberg and Harvey, 1990]. One need only bias the search according to the three principles of RFS.

Completeness and monotonic improvement

RFS first explores the subtree defined by the policy, starting with the root state. If the search strategy used for this exploration is complete (for instance, depth-first search with chronological backtracking), and if a solution exists in this subtree, RFS will find it. If a non-systematic search strategy such as iterative sampling is used then RFS is only asymptotically complete. In essence, with respect to the policy subtree, RFS is only as complete as the underlying search strategy.

If RFS discovers that there is no solution in the policy subtree, it selects an arbitrary open state and applies an arbitrary enabled operator, creating a new search state. The choice of which particular open state and enabled operator to choose is not dictated by RFS; the algorithm works no matter how the state and operator are chosen. The only requirement, and this is important, is that the subtree rooted at the new state must now be explored in the manner dictated by RFS. By repeatedly generating new open states in this manner, RFS is clearly complete, again assuming that a complete search strategy is used to explore each policy-defined subtree.

2 Please note that RFS does not actually calculate the pol­ icy's goal satisfaction probability. The monotonic improve­ ment property is an objective statement about RFS: the al­ gorithm exhibits expected monotonic improvement without having to explicitly calculate any probabilities.

Our hypothesis regarding Reaction-First Search

While RFS can be expected to monotonically improve the performance of the reactor, there is clearly a sim· pler approach: don't let the planner release prefix plans! With the principle of independent competence, the reac­ tor's goal satisfaction probability would hold steady at the point determined by its policy until sufficient time had elapsed to allow a complete solution to be found. We call this alternate approach non-incremental, since it does not issue preliminary advice to the reactor.

We hypothesize that RFS' release of prefix plans can have an advantage over the non-incremental approach. Specifically, we hypothesize that the partial plans found by RFS can help the reactor avoid dead-ends that might otherwise trap its policy. A dead-end for the policy is a state for which the policy returns the empty set and which fails to satisfy the goal. A critical choice point [Drummond, 1989] is a state from which there is an ac­ tion that leads to possible success and from which there is also an action that leads to necessary failure. In the context of RFS, a critical choice point is a state from which the probability of goal satisfaction (under the pol­ icy) is non-zero, but from which there exists a policy­ recommended action that leads to a state from which the goal satisfaction probability is zero. We hypothesize that RFS can have an advantage over the non-incremental approach since its prefix plans can provide guidance to the reactor at these critical choice points and thus help the reactor avoid dead-ends during execution.

Figure 1 sketches our hypothesis regarding the general relationship between the non-incremental approach and RFS. Assume that the reactor's prior probability of goal satisfaction is P. Thus, at time 0, there is a probabil­ ity, P, that the reactor will satisfy the given goal. The non-incremental approach ensures that the reactor's goal satisfaction probability holds steady at P until the ear­ liest time at which a solution is found. This point is indicated on the computation time axis by "ES" (ear­ liest solution). The average performance of the reactor will then increase until it reaches a maximum at the planner's latest solution ("LS") time, at which point the planner always has a solution, if one exists. The precise rate at which the reactor's average performance increases between ES and LS is a function of the search strategy and the search space.

The important aspect of our hypothesis is the per­ formance difference it predicts. The reactor's perfor­ mance profile under RFS initially tracks that of the non­ incremental approach, starting with a value of P at time 0. Whenever RFS identifies a critical choice point, the expected goal satisfaction probability should increase (there are two such increases sketched in the figure). The

.. ·

-- ES

precise size and shape of the difference is again a func­ tion of the underlying search strategy and search space. It is important to note, however, that the expected per­ formance of RFS is never worse than that obtained by the non-incremental approach and, according to our hypoth­ esis, can sometimes be significantly better. The next section experimentally explores this hypothesis.

5 Empirical results

We have implemented RFS on a telescope scheduling problem [Drummond, et al., in press], where the reactive policy is defined by a dispatch scheduler written by the company that builds the telescope controller. While we have a working version of RFS for this scheduling prob­ lem, we have not yet defined and carried out any exper­ iments. Thus, in this paper, we present the results from a detailed study of RFS at work in a simulated domain, the NASA TileWorld [Philips and Bresina, 1991]. The goal of the experiment reported here is to evaluate the hypothesis outlined in the previous section.

The problem class for this experiment is couched in terms of a two-dimensional grid of cells. The task is to retrieve a tile from one room, B, and to carry it back to a particular location in another room, A. As shown in Figure 2, room A occupies the lower left portion of the grid and room B occupies the upper right portion. The goal is satisfied if the agent, while grasping the tile, is in the lower-left corner cell of room A. Different prob­ lem instances in this class vary in terms of the obsta­ cles present in the rooms and between the rooms. For all problem instances considered, the agent is initially in the lower-left corner of room A and the tile to be retrieved is initially in the top-right corner of room B. The fig­ ure shows this common problem structure, illustrating all prior information available to the (human) designer of the reactor'.s policy.

The policy we devised for these experiments is a simple hill-climber that uses a traditional Manhattan distance calculation. The policy operates in three stages: first, move the agent from room A to room B; second, grasp the tile; third, move the agent back. The movement from room A to room B is itself implemented in three stages: first, move the agent from its initial location to one of the doors of room A; second, move the agent to one of the doors of room B; third, move the agent next to the tile. Any one of these subtrips can be halted by entrapment in a dead-end, since the policy uses Manhattan distance to suggest moves, and while this calculation provides useful guidance, it is not guaranteed to find a solution. The policy returns all moves suggested by the Manhattan distance calculation and hence is nondeterministic. Once the agent has grasped the tile, the return trip is also implemented in three stages. As for the outward journey, each of these stages can be halted by entrapment in a dead-end. Since the policy is not capable of physically backtracking there is no guarantee that it will solve the problem. Even so, it works well for many problems and satisfies the requirement of computability in time and space that are bounded by constants.

The dependent variable for this experiment is reactor performance, measured as goal satisfaction probability, and the independent variable is planning time. Intu­ itively, planning time should be measured in some metric units; however, since we carried out this experiment in Common Lisp, running on a Unix system, elapsed time is only weakly correlated with the amount of time actu­ ally spent planning. To overcome this, we observed that the time spent by the planner applying an operator to a state can be bounded by a constant. This is true since the evaluation of the policy takes constant time, as do all other operations involved with expanding a single state. While the precise value of this constant depends on a va­ riety of factors, the important aspect is that a bounded amount of time is spent applying an operator to a state. We use the term step to refer to such an operator appli­ cation. Thus, instead of measuring actual metric time we measure the number of planner steps taken.

To facilitate data collection, we designed an algorithm for calculating the probability that the policy will lead the agent into a dead-end. The procedure accepts an initial and goal location and returns the probability that the agent will become trapped in a dead-end via the execution of the policy. This procedure allows us to de­ termine the probability of goal satisfaction without ex­ plicitly executing the policy.

Figures 3 and 4 show some of our results, and more results are reported in Drummond, et al., [1992]. The left side of each figure shows a particular problem instance, and the right side shows the reactor's goal satisfaction probability as a function of planning steps. We used a depth-first chronological backtracking version of RFS for these experiments. Since the policy is nondeterministic, we ran RFS 500 times on each problem instance, and the graphs in each figure show the mean probability value obtained together with errorbars characterizing the 95% confidence interval.

Each problem instance is consistent with the prior in­ formation available to the programmer (Figure 2), but each adds some number of obstacles. Obstacles have the general shape of an "X" and are located either in the rooms or between the rooms. The arms of these "X"s define dead-ends that can trap the hill-climbing policy, and this is where planning can help provide guidance. Note, had this information been available in advance, we might have been able to formulate a better policy.

The graph in each figure shows the reactor's goal sat­ isfaction probability under RFS and the same measure for the non-incremental approach discussed in section 4. Since the non-incremental approach only releases com­ plete plans for execution, the reactor's performance re­ mains at the level defined by the policy until the plan­ ner terminates. As we predicted, there is some varia­ tion between the earliest and latest times at which the planner terminates. More importantly, our prediction of a performance difference between RFS and the non­ incremental approach is clearly demonstrated by these experimental results.

Consider Figure 4: the reactor's prior goal satisfaction probability is about 0.5, and within 10 steps the proba­ bility increases to almost 0.8. The reason for this early and significant improvement is clear from the problem instance. There are two dead-ends defined by the single "X" in room A. On its way out of the room, the agent can easily become trapped in the west or south side of the "X". When RFS gets the agent past the critical choice points that define the entries to these dead-ends, the probability of goal satisfaction increases dramatically. Of course, once past all dead-ends, the reactor's pol­ icy is able to solve the problem, without a plan. This is shown by the probability of goal satisfaction reaching 1.0 before the planner actually terminates.

It is interesting to note the points of greatest variance in the goal satisfaction probability. In Figure 3, for in­ stance, the variance is greatest around 70 planner steps. This is a result of the fact that there are a number of dif­ ferent plans that RFS might find to move the agent back to room A. Each of these plans takes the agent past the two "X"s, but there is some variability in how close these plans come to the ·various critical choice points. This gives rise to some variation in the reactor's goal satisfaction probability that finally settles down once all plans guide the reactor past all critical choice points.

This experiment clearly supports the hypothesis of section 4. The results show how prefix plans released incrementally by RFS can help the reactor avoid dead­ ends that might otherwise trap its policy.

6 Related work

Simmons' [1988] "Generate-Test-Debug" technique has partly inspired our definition of RFS. RFS starts with a specification of the reactor's behavior, reasons about how it may or may not satisfy the goal in a given situation, and "debugs" the behavior as appropriate. There is a clear opportunity here for more sophisticated approaches to debugging than are currently employed by RFS.

There are other systems that require a programmer to manually code a prior reactive competence in or­ der to avoid or reduce the need for automatic planning. In this regard there is work by Beetz and McDermott [1992], Brooks [1986], Firby [1987], Kaelbling [1988], and Georgeff and Lansky [1987]. Of these, only the system of Beetz and McDermott includes a planner. This planner, described in detail by McDermott [1992], uses a number of heuristic transformations that improve a given reac­ tive program's goal-achieving properties. We feel that it should be possible to use RFS in this transformational planner, but more work is required to demonstrate this.

There are several new architectures for the integration of plan generation and plan execution. One such archi­ tecture, RoboSoar [Laird and Rosenbloom, 1990], uses planning to resolve execution impasses, and this is simi­ lar to our view that planning is used to guide the reactor out of dead-ends defined with respect to its policy. Our results are quite different, however. RFS can be used in­ crementally, since it guarantees monotonic improvement, and no such guarantees exist for the planning component of RoboSoar. It should be easy to make the planning component of RoboSoar operate according to the three principles of RFS. If so, then RoboSoar should be able to exhibit the property of monotonic performance im­ provement. Lyons and Hendriks [1992) and Godefroid and Kabanza [1992) describe architectures for integrat­ ing planning and execution, both of which are concerned with incremental planning. Since these architectures use a projector-reactor model similar to our own, we hypoth­ esize that they can be easily extended to employ RFS.

An anytime algorithm [Dean and Boddy, 1988) is one that can be terminated and restarted at any time, where the results computed by the algorithm improve in some "well-behaved manner" as a function of time. RFS is statistically anytime, in the sense that its expected per­ formance satisfies the anytime algorithm requirements. However, the guarantee of monotonic improvement is stronger than that required of an anytime algorithm, and it is this guarantee that makes RFS usefully incremental. Boddy [1991) studies anytime algorithms in more detail.

In terms of general-purpose search, Georgeff's [1983) strategy-first search technique could be profitably inte­ grated with RFS. Strategy-first search is a technique that allows for the use of "heuristic strategies" in search con­ trol. Were we to allow a policy to return a set of opera­ tor sequences, we would be able to implement Georgeff's strategy-first search technique as an instance ofRFS. The same incremental planning result would obtain, with the only difference being the expressive power of the policy as a programming mechanism. This is an excellent area for further research.

Korf's [1990) work on RTA * was also motivated by the problem of limited computation time, based on observed drawbacks of the A* [Hart, et al., 1968) and IDA* [Korf, 1985) algorithms. As Korf noted: "a related drawback of A* and IDA* is that they must search all the way to a solution before making a commitment to even the first move in the solution." [Korf, 1990, p. 191). While RTA * is guaranteed to make locally optimal choices, it is not guaranteed to monotonically improve the performance of a plan executor. That is, RTA * cannot ensure that the prefix plans it produces over time will not adversely impact the expected performance of a system that exe­ cutes those plans. This is a natural result of the fact that RTA * was not designed to find plans for an independently competent reactor. As with the planning component of RoboSoar, however, it should be relatively easy to im­ plement a version of RTA * that adheres to the three prin­ ciples of RFS. With this done, RTA * would also exhibit the monotonic performance improvement property.

7 Summary

Reaction-First Search is a general incremental planning algorithm that produces partial plans for execution by an independently competent reactor. The expected perfor­ mance of RFS is to monotonically increase the reactor's goal satisfaction probability as a function of time spent planning. To our knowledge, RFS is the first planning al­ gorithm that guarantees this property. While the prop­ erty is statistical, this itself is rather interesting, since few average-case guarantees are made regarding plan­ ning algorithms. We have empirically supported our hy­ pothesis that there can be significant value associated with the early release of prefix plans. Our experiments demonstrated that the prefix plans found by RFS improve the reactor's performance by helping it avoid dead-ends defined with respect to its policy.

Acknowledgments

Discussions with John Allen, Peter Cheeseman, Phil Laird, and Drew McDermott have been extremely use­ ful. We would like to thank Peter Friedland, Rich Keller, Amy Lansky, Nathalie Mathe, Andrew Philpot, David Thompson, and Richard Washington for helpful com­ ments on a draft of this paper. Thanks also to Carlos Salinas for help with the PostScript figures.