Robust Periodic Planning and Execution for Autonomous Spacecraft

1 Introduction

We are developing the first on-board AI system to con­ trol an actual spacecraft. The mission, Deep Space One (DS-1), is the first in NASA's New Millennium Program (NMP), an aggressive series of technology demonstra­ tions intended to push Space Exploration into the 21st century. DS-1 will launch in mid-1998 and will navi­ gate and fly by asteroids and comets, taking pictures and sending back information to scientists on Earth. One key technology to be demonstrated is spacecraft autonomy, including on-board planning and plan execution. The spacecraft will spend long periods without the possibil­ ity of communication with ground operations staff and will, in fact, plan how and when it will communicate back to Earth. It must maintain its safety and achieve high-level goals, when possible, even in the presence of hardware faults and other unexpected events.

*This paper describes work performed at the Jet Propul­ sion Laboratory, California Institute of Technology, un­ der contract from the National Aeronautics and Space Administration.

tRecom Technologies, NASA Ames Research Center, MS 269/2, Moffett Field, CA 94035.

tcaelum Research, NASA Ames Research Center, MS 269/2, Moffett Field, CA 94035.

§Jet Propulsion Laboratory, California Institute of Tech­ nology, 4800 Oak Grove Drive, Pasadena, CA 91109.

This paper describes our approach to planning and plan execution in the context of spacecraft autonomy. Our approach is being implemented as part of the New Millennium Remote Agent (NMRA) architecture [Pellet al., 1997]. This architecture integrates traditional real­ time monitoring and control with constraint-based plan­ ning and scheduling [Muscettola, 1994], robust multi­ threaded execution [Gat, 1996], and model-based diag­ nosis and reconfiguration [Williams & Nayak, 1996].

The paper is organized as follows. Section 2 discusses the spacecraft domain and requirements which influence our design. Section 3 describes our approach to planning, execution, and robustness, and illustrates the top-level loop of our system. Section 4 addresses the issues in­ volved in generating plans to support robust execution, and Section 5 shows how such plans are executed. We then consider related work and conclude.

2 Domain and Requirements

The autonomous spacecraft domain presents a number of challenges for planning and plan execution. Many de­ vices and systems must be controlled, leading to multiple threads of complex activity. These concurrent processes must be coordinated to control for negative interactions, such as vibrations of the thruster system violating stabil­ ity requirements of the camera. Also, activities may have precise real-time constraints, such as taking a picture of an asteroid during a narrow window of observability.

Virtually all resources on spacecraft are limited and carefully budgeted. The system must ensure that they are allocated effectively to goal-achievement. Some re­ sources, like solar panel-generated power, are renewable but limited. Others, such as total propellant, are fi­ nite and must be budgeted across the entire mission.

The planner reasons about resource usage in generating plans, but because of run-time uncertainty the resource constraints must also be enforced as part of execution.

The planner and plan execution system must reason about and interact with external agents and processes, such as the on-board navigation system and the attitude controller. These external agents can provide some infor­ mation at plan time and can achieve tasks and provide more information at run-time but are never fully control­ lable or predictable. For example, the attitude controller can provide estimates of turn durations at plan time, but the completion of turns during execution is not con­ trollable and can only be observed. Plans must express compatibilities among activities, and the plan execution system must synchronize these activities at run-time.

In addition, planning and the information necessary to generate plans are also limited resources. Because of the limited on-board processing capabilities of the space­ craft, the planner must share the CPU with other critical computation tasks such as the execution engine, the real­ time control loops and the fault detection, isolation and recovery system. While the planner generates a plan, the spacecraft must continue to operate. Moreover, the plan often contains critical tasks whose execution can­ not be interrupted in order to install newly generated plans. Thus inserting a planning activity means many other activities must be suspended or postponed. Since planning is expensive, plan failure is costly. Thus plan execution must be robust in the face of a wide variety of hardware faults and delays.

3 Approach

Our approach separates an extensive, deliberative plan­ ning phase from the reactive execution phase, executing infrequently generated plans over extended time peri­ ods. How frequently and how far in advance the system should plan is constrained by several factors, including uncertainty about the results of execution. For example, uncertainty about how much thrust has accumulated af­ ter a thrusting maneuver means the system can't reliably plan how many thrusts will be needed to reach the tar­ get, thus reducing how far in advance it is productive to plan such thrusting activities. While uncertainty moti­ vates frequent planning with short scheduling horizons, the cost of planning motivates plans with long horizons.

In our approach the generation of the next plan is ex­ plicitly represented in the current plan as a task. By considering the costs and constraints of planning, the planner automatically optimizes future planning activi­ ties. When the executive reaches this task in the current scheduling horizon, it asks the planner to generate a plan for the next scheduling horizon while it continues to exe­ cute the activities remaining in the current plan. When the executive reaches the end of the current horizon, the plan for the next horizon will be ready and the executive will then install it and continue execution seamlessly.

Ideally, we would like to have the planner represent the spacecraft at the same level of detail as the execu­ tive. This approach is taken by [Bresina et al., 1996], and by [Levinson, 1994]. The approach, when feasible, has a number of benefits. First, it enables the planner to simulate the detailed functioning of the executive un­ der various conditions of uncertainty, and to produce a plan which has contingencies (branches) providing quick responses for important execution outcomes. Second, it enables the use of one language rather than two for expressing action knowledge, which simplifies knowledge engineering and helps maintain consistency of interfaces. Third, it enables the planner to monitor execution in progress and project the likely course of actions, and then provide plan refinements which can be patched di­ rectly into the currently executing plan.

Unfortunately, in our domain this single representa­ tion approach is not practical because the complexity of interactions at the detailed level of execution would make planning combinatorially intractable. Thus, we have found it necessary to make the planner operate on a more abstract model of the domain. Examples of ab­ stractions are:

• hiding details of subsystem interactions controlled by the executive
• merging a set of detailed component states into abstract states
• not modeling certain subsystems
• using conservative resource and timing estimates

These simplifications have several consequences which impact our design. One important consequence is that the planner can no longer model or predict intermediate execution states. Since the executive is managing mul­ tiple concurrent activities at a level of detail below the planner's visibility, it is difficult to provide a well-defined initial state as input to the infrequent planning process. Also, a newly generated plan may be invalidated by exe­ cution activities that occur during or even after planning but prior to execution of the new plan, since the initial conditions of that plan may no longer be consistent with the state of the spacecraft.

We address the problem of generating initial states for the next planning round differently depending on the status of the currently-executing plan. Plans normally include an activity to plan for the next horizon. At this point, the executive sends to the planner the current plan in its entirety, with annotations for the decisions that were made so far in executing it. The current plan serves as its own prediction of the future at the level of abstraction required by the planner. Thus, all the planner has to do is extend the plan to address the goals of the next planning horizon and return the result to the executive. The executive must then merge the extended plan with its current representation of the existing plan. The net result is that, from the executive's perspective, executing multiple chained plans is virtually the same as executing one long plan. This has the useful consequence that it enables the executive to engage in activities which span multiple planning horizons (such as a 3-month long engine burn) without interrupting them.

In the event of plan failure, the executive knows how to enter a stable state (called a standby mode) prior to invoking the planner, from which it generates a descrip­ tion of the resulting state in the abstract language un­ derstood by the planner. Note that establishing standby modes following plan failure is a costly activity, as it causes us to interrupt the ongoing planned activities and lose important opportunities. For example, a plan fail­ ure causing us to enter standby rriode during the comet encounter would cause loss of all the encounter science, as there is no time to re-plan before the comet is out of sight. Such concerns motivate a strong desire for plan robustness, in which the plans contain enough flexibility, and the executive has the capability, to continue execut­ ing the plan under a wide range of execution outcomes.

4 Planning

A principal goal of the NMRA is to enable a new gener­ ation of spacecraft that can carry out complete, nominal missions without any communication from ground. This is a great departure from previous and current missions (such as Voyager, Galileo or Cassini) which rely on fre­ quent and extensive communications from ground. In traditional missions, ground operations routinely uplink detailed command sequences to be executed during sub­ sequent mission phases. Such communications require costly resources such as the Deep Space Network, which makes them very expensive. Uplink independence is par­ ticularly important for missions that require fast reaction times (as it is the case for autonomous rovers, comet lan­ ders and other remote explorers); in this case detailed ground-based control is infeasible due to long communi­ cation lags. In case of loss of uplink capabilities, previous spacecraft could carry out a critical sequence of com­ mands stored on board before launch. However, these sequences were greatly simplified when compared to the uplinked sequences and could only carry out a small frac­ tion of all mission goals.

Mission Manager

NMRA is launched with a pre-defined "mission profile" that contains a list of all nominal goals to be achieved during the mission. The detailed sequence of commands to achieve such goals, however, is not pre-stored but is generated on board by the planner. A special module of the planner, the Mission Manager, determines the goals that need to be achieved in the next scheduling horizon (typically 2 weeks long) , extracts them from the mis­ sion profile and combines them with · the initial space­ craft state as determined by the executive. The result is a specific planning problem that, once solved, yields detailed execution commands. This decomposition into long-range mission planning and shorter-term detailed planning enables NMRA to undertake an extended di­ verse mission with minimal human intervention.

Requirements for Robust Execution

The NMRA must be able to respond to unexpected events during plan execution without having to plan the response. Although it is sometimes necessary to re-plan, this should not be the only option. Many situations re­ quire responses that cannot be made quickly enough if the NMRA has to plan them.

The executive must be able to react to events in such a way that the rest of the plan is still valid. To support this, the plan must be flexible enough to tolerate both unexpected events and the executive's responses without breaking. This flexibility is achieved by (1) choosing an appropriate level of abstraction for the activities and (2) generating plans in which the activities have flexible start and end times.

The abstraction level of the activities in the plan must be chosen carefully. If the activities are at too fine a level of granularity, then the plan will impose too many con­ straints on the behavior of the executive, making plan execution more fragile. However, if the granularity is too coarse, then there may be interactions among the sub-actions of activities that the planner cannot rea­ son about. In DSl, activities are abstracted to the level where there are no interactions among their sub­ activities. This level allows the planner to resolve all of the global interactions without getting into details that would over-constrain the executive.

The other mechanism by which the executive can re­ spond to events without breaking the plan is having ac­ tivities with flexible start and end times. Plans in DSl consist of temporal sequences of activities. Each activity has an earliest start time, a latest start time, an earli­ est end time, and latest end time. The planner uses a least commitment approach, constricting the start and end times only when absolutely necessary. Any flexibil­ ity remaining at the end of planning is retained in the plan. This flexibility is used by the executive to adjust the start and end times of activities as needed. For ex­ ample, if the engine does not start on the first try, the executive can try a few more times. To make time for these extra attempts, the end time is moved ahead, but not beyond the latest end time.

Changing the start or end time of an activity may also affect other activities in the plan. For example, if the spacecraft must take science data five minutes after shut­ ting down the engine, then changing the end time of the engine firing activity will change the start time of the take science data activity. To make the changes, the executive must know about the temporal constraint be­ tween the fire engine activity and th~ take science data activity. The plan therefore contains all of the tem­ poral constraints among the activities.

Although the planner is typically enabled to leave flex­ ibility in the activity start and end times because the times are under-constrained, it is sometimes required to provide such flexibility in order to operate the space­ craft successfully. For example, when the engine is com­ manded to turn on, it goes through a warm up proce­ dure and turns itself on. The warm up procedure can take up to ten minutes, but the actual warm up time is not known at plan time. It is not known until the engine actually turns on. We currently handle such cases by providing enough time in activities to handle worst-case outcomes, although we are developing a method to plan explicitly about execution-time uncertainty.

5 Execution

From the point of view of the NMRA executive, a plan is a set of time-lines. Timelines consists of a linear se­ quence of tokens, each of which represents an activity which should be taking place during a defined temporal period. A token has a start and end window, a set of pre- and post-constraints. The start arid end windows are intervals in absolute time during which the token must start and end. The pre- and post-constraints de­ scribe dependencies with respect to the starts and ends of tokens on other time-lines.

There are three different types of pre- and post­ constraints: before, after, and meets. The semantics of these constraints is fairly straightforward. A before constraint specifies that the start of a token must come before the start of another token. An after constraint specifies that the end of a token must come after the end of another token. The amount of time that may elapse between these two related events is specified as an interval. A meets-constraint specifies that the start (end) of a token must coincide with the start (end) of another token.

Issues

Plan execution would be relatively straightforward were it not for the fact that different token types have different execution semantics. In particular, there are different ways of determining whether or not a particular activity has ended. Some activities are brought to an end by the physics of the environment or the control system

(e.g. turns) while others are brought to an end simply by meeting all its internal plan constraints (e.g. the periods of constant-attitude pointing between turns).

The situation is further complicated by the fact that a naive operationalization of these constraints leads to deadlock. Consider a constant-pointing token A fol­ lowed by a turn token B. Token A (waiting for the turn) should end whenever token B (the turn) is eligible to start. However, B is constrained by the planner to fol­ low A, and so B is not eligible to start until A ends. Thus, A can never end, and B can never start.

Another issue is that some tokens don't achieve their intended post-conditions until some time after they have started. For example, consider a time-line for a device containing a token A of type device-off followed by token B of type device-on. The intent here is that the executive should turn the device on at the junction be­ tween A and B, but this cannot be done instantaneously. Thus, a token on another time-line, constrained to start after B, may fail if it depends upon the device being on, since the device may not in fact be turned on until some time after B starts. One possible solution to this problem is to change the planner model so that it gener­ ates a plan that includes an intermediate token of type device-turning-on, but this can significantly increase the size of the planner's search space, and hence the time and resources required to generate a plan.

To solve these problems, we separate the execution of a token into three stages: startup, steady-state, and ending. The startup stage performs actions to achieve the conditions that the planner intends the token to rep­ resent. The steady-state stage monitors and maintains these conditions (or signals failure if the conditions can­ not be maintained). The ending stage allows the token to perform cleanup actions before releasing control to the next token on the time-line. Tokens may have null ac­ tions in one or more stages. The algorithm for executing a token in this three-phase framework is as follows:

1. Wait for the beginning of the token's start window.
2. In parallel
3. (a) wait for token's pre-constraints to be true, and
4. (b) check that the end of the start window has not passed. If it has, signal a failure.
5. Signal that the token has started.
6. Execute the achieve-portion of the token.
7. Spawn the maintain-portion of the token as a parallel task.
8. Wait for the start of the token's end window.
9. Wait for the token's post-conditions to be true.
10. Wait for the pre-conditions of the next token to be true, except those that refer to the end of this token.

1. Stop the maintain thread spawned in step 5, and execute the cleanup-portion of the token
2. Check that the end of the end window has not passed. If it has, signal a failure. Otherwise, sig­ nal that this token has ended.

This algorithm allows all the token types to be exe­ cuted within a uniform framework.

6 Related Work

NMRA is one of the first systems to integrate closed-loop planning and execution of concurrent temporal plans. It is also the first autonomous system that will be able to achieve a sustained, multi-stage, multi-year mission without communication or guidance from earth.

Bresina et al. (1996) describe a temporal planner and executive for the autonomous telescope domain. Their approach uses a single action representation whereas ours uses an abstract planning language, but their plan representation shares with ours flexibility and uncer­ tainty about start and finish times of activities. How­ ever, their approach is currently restricted to single re­ source domains with no concurrency.

Drabble (1993) describes the EXCALIBUR system, which performs closed-loop planning and execution us­ ing qualitative domain models to monitor plan execution and to generate predicted initial states for planning after execution failures. The "kitchen" domain involved con­ current temporal plans, although it was simplified and did not require robust reactions during execution.

Currie & Tate (1991) describe the 0-Plan planning system, which when combined with a temporal scheduler can produce rich concurrent temporal plans. Reece & Tate (1994) developed an execution agent for this plan­ ner, and the combined system has been applied to many real-world problems including the military logistics do­ main. The plan repair mechanism [Drabble, Tate, & Dalton, 1996] is more sophisticated then ours, although the execution agent is weaker and does not perform execution-time task decomposition or robust execution.

The Cypress system [Wilkins et al., 1995] and the 3T system [Bonasso et al., 1996] also address the closed­ loop integration of planning and execution in the context of concurrency, although neither of these systems deals with temporal plans. It is interesting to compare how these systems differ from ours concerning the generation of execution context for the planner and the integration of new planning information back into execution. Cy­ press shares the same action formalism between plan­ ning and execution. This enables the planner to watch over execution and simulate the results forward, as dis­ cussed in section 3. The planner can detect problems in advance and send back a detailed plan refinement, and the executive can replace un-executed portions of its current plan with new portions and continue running uninterrupted.

In 3T, the planner maintains such tight control over execution that it does not even send the full plan it ha.s developed. Instead, it sends directives to the executive one at a time, and the executive then responds to each directive in turn. This provides an interesting solution to the problem of keeping the planner informed about execution and also to the problem of integrating new planning information into the execution context. How­ ever, this approach is problematic in our domain as it places severe time constraints on the planner so that it can decide what to do before the executive runs out of activities, and it requires the computational and in­ formational resources to be available for planning on a continuous basis. This is a luxury we could not afford on a spacecraft, as discussed in section 3.

Other systems integrating planning and execution in real-world control systems include Guardian [Hayes­ Roth, 1995], SOAR [Tambe et al., 1995], Atlantis [Gat, 1992] and TCA [Simmons, 1990]. These systems invoke planning as a means to. answer specific questions dur­ ing execution (like whether a particular treatment would take effect in time to heal the patient, which evasive ma­ neuver will counter the opponents current attack plan, and which path to take to get to a particular room). This use of planning contrasts with our approach, in which the planner coordinates the global activity in the sys­ tem. The local approach has the advantage of making use of special-purpose planners which can be built to an­ swer narrow questions, but our global approach has the advantage of ensuring that the different activities un­ dertaken at execution will not interact harmfully. It is not clear how the local approaches can be extended to provide similar guarantees.

7 Conclusion

A growing body of work is addressing issues of robust planning and execution in the face of failures and uncer­ tainty. The Lockheed Underwater Vehicle [Ogasawara, 1991] uses decision-theoretic planning and execution to select courses of action which maximize utility. CIRCA [Musliner, Durfee, & Shin, 1993] considers a set of states, actions, and critical failures to be avoided. It then inserts a set of sense-act transitions into a real-time controller to ensure that the controller will never enter the crit­ ical failure states. Cassandra [Pryor & Collins, 1996], Buridan [Draper, Hanks, & Weld, 1994], 0-Plan [Currie & Tate, 1991] and JIC [Drummond, Bresina, & Swan­ son, 1994] all consider actions with uncertain outcomes and produce plans that enable execution-time recovery without having to take time out for replanning.

We are currently working on extending our planning approach to support such capabilities in the context of co~current temporal plans. Our present levels of robust­ ness are achieved using the complementary approach of flexible, abstract, and conservative plans which can be exploited by a smart executive.

A final distinction between NMRA and most other planning and execution systems is that our planner actu­ ally plans how and when it will plan for the next horizon. That is, it inserts a "plan next horizon" activity into the plan and plans other supporting activities around this goal. Such activities include information-gathering ac­ tivities which will be necessary before another plan can be built. The executive then achieves these activities to enable this form of planning over multiple horizons. We believe this is a necessary capability of extended agency, and one which will become of growing concern as we de­ sign autonomous agents to achieve goals unassisted over years or decades of activity.