×

zbMATH — the first resource for mathematics

State agnostic planning graphs: deterministic, non-deterministic, and probabilistic planning. (English) Zbl 1216.68239
Summary: Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.
We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Keywords:
planning; heuristics
Software:
CUDD; Graphplan; STAN; VHPOP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Albore, H. Palacios, H. Geffner, A translation-based approach to contingent planning, in: Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, 2009, pp. 1623-1628.
[2] P. Bertoli, A. Cimatti, Improving heuristics for planning as search in belief space, in: Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, 2002, pp. 143-152.
[3] P. Bertoli, A. Cimatti, M. Roveri, P. Traverso, Planning in nondeterministic domains under partial observability via symbolic model checking, in: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001, pp. 473-478.
[4] A. Blum, M. Furst, Fast planning through planning graph analysis, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995, pp. 1636-1642.
[5] B. Bonet, H. Geffner, Planning as heuristic search: New results, in: Proceedings of the Fifth European Conference on Planning, 1999, pp. 360-372.
[6] R. Brafman, J. Hoffmann, Contingent planning via heuristic forward search with implicit belief states, in: Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling, 2005, pp. 71-80.
[7] Bryant, R., Graph-based algorithms for Boolean function manipulation, IEEE transactions on computing, C-35, 8, 677-691, (1986) · Zbl 0593.94022
[8] D. Bryce, Scalable planning under uncertainty, Ph.D. thesis, Arizona State University, May 2007.
[9] D. Bryce, O. Buffet (Eds.), The Uncertainty Part of the 6th International Planning Competition, 2008.
[10] D. Bryce, W. Cushing, S. Kambhampati, Model-lite planning: Diverse multi-option plans and dynamic objective functions, in: Proceedings of the 3rd Workshop on Planning and Plan Execution for Real-World Systems, 2007.
[11] Bryce, D.; Kambhampati, S., A tutorial on planning graph based reachability heuristics, AI magazine, 28, 1, 47-83, (2007)
[12] Bryce, D.; Kambhampati, S.; Smith, D., Planning graph heuristics for belief space search, Journal of artificial intelligence research, 26, 35-99, (2006) · Zbl 1182.68225
[13] D. Bryce, S. Kambhampati, D. Smith, Sequential Monte Carlo in probabilistic planning reachability heuristics, in: Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, 2006, pp. 233-242. · Zbl 1182.68226
[14] Bryce, D.; Kambhampati, S.; Smith, D., Sequential Monte Carlo in probabilistic planning reachability heuristics, Artificial intelligence, 172, 6-7, 685-715, (2008) · Zbl 1182.68226
[15] Culberson, J.C.; Schaeffer, J., Pattern databases, Computational intelligence, 14, 3, 318-334, (1998)
[16] W. Cushing, D. Bryce, State agnostic planning graphs, in: Proceedings of Twentieth National Conference on Artificial Intelligence, 2005, pp. 1131-1138.
[17] Darwiche, A.; Marquis, P., A knowledge compilation map, Journal of artificial intelligence research, 17, 229-264, (2002) · Zbl 1045.68131
[18] de Kleer, J., An assumption-based TMS, Artificial intelligence, 28, 2, 127-162, (1986)
[19] C. Domshlak, J. Hoffmann, Fast probabilistic planning through weighted model counting, in: Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, 2006, pp. 243-251.
[20] Doucet, A.; de Freitas, N.; Gordon, N., Sequential Monte Carlo methods in practice, (2001), Springer New York · Zbl 0967.00022
[21] S. Edelkamp, Planning with pattern databases, in: Proceedings of the 6th European Conference on Planning, 2001, pp. 13-24.
[22] A. Gerevini, B. Bonet, R. Givan (Eds.), 5th International Planning Competition, Cumbria, UK, 2006.
[23] Gerevini, A.; Saetti, A.; Serina, I., Planning through stochastic local search and temporal action graphs in LPG, Journal of artificial intelligence research, 20, 239-290, (2003) · Zbl 1058.68103
[24] J. Hoffmann, R. Brafman, Conformant planning via heuristic forward search: A new approach, in: Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling, 2004, pp. 355-364. · Zbl 1131.68525
[25] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, Journal of artificial intelligence research, 14, 253-302, (2001) · Zbl 0970.68044
[26] J. Huang, Combining knowledge compilation and search for efficient conformant probabilistic planning, in: Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, 2006, pp. 253-262.
[27] N. Hyafil, F. Bacchus, Conformant probabilistic planning via CSPs, in: Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling, 2003, pp. 205-214.
[28] N. Hyafil, F. Bacchus, Utilizing structured representations and CSPs in conformant probabilistic planning, in: Proceedings of the Sixteenth European Conference on Artificial Intelligence, 2004, pp. 1033-1034.
[29] S. Kambhampati, E. Parker, E. Lambrecht, Understanding and extending graphplan, in: Proceedings of Fourth European Conference on Planning, 1997, pp. 260-272.
[30] J. Koehler, B. Nebel, J. Hoffmann, Y. Dimopoulos, Extending planning graphs to an ADL subset, in: Proceedings of Fourth European Conference on Planning, 1997, pp. 273-285.
[31] U. Kuter, D.S. Nau, E. Reisner, R.P. Goldman, Using classical planners to solve nondeterministic planning problems, in: Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling, 2008, pp. 190-197.
[32] I. Little, D. Aberdeen, S. Theibaux, Prottle: A probabilistic temporal planner, in: Proceedings of the Twentieth National Conference on Artificial Intelligence, 2005, pp. 1181-1186.
[33] Y. Liu, S. Koenig, D. Furcy, Speeding up the calculation of heuristics for heuristic search-based planning, in: Proceedings of the Eighteenth National Conference on Artificial Intelligence, 2002, pp. 484-491.
[34] Long, D.; Fox, M., Efficient implementation of the plan graph in STAN, Journal of artificial intelligence research, 10, 87-115, (1999) · Zbl 0914.68180
[35] Long, D.; Fox, M., The 3rd international planning competition: results and analysis, Journal of artificial intelligence research, 20, 1-59, (2003) · Zbl 1036.68097
[36] McDermott, D.V., Using regression-match graphs to control search in planning, Artificial intelligence, 109, 1-2, 111-159, (1999) · Zbl 0916.68145
[37] Nguyen, X.; Kambhampati, S.; Nigenda, R.S., Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search, Artificial intelligence, 135, 1-2, 73-123, (2002) · Zbl 0984.68140
[38] Nilsson, N., Principles of artificial intelligence, (1980), Morgan Kaufmann · Zbl 0422.68039
[39] Palacios, H.; Geffner, H., Compiling uncertainty away: solving conformant planning problems using a classical planner (sometimes), (), 900-905
[40] R. Petrick, F. Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, 2002, pp. 212-222.
[41] Refanidis, I.; Vlahavas, I., The GRT planning system: backward heuristic construction in forward state-space planning, Journal of artificial intelligence research, 15, 115-161, (2001) · Zbl 0994.68136
[42] J. Rintanen, Expressive equivalence of formalisms for planning with sensing, in: Proceedings of the Thirteenth International Conference on Automated Planning and Scheduling, 2003, pp. 185-194.
[43] J. Rintanen, Conditional planning in the discrete belief space, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, 2005, pp. 1260-1265.
[44] M. Schoppers, Universal plans for reactive robots in unpredictable environments, in: Proceedings of the Tenth International Joint Conference on Artificial Intelligence, 1987, pp. 1039-1046.
[45] D. Smith, D. Weld, Conformant graphplan, in: Proceedings of the Fifteenth National Conference on Artificial Intelligence, 1998, pp. 889-896.
[46] Somenzi, F., CUDD: CU decision diagram package release 2.3.0, (1998), University of Colorado at Boulder
[47] F. Teichteil-Konigsbuch, U. Kuter, G. Infantes, Execution-aware MDP planning: Generating policies with low execution-failure probabilities, Tech. Rep., University of Maryland, Department of Computer Science, CS-TR-4942, 2009.
[48] D.-V. Tran, H.-K. Nguyen, E. Pontelli, T.C. Son, Improving performance of conformant planners: Static analysis of declarative planning domain specifications, in: Proceedings of the Eleventh International Symposium on Practical Aspects of Declarative Languages, 2009, pp. 239-253.
[49] D. Weld, C. Anderson, D. Smith, Extending graphplan to handle uncertainty and sensing actions, in: Proceedings of the Fifteenth National Conference on Artificial Intelligence, 1998, pp. 897-904.
[50] S. Yoon, A. Fern, R. Givan, S. Kambhampati, Probabilistic planning via determinization in hindsight, in: Proceedings of the Twenty-Third National Conference on Artificial intelligence, 2008, pp. 1010-1016.
[51] Younes, H.; Simmons, R., VHPOP: versatile heuristic partial order planner, Journal of artificial intelligence research, 20, 405-430, (2003) · Zbl 1036.68107
[52] Zimmerman, T.; Kambhampati, S., Using memory to transform search on the planning graph, Journal of artificial intelligence research, 23, 533-585, (2005) · Zbl 1080.68678
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.