An Incremental Learning Approach for Completable Planning

Abstract

Many real world planning domains are complex and uncertain, preventing complete a priori planning. However, real world planners can also rely on runtime information to facilitate additional planning during execution. The completable approach to planning introduces the idea of completable steps, which represent deferred planning decisions. Through completable steps, a planner can defer particular goals until execution time, when additional information may be used for their achievement. To maintain the provably correct nature of plans afforded by classical planning, completable steps have the additional requirement of achievability. Unfortunately, without additional higher-order knowledge for reasoning about achievability, proving achievability becomes infeasible for any real world domain. We thus developed an incremental approach for learning completable plans. Using this approach, instead of proving achievability a planner uses feedback from its experience with the real world to construct completable plans which cover an increasing space of situations. This approach to real-world planning has been successfully tested in a simple simulated robot navigation domain.