Learning Completable Reactive Plans through Achievability Proofs

摘要

This thesis presents an integrated approach to planning wherein a classicalplanner is augmented with the ability to defer achievable goals and address these deferred goals during execution. This integration gains from reactive planning the ability to utilize runtime information, thus reducing the need for perfect a priori information, while retaining the goal-directedness afforded by a priori planning. This approach also retains the provably-correct nature of plans constructed by a classical planner by requiring that all deferred goals have achievability proofs guaranteeing their eventual achievement. Proving achievability is shown to be possible for certain classes of problems without having to determine the actions to achieve the associated goals. General plans for use in this integrated approach are learned through a modified explanation-based learning strategy called contingent explanation-based learning. In contingent EBL, deferred goals are represented using conjectured variables, which act as placeholders for the eventual values of plan parameters whose values are unknown prior to execution. Completors are incorporated into general plans for the runtime determination of values to replace the conjectured variables. Since only conjectured variables with accompanying achievability proofs are allowed into contingent explanations, the general plans learned in contingent EBL are guaranteed to be completable. An implemented system demonstrates the use of contingent EBL in learning general completable reactive plans; which enables the construction of robust, efficient plans for spaceship acceleration. (KR)