A Correct Algorithm for Efficient Planning with Preprocessed Domain Axioms

Tools

Garagnani, M.. 2001. A Correct Algorithm for Efficient Planning with Preprocessed Domain Axioms. In: Max Bramer; Alun Preece and Frans Coenen, eds. Research and Development in Intelligent Systems XVII: Proceedings of ES2000, the Twentieth SGES International Conference on Knowledge Based Systems and Applied Artificial Intelligence, Cambridge, December 2000. London: Springer, pp. 363-374. ISBN 9781852334031 [Book Section]

No full text available

Text
ES2000.pdf
Permissions: Administrator Access Only
Download (282kB)

Official URL: https://link.springer.com/chapter/10.1007/978-1-44...

Abstract or Description

This paper describes a polynomial algorithm for preprocessing planning problems which contain domain axioms (DAs) in the form P1 ∧ P2 ∧ . . . ∧ Pn → c. The algorithm presented is an improved version of the (incorrect) transformation for DAs described by Gazen and Knoblock in [6]. The first result presented consists of a counter-example showing that Gazen and Knoblock’s preprocessing algorithm is incorrect. This is demonstrated by providing a specific set of planning problems which the algorithm does not transform into equivalent encodings. The following result described consists of a new algorithm that avoids the problems of the previous method by augmenting the state with additional assertions (‘deduction facts’) that keep track of any application of the DAs made during the plan. The final part of the paper illustrates how the new method proposed leads also to notable improvements in the efficiency of the planning process.

Item Type:

Book Section

Identification Number (DOI):

https://doi.org/10.1007/978-1-4471-0269-4_26