A number of strategies exist for the recovery from execution-time plan failures. One dimension in which these strategies differ is the degree of dependence on the reliability and availability of the planner’s knowledge. The best strategy, however, may be dependent on a number of considerations, including the type of plan failure, the critically of the failure, the availability of resources, and the reliability and availability of the specific knowledge involved in a given plan failure instance. In our work on multi-agent, multi-modal (centralized, distributed and local) planning, we are interested in intelligently selecting and applying failure recovery strategies that are appropriate to the situation and that can cope with uncertainty. We are examining a decision-theoretic approach to diagnose plan failures and to dynamically select from multiple failure recovery strategies when an execution-time plan failure occurs.