Plan Repair

Plan repair algorithms are incremental, meaning they reuse the computational effort and state from the previous plan rather than replanning from scratch. This is achieved through techniques like warm starts in optimization solvers or reusing the search graph from algorithms like Lifelong Planning A (LPA)**. The core mechanism involves updating only the parts of the plan graph affected by the change in the environment or task constraints, which dramatically reduces latency compared to a full replan.

The primary optimization goal is minimal perturbation—making the smallest necessary changes to restore plan feasibility or optimality. This is critical in physical systems where large, abrupt changes to agent trajectories can cause instability, waste energy, or confuse human collaborators. Metrics for perturbation include:

• Makespan Increase: Minimizing additional total time to complete all tasks.
• Path Deviation: Minimizing the sum of changes to individual agent paths.
• Task Reassignment Cost: Minimizing the cost of reassigning tasks between agents.

Effective plan repair maintains consistency with the unchanged portions of the original plan and the current world state. This involves:

• Temporal Consistency: Ensuring repaired plan segments align with the already-executed portions of the original plan and the current time.
• Spatial Consistency: Ensuring new path segments connect seamlessly with the agent's last known, physically achievable state (position, velocity).
• Resource Consistency: Respecting unchanged allocations of shared resources like charging stations or narrow corridors. Failure to maintain consistency can lead to deadlocks or infeasible commands.

Plan repair operates under real-time constraints, making anytime and interruptible properties essential. The algorithm must be able to return a feasible, if not optimal, repaired plan within a strict deadline (e.g., the next control cycle). If the deadline arrives, the best current solution is executed. This is often implemented using bounded suboptimal search (e.g., Weighted A*) or iterative optimization methods like Model Predictive Control (MPC) that solve a finite-horizon problem each cycle.

Plan repair is not a standalone process; it is tightly coupled with a continuous execution monitoring loop. This loop compares the agent's sensed state against the expected plan state to detect deviations that trigger repair. Common triggers include:

• Agent Failure: A robot breakdown or comms loss.
• Dynamic Obstacle: An unexpected person or vehicle enters the path.
• Task Change: A new high-priority order is received.
• Constraint Violation: The agent is running low on battery. The monitor classifies the severity of the deviation to decide between a local trajectory adjustment (e.g., Dynamic Window Approach) and a full task-sequence repair.

The concrete algorithms used for repair depend heavily on the planning domain's constraints. Key strategies include:

• Path Planning (Robotics): Using incremental graph search algorithms like D Lite* to repair a navigation path as new obstacle data arrives from sensors.
• Multi-Agent Coordination: Employing Conflict-Based Search (CBS) to resolve a new conflict by adding constraints and repairing sub-paths for affected agents only.
• Task Scheduling (Logistics): Using constraint programming solvers to repair a job schedule by relaxing and re-optimizing around a new machine downtime constraint. The choice of strategy balances repair speed, solution quality, and the complexity of the domain's dynamics.

An Autonomous Mobile Robot (AMR) following a planned path to a picking station encounters a fallen pallet blocking the aisle. The plan repair system triggers a feasibility check, determines the original path is invalid, and executes a local replanning algorithm like Timed Elastic Band (TEB). The system deforms the initial trajectory around the obstacle, recalculating velocities to maintain safety and temporal constraints, allowing the AMR to resume its mission with minimal delay.

A manual forklift transporting a high-priority load suffers a mechanical failure. The fleet orchestration platform's execution monitoring detects the agent is stopped. The plan repair process involves:

• Invalidating the forklift's assigned tasks.
• Triggering a dynamic task allocation cycle.
• Reassigning the high-priority load to the nearest available AMR with compatible capabilities.
• Replanning the AMR's entire route from its current location to the load pickup point and final destination, using a warm start from its previous idle-state plan to accelerate computation.

Three AMVs converge at a four-way intersection under their individual plans, creating a gridlock where each is waiting for the other to move. The centralized orchestration middleware's deadlock detection subsystem identifies the cyclic wait. Plan repair is initiated not by modifying paths, but by imposing priority-based routing constraints. The system temporarily elevates the priority of one agent, replans its path through the intersection first, and then sequentially repairs the plans of the remaining agents using incremental algorithms like Lifelong Planning A (LPA)** to find new conflict-free schedules.

A warehouse management system receives a rush order. The plan repair engine must integrate this new task into the existing schedule of a heterogeneous fleet. This involves:

• Inserting the new task as a node in the spatial-temporal scheduling problem.
• Re-optimizing task sequences for multiple agents to minimize total makespan, potentially using a Conflict-Based Search (CBS) variant for Multi-Agent Path Finding (MAPF).
• Repairing the physical paths for affected agents, often employing a lattice planner to generate new, smooth trajectories that accommodate the updated task sequence and time windows.

An AMR's fleet health monitoring system predicts its battery will deplete before completing its assigned task sequence. Proactive plan repair is triggered. The engine:

• Calculates the nearest available charging station and the time required to charge.
• Searches for a safe interval at the station using principles similar to Safe Interval Path Planning (SIPP).
• Modifies the agent's plan by inserting the charging task and recalculating the route to the station, ensuring dynamic constraints like minimum charge levels are respected.
• Potentially redistributes the AMR's remaining tasks to other fleet members via load balancing algorithms to maintain overall throughput.

A human operator manually declares a storage zone as temporarily inaccessible for safety reasons. The zone management protocol updates the global cost map. Any agent with a plan passing through that zone now has an invalid trajectory. The plan repair system performs a global replanning step for those agents. Algorithms like D Lite* are particularly effective here, as they can incrementally repair the path cost map and efficiently find new optimal paths from the agent's current state to its goal by reusing previous search information, avoiding a computationally expensive replan from scratch.

An optimization technique critical for real-time plan repair. It initializes a solver with the solution from a previous, similar planning problem (e.g., the now-invalid plan) to drastically reduce convergence time for finding a new optimal or feasible plan.

• Key Mechanism: Uses the previous trajectory's state sequence as the initial guess for a nonlinear optimizer like Model Predictive Control (MPC).
• Impact: Can reduce solver iterations by 40-70%, making complex kinodynamic replanning feasible at control frequencies (10-100 Hz).

The continuous process that detects the need for plan repair. It compares an agent's actual execution state—from sensors like LiDAR, odometry, and task status—against the expected state from its plan. Discrepancies trigger a replanning request.

• Key Components: State Estimators (e.g., Kalman Filters) and Anomaly Detectors that flag significant deviations in position, timing, or task progress.
• Outcome: Generates the replanning trigger that initiates the repair process.

A validation component that acts as a gatekeeper for repaired plans. Before any repaired plan is executed, the feasibility checker verifies it satisfies all system constraints.

• Checks For: Kinodynamic feasibility (adheres to velocity/acceleration limits), collision-free paths (with static and dynamic obstacles), and operational limits (battery, payload).
• Role in Repair: Often integrated within the planner in a generate-and-test loop, ensuring only viable plans are proposed for execution.