×

zbMATH — the first resource for mathematics

On the completeness of pruning techniques for planning with conditional effects. (English) Zbl 1299.90387
Summary: Pruning techniques and heuristics are two keys to the heuristic search-based planning. The helpful actions pruning (HAP) strategy and relaxed-plan-based heuristics are two representatives among those methods and are still popular in the state-of-the-art planners. Here, we present new analyses on the properties of HAP. Specifically, we show new reasons for which HAP can cause incompleteness of a search procedure. We prove that, in general, HAP is incomplete for planning with conditional effects if factored expansions of actions are used. To preserve completeness, we propose a pruning strategy that is based on relevance analysis and confrontation. We will show that both relevance analysis and confrontation are necessary. We call it the confrontation and goal relevant actions pruning (CGRAP) strategy. However, CGRAP is computationally hard to be exactly computed. Therefore, we suggest practical approximations from the literature.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory
Software:
Graphplan; MiniSat
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] H. Kautz and B. Selman, “Pushing the envelope: planning, propositional logic, and stochastic search,” in Proceedings of the 13th National Conference on Artificial Intelligence, pp. 1194-1201, August 1996.
[2] B. Bonet and H. Geffner, “Planning as heuristic search,” Artificial Intelligence, vol. 129, no. 1-2, pp. 5-33, 2001, Heuristic search in artificial intelligence. · Zbl 0971.68146 · doi:10.1016/S0004-3702(01)00108-4
[3] M. B. Do and S. Kambhampati, “Planning as constraint satisfaction: solving the planning graph by compiling it into CSP,” Artificial Intelligence, vol. 132, no. 2, pp. 151-182, 2001. · Zbl 0983.68181 · doi:10.1016/S0004-3702(01)00128-X
[4] N. Eén and A. Biere, “Effective preprocessing in SAT through variable and clause elimination,” in Theory and Applications of Satisfiability Testing, vol. 3569, pp. 61-75, Springer, Berlin, Germany, 2005. · Zbl 1128.68463 · doi:10.1007/b137280
[5] X. Li and M. Yin, “An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure,” Advances in Engineering Software, vol. 55, pp. 10-31, 2013.
[6] X. Li and M. Yin, “A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem,” Scientia Iranica, vol. 19, no. 6, pp. 1921-1935, 2012. · doi:10.1016/j.scient.2012.10.034
[7] D. Cai, J. Sun, and M. Yin, “Making FF faster in ADL domains,” in Proceedings of the 3rd International Conference on Natural Computation (ICNC ’07), vol. 2, pp. 160-164, August 2007. · doi:10.1109/ICNC.2007.464
[8] M. Katz, J. Hoffmann, and C. Domshlak, “Who said we need to relax all variables?” in Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS ’13), AAAI Press, 2013.
[9] P. H. Tu, T. C. Son, M. Gelfond, and A. R. Morales, “Approximation of action theories and its application to conformant planning,” Artificial Intelligence, vol. 175, no. 1, pp. 79-119, 2011. · Zbl 1230.68185 · doi:10.1016/j.artint.2010.04.007
[10] J. Rintanen, “Planning as satisfiability: heuristics,” Artificial Intelligence, vol. 193, pp. 45-86, 2012. · Zbl 1270.68276 · doi:10.1016/j.artint.2012.08.001
[11] J. Hoffmann and B. Nebel, “The FF planning system: fast plan generation through heuristic search,” Journal of Artificial Intelligence Research, vol. 14, pp. 253-302, 2001. · Zbl 0970.68044 · www.jair.org
[12] M. Helmert, “The fast downward planning system,” Journal of Artificial Intelligence Research, vol. 26, pp. 191-246, 2006. · Zbl 1182.68245 · www.jair.org
[13] J. Hoffmann and R. I. Brafman, “Conformant planning via heuristic forward search: a new approach,” Artificial Intelligence, vol. 170, no. 6-7, pp. 507-541, 2006. · Zbl 1131.68525 · doi:10.1016/j.artint.2006.01.003
[14] J. Hoffmann and R. Brafman, “Contingent planning via heuristic forward search with implicit belief states,” in Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS’ 05), vol. 2005, 2005.
[15] B. Bonet and E. Hansen, “Heuristic Search for Planning under Uncertainty,” in Heuristics, Probability and Causality: A Tribute To Judea Pearl, pp. 3-22, College Publications, 2010. · Zbl 1216.68237
[16] A. Gerevini, I. Serina, A. Saetti, and S. Spinoni, “Local search techniques for temporal planning in lpg,” in Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS ’03), pp. 62-72, 2003. · Zbl 1058.68103
[17] Y. Chen, B. W. Wah, and C.-W. Hsu, “Temporal planning using subgoal partitioning and resolution in SGPlan,” Journal of Artificial Intelligence Research, vol. 26, pp. 323-369, 2006. · Zbl 1182.68229 · www.jair.org
[18] S. Richter, M. Helmert, and M. Westphal, “Landmarks revisited,” in Proceedings of the 23rd AAAI Conference on Artificial Intelligence, pp. 975-982, July 2008.
[19] D. McDermott, “Using regression-match graphs to control search in planning,” Artificial Intelligence, vol. 109, no. 1, pp. 111-159, 1999. · Zbl 0916.68145 · doi:10.1016/S0004-3702(99)00010-7
[20] E. P. D. Pednault, “ADL: exploring the middle ground between STRIPS and the situation calculus,” in Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning, pp. 324-332, 1989.
[21] B. C. Gazen and C. A. Knoblock, “Combining the expressivity of ucpop with the efficiency of graphplan,” in Proceedings of the 4th European Conference on Planning (ECP ’97), pp. 221-233, 1997.
[22] J. Koehler, B. Nebel, J. Hoffmann, and Y. Dimopoulos, “Extending planning graphs to an adl subset,” in Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning (ECP ’97), pp. 273-285, 1997.
[23] C. R. Anderson, D. E. Smith, and D. S. Weld, “Conditional effects in graphplan,” in Proceedings of the AIPS, pp. 44-53, 1998.
[24] A. L. Blum and M. L. Furst, “Fast planning through planning graph analysis,” Artificial Intelligence, vol. 90, no. 1-2, pp. 281-300, 1997. · Zbl 1017.68533 · doi:10.1016/S0004-3702(96)00047-1
[25] D. S. Weld, “Introduction to least commitment planning,” AI Magazine, vol. 15, no. 4, pp. 27-61, 1994.
[26] B. Nebel, Y. Dimopoulos, and J. Koehler, “Ignoring irrelevant facts and operators in plan generation,” in Proceedings of the European Conference on Planning (ECP ’97), pp. 338-350, 1997.
[27] D. Cai, J. Hoffmann, and M. Helmert, “Enhancing the context-enhanced additive heuristic with precedence constraints,” in Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS ’09), pp. 50-57, grc, September 2009.
[28] C. Bäckström and B. Nebel, “Complexity results for SAS+ planning,” Computational Intelligence, vol. 11, no. 4, pp. 625-655, 1995. · doi:10.1111/j.1467-8640.1995.tb00052.x
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.