A Reactive Planner for a Model-based Executive

A Reactive Planner for a Model-based Executive

Brian C. Williams

Computational Sciences Division MS 269-2 NASA Ames Research Center, Moffett Field, CA 94035 USA

E-mail: williams(Dptolemy. arc. nasa. gov

Abstract

A new generation of reactive, model-based executives are emerging that make extensive use of component­ based declarative models to analyze anomalous situ­ ations and generate novel sequences for the internal control of complex autonomous systems. Burton, a generative, model-based planner offers a core element that bridges the gap between current and target states within the reactive loop. Burton is a sound, complete, reactive planner that generates a single control action of a valid plan in average case constant time, and com­ pensates for anomalies at every step. Burton will not generate irreversible, potentially damaging sequences, except to effect repairs. We present model compila­ tion, causal analysis, and online policy construction methods that are key to Burton's performance.

Conventional wisdom has largely pushed deductive reasoning out of the reactive control loop for nearly a decade. However, recent search for the surprisingly elusive, hard satisfiability problem foretells a healthy return to deductive methods(Williams & Nayak 1996b; Kautz & Selman 1996) based on RISC-like search en­ gines. This paper pushes this perspective down to re­ active time scales, reporting on a model-based plan­ ner, called Burton, that is at the core of a model­ based executive's reactive control loop. By solving the NP hard component of deductive problems at compile time, Burton exploits the expressiveness of NP hard methods, without assuming the risk of falling off the elusive cliff.

Burton's parent model-based executive is particu­ larly well suited to controlling the complex internal be­ haviors of large scale autonomous systems, we call im­ mobile robots (Williams & Nayak 1996a) . What distin­ guishes this executive is its ability to sense and control hidden state variables indirectly, and the use of compo­ nent models to identify these novel interaction paths. A marriage between this model-based executive and a classical, method-based executive provides a hybrid with an expressive scripting language and an extensive capability to generate novel responses to anomalous

P. Pandurang Nayak

Recom Technologies

NASA Ames Research Center, MS 269-2 Moffett Field, CA 94035 USA

E-mail: nayak(Dptolemy . arc . nasa. gov

situations. Significant parts of this hybrid executive will be demonstrated in late 1998 on NASA's Deep Space One autonomous spacecraft (Pell et al. 1997) .

The paper begins with an example from the space­ craft domain, and then introduces our concurrent tran­ sition system modeling formalism. Next we introduce model-based execution as identifying a current state (mode identification), generating an optimal target state (mode reconfiguration), and generating a con­ trol action to move towards the target (model-based reactive planning) . The rest of the paper presents the Burton model-based reactive planner through a series of domain restrictions, model compilation, policy con­ struction and online planning algorithms.

Example: autonomous spacecraft

First consider the underlying task. Figure 1 shows an idealized schematic of the main engine subsystem of the Cassini spacecraft and valve driver circuitry. It consists of a helium tank, two propellant tanks, two main engines, regulators, latch valves, and pyro valves. The helium tank pressurizes the propellant tanks. When propellant paths to a main engine are open, the propellants flow into the engine and produce thrust. The pyro valves are used to isolate parts of the engine. They can open or close only once.

Valves are controlled by valve drivers. Commands to the driver are sent via a control unit (VDECU). The driver and VDECU can be on or off, and recoverably or permanently failed. A recoverably failed component can be repaired by resetting it. A valve's state changes as a result of a command only if the corresponding driver and VDECU are on and healthy.

In planning an orbit insertion maneuver, a high-level deliberative planner, e.g., (Muscettola 1994), gener­ ates a sequence of behavior goals, such as producing thrust. The reactive executive achieves this goal using its component models to generate control sequences that open the relevant set of valves leading to a main engine. Valves are commanded open indirectly, and the executive must ensure that the control unit and driver leading to the valve are on and healthy prior to com­ manding the valve. Generating sequences to handle a breadth of novel situations requires extensive reason­ ing about physical processes as well as state changing actions. Doing this reactively is the focus of this paper.

Concurrent transition systems

We start by reviewing the propositional, concurrent transition system formalism introduced in (Williams & Nayak 1996b), which represents normal operation, failure, and repair of real-time software and hardware. A transition system S is a tuple (II,~' T). II is a set of variables, each ranging over a finite domain. II is partitioned into the set rr ·. of state variables, the set lie of control variables, and the set lid of dependent variables. ~ is the set of feasible assignments to vari­ ables in II. Each element of a state variable's domain is categorized nominal or failure. · Control variable values are determined exogenously by a controller. A state is an assignment to each variable in II ·. The set ~., the projection of ~ on variables in II., is the set of all feasible states. T is a finite set of transitions. Each transition T E T is a function T : ~ -+ ~. , i.e., r(o-) is the state obtained by applying transition T to any feasible assignment a. The transition Tn E T models the system's nominal behavior, while all other tran­ sitions model failures. A repair action is a transition that takes a state variable from a failure to nominal value.

A trajectory is a (finite or infinite) sequence offeasi­ ble states S : 80 , s1 , .. . such that for each s; there is a feasible assignment a; E ~which agrees with s; on assignments to variables in II. and s;+l = r(a;) for some T E T. A trajectory that involves only the nominal transition T n is called a nominal trajectory. A simple trajectory does not repeat any state.

A transition system is specified using a restricted subset of propositional temporal logic that uses the 0 operator. The propositions in this logic are all of the form y = e, where y is a variable and e is an element in y's domain. 0 is the next operator denoting truth in the next state of a trajectory.

We specify the set ~ of feasible assignments by a propositional formula pr;, i.e., ~ is the set of all vari­ able assignments that satisfy PE. A transition T of S is specified by a formula Pr, which is a conjunction of transition specifications Pr, of the form <I>; => 0y; = e;, where <I>; is a propositional formula and y; is a state variable. A state Sk can follow state Sj using T if there is an assignment ai E ~ that agrees with Sj such that for all Pr, if ai satisfies <I>; then Sk assigns e; to y; .

Example 1 Driver 1 has a state variable, dr1 , and two dependent variables cmdin1 and cmdout1. The domain of dr1 is {on, off,resettable,failed}, cmdin1 is {on, off, reset, open, close, none}, and cmdout1 is {open, close, none} . dr1 's transition diagram is:

which is specified by formulae like:

which describes the effect of resetting a driver. The driver's feasible states are specified by formulae like:

The VDECU has control input drcmdin1, whose value is propagated to cmdin1 when the VDECU is on:

(vdecu1 = onl\drcmdin1 =reset) => (cmdin1 =reset)

Opening the valve is achieved by turning the VDECU and driver on, and then setting control input drcmdin1 to open. The driver's output cmdouh is used to control the valve's state transitions.

Model-based reactive execution

We view an autonomous system as a high-level plan­ ner coupled to a low-level reactive control system. The planner generates a sequence of configuration goals, each a physical behavior like "achieve thrust." The reactive control system evolves along a trajectory that achieves these configuration goals. Reactive control is achieved using a reactive executive that generates a sequence of control actions, based on knowledge of the current state and configuration goal. A control action is an assignment to each control variable in lie, for example, corresponding to closing a switch or sending a reset message across a bus. The current state is (partially) observable through a set of vari­ ables Il0 ~ IT8 U lid, corresponding to sensors, and an observation is an assignment to each variable in Il0 ·

Definition 1 A reactive control system is a tuple (S, e, C), where Sis a transition system, e is the ini­ tial state of S, and C is a reactive executive. C takes as input the initial state e' a sequence 'Y : go' g1' ... of propositional formulae called goal configurations, and a sequence of observations o : o0 , o1 , ·· · , and in­ crementally generates a sequence of control actions p, : P,o, p,1 , . . . so that S evolves along a trajectory S: So,s1,··· that satisfies: (a) So is 6; (b) for each Si there is an assignment ai E :E that agrees with si, oi, and /.Li on the corresponding subsets of variables; and (c) if Si+l is the result of a nominal transition from Si under P,i, i.e. , Si+l = Tn(ai), then either Si+l satisfies gi or (si, si+1) is the prefix of a simple nominal trajectory that ends in a state s i that satisfies gi.

The idea is that a reactive executive continually tries to transition the system toward a state that satisfies the desired goals. It is reactive in the sense that it reacts immediately to changes in goals and to failures, i.e., each control action /.Li is incrementally generated using the new information, Oi and gi, in each state.

A model-based executive, uses a specification of a transition system to determine the desired control se­ quence in three stages- mode identification (MI), mode reconfiguration (MR) and model-based reactive plan­ ning (MRP). MI and MR set up the planning prob­ lem, identifying initial and target states, while MRP reactively generates a plan solution. More specifically, MI incrementally generates the set of most likely plant trajectories consistent with the plant transition model and the sequence of observations and control actions. This is maintained as a set of most likely current states. MR uses a plant transition model and the most likely current state generated by MI to determine a reachable target state that satisfies the goal configuration. MRP then generates the first action in a control sequence for moving from the most likely current state to the target state. After that action is performed MI confirms that the intended next state is achieved. MI and MR are discussed in (Williams & Nayak 1996b). This paper focuses on MRP.

A key decision underlying our model-based executive is the focus on the most likely trajectory generated by MI. The difficulty with the more conservative strategy of considering a single control sequence that covers a set of likely states (Williams & Nayak 1996b) is that the different states will frequently require different con­ trol sequences. While utility theory can be used to select between different control sequences for one that maximizes success (Friedrich & Nejdl1992), the cost of generating multiple states and control sequences works against our goal of building a fast reactive executive.

The greedy approach introduces risk: the control ac­ tion appropriate for the most likely trajectory may be inappropriate, or worse still damaging, if the actual state were otherwise. FUrthermore, the reactive focus of the MRP precludes extensive deliberation on the long-term consequences of actions, thus leaving open the possibility that control actions, while not outright harmful, may degrade the system's capabilities. For example, firing a pyro valve is an irreversible action that forever cuts off access to parts of the propulsion system. Such actions should be taken after due delib­ eration by the high-level planner or human operators. Hence, fundamental to the reliability of our approach is the following requirement:

Requirement 1 MRP considers only reversible con­ trol actions, unless the only effect is to repair failures. 1

Model-based reactive planning

The definition of MRP (Burton) follows from Defini­ tion 1 and the functions of MI and MR:

Definition 2 A model-based reactive planner (MRP) takes as input a specification of a transition system S, a most likely initial state Si (from MI), and a lowest cost target state ti (from MR) that satisfies goal gi . The MRP generates a control action /.Li such that for any assignment ai E :E that agrees with Si and P,i, the state Si+l = Tn(ai) is either the target state ti or (si, SiH) is the prefix of a simple nominal trajectory that ends in ti.

Given the similarity of transitions and STRIPS op­ erators, Burton's problem appears similar to STRIPS planning (Weld 1994). However, the critical differ­ ence is the distinction between classical planning and machine control. The primitive control action in a STRIPS plan is to invoke a plan operator, which di­ rectly modifies the state. Model-based planners, on the other hand, exert control by establishing values for control variables, which interact with internal state variables indirectly through co-temporal, physical in­ teractions (PE). This extension adds enormous expres­ sivity to the planner.

1 While repairing a failure is irreversible, it is important to allow a reactive executive to repair failures.

This extension equally adds to the challenge of achieving reactivity. We eliminate intractability at modeling time through an automated model compi­ lation method and four simple modeling requirements.

Compiling transition models

Recall that a transition is specified by a conjunction of formulae q,i => Qy; = e;. What distinguishes this from a simple transition is that the formula q,i can con­ tain propositions involving dependent variables that are not directly controllable, but depend on control variables through the arbitrary propositional formulae of PE. This introduces a potential computational cliff.

To simplify the transition system, we first compile away all dependent variables and corresponding in­ teractions of PE, by generating all prime implicants of Qy; = e; that do not contain dependent variables. More precisely, an implicant of Qy; = e; is a conjunc­ tion I of propositions involving state and control vari­ ables such that the transition system specification, PE U UT TPT, entails the formula I => Qy; = e;. I is a priui'e implicant if no sub-conjunction of I is an implicant. Given that dependent variables cannot be directly controlled, either by control actions or by tran­ sitions, the prime implicants of Qy; = e; completely characterize the conditions under which Yi has the value ei in the next state. For example, one prime implicant of Qdr1 =on (from Example 1) is

dr1 = resettable 1\ vdecu1 = on 1\ drcmdin1 = reset

While prime implicant generation is NP-hard, in practice even sizable implicants can be generated very fast. For example, we use an abductive best-first search (Williams & Nayak 1996b) to generate ip1plicants from a spacecraft model consisting of over 12,000 clauses in about 40 seconds on a Spare 20. We compute these implicants at compile-time, thus avoiding the risk of falling over the computational cliff at run-time, while preserving expressivity in the modeling language.

The set of prime implicants constitutes the compiled transition specification, where each implicant specifies a transition for a single state variable. The transition specification of a single variable Yi is the set of prime implicants of Qy; = e;k, for every eik in Yi 's domain. Antecedents of transition specifications now contain only state and control variables. For a transition of Yi, each antecedent involving a state variable other than Yi is called a state condition, and each antecedent involv­ ing a control variable is called a control condition. If Yi is not in the antecedent, we replicate the transition for every assignment of Yi. The transition diagram for the driver after compilation is:

The correspondence to a STRJPS operator is straightforward: state conditions, including antecedent Yi, form preconditions; the add (delete) list contains the next (previous) value of Yi · The transition is in­ voked by asserting all control conditions.

Exploiting properties of designed systems

Albeit simpler than the original specification, these compiled transitions have a complication not found in STRIPS. STRJPS operators are explicitly invoked, one at a time. In the above, a control action can invoke more than one transition. Furthermore, a transition can occur spontaneously, and cannot be prevented, if its antecedent contains no control variables.

While arbitrary transition systems can manifest these properties, physical hardware is typically de­ signed to behave like STRJPS operators. It is usually the case that each state variable is separately com­ manded and state variables maintain their values in the absence of explicit commands. The following re­ quirement prevents spontaneous state change:

Requirement 2 Each control variable has an idling assignment, and no idling assignment appears in any transition. The antecedent of every transition includes a (non-idling) control condition.

For example, drcmdin1 has idling value none, and the prime implicant of Qdr1 = on mentioned above con­ tains the non-idling drcmdin1 = reset. Exploiting this restriction, all state changes can be prevented by assigning every control variable its idling assignment. The following additional restriction guarantees that transitions can be individually invoked:

Requirement 3 No set of control conditions of one transition is a proper subset of the control conditions of a different transition.

A single transition is invoked by asserting its control conditions, and assigning all other control variables their idle assignment. Jointly these two requirements reduce MRP to STRIPS planning.

Online component of reactive planning

Given a compiled transition system S', Burton quickly generates the first control action of a valid plan, given an initial state assignment 0 and a set of goal assign­ ments 1· 2 Burton meets five desiderata. First, it only generates non-destructive actions, i.e., an action will never undo the effects of previous actions that are still needed to achieve top-level goals. Second, Burton will not propose actions that lead to dead end plans, i. e. , it will not propose an action to achieve a subgoal when one of the sibling sub goals is unachievable. Third, Bur­ ton is complete, i.e., if a planning problem that satisfies Requirements 1-4 is solvable, then Burton will generate a plan. However, Burton is not guaranteed to gener­ ate all valid plans. Fourth, Burton ensures progress to a goal, except when execution anomalies interfere, i.e., the nominal trajectory traversed by Burton for a fixed target is loop free. Fifth, Burton operates at re­ active time scales-its average runtime complexity is constant. This speed is essential to providing a model­ based executive with response times comparable to tra­ ditional executives (Firby 1987; Simmons 1994) .

Burton avoids runtime search, requires no algo­ rithms for threat detection, and expends no effort de­ termining future actions or planning for subgoals that are not supported by the first action. Traditional plan­ ners need such mechanisms to avoid destructive actions and deadend plans (Weld 1994) . Burton accomplishes this speedup by exploiting the requirement, stated ear­ lier, that all actions except repairs be !eversible, and by exploiting certain topological properties of compo­ nent connectivity that frequently occur in designed sys­ tems. The development of Burton's basic sequencing algorithm is the topic of the next three subsections, with the introduction of repair actions introduced in the fourth subsection. Finally, to achieve average case constant time Burton precompiles plans into reactive policies, without requiring enormous amounts of stor­ age. This is the topic of the fifth subsection.

Exploiting causality

A major leverage point comes from exploiting the topological properties of component connectivity. The input/output connections of the compiled plant fre­ quently do not contain feedback loops. When they do occur they are typically local and can easily be elimi­ nated through careful modeling. To be precise:

Definition 3 A causal graph Q for (compiled) transi­ tion system S is a directed graph whose vertices are the state variables of S. Q contains an edge from v 1 to v2 if v1 occurs in the antecedent of one of v2's transitions.

Requirement 4 The causal graph must be acyclic.

2 Here on, each goal is a target variable assignment gen­ erated by MR, not the configuration goal input to MR.

The causal graph for the valve circuitry follows the schematic, and is acyclic.

The basic idea underlying Burton is to solve a con­ junction of goals by working "upstream" along the acyclic causal graph, i.e., it completes a conjunct Yi = eik before conjunct Yi = ejk when Yi precedes Yi in the causal graph. For example, suppose the ini­ tial state has vlv1 = closed 1\ dr1 = off, and the target has vlv1 = open 1\ dr1 = off. Burton first focuses on vlv1 = open since the valve is downstream of the driver. As we will see, this upstream progression guar­ antees that Burton generates non-destructive actions without an explicit threat detection mechanism.

Burton generates a next control action with the Nex­ tAction function, shown below. This takes an initial state 0, a (partial) target state 1 (sorted by topological number as discussed later), a compiled transition sys­ tem S' and the flag top? to indicate a top-level call. NextAction returns a next control action, Failure if no plan exists, or Success if the initial state is a tar­ get state. A control action is a partial set of control assignments. All control variables not mentioned are assigned their idle value.

Online Algorithm: NextAction(8,-y,S' ,top?)

1. Solvable Goals?: When top?= True, unless each goal g E 'Y is labeled Reversible, return Failure.
2. Select unachieved goal: Find an unachieved goal assignment with the lowest topological number. Goal y = e1 E 'Y is unachieved if it differs from y's ini­ tial assignment y = e; E 8 . If all achieved return Success.
3. Select next transition: Let ty be the transition graph in S for goal variable y. Find a path p in ty from e; to e 1 along transitions labeled Allowed. Let SC and CC be the state and control conditions of the first transition along p.

4. Enable transition: Control= NextAction(8,SC,S',False). If Control= Success then state conditions SC are already satis­ fied, return CC to effect transition. Otherwise Con­ trol contains control assignments to progress on SC. Return Control.

Line 1 tests whether or not a conjunction oftop-level goals can be achieved, as explained in the subsection after next. This involves a simple table lookup to see if each goal is labeled Reversible. Burton only intro­ duces subgoals that can be achieved, hence the test is needed at the top level only. Line 2 works upstream along the causal graph of variables selecting the next unsatisfied (sub)goal assignment to be achieved. This upstream progression is achieved by exploiting a topo­ logical ordering, as explained in the next subsection.

Line 3 takes the first step towards achieving the se­ lected goal. Given an initial assignment y = ei and a component transition system for y, a goal assign­ ment y = e 1 is achieved by traversing a path along transitions of y from ei to e f. Respecting Restriction 1, Burton only traverses transitions with reversible ef­ fects or that perform a repair. As explained in the next section, the transitions that satisfy this restriction are those labeled Allowed. Line 3 identifies the first tran­ sition along this path from ei to e 1. Line 4 subgoals on the state conditions of this first transition, which results in Burton moving further upstream. If one or more state conditions is unsatisfied then a next control action is computed in Line 4, and returned. If all state conditions are satisfied, then the transition is ready to be traversed and Line 4 returns the transition's control conditions as the next control action.

A voiding destructive actions

Burton avoids generating destructive control actions (desiderata 1) by exploiting the acyclic nature of the causal graph. The only variables needed to achieve an assignment y = e are y's ancestors in the graph. For example, turning on the driver requires use of the VDECU but not the valve. In addition, requirements 2 and 3 guarantee that invoking transitions for y and its ancestors, when performed one at a time, will not affect any other state variables.

This suggests that Burton can achieve a conjunction of goal assignments in an order that moves along the causal graph from descendants to ancestors, i.e., a goal conjunct is achieved only after conjuncts that are its descendants. For example, dr1 = off 1\ vlv1 = open is achieved by working on vlv1 = open then dr1 = off. The same ordering holds for conjunctive subgoals, that is, state conditions of required· transitions.

Destructive subgoal interaction may occur when a variable appears upstream as a subgoal to two con­ juncts. To avoid this danger subgoals are achieved in depth first order, achieving one conjum:t before start­ ing on a second. For example, dr1 = off 1\ vlv1 = open is achieved by turning on the driver, opening the valve, and finally turning the driver off. Achieving subgoals in depth first order also ensures that Burton always makes progress towards the goal (desiderata 4) .

Depth first goal progression, together with the goal ordering constraint, is sufficient to ensure non­ destructive actions. Depth first progression is imposed by Line 4 of NextAction. Line 2 imposes the order­ ing constraint without runtime .cost through topologi­ cal numbering. At compile time each state variable is given a topological number (tn), by performing a depth first search of the graph and numbering variables on the way out. For example, tn(vlv1) = 1, tn(dri) = 2, tn(vlvz) = 3, tn(drz) = 4, and tn(vdecu1) = 5. Topological numbering imposes a total ordering that satisfies the constraint tn(A) < tn(B) whenever A is a strict descendant of B in the causal graph. Hence the proper order of goal achievement for all conjunc­ tive subgoals is determined at compile time by sorting the conditions of each transition by increasing topolog­ ical number. Burton respects an upstream progression in line 2, simply by working successively through the sorted list of conditions.

A voiding deadends through reversibility

Requirement 1 stated that Burton only perform re­ versible transitions, desiderata 2 stated that Burton avoid deadend plans, that is plans with unachievable subgoals, and desiderata 3 specified completeness. To be reactive Burton must achieve these without search. Each hinges on the following lemma:

Lemma 1 A 1\ B is reachable from e by reversible transitions exactly when A and B are separately reach­ able from e by reversible transitions.

Proof: Assume without loss of generality that tn(A) < tn(B). We previously showed that if A is achieved first, it won't be disturbed while achieving B. The transi­ tions used to achieve A are reversible, hence if nothing else each variable other than A can be restored to its value in e and then B can be achieved. o

Suppose Burton has labeled as Reversible every assignment that is reachable from initial state e using Reversible transitions. By Lemma 1 a conjunction of goal assignments is achievable exactly when each con­ junct is marked Reversible. Hence Burton can deter­ mine plan achievement at runtime simply by using one table lookup per top-level goal (line 1, NextAction).

Deadend plans, hence search, are eliminated by re­ moving the possibility of unachievable subgoals. As­ sume Burton labels a transition Allowed only if its state conditions are each labeled Reversible. Then sequences of Allowed transitions between Reversible assignments contain no unachievable subgoals. These are the transitions generated by line 3 of NextAction. By lemma 1 all other sequences lead to deadends or in­ volve irreversible transitions, hence Burton generates some plan if one exists (desiderata 3). Of course Bur­ ton can't generate all plans since subgoal interleaving isn't allowed. Finally, since depth first progression gen­ erates the control sequence in order, Burton generates the first control action without wasting work on the rest of the plan, hence achieving reactivity.

The labeling of assignments and transitions is pre­ computed for compiled transition system S' with initial state e by LabelSystem, and is linear in the size of S'.

Preprocess Algorithm: LabelSystem(S',e) For each state variable y of S' in decreasing topological order:

1. For each transition Ty of y , label Ty Allowed if all its state conditions are labeled Reversible.
2. Compute the strongly connected components (SCCs) of the Allowed transitions of y .
3. Find y's initial value y = e; E e . Label each assign­ ment in the SCC of y = e; as Reversible.

LabelSystem starts at the roots of the causal graph, using topological numbering to move to a descendant only after its ancestors have been processed. Line 1 simply executes the definition of Allowed. Note when Yi is a root, none of its transitions contain state condi­ tions, and hence are trivially Allowed. Lines 2 and 3 identify Reversible assignments. An assignment y = ek can be reversibly achieved if there exists a path along Allowed transitions from initial value ei to ek and back. Equivalently, the set of y's reversible assign­ ments is the strongly connected component (SCC) of y's Allowed transition that contains ei .

For example, starting with initial value off, the SCC for the VDECU, hence its Reversible assignment set, is {off, on}, with both resettable and failed excluded. Next, the driver has Allowed transitions between on and off due to the VDECU's SCC. With initial value on, the sec for the driver is {off, on}.

Finally, note that LabelSystem is called infrequently. Actions generated by Burton only move within the SCCs of Reversible assignments, leaving the labeling unchanged. A relabeling is needed only if an exoge­ nous action or failure moves e to an assignment that was not labeled Reversible.

Failure states and repair

To dramatically expand Burton's utility we incorpo­ rate repair actions. The occurrence of failures are out­ side Burton's control, since there are no nominal tran­ sitions that lead to failure. Hence a repair sequence is irreversible, albeit essential, and thus not covered by the development thus far. We extend Burton to permit repair sequences if they minimize irreversible effects. Burton never uses a failure to achieve a goal assign­ ment if the failure is repairable. However, if it is not repairable, then Burton is allowed to exploit the com­ ponent's faulty state. For example, suppose a switch is needed to be open, and it is permanently stuck open. Since stuck-open is irrepairable but has the desired ef­ fect , Burton exploits the failure mode.

Relaxing the reversibility constraint, if a state vari­ able y is assigned a failure e 1, then Burton is permitted to traverse a sequence of allowed transitions from e 1

to a nominal assignment, when such a path exists. If only one path exists, then y's reversible assignments are defined to be those in the sec of the first nominal assignment reached along the path. For example if the driver is initially at resettable then ~t may transition to on using reset, and the sec is {off, on}. If no path exists to a nominal assignment, then the reversible as­ signments are those in the SCC that contains e 1. For example, if the driver is at failed, then the sec is simply {failed}. Although not discussed here, Burton also handles the case where multiple paths to different sees exist.

Although Burton can now traverse irreversible tran­ sitions to effect repair, none of the assignments along this trajectory, up to the selected sec can be used to satisfy a state condition or goal assignment. Hence this extension does not endanger Burton's previously discussed properties.

Generating concurrent policies

The runtime complexity of N extAction is thus far 0 ( e * m), where e is the maximum number of transitions in a single component transition system, and m is the maximum depth of the causal graph. The cost m is incurred on line 4, while subgoaling on assignments of upstream variables, and cost e is incurred on line 3, while searching for a path through transitions. Burton reduces cost to O(m) by constructing for each variable y a feasible policy 1r y. 1r y maps pairs ( ei, e 1) to the sorted conditions of the first transition along a path from ei toe 1. If y has n values, 1r y is simply an n 2 table computed in O(n *e) time, where entries for each ei are determined by computing a spanning tree directed towards e 1 that connects all values labeled Reversible by transitions labeled Allowed. Line 3 of NextAction becomes the table lookup:

The driver and valve policies are shown above (vdecu1 =on is assumed and not shown). Suppose MI identifies the initial state { dr1 = off, vlv1 = closed}

and MR provides target { vlv1 = open, dr1 = off}, in topological order. Selecting the first target as­ signment, Burton looks up vlv1 : closed -+ open, and gets { dr1 = on, drcmdin1 = open}. The first is an unsatisfied state condition, so Burton looks up { dr1 : off -+ on}, getting { drcmdin1 = on}. This control assignment is then invoked.

Burton's feasible policies are analogous to optimal policies in control theory. An important difference is that Burton constructs a set of concurrent policies, rather than a single policy for the complete state space. The latter grows exponential in the number of state variables, and is infeasible for models like the space­ craft, which contain over 80 state variables and well over 2 80 states. In contrast, the concurrent policies grow only linearly in the number of state variables.

For a fixed target and no intervening failures, Bur­ ton generates successive control actions as a depth first traversal through the policy tables. This traversal maps out a subgoal tree, and Burton maintains an in­ dex into this tree during successive calls. To generate a sequence Burton traverses each tree edge exactly twice and generates one control action per vertex. Since the number of edges in a tree is bounded by the number of vertices, the amortized average case complexity of gen­ erating each control action is a constant. Desiderata 5, reactivity, is achieved.

Related work and conclusions

Burton combines causal models used in model-based reasoning with state transitions used in planning. Other researchers have combined model-based diagno­ sis with planning, primarily to generate repair plans (Friedrich & Nejdl 1992; Sun & Weld 1993). The main difference is that these systems include a STRIPS (rather than model-based) planning component with utility-theoretic measures for selecting amongst alter­ nate plans. Their computational complexity make them inapplicable for on-board reactive execution.

Burton differs from traditional STRIPS planners (Weld 1994) in that plan operators (transitions) are generated by a compilation process from an underlying causal model of the system that includes both within and across state constraints (PE and the Pr, respec­ tively). Furthermore, the compiled transition system is a specialized version of the general planning problem that Burton solves by a worst-case linear time, aver­ age case constant time algorithm. In contrast, general planning is PSPACE-complete. Korf (1987) defines a set of subgoals to be serializable if they can be solved in order without ever violating a subgoal solved earlier in the order. The requirement that the causal graph is acyclic ensures that Burton is only presented serializable sets of subgoals.

Finally, traditional reactive executives (Firby 1987; Simmons 1994) differ from Burton's model-based ex­ ecutive in that the former use explicitly scripted pro­ cedures to provide reactive execution, while the lat­ ter uses deductive reasoning from a causal model that combines an off-line compilation phase with an on-line policy generation phase. Other differences include the fact that traditional executives provide a richer set of control structures such as parallel execution, while Burton's executive provides a more sophisticated diag­ nosis and monitoring capability embodied in MI.

In summary, Burton is a sound and complete gen­ erative planner that uses expressive transition system models to provide the reactive sequencing capability of a model-based executive. It exploits off-line model compilation and the topological properties of compo­ nent connectivity to incrementally generate control ac­ tions in average case constant time. These control ac­ twns are guaranteed to be non-destructive, while en­ suring progress towards the goal and avoiding deadend plans.

Acknowledgements: We would like to thank Jim Kurien and Dan Weld for helpful comments on the paper.