Abstract
In dynamic environments, automated planning systems frequently encounter failures due to environmental volatility or internal model inaccuracies. This paper presents a formal mathematical model designed to minimize the cost of failure recovery. By applying decision-theoretic principles to the selection and sequencing of recovery methods, we demonstrate significant cost reductions within the Phoenix forest fire-fighting simulator. Our results indicate that ordering recovery methods by their success-to-cost ratio provides a robust framework for both operational strategy and architectural redesign.
Introduction
The ability of an autonomous agent to recover from plan failure is critical for survival in complex, unpredictable domains. While various domain-independent recovery techniques exist, their application is often guided by ad-hoc heuristics rather than systematic evaluation. This research addresses the fundamental question of how a system designer can identify and evaluate the most effective recovery techniques for a given domain. We propose that failure recovery should be treated as a decision-theoretic problem, where the goal is to minimize the expected cost of returning the system to a functional state.
The Basic Cost Model
We define a Basic Cost Model where the total expected cost of recovery is a function of the probability of specific failure types and the costs associated with the methods used to mitigate them.
The Optimal Strategy
Following decision theory, we posit that the most efficient sequence for attempting recovery methods is to order them by their success-to-cost ratio: $P(Success | Failure) / Cost$. This strategy ensures that the most "cost-effective" fixes are attempted first, minimizing the cumulative expenditure of resources before a successful recovery is achieved.
Recovery Methods in Phoenix
The model was tested using the Phoenix simulator, a complex environment modeling forest fire suppression. Agents in Phoenix utilize a suite of recovery methods:
- Wait and Retry (WATA): A simple temporal delay.
- Variable Recalculation (RV/RAV): Updating specific or all plan variables.
- Step Substitution (SA): Replacing a failed plan step with a functional equivalent.
- Replanning (RP/RT): High-level architectural repairs at the parent or top level of the plan hierarchy.
Experimental Methodology
The research followed the "Model-Analyze-Design" (MAD) methodology across three distinct experimental phases:
- Experiment 1 (Baseline): Established failure distributions and baseline costs using a random selection strategy.
- Experiment 2 (Strategy): Evaluated the performance of the optimal $P/C$ ordering strategy.
- Experiment 3 (Redesign): Used model insights to redesign the set of available recovery methods, targeting high-cost failure types.
Results and Analysis
The implementation of the optimal $P/C$ ordering strategy yielded immediate improvements. As shown in Figure 2, the actual costs under the optimal strategy were consistently lower than the baseline costs across nearly all failure types (A through J). In some failure situations, costs dropped by as much as 86%.
A key insight was the Predictability-Power Trade-off. Local methods exhibited low cost variance but lower success rates, while global replanning methods were highly powerful but carried significant cost uncertainty. Furthermore, the distribution of failures was found to be highly sensitive to environmental volatility, confirming that failures are emergent properties of agent-environment interactions.
The iterative design process guided by the cost model allowed for further optimization. By identifying failure types that were both frequent and expensive, we introduced specialized, lower-cost recovery methods.
As illustrated in Figure 5, the mean recovery cost decreased from a baseline of 2811 to 2530 with the optimal strategy, and finally to 2370 after method set redesign. Concurrently, the overall success rate of recovery attempts rose from approximately 70% to 90%.
Conclusion
This study demonstrates that a formal cost model can significantly improve the efficiency of failure recovery in complex automated systems. While the current model treats failures as black boxes, it provides a necessary foundation for systematic agent design. Future work will focus on developing "semantic" models that understand the underlying causes of failures, enabling proactive failure anticipation.
Summary updated