Derivation Replay for Partial-Order Planning

Planning and Scheduling

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Causal-Link Planning

Derivation replay was first proposed by Carbonell as a method of transferring guidance from a previous problem-solving episode to a new one. Subsequent implementations have used state-space planning as the underlying methodology. This paper is motivated by the acknowledged superiority of partial-order (PO) planners in plan generation, and is an attempt to bring derivation replay into the realm of partial-order planning. Here we develop DerSNLP, a framework for doing replay in SNLP, a partial-order plan-space planner, and analyze its relative effectiveness. We will argue that the decoupling of planning (derivation) order and the execution order of plan steps, provided by partial-order planners, enables DerSNLP to exploit the guidance of previous cases in a more efficient and straightforward fashion. We validate our hypothesis through empirical comparisons between DerSNLP and two replay systems based on state-space planners.