Using Concept Hierarchies to Organize Plan Knowledge

Abstract

This chapter presents a unified theory of planning and its implementation in a system called DAEDALUS. DAEDALUS begins with knowledge of the operators for a domain and, like Minton's (1988) PRODIGY, uses means-ends analysis to construct plans. However, DAEDALUS stores these plans (cases) in a probabilistic concept hierarchy, indexing them by the differences they reduce. Upon encountering a previously unseen problem, the system retrieves a relevant plan (one with analogous differences) and uses it to select operators for the new task. The retrieval process leads DAEDALUS to generalize its stored plans so that it gradually shifts from a cased-based to a schema-based mode, while still retaining the ability to employ means-ends analysis when necessary. DAEDALUS operators are similar to those used by STRIPS but unlike STRIPS, which kept operators in a linear list, the current system organizes its operators in a probabilistic concept hierarchy, like that used in COBWEB. Also, the planning algorithm is based on simple means-ends analysis, again as in STRIPS. DAEDALUS differs from most means-ends planners in the way it accesses its operators from memory. Initially, DAEDALUS has access only to the domain operators stored in its concept hierarchy. As it gains more experience in a domain, DAEDALUS will begin to encounter problems that are similar to earlier ones. Once DAEDALUS has been implemented and tested, the exploration of several variants and extensions to the basic approach becomes available.