Plan merging & plan reuse as satisfiability

Planning as satisfiability has hitherto focused only on purely generative planning. There is an evidence in traditional refinement planning that planning incrementally by reusing or merging plans can be more efficient than planning from scratch (sometimes reuse is not more efficient, but becomes necessary if the cost of abandoning the reusable plan is too high, when users are charged for the planning solution provided). We adapt the satisfiability paradigm to these scenarios by providing a framework where reusable or mergeable plans can be either contiguous or partially ordered and their actions can be removed and new actions can be added. We report the asymptotic sizes of the propositional encodings for several cases of plan reuse and plan merging. Our empirical evaluation shows that the satisfiability paradigm can scale up to handle plan reuse and plan merging.