×

zbMATH — the first resource for mathematics

State space search nogood learning: online refinement of critical-path dead-end detectors in planning. (English) Zbl 1402.68165
Summary: Conflict-directed learning is ubiquitous in constraint satisfaction problems like SAT, but has been elusive for state space search on reachability problems like classical planning. Almost all existing approaches learn nogoods relative to a fixed solution-length bound, in which case planning/reachability reduces to a constraint satisfaction problem. Here we introduce an approach to learning more powerful nogoods, that are sound regardless of solution length, i.e., that identify dead-end states for which no solution exists.
The key technique we build on are critical-path heuristics \(h^C\), relative to a set \(C\) of conjunctions. These recognize a dead-end state \(s\), returning \(h^C(s) = \infty\), if \(s\) has no solution even when allowing to break up conjunctive subgoals into the elements of \(C\). Our key idea is to learn \(C\) during search. Whenever forward search has identified an unrecognized dead-end \(s\), where \(h^C(s) < \infty\), we analyze the situation at \(s\), and add new conjunctions into \(C\) in a way guaranteeing to obtain \(h^C(s) = \infty\). Thus we learn to recognize \(s\), as well as similar dead-ends search may encounter in the future. We furthermore learn clauses where \(s^\prime \nvDash \phi\) implies \(h^C(s^\prime) = \infty\), to avoid the overhead of computing \(h^C\) on every search state. Arranging these techniques in a depth-first search, we obtain an algorithm approaching the elegance of nogood learning in constraint satisfaction, learning to refute search subtrees.
We run comprehensive experiments on solvable and unsolvable planning benchmarks. In cases where forward search can identify dead-ends, and where \(h^C\) dead-end detection is effective, our techniques reduce the depth-first search space size by several orders of magnitude, and often result in state-of-the-art performance.
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dechter, R., Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition, Artif. Intell., 41, 273-312, (1990)
[2] Prosser, P., Hybrid algorithms for the constraint satisfaction problem, Comput. Intell., 9, 268-299, (1993)
[3] Marques-Silva, J.; Sakallah, K., GRASP: a search algorithm for propositional satisfiability, IEEE Trans. Comput., 48, 506-521, (1999) · Zbl 1392.68388
[4] Moskewicz, M.; Madigan, C.; Zhao, Y.; Zhang, L.; Malik, S., Chaff: engineering an efficient SAT solver, (Proceedings of the 38th Conference on Design Automation, DAC-01, (2001), IEEE Computer Society Las Vegas, Nevada, USA)
[5] Dechter, R.; Frost, D., Backjump-based backtracking for constraint satisfaction problems, Artif. Intell., 136, 147-188, (2002) · Zbl 0995.68102
[6] Eén, N.; Sörensson, N., An extensible sat-solver, (Proceedings of the 6th International Conference Theory and Applications of Satisfiability Testing, SAT’03, (2003)), 502-518 · Zbl 1204.68191
[7] Beame, P.; Kautz, H. A.; Sabharwal, A., Towards understanding and harnessing the potential of clause learning, J. Artif. Intell. Res., 22, 319-351, (2004) · Zbl 1080.68651
[8] Kautz, H.; Selman, B., Unifying SAT-based and graph-based planning, (Pollack, M., Proceedings of the 16th International Joint Conference on Artificial Intelligence, IJCAI’99, (1999), Morgan Kaufmann Stockholm, Sweden), 318-325
[9] Rintanen, J.; Heljanko, K.; Niemelä, I., Planning as satisfiability: parallel plans and algorithms for plan search, Artif. Intell., 170, 1031-1080, (2006) · Zbl 1131.68099
[10] Blum, A. L.; Furst, M. L., Fast planning through planning graph analysis, Artif. Intell., 90, 279-298, (1997) · Zbl 1017.68533
[11] Long, D.; Fox, M., Efficient implementation of the plan graph in STAN, J. Artif. Intell. Res., 10, 87-115, (1999) · Zbl 0914.68180
[12] Kambhampati, S., Planning graph as a (dynamic) CSP: exploiting EBL, DDB and other CSP search techniques in graphplan, J. Artif. Intell. Res., 12, 1-34, (2000) · Zbl 0940.68100
[13] Bradley, A. R., Sat-based model checking without unrolling, (Proceedings of the 12th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI’11, (2011)), 70-87 · Zbl 1317.68109
[14] Suda, M., Property directed reachability for automated planning, J. Artif. Intell. Res., 50, 265-319, (2014) · Zbl 1361.68208
[15] Minton, S.; Carbonell, J. G.; Knoblock, C. A.; Kuokka, D.; Etzioni, O.; Gil, Y., Explanation-based learning: a problem solving perspective, Artif. Intell., 40, 63-118, (1989)
[16] Kambhampati, S.; Katukam, S.; Qu, Y., Failure driven dynamic search control for partial order planners: an explanation based approach, Artif. Intell., 88, 253-315, (1996) · Zbl 0907.68176
[17] Kambhampati, S., On the relations between intelligent backtracking and failure-driven explanation-based learning in constraint satisfaction and planning, Artif. Intell., 105, 161-208, (1998) · Zbl 0909.68139
[18] Bhatnagar, N.; Mostow, J., On-line learning from search failures, Mach. Learn., 15, 69-117, (1994)
[19] Kolobov, A.; Mausam; Weld, D. S., Discovering hidden structure in factored mdps, Artif. Intell., 189, 19-47, (2012) · Zbl 1251.68206
[20] Korf, R. E., Real-time heuristic search, Artif. Intell., 42, 189-211, (1990) · Zbl 0718.68082
[21] Reinefeld, A.; Marsland, T. A., Enhanced iterative-deepening search, IEEE Trans. Pattern Anal. Mach. Intell., 16, 701-710, (1994)
[22] Barto, A. G.; Bradtke, S. J.; Singh, S. P., Learning to act using real-time dynamic programming, Artif. Intell., 72, 81-138, (1995)
[23] Bonet, B.; Geffner, H., Learning depth-first search: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to mdps, (Long, D.; Smith, S., Proceedings of the 16th International Conference on Automated Planning and Scheduling, ICAPS’06, (2006), Morgan Kaufmann Ambleside, UK), 142-151
[24] Smith, D. E., Choosing objectives in over-subscription planning, (Koenig, S.; Zilberstein, S.; Koehler, J., Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS’04, (2004), Morgan Kaufmann Whistler, Canada), 393-401
[25] Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; Dimopoulos, Y., Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artif. Intell., 173, 619-668, (2009) · Zbl 1191.68634
[26] Domshlak, C.; Mirkis, V., Deterministic oversubscription planning as heuristic search: abstractions and reformulations, J. Artif. Intell. Res., 52, 97-169, (2015) · Zbl 1314.68291
[27] Haslum, P.; Geffner, H., Heuristic planning with time and resources, (Cesta, A.; Borrajo, D., Proceedings of the 6th European Conference on Planning, ECP’01, (2001), Springer-Verlag), 121-132
[28] Nakhost, H.; Hoffmann, J.; Müller, M., Resource-constrained planning: a Monte Carlo random walk approach, (Bonet, B.; McCluskey, L.; Silva, J. R.; Williams, B., Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS’12, (2012), AAAI Press), 181-189
[29] Coles, A. J.; Coles, A.; Fox, M.; Long, D., A hybrid LP-RPG heuristic for modelling numeric resource flows in planning, J. Artif. Intell. Res., 46, 343-412, (2013) · Zbl 1272.68371
[30] Junghanns, A.; Schaeffer, J., Sokoban: evaluating standard single-agent search techniques in the presence of deadlock, (Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, (1998)), 1-15
[31] Bjarnason, R.; Tadepalli, P.; Fern, A., Searching solitaire in real time, ICGA J., 30, 131-142, (2007)
[32] Behrmann, G.; Bengtsson, J.; David, A.; Larsen, K. G.; Pettersson, P.; Yi, W., UPPAAL implementation secrets, (Proceedings of the 7th International Symposium on Formal Techniques in Real-Time and Fault Tolerant Systems, (2002))
[33] Holzmann, G., The spin model checker - primer and reference manual, (2004), Addison-Wesley
[34] Edelkamp, S.; Lluch-Lafuente, A.; Leue, S., Directed explicit-state model checking in the validation of communication protocols, Int. J. Softw. Tools Technol. Transf., 5, 247-267, (2004)
[35] Bäckström, C.; Jonsson, P.; Ståhlberg, S., Fast detection of unsolvable planning instances using local consistency, (Helmert, M.; Röger, G., Proceedings of the 6th Annual Symposium on Combinatorial Search, SOCS’13, (2013), AAAI Press), 29-37
[36] Hoffmann, J.; Kissmann, P.; Torralba, Á., “distance”? who cares? tailoring merge-and-shrink heuristics to detect unsolvability, (Schaub, T., Proceedings of the 21st European Conference on Artificial Intelligence, ECAI’14, (2014), IOS Press Prague, Czech Republic) · Zbl 1366.68264
[37] Muise, C. J.; McIlraith, S. A.; Beck, J. C., Improved non-deterministic planning by exploiting state relevance, (Bonet, B.; McCluskey, L.; Silva, J. R.; Williams, B., Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS’12, (2012), AAAI Press)
[38] Camacho, A.; Muise, C.; McIlraith, S. A., From FOND to robust probabilistic planning: computing compact policies that bypass avoidable deadends, (Coles, A.; Coles, A.; Edelkamp, S.; Magazzeni, D.; Sanner, S., Proceedings of the 26th International Conference on Automated Planning and Scheduling, ICAPS’16, (2016), AAAI Press)
[39] Haslum, P.; Geffner, H., Admissible heuristics for optimal planning, (Chien, S.; Kambhampati, R.; Knoblock, C., Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS’00, (2000), AAAI Press Menlo Park, Breckenridge, CO), 140-149
[40] Bonet, B.; Geffner, H., Planning as heuristic search, Artif. Intell., 129, 5-33, (2001) · Zbl 0971.68146
[41] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, J. Artif. Intell. Res., 14, 253-302, (2001) · Zbl 0970.68044
[42] Edelkamp, S., Planning with pattern databases, (Cesta, A.; Borrajo, D., Proceedings of the 6th European Conference on Planning, ECP’01, (2001), Springer-Verlag), 13-24
[43] Helmert, M.; Domshlak, C., Landmarks, critical paths and abstractions: What’s the difference anyway?, (Gerevini, A.; Howe, A.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS’09, (2009), AAAI Press), 162-169
[44] Richter, S.; Westphal, M., The LAMA planner: guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res., 39, 127-177, (2010) · Zbl 1205.68383
[45] Helmert, M.; Haslum, P.; Hoffmann, J.; Nissim, R., Merge & shrink abstraction: a method for generating lower bounds in factored state spaces, J. Assoc. Comput. Mach., 61, (2014) · Zbl 1295.68189
[46] Dräger, K.; Finkbeiner, B.; Podelski, A., Directed model checking with distance-preserving abstractions, (Valmari, A., Proceedings of the 13th International SPIN Workshop, SPIN 2006, Lecture Notes in Computer Science, vol. 3925, (2006), Springer-Verlag), 19-34 · Zbl 1178.68338
[47] Helmert, M.; Haslum, P.; Hoffmann, J., Flexible abstraction heuristics for optimal sequential planning, (Boddy, M.; Fox, M.; Thiebaux, S., Proceedings of the 17th International Conference on Automated Planning and Scheduling, ICAPS’07, (2007), Morgan Kaufmann Providence, Rhode Island, USA), 176-183
[48] Dräger, K.; Finkbeiner, B.; Podelski, A., Directed model checking with distance-preserving abstractions, Int. J. Softw. Tools Technol. Transf., 11, 27-37, (2009)
[49] Torralba, Á.; Hoffmann, J.; Kissmann, P., MS-unsat and simulationdominance: merge-and-shrink and dominance pruning for proving unsolvability, (UIPC 2016 Planner Abstracts, (2016)), 12-15
[50] Pommerening, F.; Seipp, J., Fast downward dead-end pattern database, (UIPC 2016 Planner Abstracts, (2016)), 2
[51] Pommerening, F.; Helmert, M.; Röger, G.; Seipp, J., From non-negative to general operator cost partitioning, (Bonet, B.; Koenig, S., Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI’15, (2015), AAAI Press), 3335-3341
[52] Seipp, J.; Pommerening, F.; Helmert, M., New optimization functions for potential heuristics, (Brafman, R.; Domshlak, C.; Haslum, P.; Zilberstein, S., Proceedings of the 25th International Conference on Automated Planning and Scheduling, ICAPS’15, (2015), AAAI Press), 193-201
[53] Seipp, J.; Pommerening, F.; Sievers, S.; Wehrle, M., Fast downward aidos, (UIPC 2016 Planner Abstracts, (2016)), 28-38
[54] Steinmetz, M.; Hoffmann, J., Towards clause-learning state space search: learning to recognize dead-ends, (Schuurmans, D.; Wellman, M., Proceedings of the 30th AAAI Conference on Artificial Intelligence, AAAI’16, (2016), AAAI Press)
[55] Steinmetz, M.; Hoffmann, J., Clone: a critical-path driven clause learner, (UIPC 2016 Planner Abstracts, (2016)), 24-27
[56] Torralba, Á.; Alcázar, V., Constrained symbolic search: on mutexes, BDD minimization and more, (Helmert, M.; Röger, G., Proceedings of the 6th Annual Symposium on Combinatorial Search, SOCS’13, (2013), AAAI Press), 175-183
[57] Torralba, Á., Sympa: symbolic perimeter abstractions for proving unsolvability, (UIPC 2016 Planner Abstracts, (2016)), 8-11
[58] 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
[59] Gnad, D.; Steinmetz, M.; Jany, M.; Hoffmann, J.; Serina, I.; Gerevini, A., Partial delete relaxation, unchained: on intractable red-black planning and its applications, (Baier, J.; Botea, A., Proceedings of the 9th Annual Symposium on Combinatorial Search, SOCS’16, (2015), AAAI Press)
[60] Gnad, D.; Steinmetz, M.; Hoffmann, J., Django: unchaining the power of red-black planning, (UIPC 2016 Planner Abstracts, (2016)), 19-23
[61] Wehrle, M.; Helmert, M., Efficient stubborn sets: generalized algorithms and selection strategies, (Chien, S.; Do, M.; Fern, A.; Ruml, W., Proceedings of the 24th International Conference on Automated Planning and Scheduling, ICAPS’14, (2014), AAAI Press)
[62] Torralba, Á.; Hoffmann, J., Simulation-based admissible dominance pruning, (Yang, Q., Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI’15, (2015), AAAI Press/IJCAI), 1689-1695
[63] Torralba, Á.; Kissmann, P., Focusing on what really matters: irrelevance pruning in merge-and-shrink, (Lelis, L.; Stern, R., Proceedings of the 8th Annual Symposium on Combinatorial Search, SOCS’15, (2015), AAAI Press), 122-130
[64] Haslum, P., Improving heuristics through relaxed search - an analysis of TP4 and HSP*a in the 2004 planning competition, J. Artif. Intell. Res., 25, 233-267, (2006) · Zbl 1182.68062
[65] Haslum, P., \(h^m(P) = h^1(P^m)\): alternative characterisations of the generalisation from \(h^{\max}\) to \(h^m\), (Gerevini, A.; Howe, A.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS’09, (2009), AAAI Press), 354-357
[66] Haslum, P., Incremental lower bounds for additive cost planning problems, (Bonet, B.; McCluskey, L.; Silva, J. R.; Williams, B., Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS’12, (2012), AAAI Press), 74-82
[67] Keyder, E.; Hoffmann, J.; Haslum, P., Improving delete relaxation heuristics through explicitly represented conjunctions, J. Artif. Intell. Res., 50, 487-533, (2014) · Zbl 1367.68265
[68] Fickert, M.; Hoffmann, J.; Steinmetz, M., Combining the delete relaxation with critical-path heuristics: a direct characterization, J. Artif. Intell. Res., 56, 269-327, (2016) · Zbl 1362.68258
[69] Keyder, E.; Hoffmann, J.; Haslum, P., Semi-relaxed plan heuristics, (Bonet, B.; McCluskey, L.; Silva, J. R.; Williams, B., Proceedings of the 22nd International Conference on Automated Planning and Scheduling, ICAPS’12, (2012), AAAI Press), 128-136
[70] Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 165-204, (1994) · Zbl 0821.68065
[71] Hoffmann, J., Local search topology in planning benchmarks: an empirical analysis, (Nebel, B., Proceedings of the 17th International Joint Conference on Artificial Intelligence, IJCAI’01, (2001), Morgan Kaufmann Seattle, Washington, USA), 453-458
[72] Hoffmann, J., Where ‘ignoring delete lists’ works: local search topology in planning benchmarks, J. Artif. Intell. Res., 24, 685-758, (2005) · Zbl 1080.68668
[73] Hoffmann, J.; Fickert, M., Explicit conjunctions w/o compilation: computing \(h^{\operatorname{FF}}(\operatorname{\Pi}^C)\) in polynomial time, (Brafman, R.; Domshlak, C.; Haslum, P.; Zilberstein, S., Proceedings of the 25th International Conference on Automated Planning and Scheduling, ICAPS’15, (2015), AAAI Press)
[74] Nilsson, N. J., Problem solving methods in artificial intelligence, (1971), McGraw-Hill
[75] Jiménez, P.; Torras, C., An efficient algorithm for searching implicit AND/OR graphs with cycles, Artif. Intell., 124, 1, 1-30, (2000) · Zbl 0957.68034
[76] Bonet, B.; Geffner, H., Labeled RTDP: improving the convergence of real-time dynamic programming, (Giunchiglia, E.; Muscettola, N.; Nau, D., Proceedings of the 13th International Conference on Automated Planning and Scheduling, ICAPS’03, (2003), Morgan Kaufmann Trento, Italy), 12-21
[77] Tarjan, R. E., Depth first search and linear graph algorithms, SIAM J. Comput., 1, 146-160, (1972) · Zbl 0251.05107
[78] Bonet, B.; Geffner, H., Faster heuristic search algorithms for planning with uncertainty and full feedback, (Gottlob, G., Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI’03, (2003), Morgan Kaufmann Acapulco, Mexico), 1233-1238
[79] Helmert, M., The fast downward planning system, J. Artif. Intell. Res., 26, 191-246, (2006) · Zbl 1182.68245
[80] Helmert, M., Concise finite-domain representations for PDDL planning tasks, Artif. Intell., 173, 503-535, (2009) · Zbl 1191.68635
[81] Gnad, D.; Torralba, Á.; Hoffmann, J.; Wehrle, M., Decoupled search for proving unsolvability, (UIPC 2016 Planner Abstracts, (2016)), 16-18
[82] Valmari, A., Stubborn sets for reduced state space generation, (Proceedings of the 10th International Conference on Applications and Theory of Petri Nets, (1989)), 491-515
[83] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35, 677-691, (1986) · Zbl 0593.94022
[84] Edelkamp, S.; Helmert, M., Exhibiting knowledge in planning problems to minimize state encoding length, (Biundo, S.; Fox, M., Proceedings of the 5th European Conference on Planning, ECP’99, (1999), Springer-Verlag), 135-147
[85] Balyo, T.; Suda, M., Reachlunch entering the unsolvability IPC 2016, (UIPC 2016 Planner Abstracts, (2016)), 3-5
[86] Seipp, J.; Helmert, M., Counterexample-guided Cartesian abstraction refinement, (Borrajo, D.; Fratini, S.; Kambhampati, S.; Oddi, A., Proceedings of the 23rd International Conference on Automated Planning and Scheduling, ICAPS’13, (2013), AAAI Press Rome, Italy), 347-351
[87] Seipp, J.; Helmert, M., Diverse and additive Cartesian abstraction heuristics, (Chien, S.; Do, M.; Fern, A.; Ruml, W., Proceedings of the 24th International Conference on Automated Planning and Scheduling, ICAPS’14, (2014), AAAI Press)
[88] Gnad, D.; Hoffmann, J., Beating LM-cut with \(h^{m a x}\) (sometimes): fork-decoupled state space search, (Brafman, R.; Domshlak, C.; Haslum, P.; Zilberstein, S., Proceedings of the 25th International Conference on Automated Planning and Scheduling, ICAPS’15, (2015), AAAI Press)
[89] Gnad, D.; Hoffmann, J., Red-black planning: a new tractability analysis and heuristic function, (Lelis, L.; Stern, R., Proceedings of the 8th Annual Symposium on Combinatorial Search, SOCS’15, (2015), AAAI Press)
[90] Korovin, K.; Suda, M., Iproverplan: a system description, (UIPC 2016 Planner Abstracts, (2016)), 6-7
[91] Haslum, P., Adapting \(h^{+ +}\) for proving plan non-existence, (UIPC 2016 Planner Abstracts, (2016)), 1
[92] Hoffmann, J., Analyzing search topology without running any search: on the connection between causal graphs and \(h^+\), J. Artif. Intell. Res., 41, 155-229, (2011) · Zbl 1218.68160
[93] Laborie, P.; Ghallab, M., Planning with sharable resource constraints, (Mellish, S., Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI’95, (1995), Morgan Kaufmann Montreal, Canada), 1643-1649
[94] Koehler, J., Planning under resource constraints, (Prade, H., Proceedings of the 13th European Conference on Artificial Intelligence, ECAI’98, (1998), Wiley Brighton, UK), 489-493
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.