SHOP (Simple Hierarchical Ordered Planner)

Version 1.2, 12/21/98

Dana S. Nau
Department of Computer Science,
and Institute for Systems Research
University of Maryland
College Park, MD 20742

1 Introduction

SHOP (Simple Hierarchical Ordered Planner) is a Hierarchical Task-Network (HTN) planner in which all task decompositions produce totally ordered sets of subtasks. SHOP plans for these subtasks in the same order that they will later be executed. Thus, whenever it plans for a task, SHOP already knows the task's input state, because it has already completely planned everything that comes before the task. This keeps the implementation of the planner very simple, while allowing it to use a more expressive state representation than most other AI planners.

SHOP is distributed under the terms of the GNU General Public License (a copy of which is included here). It is free software, it comes with absolutely no warranty, and you are allowed to redistribute it under certain conditions. See the GNU General Public License for details.

2 Definitions and Notation

2.1 Symbols

In the expressions defined below, there are five kinds of symbols: variable symbols, constant symbols, function symbols, primitive task symbols, and compound task symbols. To distinguish among these symbols, SHOP uses the following conventions:

• a variable symbol can be any Lisp symbol whose name begins with a question mark (such as ?x or ?hello-there);
• a primitive task symbol can be any Lisp symbol whose name begins with an exclamation point (such as !unstack or !putdown);
• a constant symbol, function symbol, predicate symbol, or compound task symbol can be any Lisp symbol whose name does not begin with a question mark or exclamation point.

In everything that follows, a ground expression is one that contains no variable symbols.

2.2 Logical Expressions

A term is either a variable symbol, a constant symbol, or a list of the form

(f t₁ t₂ ... t_n)

where f is a function symbol and each t_i is a term. A logical atom is a list of the form

(p t₁ t₂ ... t_n)

where p is a predicate symbol and each t_i is a term. A literal is any of the following:

• a logical atom a;
• an expression of the form (not a) where a is a logical atom (the intended meaning is that the expression is true if a is false);
• an expression of the form (eval e) where e is a Lisp expression (the intended meaning is that the expression is true if the Lisp evaluator returns a non-nil value for e).

A conjunct is a list of literals (l₁ l₂ l₃ ... l_n). A tagged conjunct is a list of the form (:first . C) where C is a conjunct. (The :first tag is a way to indicate to the theorem prover that we only want to see the first proof of C, rather than every possible proof. For details, see the discussion of tagged conjuncts at the end of Section 2.3, and the description of find-satisfiers in Section 3.)

An axiom is an expression of the following form, where a is a logical atom and each C_i is a conjunct or a tagged conjunct:

(:- a C₁ C₂ C₃ ... C_n)

The axiom's head is the atom a, and its tail is the list (C₁ C₂ C₃ ... C_n). The intended meaning of an axiom is that a is true if C₁ is true, or if C₁ is false but C₂ is true, or if both C₁ and C₂ are false but C₃ is true, ..., or if all of C₁, C₂, C₃, ..., C_n-1 are false but C_n is true. For example, the following axiom says that a location is in walking distance if the weather is good and the location is within two miles of home, or if the weather is not good and the location is within one mile of home:

(:- (walking-distance ?x)
    ((weather-is good) (distance home ?x ?d) (eval (<= '?d 2)))
    ((distance home ?x ?d) (eval (<= '?d 1))))

The quote marks in the expressions (<= '?d 2) and (<= '?d 2) are to prevent the Lisp evaluator from trying to evaluate the value of ?d.

2.3 Substitutions, Unification, and Truth

A substitution is a list of dotted pairs of the form

((x₁ . t₁) (x₂ . t₂) ... (x_k . t_k))

where every x_i is a variable symbol and every t_i is a term. If u is a substitution and e is an expression, then e^u is the substitution instance produced by taking e and replacing each occurrence of each variable symbol x_i with the corresponding term t_i. If u and v are two substitutions, then u is a generalization of v if for every expression e, e^v is a substitution instance of e^u.

If e is an expression and x₁, x₂, ..., x_k are the variable symbols in e, then a standardizer for e is a substitution of the form

((x₁ . y₁) (x₂ . y₂) ... (x_k . y_k))

where each y_i is a new variable symbol that is not used anywhere else.

If d and e be two expressions and there is a substitution u such that d^u = e^u, then we say that d and e are unifiable and u is a unifier of d and e. If the unifier u is a generalization of every unifier of d and e, then u is a most general unifier (or mgu) of d and e.

A state is a list of ground atoms intended to represent some "state of the world". An axiom list is a list of axioms intended to represent what we can infer from a state. If C is a conjunct or a tagged conjunct, then C is a consequent of a state S and an axiom list X if there for every literal l in C, l is a consequent from S and X. The literal l is a consequent of S and X if any of the following is true:

• l is an atom in S;
• l is a ground expression of the form (eval e) and the Lisp evaluator returns something non-nil when applied to e;
• l is an expression of the form (not a) and the atom a is not a consequent of S and X;
• there is an axiom(:- a C₁ C₂ C₃ ... C_n) in X and a substitution v such that l = a^v and one of the following holds:
  • C₁^v is a consequent of S and X;
  • C₁^v is not a consequent of S and X, but C₂^v is a consequent of S and X;
  • neither C₁^v nor C₂^v is a consequent of S and X, but C₃^v is a consequent of S and X;
  • ...;
  • none of C₁^v, C₂^v, C₃^v, ..., C_n-1^v is a consequent of S in X, but C_n^v is a consequent of S and X.

If C is a consequent of S and X, then it is a most general consequent of S and X for every consequent C' of S and X, if C is a substitution instance of C' then C' is also a substitution instance of C.

Let S be a state, X be an axiom list, and C be an ordinary (i.e., non-tagged) conjunct. If there is a substitution u such that C^u is a consequent of S and X, then we say that S and X satisfy C, and that u is a satisfier for C from S and X. The satisfier u is a most general satisfier (or mgs) if for every generalization v of u such that C^v is a consequent of S and X, u is also a generalization of v. Note that if u is an mgs for C from S and X, then C^u is a most general consequent of S and X.

A conjunct can have several distinct mgs's. For example, suppose X contains the "walking distance" axiom given earlier, and S is the state

((weather-is good) (distance home convenience-store 1) (distance home gas-station 2))

Then there are two mgs's for the conjunct ((walking-distance ?y)) from S and X: ((?y . convenience-store)) and ((?y . gas-station)).

Let S be a state, X be an axiom list, and C = (:first C') be a tagged conjunct, and suppose let u₁, u₂, ..., u_k be all of the mgs's for C' from S and X, listed in the order that a left-to-right search would find them. Then the first one of these mgs's (i.e., u₁) is the mgs for C' from S and X. For example, if S and X are as in the previous example, then the mgs for the tagged conjunct (:first (walking-distance ?y)) from S and X is ((?y . convenience-store)).

2.4 Tasks, Operators, and Methods

A task atom is an expression of the form

(s t₁ t₂ ... t_n)

where s is a task symbol, and the arguments t₁, t₂, ..., t_n are terms. The task atom is primitive if s is a primitive task symbol, and it is compound if s is a compound task symbol.

An operator is a list of the form

(:operator h D A)

where h is a primitive task atom (called the operator's head), and D (the operator's deletions) and A (the operator's additions) are condition lists that contain no variable symbols other than those in h. The intent of an operator is to specify that the task h can be accomplished by modifying the current state of the world to remove every logical atom in D and add every logical atom in A.

Let S be a state, t be a primitive task atom, and o be the operator (:operator h D A). Suppose that there is an mgu u for t and h, and that h^u is ground. Then we say that o matches t, and that the list (o^u) is a simple plan for t. If we execute o^u in the state S, it produces the state o^u(S) = (S - A^u) U A^u. Here is an example:

S =	((has-money john 40) (has-money mary 30))
t =	(!set-money john 40 35)
o =	(:operator (!set-money ?person ?old ?new) ((has-money ?person ?old)) ((has-money ?person ?new)))
u =	((?person . john) (?old . 40) (?new . 35))
ou =	(:operator (!set-money john 40 35) ((has-money john 40)) ((has-money john 35)))
ou(s) =	((has-money john 35) (has-money mary 30))

A task list is a list of task atoms. A method is a list of the form

(:method h C₁ T₁ C₂ T₂ ... C_k T_k)

where

• h is a task atom (which is called the method's head);
• each C_i (which is called a precondition list of the method) is either a condition list or a tagged condition list;
• each T_i (which is called a tail of the method) is a Lisp expression that returns a task list.

The purpose of a method is to specify the following:

• if the current state of the world satisfies C₁, then h can be accomplished by performing the tasks in T₁ in the order given;
• otherwise, if the current state of the world satisfies C₂, then h can be accomplished by performing the tasks in T₂ in the order given;
• ...;
• otherwise, if the current state of the world satisfies C_k, then h can be accomplished by performing the tasks in T_k in the order given.

Let m = (:method h C₁ T₁ C₂ T₂ ... C_k T_k) be a method, S be a state, and t be a task atom (which may or may not be ground). Suppose there is an mgu u that unifies t with h (in which case we say that m matches t). Furthermore, suppose m has a precondition C_i such that S satisfies C_i^u (if there is more than one such C_i, then let C_i be the first one). Then C_i and T_i are m's active precondition and m's active tail, respectively. Let V = {v₁, v₂, ..., v_n} be the set of all mgs's for C_i^u. There are two cases:

1. C_i^u is an ordinary condition list. Then for every v in V, the method instance (m^u)^v is applicable to the task instance (t^u)^v in the state s.
2. C_i^u is a tagged condition list. Then for the first v in V (where the members of V are listed in the order that the planner computes them), the method instance (m^u)^v is applicable to the task instance (t^u)^v in the state s.

The result of applying (m^u)^v to (g^u)^v is the task list returned by eval((T_i^u)^v), where eval is the Lisp eval function. This task list is called a simple reduction of g by m. Here is an example:

s =	((has-money john 40) (has-money mary 30))
g =	(transfer-money john mary 5)
m =	(:method (transfer-money ?p1 ?p2 ?amount) ((has-money ?p1 ?m1) (has-money ?p2 ?m2) (eval (>= ?m1 ?amount))) `((!set-money ?p1 ?m1 ,(- ?m1 ?amount)) (!set-money ?p2 ?m2 ,(+ ?m2 ?amount))))
h =	(transfer-money ?p1 ?p2 ?amount)
C1 =	((has-money ?p1 ?m1) (has-money ?p2 ?m2) (eval (>= ?m1 ?amount)))
T1 =	`((!set-money ?p1 ?m1 ,(- ?m1 ?amount)) (!set-money ?p2 ?m2 ,(+ ?m2 ?amount))))
u =	((?p1 . john) (?p2 . mary) (?amount . 5))
v =	((?m1 . 40) (?m2 . 30))
(C1u)v =	((has-money john 40) (has-money mary 30) (eval (>= 40 30)))
(Tu)v =	`((!set-money john 40 ,(- 40 5)) (!set-money mary 30 ,(+ 30 5)))
eval((Tu)v) =	((!set-money john 40 35) (!set-money mary 30 35))

In m's tail, the backquote and commas are Lisp constructs that produce selective evaluation of portions of the expression.

2.5 Plans and Planning Problems

A plan is a list of simple plans (or equivalently, a list of heads of ground operator instances). If p is a plan and S is a state, then p(S) is the state produced by starting with S and executing the ground operator instances in the order that their heads appear in p.

A planning domain is a list of axioms, operators, and methods. A planning problem is a triple (S,T,D), where S is a state T is a list of tasks to be accomplished in S, and D is a planning domain. If (S, T, D) is a planning problem, then plans(S, T, D), the set of all plans for T from s in D, is defined recursively as follows.

Case 1: T is empty. Then plans(S, T, D) contains exactly one plan, namely the empty plan.

Case 2: T is nonempty. Then let t = car(T) be the first task atom in T, and T' = cdr(T) be the remaining task atoms.

Case 2a: t is primitive. Then

plans(S, T, D) = {cons(t, q) : p is a simple plan for t and q is in plans(p(S), T', D)}

Case 2b: t is compound. Then

plans(S, T, D) = U {plans(S, append(r, T'), D) : r is a simple reduction of t in S}.

Here is an example:

S =	nil
T =	((do-both op1 op2))
D =	((:operator (do ?operation) nil ((did ?operation)))) (:method (do-both ?x ?y) nil ((do ?x) (do ?y))) (:method (do-both ?x ?y) nil ((do ?y) (do ?x))))
plans(S, T, D) =	(((do op1) (do op2) (did op1))) ((do op2) (do op1) (did op2))))

3 Functions provided by the planner

(variablep e)

This predicate returns T if the expression e is a variable symbol (i.e., a symbol whose name begins with a question mark), and nil otherwise.

(primitivep e)

This predicate returns T if the expression e is a primitive task symbol (i.e., a symbol whose name begins with an exclamation point), and nil otherwise.

(apply-substitution e u)

e is an expression and u is a substitution. The function returns e^u.

(compose-substitutions u v)

If u and v are substitutions, then this function returns a substitution w such that for every expression e, e^w = (e^u)^v.

(standardizer e)

This function returns a standardizer for e.

(standardize e)

This function is equivalent to (apply-substitution e (standardizer e)).

(unify d e)

This procedure returns an mgu for the expressions d and e if they are unifiable, and returns nil otherwise. In addition to being a most-general unifier, the mgu replaces every variable symbol of the unified expression with a new variable symbol that has never been used elsewhere.

(find-satisfiers C S X &optional just-one)

If C is a condition list, S is a state, and X is an axiom list, then this function returns a list of mgs's, one for every most general instance of C that is satisfied by S and X. If the optional argument just-one is non-nil, then the function returns the first mgs it finds, rather than all of them. Calling (find-satisfiers C S X) is roughly equivalent to calling the following pseudocode with u = nil, and then returning answers:

• global answers = nil
• procedure seek-satisfiers(C, S, X, u)
  • if goals is empty then
    • insert u into answers
    • return
  • end
  • a = the first atom in C; B = the remaining atoms of C
  • if c is an expression of the form (not e) then
    • if find-satisfiers(e, S, X) = nil then call seek-satisfiers(B, S, X, u)
    • return
  • else if a is an expression of the form (eval e) then
    • if eval(e) is non-nil then call seek-satisfiers(B, S, X, u)
    • return
  • end
  • for every atom s in S that unifies with a
    • let v be the unifier
    • insert compose-substitutions(u,v) into answers
  • end
  • for every axiom x in X whose head unifies with a
    • let v be the unifier
    • if tail(x) contains a conjunct c such that seek-satisfiers(append(c^v, B^v), S) is non-nil then
      • let c be the first such conjunct
      • for every v in seek-satisfiers(append(c^v, B^v), S)
        • insert compose-substitutions(u, v) into answers
    • end
  • end
• end seek-satisfiers

(apply-method S t m)

If S is a state, t is a task, and m = (:method h C₁ T₁ C₂ T₂ ... C_k T_k) is a method, then this function does the following:

• If m is not applicable to t in S, then the function returns the symbol fail.
• If m is applicable to t in S and the active precondition C_i is an ordinary condition list, then the function returns a list of all simple reductions of T_i, one for each satisfier of C_i in S.
• If m is applicable to t in S and the active precondition C_i is a tagged condition list, then the function returns one of T_i's simple reductions, namely the one that corresponds to C_i's first satisfier in S.
  
  

(apply-operator S t o)

If S is a state, t is a task, and o is an operator, then this function does the following:

• If there is an mgu u for o and t, then it returns the state produced by executing o^u in S.
• Otherwise, it returns FAIL.

(make-domain domain-name D)

This function gives the name domain-name to planning domain D. (More specifically, what it does is to store D's axioms, operators, and methods on domain-name's property list.)

(make-problem problem-name S T domain-name)

This function gives the name problem-name to the planning problem (S,T,D), where D is the planning domain whose name is domain-name. (More specifically, what it does is to store S, T, and domain-name on problem-name's property list.)

(make-problem-set set-name list-of-problems)

This function gives the name set-name to the set of planning problems in list-of-problems. (More specifically, what it does is to store list-of-problems on set-name's property list.)

(run-problems name-or-list &key which gc verbose)

name-or-list should be either a list of problem names or the name of a problem set. This function runs find-plans on each planning problem specified by the list or problem set. The keyword arguments are simply passed on to find-plans.

(find-plans problem &key which gc verbose)

This function searches for members of plans(S, T, D), where (S, T, D) is the planning problem whose name is problem. Calling (find-plans problem) without any keyword arguments is equivalent to calling the following pseudocode with p = nil:

• procedure seek-plans(S, T, D, p)
  • if T = nil then return (p)
  • t = the first task in T
  • T' = the remaining tasks in T
  • if g is primitive then
    • for every simple plan q for g
      • answer = seek-plans(q(s), T', D, append(p, q))
      • if answernil then return answer
    • end
  • else
    • for every simple reduction r for g in s
      • answer = seek-plans(s, append(r, T'), D), p)
      • if answernil then return answer
    • end
  • end
  • return nil
• end seek-plans

The keyword arguments are as follows:

• which says what kind of search to do. Here are its possible values and what they mean:

  :all	do a depth-first search for all plans in plans(S, T, M)
  :first (the default)	do a depth first search, stopping after the first plan found
  :shallowest	do a depth-first search for the shallowest plan in the search space (or the first such plan if there is more than one of them)
  :all-shallowest	do a depth-first search for all shallowest plans in the search space
  :id-all	do an iterative-deepening search for all shallowest plans in plans(S,T,M)
  :id-first	do an iterative-deepening search, stopping after the first plan found

  The :id-all and :id-first options are equivalent to taking a modified version of seek-plans that backtracks each time it reaches depth d, and calling it repeatedly with d = 1, 2, ..., until answers is non-nil.
  
• Calling find-plans with gcnil is equivalent to doing a garbage collection just before each top-level call to seek-plans. This can make it easier to get repeatable experimental results.
  
  
• verbose tells find-plans what kind of information to print out. Here are its possible values and what they mean:

  0	print nothing
  1 (the default)	print the plans found, plus some statistics about the search
  2	print the above, plus information about success or failure at each leaf of the planner's search tree
  3	print the above, plus a message each time the planner prunes a node
  4	print the above, plus the task at each node of the planner's search tree
  5	print the above, plus information about success or failure at each leaf of find-satisfiers's search tree
  6	print the above, plus the goal at each node of find-satisfiers's search tree

  If verbose = 0 then find-plans returns a list of all of the plans it found; otherwise it returns nil.

4 Notes

1. Since the null conjunct is always true, an axiom of the form (:- a nil) is equivalent to asserting the atom a as a basic fact.
2. An axiom with several conjuncts in its tail has a different semantics than what you would get by making each conjunct the tail of a separate axiom. For example, consider the following axiom lists:

   X1 =	((:- (a ?x) ((b ?x)) ((c ?x)))))
   X2 =	((:- (a ?x) ((b ?x))) (:- (a ?x) ((c ?x))))

   
   

   In X₁, the single axiom acts like an if-then-else: if ((b ?x)) is true then find-satisfiers returns the satisfiers for (b ?x); otherwise if ((c ?x)) is true then it returns the satisfiers for (c ?x). In X₂, the set of axioms acts like a logical "or": find-satisfiers returns every satisfier for (b ?x) and every satisfier for (c ?x). For example,

   (find-satisfiers '((a ?u)) '((b 2) (c 3)) X₁)
   
   

   would return (((?u . 2))), but

   (find-satisfiers '((a ?u)) '((b 2) (c 3)) X₂)
   
   

   would return (((?u . 2)) ((?u . 3))).

3. Since unify standardizes variables when it unifies them, there is no need for you to standardize variables by hand, with one exception: whenever you define a planning problem p = (S,T,D), you should make sure that all of the variable symbols in T are distinct from all of the variable symbols in D.
   
   
4. Since a primitive task name is basically a call to an operator, you should never create a set of methods and operators that has more than one operator for the same primitive task. Otherwise, your plans will be ambiguous.
   
   
5. The following two calls to the planner will find the same set of all shallowest plans, but will search for those plans in different ways:
   (find-plans p :kind :all-shallowest)
   (find-plans p :kind :id-all)
   

   Likewise, the following two calls to the planner will both find the same shallowest plan, but will search for it in different ways:

   (find-plans p :kind :shallowest)
   (find-plans p :kind :id-first)
   

   Which call runs faster depends on the shape of the search space. In the examples that I have tried, depth-first search ran more quickly than the equivalent iterative-deepening search. However, it certainly is possible to construct planning problems in which iterative deepening runs faster than depth-first search, as well as problems in which iterative deepening terminates but depth-first search doesn't.