Browse Theses

Incorrect domain theories, and the flawed plans derived from them, are an inescapable aspect of planning in the real world. Previous learning approaches to the incorrect domain theory problem have relied on diagnosing failures to determine fixes to the domain theory to prevent the failures in the future. However, perfect failure diagnosis is itself an intractable problem, and preventive learners are subject to the problem of faulty fixes due to incorrect failure diagnoses.

This thesis presents completable planning, an incremental learning approach that augments classical plans with generalized alternative plan segments called contingent plans, which serve to cure failures by providing recovery routes from the execution failures of flawed plans constructed using incorrect domain theories. By constructing contingent plans only in response to actual failures encountered during execution, a completable planner is saved the effort of planning for all possible outcomes. By requiring only that failures be treated and not necessarily explained, a completable planner is freed from the cost and reliance on perfect failure diagnosis. The contingent plans learned through completable planning are also guaranteed never to decrease the probability of success of the original plan.

A completable planning strategy is defined by the decisions on the expectations to verify during execution, when to initiate contingent planning in response to an unexpected outcome, and what portion of the plan to reuse. As a curative approach, completable planning is more susceptible than a preventive approach to the limitations of its native planning strategy. An investigation of the effects of completable planning strategy on planning performance and learning performance is thus important, and this thesis presents the results of such a study.

This thesis also presents a method for addressing these limitations called probably approximately correct (PAC) completable planning. The PAC approach to completable planning allows a completable plans to find one that satisfies given constraints on the probability of success of a plan, execution cost, and planning cost.