Download the full-sized PDF of Downward Path Preserving State Space AbstractionsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

Downward Path Preserving State Space Abstractions Open Access


Author or creator
Zilles, Sandra
Ball, Marcel
Holte, Robert
Additional contributors
downward path preserving property
spurious states
Type of item
Computing Science Technical Report
Computing science technical report ID
Technical report TR09-04. Abstraction is a popular technique for speeding up planning and search. A problem that often arises in using abstraction is the generation of abstract states, called spurious states, from which the goal state is reachable in the abstract space but for which there is no corresponding state in the original space from which the goal state can be reached. The experiments in this paper demonstrate that this problem may arise even when standard abstraction methodsare applied to benchmark planning problem domains: spurious states cause the pattern databases representing the heuristics to be excessively large and slow down planning and search by reducing the heuristic values. Known automated techniques to get rid of a large portion of spurious states turn out to avoid the memory problem, while at the same time not avoiding the problem of bad heuristic quality. The main contribution of this paper is theoretical. We formally define a characteristic property - the downward path preserving property (DPP) - that guarantees an abstraction will not contain spurious states. How this property can be achieved is studied both for techniques focussing on automated domain-independent abstraction and for techniques focussing on domain-specific abstraction. We analyze the computational complexity of (i) testing the downward path preserving property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space. Strong hardness results show a close connection between these decision problems and the plan existence problem in typical planning settings including SAS+ and propositional STRIPS. On the positive side, we identify formal conditions under which finding downward path preserving abstractions is provably tractable and show that some popular heuristic search and planning domains have an encoding that matches these conditions. This includes a new encoding of the Blocks World domain, for which DPP abstractions can be easily defined.
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 326203
Last modified: 2015:10:12 13:49:36-06:00
Filename: TR09-04.pdf
Original checksum: 055fc1b2467bfdede3e792ca7a142140
Well formed: false
Valid: false
Status message: Lexical error offset=321027
Page count: 33
Activity of users you follow
User Activity Date