Contingency selection in plan generation

Planning under uncertainty is a ubiquitous subarea of the recent planning literature. Systems that plan under uncertainty provide mechanisms for generating contingency plans: conditional planners can generate branching plans by allowing for actions with multiple possible outcomes (thus possible failures) and sensing actions that let the agent determine the current state. A key question in conditional planning is: how many, and which of the possible execution failures should be planned for by including conditional branches? This thesis addresses the question of selecting contingencies to repair with conditional branches before plan execution starts. A closely related issue is the identification of the types of repairs that can be performed once a contingency is selected. In the thesis, recent work on conditional and/or probabilistic planning is synthesized into a unifying algorithm that incorporates and clarifies the main techniques that have been developed. The main feature of the algorithm is the decoupling of the search-control strategy from the underlying plan-refinement process by including two direct methods for repairing possible failure points among the plan-refinement operations. The first method is corrective repair: the process of using steps to try to correct the situation after a failure. The second method is preventive repair: the process of using steps to try to reduce the chance of failure. The algorithm is fully implemented in a planning system called Mahinur and the system is used as a framework for principled prioritization of repairs for failure points. This prioritization is achieved by using a decision theoretic account of the expected value of performing the repairs considering the probability of failure and the impact of the failure on the top-level goals assigned to the agent. The benefits of contingency selection axe shown experimentally in synthetic domains and a realistic domain involving oil spill response plans. The effectiveness of additional conditional, probabilistic planning heuristics are analyzed and demonstrated empirically.