Fast Planning Through Planning Graph Analysis

@inproceedings{citeulike:557547, abstract = {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 shortestpossible 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...}, author = {Blum, Avrim and Furst, Merrick }, booktitle = {Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 95)}, citeulike-article-id = {557547}, comment = {This proposal represents a planning problem as a directed graph in which nodes may be partitioned into levels such that all edges are from one level to the next. Nodes in the 0th and all even levels consist of atoms and those in the odd levels represent operators. The initial level is exactly those atoms which are true in the initial state of the problem. Subsequent odd levels of the graph are generated by including a node for each legal operator instantiation from the atoms of the previous state, as well as a no-op for each atom in the previous level. Subsequent even levels of the graph are generated by including a node for each atom that is in an add list of of an operator instantiation from the previous level, as well as all atoms in earlier even states. Edges are added from each atom in an even-numbered level to the operators in the next level for which it is a precondition. Edges are added from each operator in an odd-numbered level to each atom in the following level that is a member of its add list. A different type of edge is added from each operator in an odd-numbered level to each atom in the following level that is a member of its delete list. Furthermore, exclusivity constraints are noted between actions that may not be undertaken simultaneously and between atoms that may not be simultaneously true. When a level contains all atoms that are goals of the problem, there may be a solution to the problem. If possible, a plan is generated by walking backwards through the levels, selecting actions that cause goals to be true and making the preconditions of those actions new goals, while not selecting any exclusive actions. I understand and accept the basic premise of this algorithm, but I had difficulty working through an example in practice because it is not clear exactly now exclusivity and the inclusion of no-ops works. I have not taken the time to thoroughly study the author's claims about complexity, but am satisfied that they have shown their system to be empirically much faster than other known planning systems of the day.}, keywords = {planning}, pages = {1636--1642}, posted-at = {2006-09-26 19:05:49}, priority = {0}, title = {Fast Planning Through Planning Graph Analysis}, url = {http://citeseer.ist.psu.edu/blum95fast.html}, year = {1995} }

TY - CONF ID - citeulike:557547 L3 - citeulike-article-id:557547 TI - Fast Planning Through Planning Graph Analysis T2 - Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 95) SP - 1636 EP - 1642 N2 - 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 shortestpossible 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... KW - planning N1 - This proposal represents a planning problem as a directed graph in which nodes may be partitioned into levels such that all edges are from one level to the next. Nodes in the 0th and all even levels consist of atoms and those in the odd levels represent operators. The initial level is exactly those atoms which are true in the initial state of the problem. Subsequent odd levels of the graph are generated by including a node for each legal operator instantiation from the atoms of the previous state, as well as a no-op for each atom in the previous level. Subsequent even levels of the graph are generated by including a node for each atom that is in an add list of of an operator instantiation from the previous level, as well as all atoms in earlier even states. Edges are added from each atom in an even-numbered level to the operators in the next level for which it is a precondition. Edges are added from each operator in an odd-numbered level to each atom in the following level that is a member of its add list. A different type of edge is added from each operator in an odd-numbered level to each atom in the following level that is a member of its delete list. Furthermore, exclusivity constraints are noted between actions that may not be undertaken simultaneously and between atoms that may not be simultaneously true. When a level contains all atoms that are goals of the problem, there may be a solution to the problem. If possible, a plan is generated by walking backwards through the levels, selecting actions that cause goals to be true and making the preconditions of those actions new goals, while not selecting any exclusive actions. I understand and accept the basic premise of this algorithm, but I had difficulty working through an example in practice because it is not clear exactly now exclusivity and the inclusion of no-ops works. I have not taken the time to thoroughly study the author's claims about complexity, but am satisfied that they have shown their system to be empirically much faster than other known planning systems of the day. AU - Blum, Avrim AU - Furst, Merrick PY - 1995/// UR - http://citeseer.ist.psu.edu/blum95fast.html ER -