×

A framework for analysing state-abstraction methods. (English) Zbl 1486.68175

Summary: Abstraction has been used in combinatorial search and action planning from the very beginning of AI. Many different methods and formalisms for state abstraction have been proposed in the literature, but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on graph transformations. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. We model six different abstraction methods from the planning literature and analyse their intrinsic properties. We show how to capture many search abstraction concepts (such as avoiding backtracking between levels) and how to put them into a broader context. We also use the framework to identify and investigate connections between refinement and heuristics – two concepts that have usually been considered as unrelated in the literature. This provides new insights into various topics, e.g. Valtorta’s theorem and spurious states. We finally extend the framework with composition of transformations to accommodate for abstraction hierarchies, and other multi-level concepts. We demonstrate the latter by modelling and analysing the merge-and-shrink abstraction method.

MSC:

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

References:

[1] Aghighi, M.; Bäckström, C., Cost-optimal and net-benefit planning-a parameterised complexity view, (Proceedings of the 24th International Joint Conference on Artificial Intelligence. Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina (2015)), 1487-1493
[2] Ancona, M.; Floriani, L. D.; Deogun, J. S., Path problems in structured graphs, Comput. J., 29, 553-563 (1986) · Zbl 0607.05042
[3] Bacchus, F.; Yang, Q., Downward refinement and the efficiency of hierarchical problem solving, Artif. Intell., 71, 43-100 (1994) · Zbl 0938.68829
[4] Bäckström, C., Expressive equivalence of planning formalisms, Artif. Intell., 76, 17-34 (1995)
[5] Bäckström, C.; Jonsson, P., Planning with abstraction hierarchies can be exponentially less efficient, (Proceedings of the 14th International Joint Conference on Artificial Intelligence. Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995, Montréal QC, Canada (1995)), 1599-1605
[6] Bäckström, C.; Jonsson, P., Abstracting abstraction in search with applications to planning, (Principles of Knowledge Representation and Reasoning: Proceedings of the 13th International Conference. Principles of Knowledge Representation and Reasoning: Proceedings of the 13th International Conference, KR 2012, Rome, Italy (2012)), 446-456
[7] Bäckström, C.; Jonsson, P., Bridging the gap between refinement and heuristics in abstraction, (Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China (2013)), 2261-2267
[8] Bäckström, C.; Jonsson, P.; Ordyniak, S.; Szeider, S., A complete parameterized complexity analysis of bounded planning, J. Comput. Syst. Sci., 81, 1311-1332 (2015) · Zbl 1320.68096
[9] Bäckström, C.; Jonsson, P.; Ståhlberg, S., Fast detection of unsolvable planning instances using local consistency, (Proceedings of the 6th Annual Symposium on Combinatorial Search. Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013, Leavenworth, WA, USA (2013)), 29-37
[10] Bäckström, C.; Klein, I., Planning in polynomial time: the SAS-PUBS class, Comput. Intell., 7, 181-197 (1991)
[11] Bäckström, C.; Nebel, B., Complexity results for SAS^+ planning, Comput. Intell., 11, 625-656 (1995)
[12] Balcázar, J., The complexity of searching implicit graphs, Artif. Intell., 86, 171-188 (1996) · Zbl 1506.68117
[13] Bogomolov, S.; Magazzeni, D.; Podelski, A.; Wehrle, M., Planning as model checking in hybrid domains, (Proceedings of the 28th AAAI Conference on Artificial Intelligence. Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI 2014, Québec City, QC, Canada (2014)), 2228-2234
[14] Bonet, B.; Loerincs, G.; Geffner, H., A robust and fast action selection mechanism for planning, (Proceedings of the 14th National Conference on Artificial Intelligence. Proceedings of the 14th National Conference on Artificial Intelligence, AAAI 1997, Providence, RI, USA (1997)), 714-719
[15] Botea, A.; Enzenberger, M.; Müller, M.; Schaeffer, J., Macro-FF: improving AI planning with automatically learned macro-operators, J. Artif. Intell. Res., 24, 581-621 (2005) · Zbl 1080.68657
[16] Bundy, A.; Giunchiglia, F.; Sebastiani, R.; Walsh, T., Calculating criticalities, Artif. Intell., 88, 39-67 (1996) · Zbl 0906.68138
[17] Bylander, T., The computational complexity of propositional Strips planning, Artif. Intell., 69, 165-204 (1994) · Zbl 0821.68065
[18] Choueiry, B. Y.; Iwasaki, Y.; McIlraith, S. A., Towards a practical theory of reformulation for reasoning about physical systems, Artif. Intell., 162, 145-204 (2005) · Zbl 1132.68694
[19] Clarke, E. M.; Grumberg, O.; Jha, S.; Lu, Y.; Veith, H., Counterexample-guided abstraction refinement for symbolic model checking, J. ACM, 50, 752-794 (2003) · Zbl 1325.68145
[20] Clarke, E. M.; Grumberg, O.; Long, D. E., Model checking and abstraction, ACM Trans. Program. Lang. Syst., 16, 1512-1542 (1994)
[21] Cousot, P.; Cousot, R., Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, (Conference Record of the 4th ACM Symposium on Principles of Programming Languages. Conference Record of the 4th ACM Symposium on Principles of Programming Languages, POPL 1977, Los Angeles, CA, USA (1977)), 238-252
[22] Cousot, P.; Cousot, R., Abstract interpretation: past, present and future, (Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS 2014, Vienna, Austria (2014)), Article 2 pp. · Zbl 1401.68037
[23] Culberson, J. C.; Schaeffer, J., Pattern databases, Comput. Intell., 14, 318-334 (1998)
[24] Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of A^⁎, J. ACM, 32, 505-536 (1985) · Zbl 0631.68075
[25] Domshlak, C.; Hoffmann, J.; Katz, M., Red-black planning: a new systematic approach to partial delete relaxation, Artif. Intell., 221, 73-114 (2015) · Zbl 1328.68194
[26] Domshlak, C.; Hoffmann, J.; Sabharwal, A., Friends or foes? On planning as satisfiability and abstract CNF encodings, J. Artif. Intell. Res., 36, 415-469 (2009) · Zbl 1188.68270
[27] Domshlak, C.; Katz, M.; Lefler, S., When abstractions met landmarks, (Proceedings of the 20th International Conference on Automated Planning and Scheduling. Proceedings of the 20th International Conference on Automated Planning and Scheduling, ICAPS 2010, Toronto, ON, Canada (2010)), 50-56
[28] Domshlak, C.; Nazarenko, A., The complexity of optimal monotonic planning: the bad, the good, and the causal graph, J. Artif. Intell. Res., 48, 783-812 (2013) · Zbl 1361.68196
[29] Ebendt, R.; Drechsler, R., Weighted A^⁎ search - unifying view and application, Artif. Intell., 173, 1310-1342 (2009) · Zbl 1194.68207
[30] Edelkamp, S.; Leue, S.; Visser, W., Summary of Dagstuhl seminar 06172 on directed model checking, (Directed Model Checking (2007))
[31] Edelkamp, S.; Schrödl, S., Heuristic Search - Theory and Applications (2012), Academic Press · Zbl 1238.68150
[32] Eriksson, S.; Röger, G.; Helmert, M., A proof system for unsolvable planning tasks, (Proceedings of the 28th International Conference on Automated Planning and Scheduling. Proceedings of the 28th International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands (2018)), 65-73
[33] Fan, G.; Holte, R. C., The spurious path problem in abstraction, (Proceedings of the 8th Annual Symposium on Combinatorial Search. Proceedings of the 8th Annual Symposium on Combinatorial Search, SoCS 2015, Ein Gedi, Israel (2015)), 18-27
[34] Felner, A.; Zahavi, U.; Holte, R.; Schaeffer, J.; Sturtevant, N. R.; Zhang, Z., Inconsistent heuristics in theory and practice, Artif. Intell., 175, 1570-1603 (2011) · Zbl 1225.68244
[35] Galperin, H.; Wigderson, A., Succinct representations of graphs, Inf. Control, 56, 183-198 (1983) · Zbl 0538.68053
[36] Gaschnig, J., A problem similarity approach to devising heuristics: first results, (Proceedings of the 6th International Joint Conference on Artificial Intelligence. Proceedings of the 6th International Joint Conference on Artificial Intelligence, IJCAI 1979, Tokyo, Japan (1979)), 301-307
[37] Geißer, F.; Keller, T.; Mattmüller, R., Abstractions for planning with state-dependent action costs, (Proceedings of the 26th International Conference on Automated Planning and Scheduling. Proceedings of the 26th International Conference on Automated Planning and Scheduling, ICAPS 2016, London, UK (2016)), 140-148
[38] Giunchiglia, F.; Villafiorita, A.; Walsh, T., Theories of abstraction, AI Commun., 10, 167-176 (1997)
[39] Giunchiglia, F.; Walsh, T., A theory of abstraction, Artif. Intell., 57, 323-389 (1992) · Zbl 0762.68054
[40] Govindaraju, S. G.; Dill, D. L., Verification by approximate forward and backward reachability, (Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design. Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1998, San Jose, CA, USA (1998)), 366-370
[41] Gregory, P.; Long, D.; Fox, M.; Beck, J. C., Planning modulo theories: extending the planning paradigm, (Proc. 22nd International Conference on Automated Planning and Scheduling (ICAPS-2012) (2012))
[42] Gregory, P.; Long, D.; McNulty, C.; Murphy, S. M., Exploiting path refinement abstraction in domain transition graphs, (Proceedings of the 25th AAAI Conference on Artificial Intelligence. Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, CA, USA (2011)), 971-976
[43] Guida, G.; Somalvico, M., A method for computing heuristics in problem solving, Inf. Sci., 19, 251-259 (1979) · Zbl 0442.68097
[44] Hart, P. E.; Nilsson, N. J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 4, 100-107 (1968)
[45] Haslum, P.; Botea, A.; Helmert, M.; Bonet, B.; Koenig, S., Domain-independent construction of pattern database heuristics for cost-optimal planning, (Proceedings of the 22nd AAAI Conference on Artificial Intelligence. Proceedings of the 22nd AAAI Conference on Artificial Intelligence, AAAI 2007, Vancouver, BC, Canada (2007)), 1007-1012
[46] Haslum, P.; Jonsson, P., Planning with reduced operator sets, (Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems. Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000, Breckenridge, CO, US (2000)), 150-158
[47] Helmert, M.; Domshlak, C., Landmarks, critical paths and abstractions: what’s the difference anyway?, (Proceedings of the 19th International Conference on Automated Planning and Scheduling. Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS 2009, Thessaloniki, Greece (2009)), 162-169
[48] Helmert, M.; Haslum, P.; Hoffmann, J., Flexible abstraction heuristics for optimal sequential planning, (Proceedings of the 17th International Conference on Automated Planning and Scheduling. Proceedings of the 17th International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, RI, USA (2007)), 176-183
[49] Helmert, M.; Haslum, P.; Hoffmann, J.; Nissim, R., Merge-and-shrink abstraction: a method for generating lower bounds in factored state spaces, J. ACM, 61, Article 16 pp. (2014) · Zbl 1295.68189
[50] Heusner, M.; Wehrle, M.; Pommerening, F.; Helmert, M., Under-approximation refinement for classical planning, (Proceedings of the 24th International Conference on Automated Planning and Scheduling. Proceedings of the 24th International Conference on Automated Planning and Scheduling, ICAPS 2014, Portsmouth, NH, USA (2014)), 365-369
[51] Hoffmann, J., Where ‘ignoring delete lists’ works: local search topology in planning benchmarks, J. Artif. Intell. Res., 24, 685-758 (2005) · Zbl 1080.68668
[52] Hoffmann, J.; Kissmann, P.; Torralba, Á., “Distance”? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability, (Proceedings of the 21st European Conference on Artificial Intelligence. Proceedings of the 21st European Conference on Artificial Intelligence, ECAI 2014, Prague, Czech Republic (2014)), 441-446 · Zbl 1366.68264
[53] Hoffmann, J.; Porteous, J.; Sebastia, L., Ordered landmarks in planning, J. Artif. Intell. Res., 22, 215-278 (2004) · Zbl 1080.68670
[54] Hoffmann, J.; Sabharwal, A.; Domshlak, C., Friends or foes? An AI planning perspective on abstraction and search, (Proceedings of the 16th International Conference on Automated Planning and Scheduling. Proceedings of the 16th International Conference on Automated Planning and Scheduling, ICAPS 2006, Cumbria, UK (2006)), 294-303
[55] Holte, R.; Arneson, B.; Burch, N., PSVN Manual (2014), Department of Computing Science, University of Alberta: Department of Computing Science, University of Alberta Edmonton, AB, Canada, Technical Report TR14-03
[56] Holte, R. C., Common misconceptions concerning heuristic search, (Felner, A.; Sturtevant, N. R., Proceedings of the 3rd Annual Symposium on Combinatorial Search. Proceedings of the 3rd Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, GA, USA, July 8-10, 2010 (2010), AAAI Press), 46-51
[57] Holte, R. C.; Choueiry, B., Abstraction and reformulation in artificial intelligence, Philos. Trans. R. Soc. Lond. B, 29, 358, 1197-1204 (2003)
[58] Holte, R. C.; Hernádvölgyi, I. T., A space-time tradeoff for memory-based heuristics, (Proceedings of the 16th National Conference on Artificial Intelligence. Proceedings of the 16th National Conference on Artificial Intelligence, AAAI 1999, Orlando, FL, USA (1999)), 704-709
[59] Holte, R. C.; Mkadmi, T.; Zimmer, R. M.; MacDonald, A. J., Speeding up problem solving by abstraction: a graph oriented approach, Artif. Intell., 85, 321-361 (1996)
[60] Holte, R. C.; Perez, M. B.; Zimmer, R. M.; MacDonald, A. J., The Tradeoff Between Speed and Optimality in Hierarchical Search (1995), Computer Science, University of Ottawa, Technical Report TR-95-19
[61] Holte, R. C.; Perez, M. B.; Zimmer, R. M.; MacDonald, A. J., Hierarchical A^⁎: searching abstraction hierarchies efficiently, (Proceedings of the 13th National Conference on Artificial Intelligence. Proceedings of the 13th National Conference on Artificial Intelligence, AAAI 1996, Portland, OR, USA (1996)), 530-535
[62] Karpas, E.; Domshlak, C., Optimal search with inadmissible heuristics, (Proceedings of the 22nd International Conference on Automated Planning and Scheduling. Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS 2012, Atibaia, São Paulo, Brazil (2012)), 92-100
[63] Knoblock, C. A., A theory of abstraction for hierarchical planning, (Benjamin, D. P., Change of Representation and Inductive Bias (1990), Kluwer: Kluwer Boston, MA, USA), 81-104 · Zbl 0792.68167
[64] Knoblock, C. A., Search reduction in hierarchical problem solving, (Proceedings of the 9th National Conference on Artificial Intelligence. Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991, Anaheim, CA, USA (1991)), 686-691
[65] Knoblock, C. A., Automatically generating abstractions for planning, Artif. Intell., 68, 243-302 (1994) · Zbl 0942.68712
[66] Knoblock, C. A.; Tenenberg, J. D.; Yang, Q., Characterizing abstraction hierarchies for planning, (Proceedings of the 9th National Conference on Artificial Intelligence. Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991, Anaheim, CA, USA (1991)), 692-697
[67] Korf, R. E., Macro-operators: a weak method for learning, Artif. Intell., 26, 35-77 (1985) · Zbl 0562.68071
[68] Korf, R. E., Planning as search: a quantitative approach, Artif. Intell., 33, 65-88 (1987)
[69] Korf, R. E., Linear-time disk-based implicit graph search, J. ACM, 55, Article 26 pp. (2008) · Zbl 1325.68218
[70] Lengauer, T.; Wagner, K. W., The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, J. Comput. Syst. Sci., 44, 63-93 (1992) · Zbl 0743.68078
[71] McDermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Weld, D.; Wilkins, D., PDDL—the Planning Domain Definition Language (1998), Yale Center for Computational Vision and Control: Yale Center for Computational Vision and Control New Haven, CT, USA, Technical Report CVC TR98003/DCS TR1165
[72] McDermott, D. V., A heuristic estimator for means-ends analysis in planning, (Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems. Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems, AIPS 1996, Edinburgh, UK (1996)), 142-149
[73] Nayak, P. P.; Levy, A. Y., A semantic theory of abstractions, (Proceedings of the 14th International Joint Conference on Artificial Intelligence. Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995, Montréal QC, Canada (1995)), 196-203
[74] Newell, A.; Shaw, J. C.; Simon, H. A., Report on a general problem-solving program, (IFIP Congress. IFIP Congress, Paris, France (1959), UNESCO), 256-264 · Zbl 0112.08502
[75] Nissim, R.; Hoffmann, J.; Helmert, M., Computing perfect heuristics in polynomial time: on bisimulation and merge-and-shrink abstraction in optimal planning, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, Barcelona, Catalonia, Spain (2011)), 1983-1990
[76] Pang, B.; Holte, R. C., Multimapping abstractions and hierarchical heuristic search, (Proceedings of the 5th Annual Symposium on Combinatorial Search. Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012, Niagara Falls, ON, Canada (2012)), 72-79
[77] Pommerening, F.; Helmert, M.; Bonet, B., Abstraction heuristics, cost partitioning and network flows, (Proceedings of the 27th International Conference on Automated Planning and Scheduling. Proceedings of the 27th International Conference on Automated Planning and Scheduling, ICAPS 2017, Pittsburgh, PA, USA (2017)), 228-232
[78] Sacerdoti, E. D., Planning in a hierarchy of abstraction spaces, Artif. Intell., 5, 115-135 (1974) · Zbl 0288.68052
[79] Sacerdoti, E. D., The nonlinear nature of plans, (Advance Papers of the 4th International Joint Conference on Artificial Intelligence. Advance Papers of the 4th International Joint Conference on Artificial Intelligence, IJCAI 1975, Tbilisi, Georgia, USSR (1975)), 206-214
[80] Saitta, L.; Zucker, J. D., Abstraction in Artificial Intelligence and Complex Systems (2013), Springer: Springer New York
[81] Saribatur, Z. G.; Wallner, J. P.; Woltran, S., Explaining non-acceptability in abstract argumentation, (Proceedings of the 24th European Conference on Artificial Intelligence. Proceedings of the 24th European Conference on Artificial Intelligence, ECAI 2020, Santiago de Compostela, Spain (2020)), 881-888 · Zbl 1464.68371
[82] Seipp, J.; Helmert, M., Counterexample-guided Cartesian abstraction refinement, (Proceedings of the 23rd International Conference on Automated Planning and Scheduling. Proceedings of the 23rd International Conference on Automated Planning and Scheduling, ICAPS 2013, Rome, Italy (2013)), 347-351
[83] Seipp, J.; Helmert, M., Counterexample-guided Cartesian abstraction refinement for classical planning, J. Artif. Intell. Res., 62, 535-577 (2018) · Zbl 1448.68392
[84] Sievers, S., Merge-and-Shrink Abstractions for Classical Planning (2017), Universität Basel, Ph.D. thesis
[85] Sievers, S.; Wehrle, M.; Helmert, M., Generalized label reduction for merge-and-shrink heuristics, (Brodley, C. E.; Stone, P., Proceedings of the 28th AAAI Conference on Artificial Intelligence. Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, July 27-31, 2014 (2014), AAAI Press), 2358-2366
[86] Smith, D.; Peot, M., A critical look at Knoblock’s hierarchy mechanism, (Proceedings of the 1st International Conference on Artificial Intelligence Planning Systems. Proceedings of the 1st International Conference on Artificial Intelligence Planning Systems, AIPS 1992, College Park, MD, USA (1992)), 307-308
[87] Steinmetz, M.; Torralba, Á., Bridging the gap between abstractions and critical-path heuristics via hypergraphs, (Proceedings of the 29th International Conference on Automated Planning and Scheduling. Proceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA (2019)), 473-481
[88] Sturtevant, N. R.; Buro, M., Partial pathfinding using map abstraction and refinement, (Proceedings of the 20th National Conference on Artificial Intelligence. Proceedings of the 20th National Conference on Artificial Intelligence, AAAI 2005, Pittsburgh, PA, USA (2005)), 1392-1397
[89] Tate, A., Generating project networks, (Proceedings of the 5th International Joint Conference on Artificial Intelligence. Proceedings of the 5th International Joint Conference on Artificial Intelligence, Cambridge, MA, USA (1977)), 888-893
[90] Valtorta, M., A result on the computational complexity of heuristic estimates for the A^⁎ algorithm, Inf. Sci., 34, 47-59 (1984) · Zbl 0556.68013
[91] Yang, F.; Culberson, J. C.; Holte, R.; Zahavi, U.; Felner, A., A general theory of additive state space abstractions, J. Artif. Intell. Res., 32, 631-662 (2008) · Zbl 1182.68078
[92] Zilles, S.; Holte, R. C., The computational complexity of avoiding spurious states in state space abstraction, Artif. Intell., 174, 1072-1092 (2010) · Zbl 1210.68105
[93] Zucker, J. D., A grounded theory of abstraction in artificial intelligence, Philos. Trans. R. Soc. Lond. B, 29, 358, 1293-1309 (2003)
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.