Introduction
Automated planners—systems that generate sequences of actions to achieve complex goals—frequently encounter failures during execution. While some failures stem from environmental unpredictability, many are "internal," caused by incomplete domain models or unforeseen interactions between actions. A significant challenge in debugging these systems is that traditional tools often require the very thing the designer lacks: a near-perfect model of the domain.
This paper introduces Failure Recovery Analysis (FRA), a statistical method for debugging planners by analyzing execution traces. FRA is a "weak model" approach, meaning it identifies patterns of failure without requiring a complete formal proof of the plan's correctness. Crucially, it helps designers identify when a planner's own recovery actions (intended to fix a problem) are inadvertently causing future failures.
The Failure Recovery Analysis (FRA) Method
FRA follows a four-step procedure to bridge the gap between raw execution data and actionable design improvements.
1. Isolating Dependencies
The process begins by statistically analyzing execution traces. The system uses contingency tables and G-tests to determine if a specific failure is significantly more likely to occur after a specific precursor, such as a previous recovery action. This step identifies "pathogenic" recovery actions that may be solving an immediate issue while sowing the seeds for a later crash.
2. Mapping to Suggestive Plan Structures
Once a statistical link is found, the system looks for "suggestive structures" in the plan library. These are common coding idioms—such as shared variables, shared resources, or sequential ordering—that might explain the statistical correlation. For example, if a recovery action and a subsequent failure both interact with the same variable, that variable becomes a primary suspect for the bug.
3. Explaining and Recommending
The system generates "sketches" or hypotheses explaining the failure. A common explanation is an "Implicit Assumption," where two different actions use the same variable but assume different units or contexts. Based on these explanations, FRA suggests modifications, such as making assumptions explicit or limiting the conditions under which a specific "band-aid" recovery action can be used.
Experimental Evaluation: The Phoenix System
The research utilized the Phoenix system, a complex simulator for forest fire fighting in Yellowstone National Park. The analysis was performed on datasets representing over 5,000 hours of simulated time.
FRA identified a strong dependency between a specific recovery action ($R_{sp}$, substitute-projection-action) and a failure type ($F_{vit}$, insufficient-time failure). By following FRA's recommendations to make resource assumptions explicit, the research team restructured the planner, leading to significant improvements:
- Quantitative Improvement: The mean failure rate dropped from 0.41 to 0.33 failures per hour.
- Bug Elimination: Four major dependency chains involving projection actions were completely eliminated.
- Efficiency: While gathering simulation data took days, the actual FRA statistical analysis was completed in less than five minutes.
Conclusion and Future Work
FRA demonstrates that recovery actions are not always neutral; they can act as pathogens within a system. By focusing on common plan idioms, FRA provides a bridge between abstract statistical correlations and concrete code fixes. While the method is data-hungry—requiring thousands of hours of simulation to catch rare failures—it offers a unique advantage during early-stage development when domain models are still incomplete. Future work aims to extend the system's ability to track long-distance temporal dependencies without succumbing to combinatorial explosion.
Summary updated