2008

Software for Continuous Replanning During Execution

Feedback from execution of a plan is used to update the plan continuously.

Continuous Activity Scheduling Planning Execution and Replanning (CASPER) is a computer program for automated planning of interdependent activities within a system subject to requirements, constraints, and limitations on resources. Now at the prototype stage of development, CASPER was conceived to enable a robotic exploratory spacecraft to perform onboard, autonomous planning and replanning of scientific observations and other functions in response to diverse unanticipated phenomena that could include unknown or changing environmental conditions, equipment failures, and errors in mathematical models used in planning. On Earth, CASPER could be adapted to use in scheduling operations of production lines and other complex systems.

CASPER implements a concept of continuous planning integrated with execution, in contradistinction to the traditional concept of batch planning followed by execution. In traditional batch planning, time in the planned system is divided up into a number of relatively long planning horizons. When one nears the end of the current horizon, one projects what the state of the system will be at the end of execution of the current plan. The planning algorithm is then invoked with (1) a new set of goals for the next time horizon and (2) the projected end-of-execution state as the initial state for the next horizon. In this batch approach, planning is usually considered an off- line process that entails considerable computation, and there is significant delay from the instant when the planning algorithm is invoked to the instant when the algorithm issues a new plan. In the event of a disruption (caused, for example, by an equipment failure or an inaccurate projection of the initial state) it could be necessary to stop execution of the current plan and put the system in a safe reduced operational mode for a considerable amount of time until a new batch plan is generated. On the other hand, if a fortuitous event occurs (e.g., a planned activity is completed ahead of schedule), it may not be possible to take advantage of the opportunity thus created because it would take too long to respond with a new batch plan.

In traditional batch planning (see figure), a planning algorithm is presented with goals and an initial state. In CASPER, the planning algorithm is presented with a current set of goals, a current plan, a current state, and a model of the expected future state. At any time, the planning algorithm can be called upon to update the goals, current state, or planning horizon (at increments of time much smaller than those of batch planning) in response to an unexpected event or simply in response to the passage of time. The replanning cycle comprises the following steps:

1. Changes to the goals and the initial state are posted to the plan.

2. The effects of the changes are propagated through the current plan projections, and resulting conflicts (if any) are identified.

3. Iterative plan-repair subalgorithms are invoked to eliminate conflicts and make the plan appropriate for the current state and goals. It is these subalgorithms that make it possible to update the plan incrementally (nearly continuously) during execution in response to changing conditions and unforeseen events.

This work was done by Russell Knight, Steve Chien, Robert Sherwood, Gregg Rabideau, Darren Mutz, Tara Estlin, Forest Fisher, and Barbara Engelhardt of Caltech for NASA’s Jet Propulsion Laboratory. Under the Information Sciences category.

This software is available for commercial licensing. Please contact Don Hart of the California Institute of Technology at (818) 393- 3425. Refer to NPO-20972.

This Brief includes a Technical Support Package (TSP).

Software for Continous Replanning During Execution (reference NPO-20972) is currently available for download from the TSP library.

Please Login at the top of the page to download.