Our basic model for replanning is bottom-up in nature, being driven by the activities of the executor. The executor is responsible for recognizing replannable failure situations, requesting new plans from the planner, and finally implementing the new plan.
We developed a transformational approach to replanning where the activities in the original plan are left unmodified when possible. In particular, the planner modifies the failed plan during replanning rather than generate a completely new plan, and the executor continues execution of threads in the original plan that are unaffected by the failure while replanning takes place. This approach contrasts with many existing methods which simply abort execution of the old plan upon failure, then begin execution of a new plan. The transformational approach has the advantage of preserving undisturbed those activities in progress that remain part of the new plan. This property is essential in domains where it is infeasible to halt all execution activities while replanning some portion of the overall plan.
An application PRS agent initiates the replanning process upon detection of a failure that it recognizes as replannable ( describes the criteria for replannability). All requests for replanning are forwarded to a special PRS agent named Replanner which performs all necessary communication with SIPE-2, thus enabling the agent that requested replanning to continue execution of those parts of the plan that are unaffected by this failure. The Replanner agent is identical to other PRS agents; its specialized behavior results from the specific set of ACTs that it executes.
The message sent to the Replanner agent indicates the name of the application agent requesting the replanning, a unique identifier for this particular failure episode, the plan being executed, the failed goal, and the execution front. The execution front is a list of the nodes last successfully executed on each parallel thread of the plan. The Replanner agent also sends SIPE-2 relevant information from its database that characterizes the current world state. Without such updates, SIPE-2 could only generate plans for the original state rather than the state in which the failure occurred, since it does not monitor the world during execution. The Replanner agent then awaits a response. In general, SIPE-2 will reply with a new plan that addresses the failure. The new plan is forwarded to the PRS agent that requested the replanning, which then integrates it with its current activities. If no new plan can be generated for the overall goal, the Replanner notifies the requesting PRS agent, which in turn terminates its execution of the original plan.
When issued a replanning request, SIPE-2 responds by trying to modify the failed plan rather than producing a new plan from scratch. Doing so is often more efficient, since only limited changes are generally needed to fix the original plan. SIPE-2 begins by simulating the original plan through the execution front, then comparing its expected world state with the actual state provided by PRS-CL. SIPE-2 collects those formulae not expected to be true and determines how they affect the failed plan. The plan is modified to eliminate any problems by deleting unnecessary subplans and inserting new goals (as described in ). The planner ensures that the future consequences of the new plan do not interfere with the still-active execution threads.
One of the key technical difficulties in developing the replanning capability was integrating the revised plan with the current activities of the executor. This problem is further complicated for asynchronous planning, since execution of the original plan continues while the new plan is generated. To this end, SIPE-2 provides PRS-CL with both a new plan and a node map. The node map is a partial mapping from nodes in the original plan that have been changed or removed to nodes in the new plan. The node-map encodes sufficient information for PRS-CL to transform its current activities during transfer of control to the new plan. Actions/subgoals being executed from nodes that are not in the node map simply continue execution. For nodes mapped by the node map, PRS-CL aborts their associated activities, and begins execution at the node in the new plan specified by the node map. The transformational approach required the development of a number of complex routines for manipulating the run-time activities of PRS-CL.