zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

68T20AI problem solving (heuristics, search strategies, etc.)
68R10Graph theory in connection with computer science (including graph drawing)
Full Text: DOI
[1] Barrett, A.; Weld, D. S.: Partial-order planning: evaluating possible efficiency gains. Artif. intell. 67, 71-112 (1994) · Zbl 0807.68080 · doi:10.1016/0004-3702(94)90012-4
[2] Blum, A.; Furst, M.: Fast planning through planning graph analysis. Proceedings IJCAI-95, 1636-1642 (1995)
[3] Bylander, T.: The computational complexity of propositional STRIPS planning. Artif. intell. 69, 165-204 (1994) · Zbl 0821.68065 · doi:10.1016/0004-3702(94)90081-7
[4] J. Carbonell, personal communication, 1994.
[5] Chapman, D.: Planning for conjunctive goals. Artif. intell. 32, 333-377 (1987) · Zbl 0642.68171 · doi:10.1016/0004-3702(87)90092-0
[6] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.: Introduction to algorithms. (1990) · Zbl 1158.68538
[7] Etzioni, O.: A structural theory of explanation-based learning. Phd thesis (1990)
[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 · doi:10.1016/0004-3702(71)90010-5
[9] Goldberg, A. V.; Tarjan, R. E.: A new approach to the maximum flow problem. Proceedings eighteenth ACM symposium on theory of computing, 136-146 (1986)
[10] Knoblock, C. A.: Generating parallel execution plans with a partial-order planner. Proceedings AIPS-94, 98-103 (1994)
[11] Mcallester, D.; Rosenblitt, D.: Systematic nonlinear planning. Proceedings AAAI-91, 634-639 (1991)
[12] Srinivasan, R.; Howe, A.: Comparison of methods for improving search efficiency in a partial-order planner. Proceedings IJCAI-95, 1620-1626 (1995)
[13] Stone, P.; Veloso, M.; Blythe, J.: The need for different domain-independent heuristics. Proceedings AIPS-94, 164-169 (1994)
[14] Veloso, M.; Blythe, J.: Linkability: examining causal link commitments in partial-order planning. Proceedings AIPS-94, 164-169 (1994)
[15] Weld, D. S.: An introduction to least-commitment planning. AI magazine 15, No. 4, 27-61 (1994)