Fast Planning Through Planning Graph Analysis-英文文献.pdf

Fast Planning Through Planning Graph Analysis  Avrim L Blum Merrick L Furst Scho ol of Computer Science Scho ol of Computer Science Carnegie Mellon University Carnegie Mellon University Pittsburgh PA Pittsburgh PA avrimcscmu edu mxfcscmu edu Final version in A rticial Intel ligenc e Abstract We intro duce a new approach to planning in STRIPSlike domains based on con structing and analyzing a compact structure we call a Planning Graph We describ e a new planner Graphplan that uses this paradigm Graphplan always returns a shortest p ossible partialorder plan or states that no valid plan exists We provide empirical evidence in favor of this approach showing that Graphplan outp erforms the totalorder planner Pro digy and the partialorder planner UCPOP on a variety of interesting natural and articial planning problems We also give empir ical evidence that the plans pro duced by Graphplan are quite sensible Since searches made by this approach are fundamentally dierent from the searches of other common planning metho ds they provide a new p ersp ective on the planning problem Keywords General Purp ose Planning STRIPS Planning Graph Algorithms Planning Graph Analysis Intro duction In this pap er we intro duce a new planner Graphplan which plans in STRIPSlike domains The algorithm is based on a paradigm we call Planning Graph Analysis In this approach rather than immediately embarking up on a search as in standard planning metho ds the algorithm instead b egins by explicitly constructing a compact