Structured-Based Generation of Plans

Extending Theories of Action: Formal Theory and Practical Applications

Volume

Papers from the 1995 AAAI Spring Symposium

Contents

I show that (1) compositional planning is possible when goals are independent; (2) there is a calculus for compositional planning, called plan calculus, that depends on the availability of such independence information; and (3) the causal structure of symbolic causal network encodes the independence information required by plan calculus. Therefore, I show that if a domain is represented using a symbolic causal network, then plan calculus can be used to compose a plan for some complex goal using only plans for local goals (those involving only a proposition and its parents). This leads to structure-based algorithms for plan generation; that is, algorithms for which the computational complexity is parameterized by the topology of the corresponding causal structure.