Tradeoffs between encodings based on different proof strategies
Causal encodings in general have more clauses than state-space encodings
- O( #actions x #actions x #fluents) for causal link variables
- Could be reduced by using white-knight based proofs
- O(#actions x #actions x #actions) clauses for partial ordering
- Could be reduced by using contiguous ordering
- However, the best causal encodings will still be dominated by the backward state-space encodings [Mali & Kambhampati, 99]
Paradoxical given the success of partial order planners in conjunctive planning?
- Not really! We are using causal proof which is typically longer than state-based proofs, and are not using the flexibility of step insertion.
- Can be helpful in incremental planning & Plan reuse
- Are helpful in using causal domain specific knowledge (e.g. HTN schemas)