Plan Repair

Plan repair focuses on making minimal changes to an existing, failed plan rather than discarding it and starting from scratch. This involves identifying the specific point of failure and adjusting subsequent actions to accommodate the new world state. The core principle is incrementalism: preserving as much of the original, valid plan structure as possible to conserve computational effort and maintain plan stability. For example, if a delivery robot finds a door locked, a repair algorithm might insert a 'request key' action rather than re-planning the entire route from the warehouse.

Repair is triggered by a discrepancy between the expected state (as predicted by the plan's effects) and the observed state during execution. This requires continuous execution monitoring to detect failures such as:

• Precondition violations: An action's required conditions are not met.
• Unexpected state changes: External events alter the world independently of the agent's actions.
• Action execution failures: An action is attempted but does not produce its intended effects. The monitoring system compares sensor readings or state assertions against the plan's timeline to identify the precise moment and nature of the failure.

While often used interchangeably, replanning and plan repair represent different strategies on a spectrum. Classical replanning treats the current, unexpected state as a new initial state and invokes the full planner from scratch, guaranteeing a correct solution but at high computational cost. Plan repair is a more efficient, anytime algorithm that attempts to patch the existing plan. The choice depends on the severity of the failure, time constraints, and domain dynamics. In highly dynamic environments, the speed of repair is often critical, favoring local modifications.

This is a primary algorithmic approach where repair operations are performed directly on the plan structure itself, not by searching the state space. Common repair operators include:

• Action insertion: Adding a new action to achieve a missing precondition.
• Action reordering: Changing the sequence of actions to resolve a causal link threat or resource conflict.
• Action substitution: Replacing a failed action with a different one that achieves the same subgoal.
• Goal re-establishment: Adding actions to re-achieve a goal fact that was made true earlier but has since become false. These operators are applied iteratively until the plan is consistent and reaches the goal from the current state.

This sophisticated technique analyzes the causal structure of the plan to understand why the failure occurred. It builds a dependency graph linking actions through their preconditions and effects. When a failure is detected (e.g., a required precondition is false), the algorithm backtracks through this graph to find the culprit action whose effect was expected but did not materialize, or whose effect was unexpectedly deleted. Repair then focuses on this subgraph, minimizing changes to unrelated parts of the plan. This method is more informed than blind plan-space operators.

Robust autonomous systems often combine plan repair with contingency planning. Before execution, the planner may generate a primary plan alongside a set of expected failure modes and pre-computed repair strategies or branching points. During execution, if a monitored failure matches a predicted contingency, the corresponding repair patch can be applied instantly. This hybrid approach blends the efficiency of pre-computation with the flexibility of runtime repair, creating systems that are both robust and responsive. It is essential for domains with known, high-probability uncertainties.

The computational process of generating a sequence of actions, known as a plan, that transforms an initial state of the world into a desired goal state. It is the foundational discipline from which plan repair emerges.

• Core Problem: Given a formal description of the initial state, goal state, and possible actions, find a valid sequence.
• Contrast with Plan Repair: Automated planning typically generates a plan from scratch, while plan repair modifies an existing, failing plan.

The phase where a generated plan's sequence of actions is dispatched to actuators or simulators to physically or virtually change the state of the world. Plan repair is triggered by failures detected during execution monitoring.

• Execution Monitoring: Continuously compares the expected state (from the plan's predictions) with the observed state (from sensors).
• Failure Detection: A discrepancy between expected and observed state signals the need for repair. Common causes include action failure, exogenous events, or modeling errors.

A planning paradigm that generates conditional plans (e.g., trees or policies) specifying different future actions based on the outcomes of sensory observations made during execution. It is a proactive alternative to reactive plan repair.

• Key Structure: Plans are often conditional branches (if-else) or full policies mapping belief states to actions.
• Use Case vs. Repair: Ideal for domains with predictable uncertainty (e.g., sensor noise). Plan repair is used when uncertainty is unpredictable or the contingent plan's branches are insufficient.

Often used synonymously with plan repair, but can imply a more comprehensive approach. Strictly, replanning involves discarding the failed plan and initiating a new planning cycle from the current (unexpected) state.

• Full Replanning: Treats the current state as a new initial state and calls the planner again. Can be computationally expensive but guarantees a fresh solution.
• Contrast with Local Repair: Plan repair seeks minimal modifications (e.g., splicing in a new action sequence) to preserve the valid parts of the original plan, which is often more efficient.

The continuous process of tracking plan progress and comparing the predicted state effects of actions against the real-world observed state. It is the critical subsystem that identifies the need for plan repair.

• Components: Includes state estimation (determining the current world state) and discrepancy detection.
• Triggers: Monitors for action failures (an action's preconditions were met but its effects did not occur), unexpected state changes (exogenous events), or violated state invariants.

A class of automated planning that deals with actions having explicit durations, concurrent execution, and temporal constraints between plan events. Plan repair in temporal domains must respect these complex constraints.

• Added Complexity: Repair must adjust action start/end times and manage resource profiles, not just action ordering.
• Example: In a manufacturing schedule, if a machine breaks down, repairing the plan may involve rescheduling subsequent jobs on other machines while respecting delivery deadlines.