Accession Number : ADA303260

Title :   Fast Planning Through Planning Graph Analysis.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Blum, Avrim L. ; Furst, Merrick L.

PDF Url : ADA303260

Report Date : DEC 1995

Pagination or Media Count : 23

Abstract : We introduce a new approach to planning in STRIP S-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. (AN)

Descriptors :   *ARTIFICIAL INTELLIGENCE, ALGORITHMS, OPTIMIZATION, GRAPHS, LEARNING MACHINES, PROBLEM SOLVING, APPROXIMATION(MATHEMATICS), PLANNING, HEURISTIC METHODS, DYNAMIC PROGRAMMING, C PROGRAMMING LANGUAGE.

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE