A Correct Algorithm for Efficient Planning with Preprocessed Domain Axioms

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
[img] Text
ES2000.pdf
Permissions: Administrator Access Only

Download (282kB)

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

Keywords:

Planning Graph, Planning Problem, Conditional Effect, Plan Solution, Conditional Deletion

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
2001Published

Item ID:

27712

Date Deposited:

13 Dec 2019 11:00

Last Modified:

13 Dec 2019 11:07

URI:

http://research.gold.ac.uk/id/eprint/27712

View statistics for this item...

Edit Record Edit Record (login required)