×

Fast planning through planning graph analysis. (English) Zbl 1017.68533

Summary: We introduce a new approach to planning in STRIPS-like domains based on constructing and analyzing a compact structure we call a planning graph. We describe a new planner, Graphplan, that uses this paradigm. Graphplan always returns a shortest possible partial-order plan, or states that no valid plan exists.
We provide empirical evidence in favor of this approach, showing that Graphplan outperforms the total-order planner, Prodigy, and the partial-order planner, UCPOP, on a variety of interesting natural and artificial planning problems. We also give empirical evidence that the plans produced by Graphplan are quite sensible. Since searches made by this approach are fundamentally different from the searches of other common planning methods, they provide a new perspective on the planning problem.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68R10 Graph theory (including graph drawing) in computer science

Software:

Graphplan; UCPOP; Prodigy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barrett, A.; Weld, D. S., Partial-order planning: evaluating possible efficiency gains, Artif. Intell., 67, 71-112 (1994) · Zbl 0807.68080
[2] Blum, A.; Furst, M., Fast planning through planning graph analysis, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1636-1642 · Zbl 0770.46035
[3] Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 165-204 (1994) · Zbl 0821.68065
[4] J. Carbonell, personal communication, 1994.; J. Carbonell, personal communication, 1994.
[5] Chapman, D., Planning for conjunctive goals, Artif. Intell., 32, 333-377 (1987) · Zbl 0642.68171
[6] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., (Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge), MA/McGraw-Hill, New York · Zbl 1158.68538
[7] Etzioni, O., A structural theory of explanation-based learning, (PhD thesis (1990), Carnegie Mellon University: Carnegie Mellon University Pittsburgh, PA), CMU-CS-90-185
[8] Fikes, R. E.; Nilsson, N. J., STRIPS: a new approach to the application of theorem proving to problem solving, Artif. Intell., 2, 189-208 (1971) · Zbl 0234.68036
[9] Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum flow problem, (Proceedings Eighteenth ACM Symposium on Theory of Computing. Proceedings Eighteenth ACM Symposium on Theory of Computing, Berkeley, CA (1986)), 136-146
[10] Knoblock, C. A., Generating parallel execution plans with a partial-order planner, (Proceedings AIPS-94. Proceedings AIPS-94, Chicago, IL (1994)), 98-103
[11] McAllester, D.; Rosenblitt, D., Systematic nonlinear planning, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 634-639
[12] Srinivasan, R.; Howe, A., Comparison of methods for improving search efficiency in a partial-order planner, (Proceedings IJCAI-95. Proceedings IJCAI-95, Montreal, Que. (1995)), 1620-1626
[13] Stone, P.; Veloso, M.; Blythe, J., The need for different domain-independent heuristics, (Proceedings AIPS-94. Proceedings AIPS-94, Chicago, IL (1994)), 164-169
[14] Veloso, M.; Blythe, J., Linkability: examining causal link commitments in partial-order planning, (Proceedings AIPS-94. Proceedings AIPS-94, Chicago, IL (1994)), 164-169
[15] Weld, D. S., An introduction to least-commitment planning, AI Magazine, 15, 4, 27-61 (1994)
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.