×

zbMATH — the first resource for mathematics

Red-black planning: a new systematic approach to partial delete relaxation. (English) Zbl 1328.68194
Summary: To date, delete relaxation underlies some of the most effective heuristics for deterministic planning. Despite its success, however, delete relaxation has significant pitfalls in many important classes of planning domains, and it has been a challenge from the outset to devise heuristics that take some deletes into account. We herein devise an elegant and simple method for doing just that. In the context of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red-black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. We investigate the tractability region of red-black planning, extending H. Chen and O. Giménez’ characterization theorems for regular planning to the more general red-black setting [J. Comput. Syst. Sci. 76, No. 7, 579–592 (2010; Zbl 1197.68069)]. In particular, we identify significant islands of tractable red-black planning, use them to design practical heuristic functions, and experiment with a range of “painting strategies” for automatically choosing the red variables. Our experiments show that these new heuristic functions can improve significantly on the state of the art in satisficing planning.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Citations:
Zbl 1197.68069
Software:
UCPOP; TorchLight; SAPA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Katz, M.; Hoffmann, J.; Domshlak, C., Who said we need to relax all variables?, (Borrajo, D.; Fratini, S.; Kambhampati, S.; Oddi, A., Proceedings of the 23rd International Conference on Automated Planning and Scheduling, ICAPS’13, Rome, Italy, (2013), AAAI Press), 126-134
[2] Katz, M.; Hoffmann, J.; Domshlak, C., Red-black relaxed plan heuristics, (desJardins, M.; Littman, M., Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI’13, Bellevue, WA, USA, (2013), AAAI Press), 489-495
[3] Katz, M.; Hoffmann, J., Red-black relaxed plan heuristics reloaded, (Helmert, M.; Röger, G., Proceedings of the 6th Annual Symposium on Combinatorial Search, SOCS’13, (2013), AAAI Press), 105-113
[4] McDermott, D. V., Using regression-match graphs to control search in planning, Artif. Intell., 109, 111-159, (1999) · Zbl 0916.68145
[5] Bonet, B.; Geffner, H., Planning as heuristic search, Artif. Intell., 129, 5-33, (2001) · Zbl 0971.68146
[6] 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
[7] Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 165-204, (1994) · Zbl 0821.68065
[8] Hoffmann, J., Where ‘ignoring delete lists’ works: local search topology in planning benchmarks, J. Artif. Intell. Res., 24, 685-758, (2005) · Zbl 1080.68668
[9] Helmert, M.; Mattmüller, R., Accuracy of admissible heuristic functions in selected planning domains, (Fox, D.; Gomes, C., Proceedings of the 23rd National Conference of the American Association for Artificial Intelligence, AAAI-08, Chicago, Illinois, USA, (2008), AAAI Press), 938-943
[10] Gerevini, A.; Saetti, A.; Serina, I., Planning through stochastic local search and temporal action graphs, J. Artif. Intell. Res., 20, 239-290, (2003) · Zbl 1058.68103
[11] 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
[12] Helmert, M., A planning heuristic based on causal graph analysis, (Koenig, S.; Zilberstein, S.; Koehler, J., Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS’04, Whistler, Canada, (2004), Morgan Kaufmann), 161-170
[13] Coles, A.; Fox, M.; Long, D.; Smith, A., A hybrid relaxed planning graph’LP heuristic for numeric planning domains, (Rintanen, J.; Nebel, B.; Beck, J. C.; Hansen, E., Proceedings of the 18th International Conference on Automated Planning and Scheduling, ICAPS’08, (2008), AAAI Press), 52-59
[14] 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
[15] 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
[16] Do, M. B.; Kambhampati, S., Sapa: a domain-independent heuristic metric temporal planner, (Cesta, A.; Borrajo, D., Recent Advances in AI Planning. 6th European Conference on Planning, ECP-01, Toledo, Spain, Lecture Notes in Artificial Intelligence, (2001), Springer-Verlag), 109-120
[17] van den Briel, M.; Benton, J.; Kambhampati, S.; Vossen, T., An LP-based heuristic for optimal planning, (Bessiere, C., Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming, CP’07, Lecture Notes in Computer Science, vol. 4741, (2007), Springer-Verlag), 651-665 · Zbl 1145.68537
[18] Baier, J. A.; Botea, A., Improving planning performance using low-conflict relaxed plans, (Gerevini, A.; Howe, A.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS’09, (2009), AAAI Press), 10-17
[19] Helmert, M.; Geffner, H., Unifying the causal graph and additive heuristics, (Rintanen, J.; Nebel, B.; Beck, J. C.; Hansen, E., Proceedings of the 18th International Conference on Automated Planning and Scheduling, ICAPS’08, (2008), AAAI Press), 140-147
[20] Cai, D.; Hoffmann, J.; Helmert, M., Enhancing the context-enhanced additive heuristic with precedence constraints, (Gerevini, A.; Howe, A.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS’09, (2009), AAAI Press), 50-57
[21] Fox, M.; Long, D., Hybrid STAN: identifying and managing combinatorial optimisation sub-problems in planning, (Nebel, B., Proceedings of the 17th International Joint Conference on Artificial Intelligence, IJCAI-01, Seattle, Washington, USA, (2001), Morgan Kaufmann), 445-450
[22] Fox, M.; Long, D., Stan4: a hybrid planning strategy based on subproblem abstraction, AI Mag., 22, 81-84, (2001)
[23] Keyder, E.; Geffner, H., Heuristics for planning with action costs revisited, (Ghallab, M., Proceedings of the 18th European Conference on Artificial Intelligence, ECAI-08, Patras, Greece, (2008), Wiley), 588-592
[24] 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
[25] 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
[26] 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
[27] Knoblock, C., Automatically generating abstractions for planning, Artif. Intell., 68, 243-302, (1994) · Zbl 0942.68712
[28] Brafman, R.; Domshlak, C., Structure and complexity in planning with unary operators, J. Artif. Intell. Res., 18, 315-349, (2003) · Zbl 1056.68129
[29] Helmert, M., The fast downward planning system, J. Artif. Intell. Res., 26, 191-246, (2006) · Zbl 1182.68245
[30] 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
[31] Kupferschmid, S.; Hoffmann, J.; Dierks, H.; Behrmann, G., Adapting an AI planning heuristic for directed model checking, (Valmari, A., Proceedings of the 13th International SPIN Workshop, SPIN 2006, Lecture Notes in Computer Science, vol. 3925, (2006), Springer-Verlag), 35-52 · Zbl 1178.68347
[32] Chen, H.; Giménez, O., Causal graphs and structurally restricted planning, J. Comput. Syst. Sci., 76, 579-592, (2010) · Zbl 1197.68069
[33] Seipp, J.; Helmert, M., Fluent merging for classical planning problems, (ICAPS 2011 Workshop on Knowledge Engineering for Planning and Scheduling, (2011)), 47-53
[34] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer-Verlag
[35] Koehler, J.; Hoffmann, J., On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm, J. Artif. Intell. Res., 12, 338-386, (2000) · Zbl 0946.68130
[36] 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
[37] Gerevini, A.; Schubert, L., Inferring state-constraints for domain independent planning, (Mostow, J.; Rich, C., Proceedings of the 15th National Conference of the American Association for Artificial Intelligence, AAAI’98, Madison, WI, USA, (1998), MIT Press), 905-912
[38] Fox, M.; Long, D., The automatic inference of state invariants in TIM, J. Artif. Intell. Res., 9, 367-421, (1998) · Zbl 0910.68199
[39] Rintanen, J., An iterative algorithm for synthesizing invariants, (Kautz, H. A.; Porter, B., Proceedings of the 17th National Conference of the American Association for Artificial Intelligence, AAAI-00, Austin, TX, USA, (2000), AAAI Press), 806-811
[40] Helmert, M., Concise finite-domain representations for PDDL planning tasks, Artif. Intell., 173, 503-535, (2009) · Zbl 1191.68635
[41] Williams, B. C.; Nayak, P. P., A reactive planner for a model-based executive, (Pollack, M., Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI-97, Nagoya, Japan, (1997), Morgan Kaufmann), 1178-1185
[42] Domshlak, C.; Dinitz, Y., Multi-agent offline coordination: structure and complexity, (Cesta, A.; Borrajo, D., Recent Advances in AI Planning. 6th European Conference on Planning, ECP-01, Toledo, Spain, Lecture Notes in Artificial Intelligence, (2001), Springer-Verlag), 34-43
[43] Hoffmann, J.; Porteous, J.; Sebastia, L., Ordered landmarks in planning, J. Artif. Intell. Res., 22, 215-278, (2004) · Zbl 1080.68670
[44] Karpas, E.; Domshlak, C., Cost-optimal planning with landmarks, (Boutilier, C., Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI 2009, Pasadena, California, USA, (2009), Morgan Kaufmann), 1728-1733
[45] 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
[46] Richter, S.; Helmert, M., Preferred operators and deferred evaluation in satisficing planning, (Gerevini, A.; Howe, A.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS’09, (2009), AAAI Press), 273-280
[47] Rintanen, J., Planning as satisfiability: heuristics, Artif. Intell., 193, 45-86, (2012) · Zbl 1270.68276
[48] Cenamor, I.; de la Rosa, T.; Fernández, F., IBACOP and IBACOP2 planner, (IPC 2014 Planner Abstracts, (2014)), 35-38
[49] Penberthy, J. S.; Weld, D. S., UCPOP: a sound, complete, partial order planner for ADL, (Nebel, B.; Swartout, W.; Rich, C., Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, KR-92, Cambridge, MA, (1992), Morgan Kaufmann), 103-114
[50] Nguyen, X.; Kambhampati, S., Reviving partial order planning, (Nebel, B., Proceedings of the 17th International Joint Conference on Artificial Intelligence, IJCAI-01, Seattle, Washington, USA, (2001), Morgan Kaufmann), 459-464
[51] Nakhost, H.; Müller, M., Action elimination and plan neighborhood graph search: two algorithms for plan improvement, (Brafman, R. I.; Geffner, H.; Hoffmann, J.; Kautz, H. A., Proceedings of the 20th International Conference on Automated Planning and Scheduling, ICAPS’10, (2010), AAAI Press), 121-128
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.