Completable Planning: A Curative Learning Approach to the Imperfect Theory Problem

Melinda T. Gervasio and Gerald F. DeJong

The complexity of the real world makes a perfect characterization impossible. Purely deliberative approaches such as classical planning are thus susceptible to unexpected failures. Preventive learning approaches address the imperfect theory problem through the diagnosis of such failures and the determination of fixes to avoid similar failures in the future. Curative learning approaches such as completable planning instead treat failures as alternative outcomes and learn alternative plans to the recover from the failures. Through learning, a completable planner learns to plan only for the more likely outcomes in the particular problem distribution it faces. It thus significantly reduces the cost of disjunctive planning.. As a curative learning approach, it is also better suited to domains where outright failures are unacceptable or failure diagnosis is expensive, making preventive learning infeasible. Completable planning is a general incremental learning approach whose success in real world domains may be increased through the integration of other learning techniques and the consideration of different planning perspectives.
