Downward Path Preserving State Space Abstractions

摘要: Abstraction is a popular technique for speeding up planning and search. A problem that often arises in using abstraction the generation of abstract states, called spurious from which goal state reachable space but there no corresponding original can be reached. The experiments this paper demonstrate may arise even when standard methods are applied to benchmark domains: states cause pattern databases representing heuristics excessively large slow down search by reducing heuristic values. Known automated techniques get rid portion turn out avoid memory problem, while at same time not avoiding bad quality. main contribution theoretical. We formally define characteristic property—the downward path preserving property (DPP)—that guarantees an will contain states. How achieved studied both focussing on domain-independent domain-specific abstraction. analyze computational complexity (i) testing given (ii) determining whether achievable all space. Strong hardness results show close connection between these decision problems plan existence typical settings including sas propositional strips. On positive side, we identify formal conditions under finding abstractions provably tractable some domains have encoding matches conditions. This includes new Blocks World domain, DPP easily defined.