SHOP: Simple Hierarchical Ordered Planner Export

@techreport{citeulike:604605, author = {Nau, Dana and Cao, Yue and Lotem, Amnon and Munoz-Avila, Hector}, citeulike-article-id = {604605}, comment = {This paper describes the design of SHOP, a hierarchical planner. The principal differences between SHOP and most other planners are that SHOP uses hierarchical planning and that SHOP uses total-order forward search. The authors have found that domain-specific heuristics can be used to guide a forward search towards a goal significantly faster than partial-order planning, even though partial-order performs much better in the absence of these heuristics. These heuristics may only be used when the state of the world at a given plan step is known, which is not the case in partial-order planning. SHOP uses conjunctions of logical atoms to describe states, Horn clauses (\$x(Y) :- a(Y,2)\$) to describe axioms, and a set of variable assignments that satisfies these to ground statements. It defines operators as a primitive task, a set of atoms to remove from the world state, and a set of atoms to add to the world state. Operators do not contain preconditions because the order of operators within a method is fixed. A method is defined as a compound task, a precondition that is a conjunct of atoms, and an ordered list of subtasks. Every method in a planning problem must be explictly described in this manner, and there may be many methods for solving a given task. The planning process begins with the first high-level task to be completed. This task is decomposed into its subtasks, each of which is decomposed in order until they have been reduced to operators. Then the next task is decomposed. SHOP is written in Lisp, but it scales better with problem complexity than two partial-order planners known for their speed. In addition to finishing more quickly for complex problems, SHOP actually finds shorter, more efficient plans than the other systems in many cases.}, institution = {Department of Computer Science and Institute for Systems Research, University of Maryland}, keywords = {htns, planning}, posted-at = {2006-04-27 17:00:25}, priority = {0}, title = {SHOP: Simple Hierarchical Ordered Planner}, volume = {CS-TR-3981, UMIACS-TR-9904}, year = {1999} }

TY - RPRT ID - citeulike:604605 L3 - citeulike-article-id:604605 TI - SHOP: Simple Hierarchical Ordered Planner VL - CS-TR-3981, UMIACS-TR-9904 KW - htns KW - planning N1 - This paper describes the design of SHOP, a hierarchical planner. The principal differences between SHOP and most other planners are that SHOP uses hierarchical planning and that SHOP uses total-order forward search. The authors have found that domain-specific heuristics can be used to guide a forward search towards a goal significantly faster than partial-order planning, even though partial-order performs much better in the absence of these heuristics. These heuristics may only be used when the state of the world at a given plan step is known, which is not the case in partial-order planning. SHOP uses conjunctions of logical atoms to describe states, Horn clauses ($x(Y) :- a(Y,2)$) to describe axioms, and a set of variable assignments that satisfies these to ground statements. It defines operators as a primitive task, a set of atoms to remove from the world state, and a set of atoms to add to the world state. Operators do not contain preconditions because the order of operators within a method is fixed. A method is defined as a compound task, a precondition that is a conjunct of atoms, and an ordered list of subtasks. Every method in a planning problem must be explictly described in this manner, and there may be many methods for solving a given task. The planning process begins with the first high-level task to be completed. This task is decomposed into its subtasks, each of which is decomposed in order until they have been reduced to operators. Then the next task is decomposed. SHOP is written in Lisp, but it scales better with problem complexity than two partial-order planners known for their speed. In addition to finishing more quickly for complex problems, SHOP actually finds shorter, more efficient plans than the other systems in many cases. AU - Nau, Dana AU - Cao, Yue AU - Lotem, Amnon AU - Munoz-Avila, Hector PY - 1999/// ER -