×

The computational complexity of avoiding spurious states in state space abstraction. (English) Zbl 1210.68105

Summary: Abstraction is a powerful technique for speeding up planning and search. A problem that can arise 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. Spurious states can be harmful, in practice, because they can create artificial shortcuts in the abstract space that slow down planning and search, and they can greatly increase the memory needed to store heuristic information derived from the abstract space (e.g., pattern databases).
This paper analyzes the computational complexity of creating abstractions that do not contain spurious states. We define a property – the downward path preserving property (DPP) – that formally captures the notion that an abstraction does not result in spurious states. We then 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. The strong hardness results shown carry over to typical description languages for planning problems, including sas\(^{+}\) and propositional strips. On the positive side, we identify and illustrate formal conditions under which finding downward path preserving abstractions is provably tractable.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amarel, Saul, On representations of problems of reasoning about actions, (Michie, Donald, Machine Intelligence, vol. 3 (1968), Edinburgh University Press), 131-171 · Zbl 0197.14901
[2] Bacchus, Fahiem; Yang, Qiang, The downward refinement property, (Proceedings of the 12th International Joint Conference on Artificial Intelligence (1991), Morgan Kaufmann), 286-293 · Zbl 0747.68063
[3] Bacchus, Fahiem; Yang, Qiang, Downward refinement and the efficiency of hierarchical problem solving, Artificial Intelligence, 71, 1, 43-100 (1994) · Zbl 0938.68829
[5] Bäckström, Christer; Nebel, Bernhard, Complexity results for \(\text{SAS} +\) planning, Computational Intelligence, 11, 625-656 (1995)
[6] Benjamin, D. Paul, Change of Representation and Inductive Bias (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA · Zbl 0747.68003
[7] Bonet, Blai; Geffner, Hector, Planning as heuristic search, Artificial Intelligence, 129, 1-2, 5-33 (2001) · Zbl 0971.68146
[8] Culberson, Joseph; Schaeffer, Jonathan, Searching with pattern databases, (Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence. Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, Lecture Notes in Computer Science, vol. 1081 (1996), Springer), 402-416
[9] Culberson, Joseph; Schaeffer, Jonathan, Pattern databases, Computational Intelligence, 14, 3, 318-334 (1998)
[11] Fikes, Richard; Nilsson, Nils J., STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence, 2, 3/4, 189-208 (1971) · Zbl 0234.68036
[18] Hernádvölgyi, István; Holte, Robert C., Experiments with automatically created memory-based heuristics, (Proceedings of the Symposium on Abstraction, Reformulation and Approximation. Proceedings of the Symposium on Abstraction, Reformulation and Approximation, Lecture Notes in Artificial Intelligence, vol. 1864 (2000), Springer), 281-290 · Zbl 0989.68547
[20] Holte, Robert C.; Mkadmi, Taieb; Zimmer, Robert M.; MacDonald, Alan J., Speeding up problem-solving by abstraction: A graph-oriented approach, Artificial Intelligence, 85, 321-361 (1996)
[21] Knoblock, Craig A., Automatically generating abstractions for planning, Artificial Intelligence, 68, 2, 243-302 (1994) · Zbl 0942.68712
[22] Korf, Richard E., Towards a model of representation changes, Artificial Intelligence, 14, 1, 41-78 (1980)
[25] McDermott, Drew, Using regression-match graphs to control search in planning, Artificial Intelligence, 109, 1-2, 111-159 (1999) · Zbl 0916.68145
[26] McDermott, Drew, The 1998 AI planning systems competition, AI Magazine, 2, 2, 35-55 (2000)
[27] Pearl, Judea, Heuristics - Intelligent Search Strategies for Computer Problem Solving (1984), Addison-Wesley · Zbl 0527.68075
[28] Prieditis, Armand, Machine discovery of effective admissible heuristics, Machine Learning, 12, 117-141 (1993) · Zbl 0784.68064
[29] Sacerdoti, Earl D., Planning in a hierarchy of abstraction spaces, Artificial Intelligence, 5, 2, 115-135 (1974) · Zbl 0288.68052
[30] Schaefer, Thomas, The complexity of satisfiability problems, (Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (1978), ACM), 216-226 · Zbl 1282.68143
[31] Shimozono, Shinichi; Miyano, Satoru, Complexity of finding alphabet indexing, TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, E78-D, 1, 13-18 (1995) · Zbl 0939.68663
[32] Slocum, Jerry; Sonneveld, Dic, The 15 Puzzle (2006), Slocum Puzzle Foundation
[33] Van Baalen, Jeffrey, Automated design of specialized representations, Artificial Intelligence, 54, 1, 121-198 (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.