3.2.1 find-plans

The find-plans function has one mandatory argument, the name of a planning problem, and a set of optional keyword arguments. It returns up to four values. find-plans will always return two values: (1) a list of plans and (2) the total amount of CPU time used during planning (in seconds). If the :plan-tree argument (see below) is non-NIL, then two additional values will be returned: (3) a list of plan tree data structures and (4) a list of final state data structures. From the plan state data structures, the user can extract full state trajectories for the plans.

Function: find-plans problem &key domain which verbose gc pp plan-tree optimize-cost collect-state time-limit explanation depth-cutoff state tasks state-type hand-steer leashed out-stream ¶

find-plans looks for solutions to the planning problem named problem. The keyword arguments are as follows: :which tells what kind of search to do. Its possible values are: :first - depth-first search, returning the first plan found. :all - depth-first search for *all* plans. :shallowest - depth-first search for the shallowest plan in the search space (this usually is also the shortest plan). If there’s more than one such plan, return the first.

:all-shallowest - depth-first search for all shallowest plans.

:id-first - iterative deepening search, returning the first plan.

:id-all - iterative deepening search for all shallowest plans.

:random - Randomized search. Used by Monroe. Not for normal

SHOP3 domains, since normal SHOP3 domains have order- dependent semantics.

:mcts - Monte Carlo Tree Search mode (experimental and unstable).

:verbose says how much information to print about the plans SHOP3

finds. Its values can be any of the following: 0 or nil - print nothing 1 or :stats - print some statistics on SHOP3’s operation 2 or :plans - print the stats and print all plans found, but omit operator costs and omit all operators whose names start with "!!" 3 or :long-plans - print the stats and plans, including all operator costs and all operators (even those whose names start with "!!")

:gc says whether to do a garbage collection before calling seek-plans

:plan-tree indicates whether or not to return plan tree(s).

:collect-state indicates whether or not to return final state(s). For backward-

compatibility, states are also returned whenever :plan-tree is true. This should probably eventually change.

return values:

plans found --- a list of plans. Each plan is a list that alternates a between instantiated operators and costs run time --- floating point value in seconds /if/ the plan-tree keyword argument is supplied, there will be two additional return values: plan-trees --- a list of plan trees, whose form is specified elsewhere. final-states --- a list of final state structures, one per plan.

3.2.2 find-plans-stack

Function: find-plans-stack problem &key domain verbose plan-tree gc no-dependencies repairable rationale state-type out-stream which analogical-replay unpack-returns make-analogy-table ¶

Top level search function for explicit-state search in SHOP3. Does not support the full range of options supported by SHOP3’s ‘find-plans-stack‘.

Keyword arguments:

• domain : either a domain name (symbol) or a ‘shop:domain‘ object.
• verbose : 0, 1, 2, 3; default 0
• plan-tree : build and return a plan tree? (‘plan-tree:top-node‘), defaults to ‘nil‘.
• gc : If possible, perform a full gc before starting to plan. Default: current value of ‘shop:*gc*‘.
• no-dependencies : if building a plan tree, build it *without* causal dependencies. Default: ‘nil‘.
• repairable : return plans that can be repaired. Default: ‘nil‘.
• rationale : build a plan tree with rationale information. Default: ‘nil‘.
• state-type : what state type should be used for representing world states? (Note: world-state/SHOP state, *not* search-state). Default: ‘:mixed‘.
• out-stream : where should output be printed. Default: ‘t‘ (standard output).
• which : What/how many plans should be returned? Supports only ‘:first‘ (the default) and ‘:all‘.
• analogical-replay : Do search informed by the contents of the ‘*analogical-replay-table*‘. Default: ‘nil‘.
• make-analogy-table : Populate ‘*analogical-replay-table*‘ while planning. Only works with ‘:which‘ = ‘:first‘. Default: ‘nil‘.
• unpack-returns : If true, return values in a way compatible with ‘find-plans‘. If false, return a list of ‘plan-return‘ objects instead. See discussion of return values, below. Default: ‘t‘.

Return values: There are two possible return types, selected by the keyword argument ‘unpack-returns‘:

1. Default/compatible with ‘find-plans‘:

• List of plans
• List of plan trees (if computed)
• List of plan tree lookup tables
• List of final world states
• List of analogical replay tables (if computed)

To comply with SHOP3, though, always returns a list of plans. If the plan-tree keyword argument is non-NIL, will return an enhanced plan tree, with causal links, unless no-dependencies is non-NIL. Returns the values returned by seek-plans-stack, qv.

3.2.3 do-problems

The do-problems function has one mandatory argument, which can either be the name of a planning problem set or a list of names of planning problems. It executes find-plans on each of the given planning problems and returns nil.

Function: do-problems problems &rest keywords ¶

do-problems runs find-plans on each problem in problems, which may be either a problem-set name (a symbol) or a list of problems.

Returns nothing of interest: should only be run for what it displays on the console.

3.2.4 Common Keyword Arguments

The keyword arguments to find-plans and do-problems are as follows:

• which says what kind of search to do. Here are its possible values and what they mean. The default value of which is the value of the global variable *which* (whose default value is :first).

  Value	Kind of search
  :first	Depth first search, stopping at the first plan found
  :all	Depth-first search, but don’t stop until all plans in plans(S, T, M) have been found
  :shallowest	Depth-first search for the shallowest plan, or the first such plan if there is more than one of them. In many domains this is also the least-cost plan
  :all-shallowest	Depth-first search for all shallowest plans in the search space
  :id-first	Iterative-deepening search, stopping after the first plan found
  :id-all	Iterative-deepening search for all shallowest plans

  The iterative deepening options, :id-all and :id-first, are equivalent to taking a modified version of find-plans that backtracks each time it reaches depth d, and calling it repeatedly with d = 1, 2, …, until a plan is found.

• verbose says what information to print out, as shown in the following table. The default value for verbose is 1.

  Value	What to print
  0 or nil	Nothing
  1 or :stats	Some statistics about the search
  2 or :plans	The statistics plus a succinct version of each plan found: internal operators (see internal operators), and operator costs are omitted.
  3 or :long-plans	The statistics plus the complete version of each plan found

• If gc is non-nil, then find-plans calls the garbage collector just before starting its search, thus making it somewhat easier to get repeatable experimental results. The default value of gc is T.
• If pp is non-nil, then all printing done by SHOP3 is performed using the Common Lisp pretty-printing mechanism. This typically leads to more easily read output. The default value of pp is T.
• The state argument controls how states are represented internally. SHOP3 can have different performance characteristics depending on the value provided to this augment. If you are encountering out-of-memory errors in SHOP3 or you want to get the maximum speed possible from SHOP3 for a particular set of problems, you may wish to experiment with different values for this argument. The default value is :mixed, which represents states using a combination of lists and hash tables; this value has been shown to provide a reasonably good combination of speed and memory usage on a variety of test problems. The other values are :list, :hash, and :bit.
• The optimize-cost argument is used to perform planning with branch-and-bound optimization of the total plan cost. The default value for this argument is nil. If the value of this argument is nil, the optimization feature is disabled. If the value of the argument is t, SHOP3 will search for plans with the minimum total cost. If the value of the argument is a number, SHOP3 will use the branch-and-bound technique to search for plans with cost less than or equal to the value of the argument. The optimization feature is written under the assumption that the costs of operators are always non-negative. If this assumption is invalid, SHOP3 will produce unreliable results (specifically it will prune out some valid plans). The interaction of :optimize-cost with the various options for :which can be subtle. Below are notes on each possible combination:
• (:which :first :optimize-cost t)

  Under these arguments, SHOP3 returns the first plan found for which no other valid plan has a lower total cost. Note that this option may take much more time to run than using (:which :first :optimize-cost nil) since even after it finds the plan, it must keep searching to see if it can find a cheaper plan. However, this option may be significantly faster than (:which :all :optimize-cost nil) since the branch-and-bound mechanism will prune out non-optimal plans without having to consider them all the way to the end. In some cases, this will mean that (:which :first :optimize-cost t) terminates and (:which :all :optimize-cost nil) does not.

• (:which :first :optimize-cost number)

  Under these arguments, SHOP3 returns the first plan found whose total cost is less than or equal to the number given. If there is no plan whose total cost is less than or equal to that number, SHOP3 will return no plans. Note that if the number given is large enough, these arguments can produce results much more quickly than with (:which :first :optimize-cost t); specifically, as soon as SHOP3 finds a plan for which the cost is met, it can terminate and does not have to keep searching for cheaper plans.

• (:which :all :optimize-cost t)

  Under these arguments, SHOP3 returns all plans for which no other valid plan has a lower total cost. Obviously, all plans returned under these options will have equal total cost.

• (:which :all :optimize-cost number)

  Under these arguments, SHOP3 returns all plans with total cost less than or equal to the given number.

• (:which :shallowest :optimize-cost t)

  Under these arguments, SHOP3 returns a plan that has the shallowest depth of all valid plans and for which there is no other shallowest depth valid plan which has a lower total cost. In other words, these arguments produce the cheapest of all shallowest plans (which, incidentally, is not necessarily the same thing as the shallowest of all cheapest plans).

• (:which :shallowest :optimize-cost number)

  Under these arguments, SHOP3 returns a plan which has the shallowest depth of all valid plans and whose total cost is less than or equal to the given number. Note that if there is no plan whose cost is less than or equal to the number and whose depth is shallowest among all valid plans, then no plan will be returned (even if there are deeper plans which do have cost less than or equal to the number).

• (:which :all-shallowest :optimize-cost t)

  Under these arguments, SHOP3 returns all plans which have the shallowest depth of all valid plans and for which there is no other shallowest depth valid plan which has a lower total cost.

• (:which :all-shallowest :optimize-cost number)

  Under these arguments, SHOP3 returns all plans which have the shallowest depth and whose total cost is less than or equal to the given number.

• (:which :id-first) or (:which :id-all)

  The :id-first and :id-all options produce the same results as the shallowest and all-shallowest arguments, respectively for each different combination with :optimize-cost. Note, however, that there are domains for which SHOP3 will terminate using id-first and id-all and will not terminate using other values for :which.

• The time-limit argument may either nil or a number. Its default is nil and if it is nil, no time limit is imposed on the planning process. If the time-limit argument is a number, SHOP3 will check the elapsed CPU time at the start of each step of the planning process, and if the number of seconds elapsed is greater than the argument value, SHOP3 will immediately terminate. The main use for this feature is in combination with (:optimize-cost t) argument, in order to return the optimal value found within the given time limit. For example, consider the call (find-plans 'foo :verbose 1 :optimize-cost t :time-limit 120). This call addresses a problem named foo, and runs until it either finds the minimum cost plan or until 2 minutes have elapsed. It then returns the lowest cost plan that it found during that time. This functionality is inspired, in part, by Anytime Algorithms (see Dean & Boddy, 1998).
• If explanation is non-nil, SHOP3 adds extra information at the end of each operator explaining how the preconditions for that operator were satisfied. Currently supports only logical atoms, and, and or; it doesn’t work with forall, not, eval, etc. If this feature is used with the external-access-hook feature (see Hook Routines), any attribution information provided by the external-access-hook routine is included in the relevant explanation. The default value of explanation is nil.
• The plan-tree argument defaults to nil; if true, the planner will return two additional values: (1) a list of complete task decomposition trees for the plans and (2) a list of plan state data structures corresponding to the final states of each plan. Plan trees are encoded in a nested list format in which the decomposition of an upper level task into lower level tasks is represented by the upper level task atom, followed by trees for each lower level task. The leaves of the tree, involving operators, are each lists of three elements: the cost of the operator, the task atom for the operator, and the numerical position of the operator in the plan (starting at 1). For example, a task (travel houston springfield) that was directly decomposed into operators, (!fly houston boston) with cost 200 and (!drive boston springfield) with cost 50, would have the following plan tree:

  ((travel houston springfield)
   (200 (!fly houston boston) 1)
   (50 (!drive boston springfield) 2))
  

4.3.1 List Terms

A list term is a term having the form

([list] t1 t2 … tn [. l])

where list is an optional reserved word and each t_i is a term. This specifies that t₁ t₂ … t_n are the items of a list. If the final, optional element is included, the item l should evaluate to a list; all items in l are included in the list after t₁ through t_n.

4.3.2 Eval Terms

An eval term is an expression of the form

(eval general-lisp-expression)

The value associated with an eval term is determined as follows. First, any variable symbols which appear in general-lisp-expression and are bound are replaced by the values that they are bound to. Then, the entire expression is evaluated in Lisp. For example, if the variable symbol ?foo is bound to the value 3 then the term:

(eval (mapcar #'(lambda (x) (+ x ?foo)) `(1 2 ,(* ?foo ?foo))))

will have as its value a list containing the numbers 4, 5, and 12.

Note that variable substitutions in eval terms are handled before any evaluation of the expression, as in Lisp macros. One implication of this fact is that variables with symbolic values must be explicitly quoted if they are to be treated as Lisp symbols. For example, if the variable ?foo is bound to the symbol bar, the following eval term has the value (bar baz):

(eval (list '?foo 'baz))

But if this were written

(eval (list ?foo 'baz))

it would cause a Lisp error when Lisp attempts to find the value of bar, which it would believe to be a variable.

4.3.3 Call terms

A call term is not as expressive as an eval term. In particular, it does not support the evaluation of Lisp macros (including macro characters such as backquote). Both call and eval are supported in SHOP3 because the former is compatible with JSHOP 1.0 and the latter is compatible with SHOP 1.x. SHOP3 users who are not interested in either form of compatibility may use either form.

A call term is an expression of the form

(call f t1 t2 … tn)

where f is a function symbol and each t_i is a term or a call term. A call term has a special meaning to SHOP3, because it tells SHOP3 that f is an attached procedure, i.e., that whenever SHOP3 needs to evaluate a precondition or task list that contains a call term, SHOP3 should replace the call term with the result of applying the function f to the arguments t₁, t₂, …, t_n. We later will define preconditions (see preconditions) and task lists (see Task Lists).

For example, the following call term would have the value 6:

(call + (call + 1 2) 3)

4.5.1 Conjuncts

A conjunct has the form

([and]l1 l2 … ln)

where each l_i is a logical expression.

Note that if there are 0 conjuncts (e.g., the expression is ()) then the form always evaluates to true.

Also note that implicit conjunction (list of logical expressions without an explicit and) is deprecated, and will eventually be removed, as it significantly complicates SHOP3’s parsing – and reading SHOP3 code by humans.

4.5.2 Disjuncts

A disjunct is an expression of the form

(or l1 l2 … ln)

where l₁, l₂ … l_n are logical expressions.

4.5.3 Negations

A negation is an expression of the form

(not l)

where l is a logical expression.

4.5.4 Implications

An implication is an expression of the form

(imply Y Z)

where Y and Z are logical expressions. The intent of an implication is to evaluate its logical counterpart; that is, \neg Y \lor Z. Note that the context should not leave free variables in Y, or the semantics of the implication will be ambiguous.

4.5.5 Universal Quantifications

A universal quantification expression is an expression of the form

(forall V E1 E2)

where E₁ and E₂ are logical expressions, and V is the list of variables in E₁. To satisfy a universally quantified expression, the following must hold: for each possible substitution u for variables in V, if E₁^u is satisfied then E₂^u must also be satisfied in the current state of the world. Note that this use of the keyword forall is distinct from its use in add and delete lists in operators (see Operators): the latter is used to express a set of effects rather than a logical expression and consequently has a different syntax.

There is no need for existential quantifications. See [Ghallab et al., 2004] or Internal Knowledge Structures.

4.5.6 Assignments

A simple assignment expression has the form

(assign v e)

where v is a variable symbol and e is general Lisp expression. The intent of an assignment expression is to bind the value of e to the variable symbol v. Variable substitutions in assignment expressions are done using literal substitutions, as with eval terms (see Eval Terms). For example, if ?foo is bound to the symbol if and ?bar is bound to the number 0 then the following expression will bind the variable ?baz to the list (if fish):

(assign ?baz (?foo (< ?bar 3) (list '?foo 'fish) (/ 8 ?bar)))

Similarly, if ?foo is bound to list and ?bar is bound to 4 then the expression above will bind ?baz to the list (nil (list fish) 2).²

Note: assign is not the default way to bind SHOP3’s logical variables. The default way to bind logical variables is through unification. assign is specifically for use when you wish to use Lisp code to produce values you will bind variables to. To that end, assign expects that its second argument will be a Lisp expression and it will evaluate that expression. It is because of this evaluation process that the following expression (with = interpreted as unification)

(= ?x foo)

will bind ?x to the symbol foo, but

(assign ?x foo)

will cause a run-time error. In the second example, SHOP3 will attempt to evaluate foo and report it as an unbound variable – unless this is evaluated in a context where foo is a variable, in which case ?x will be bound to the current value of foo.

SHOP3 also offers a compound assignment expression of this form:

(assign* v e)

As in the simple assign, v is a variable symbol and e is general Lisp expression. However, for assign*, e should evaluate to a list of possible values and through backtracking, SHOP3’s theorem-prover will find all solutions with v bound to the various values of e in turn.

4.5.7 Eval expressions

An eval expression has the same form as an eval term (see Eval Terms). Unlike an eval term, however, an eval expression is interpreted simply as either true or false rather than having some value which would be used as an argument to a predicate. Thus an eval expression typically invokes boolean Lisp functions such as evenp or >=.

Note that if you use an eval expression for its side effects, you must be careful to ensure that it still returns a true value. For example, if you introduce an invocation of format for debugging purposes, remember that format always returns nil, and will cause the containing precondition to fail!

4.5.8 Call expressions

A call expression has the same form as a call term (see Call terms). As with eval expressions (see Eval expressions), call expressions are interpreted as either true or false, and the warning mentioned there about using eval expressions for side effects applies to call expressions, as well.

4.5.9 Enforce expressions

An enforce expression has the form

(enforce t1 &rest error-args)

Enforce expressions are for goals that should always be satisfied. SHOP3’s theorem-prover will attempt to prove t₁ and if it fails, will call error with error-args. For example

(enforce (x-position ?aircraft)
          "~A x-position undefined." (quote ?aircraft))

Enforce expressions are useful when debugging domains.

4.5.10 Setof expressions

A setof expression has the form

(setof term expr set-var)

Find all solutions to expr, and bind the set of values for term in expr to set-var. For example

(setof ?u (uav ?u) ?uavs)

will bind ?uavs to the set of UAVs in the current state.

(setof (pair ?u1 ?u2)
  (and (uav ?u1) (uav ?u2) (line-of-sight ?u1 ?u2))
  ?pairs)

will bind ?pairs to a set of terms, e.g., ((pair rotor1 fw2) (pair rotor2 fw3)) indicating pairs of UAVs with line of sight from the first to the second.

Note: The semantics of setof are to fail if the expr is an unsatisfiable goal, rather than to succeed with set-var bound to ().

Note: Support for general terms as the first argument to setof and bagof (see Bagof expressions) is new in version 3.4 of SHOP3. Code that depends on it should use a corresponding version dependency qualifier in, e.g., ASDF ((:version "shop3" "3.4")).

4.5.11 Bagof expressions

The syntax for bagof is the same as for setof (see Setof expressions), but binds set-var to a bag of results, which may contain duplicates, instead of a set.

4.6.1 First Satisfiers Precondition

A first satisfier precondition has the form

(:first l1 l2 … ln)

where each l_i is a logical expression. Such a precondition causes SHOP3 to consider only the first set of bindings that satisfies all of the given expressions. Alternative bindings will not be considered even if the first bindings found do not lead to a valid plan.

4.6.2 Sorted Precondition

A sorted precondition has the form

(:sort-by v [e] l)

where v is a variable symbol, e.g., ?x; e is a general Lisp expression that should evaluate to a comparison function; and l is a logical expression. Such a precondition causes SHOP3 to consider bindings for v in a specific order: bindings are sorted such that if the comparison function holds between values x and y then bindings of v to x may not occur after bindings of v to y. For example consider the precondition:

(:sort-by ?d #'> (and (at ?here) (distance ?here ?there ?d)))

This precondition will cause SHOP3 to consider bindings in decreasing (high to low) order of the value of ?d. If the comparison function (e) is omitted, it defaults to #'<, indicating increasing (low to high) order.

4.10.1 Internal Operators

As noted above, the head of the operator is a primitive task atom, so it must begin with a primitive task symbol, i.e., a symbol that begins with an exclamation point. Note that operator names which begin with two exclamation points have a special meaning in SHOP3; operators of this sort are known as internal operators. Internal operators are ones which are used for purposes internal to the planning process and are not intended to correspond to actions performed in the plan (e.g., to do some computation which will later be useful in deciding what actions to perform). Other than requiring two exclamation points at the start of the name, the syntax for internal operators is identical to the syntax for other operators. SHOP3 handles internal operators exactly the same way as ordinary operators during planning. SHOP3 includes these operators in any plans that it returns at the end of execution. It may, however, omit them from the printout of the final plan (depending on the value of the :verbose argument (see verbose).

The primary reason that the internal operator syntax exists in SHOP3 is so that automated systems which use SHOP3 plans as an input can easily distinguish between those operators which involve action and those which were merely internal to the planning process.

4.10.2 Operators must be deterministic

When designing an operator, it is important to ensure that each variable symbol in the add list, delete list, and cost always be bound to a single value when the operator is invoked. Variable symbols can be bound in the head of the operator (by the method that invokes the associated primitive task) or in the precondition of the operator. An operator should be written such that for any variable appearing after the precondition (a) no two unifiers of the precondition have different bindings for that variable, and (b) unification results in some binding for it, i.e. it does not remain unbound. SHOP3 does not check this requirement; if conflicting unifiers are available when applying an operator, it will apply one arbitrarily. This can lead to unpredictable behavior and plans with ambiguous semantics. In general, we recommend that operator preconditions be designed such that only one unifier is possible. However, SHOP3 will be able to correctly process operators that have multiple unifiers for preconditions as long as no two unifiers can provide different values for a variable that appears in the add list, delete list, or cost.

4.10.3 Protection conditions

In the definition of operators, a protection condition is an expression of the form

(:protection a)

where a is a logical atom. The purpose of a protection condition in the add list is to tell SHOP3 that it should not execute any operator that deletes a. The purpose of a protection condition in the delete list is to cancel a previously added protection condition. For example, if we drive a delivery truck to a certain location in order to pick up a package, then we might not want to allow the truck to be moved away from that location until after we have picked up the package.  To represent this, we might use the following operators:

(:op (!drive-to ?truck ?old-loc ?location)
   :delete ((at ?truck ?old-loc))
   :add ((at ?truck ?location)
           (:protection (at ?truck ?location))))
(:op (!pick-up ?truck ?package ?location)
  :delete
    ((at ?package ?location)
     (:protection (at ?truck ?location)))
   :add ((in ?package ?truck)))

4.10.4 Operators: Legacy Syntax

In our work with SHOP2, we found that operator definitions in its original syntax were prone to hard-to-detect syntax errors and typos that can give rise to difficult to identify “garbage in/garbage out” bugs. Particularly prevalent are hard-to-identify bugs arising when a programmer inadvertently reverses the order of add and delete lists in a SHOP3 operator. These problems are exacerbated by the extreme permissiveness of SHOP3’s parser. This led us to the new syntax, described above, which relies on keywords to make operator definitions more readable, and less error-prone. Our new syntax also supports arbitrary order and the omission of empty components, without the “DWIM” parsing in SHOP2. Because of its many advantages, so we encourage you to adopt the new syntax, instead of continuing to use the “classical” form described here, although it is still supported.

The original operator definition syntax was as follows:

(:operator head precondition delete-list add-list [c])

The two operators described above are written in the old syntax as follows:

(:operator (!drive-to ?truck ?old-loc ?location)
   ()
   ((at ?truck ?old-loc))
   ((at ?truck ?location)
    (:protection (at ?truck ?location))))
(:operator (!pick-up ?truck ?package ?location)
  ()
  ((at ?package ?location)
   (:protection (at ?truck ?location)))
  ((in ?package ?truck)))

For backwards compatibility with SHOP 1.x, SHOP3 will also accept operators where the precondition P is missing. In this case the domain definition pre-processing code puts a null precondition into the operator, which is always satisfied. SHOP3’s ability to recognize operators without preconditions is deprecated and is likely to disappear in the future.

4.12.1 Simple Form

A planning domain definition in the simple form looks like this:

(defdomain domain-name (i1 i2 … in))

where domain-name is a symbol (which does not need to be quoted). Beginning users of SHOP3 should simply use the simple domain-name form of this argument.

Each item i_i is one of the following: an operator, a method, or an axiom.

4.12.2 Extended form

The extended form of the SHOP3 domain definition looks like this:

(defdomain (domain-name &rest args) (i1 i2 … in))

args includes the following keyword arguments:

• a :type keyword argument, allowing the domain modeler to indicate a specific subclass of the SHOP3 domain class. E.g., one might have (my-domain :type pddl-domain).
• A :redefine-ok argument. If this is NIL (the default), defdomain will warn when the domain domain-name is already defined.
• A :noset argument. Should the dynamic variable *domain* be bound as a side-effect of evaluating the defdomain expression?Currently this defaults to NIL, to provide for backward compatibility, but I would like to see this move to defaulting to T. See discussion of *domain* below.

4.12.3 The *domain* variable

This is actually a bit of a kludge. The existing defdomain implementation, as a side-effect, sets the global variable *domain*. If this were only a default domain name, that would be fine, but it is used everywhere as a special variable to mean “the domain within which we are planning.” So if there’s concurrent action, or there are multiple copies of SHOP (or its component libraries) running in a single Lisp image, bad things can happen. I would like to stamp out the use of *domain* as a default domain.

The question of which additional arguments are accepted in args is a matter for the implementer of the specialized domain type⁴ being used. Any additional arguments will be passed to the make-instance method for the domain subclass.⁵ SHOP3 extenders can create new subclasses of domain that accept initialization arguments. A first example of the use of this is the built-in pddl-domain class.

If you are using the extended form of defdomain, you should have in hand a new SHOP3 domain subclass, with a description of its arguments. If you do not, you should ignore the extended form.

4.12.4 Inclusion directives

A domain definition can include the items of another domain by reference using the include directive:

(:include domain-name file-name)

for example

(:include flight-operators
  #.(asdf:system-relative-pathname "core-domains" "domains.lisp"))

would take the text of the flight-operators domain, which should be found in the domains.lisp file. Note the use of the reader evaluation form – #. – to force evaluation of the expression that yields the pathname.

Designer’s Note: SHOP3’s inclusion directive is a mess. SHOP3 really needs an inclusion directive, but it is a poor fit to defdomain, because the latter is an executable macro, but the inclusion directive is inherently file-based, rather than code (s-expression)-based. I have not been able to come up with a more graceful solution, however. –rpg

5.1.1 Implementation Notes

As the name suggests, the domain mixin class fluents-mixin is responsible for the correct interpretation of PDDL metric fluents. This requires extensions to the SHOP theorem prover and to the interpretation of PDDL actions.

In its state representation, SHOP stores the current values of metric fluents using the dedicated predicate FLUENT-VALUE, as in, for example: (fluent-value (capacity jug0) 12). When the value of a metric fluent must be found, this is the form of literal that is actually retrieved.

In the grammar of PDDL, there are also fluent expressions (f-exps) that are made up of fluent values, numbers, binary and unary operators. Internally, the SHOP theorem-prover uses the special predicate F-EXP-VALUE to find values of such expressions, and has a special-purpose inference rule coded for them. These expressions appear both in preconditions (as part of comparison predications) and in action effects (as part of updates).

A fluent comparison (f-comp in the PDDL grammar) is a binary comparison applied to two f-exps. Internally, the theorem-prover uses the distinguished predicate fluent-check to check these. As one would expect, it first evaluates the two fluent expressions and then applies the comparison operator.

When handling updates to fluent expressions, parsing methods on the fluents-mixin class will translate update expressions into new fluent-update expressions of the following form:

(fluent-update update-op fluent-function f-exp)

Special code for handling such effect expressions has been added to the apply-action function in SHOP.

5.2.1 Enhanced Preconditions

PDDL method preconditions are based on PDDL goals, but with the following extensions:

• A PDDL method’s preconditions may use the :sort-by keyword. More precisely:

  P	::= PDDL goal
  v	::= PDDL/SHOP variable
  P_v	::= PDDL goal with v appearing free
  precond	::= P | P_v with v a method parameter | :sort-by v [<rel>] P_v

• Variables that appear free in the head of the PDDL method may appear free in the precondition, hence the use of P and P_v.

PDDL goals are as described in the PDDL syntax (we have used the PDDL 2.1 paper as primary source). Note that PDDL goals with free variables are permitted, as long as the free variables appear in the parameters for the task.

Currently we do not support typing in PDDL method task heads, but this could change.

11.1.1 Substitutions

Update note: The variable bindings in a substitution are no longer represented by dotted pairs. Instead, they are represented by Common Lisp structures that have ‘binding-var‘ and ‘binding-value‘ slots. So, until there has been time for a rewrite, please read “binding structure” for “dotted pair” in the following. [rpg 12 June 2018]

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 e is an expression and u is the above substitution, then the substitution instance e^u is the expression produced by starting with e and replacing each occurrence of each variable symbol x_i with the corresponding term t_i.

If d and e are two expressions, then:

• d is a generalization of e if e is a substitution instance of d;
• d is a strict generalization of e if d is a generalization of e but e is not a generalization of d;
• d and e are equivalent if each is a generalization of the other.

If u and v are two substitutions, then:

• u is a generalization of v if for every expression e, e^u is a generalization of e^v;
• u is a strict generalization of v if for every expression e, e^u is a strict generalization of e^v;
• u and v are equivalent if for every expression e, e^u and e^v are equivalent.

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. Note that if u is a standardizer for e, then e and e^u are equivalent expressions.

If d and e are expressions and there is a substitution u such that d^u = e^u, then d and e are unifiable and u is a unifier for them. A unifier of d and e is a most general unifier (or mgu) of d and e if it is a generalization of every unifier of d and e. Note that all mgu’s for d and e are equivalent.

11.1.2 States and Satisfiers

A state is a list of ground atoms intended to represent some “state of the world”. A conjunct C is a consequent of a state S and an axiom list X if every logical expression l in C is a consequent of S and X. A logical expression l is a consequent of S and X if one of the following is true:

• l is an atom in S;
• l is a ground expression of the form (eval f t1 t2 … tn), and the evaluation of f with arguments t₁,t₂,…,t_n returns a non-nil value;
• l is a ground expression of the form (call f t1 t2 … tn), and the evaluation of f with arguments t₁,t₂,…,t_n returns a non-nil value;
• l is an expression of the form (not a), and the atom a is not a consequent of S and X;
• l is an expression of the form (assign v t), where v is a variable symbol and t is any Lisp expression. The value of t, which was evaluated via a call to the Lisp evaluator, is a substitution of v, i.e.( v . t). This term is always a consequent of S and X;
• l is an expression of the form (or l₁ l₂ … l_n), where l₁, l₂, l₃, …, l_n are logical expressions, and at least one expression in this list is a consequent of S and X;
• l is an expression of the form (forall V Y Z), where Y and Z are logical expressions and V is the list of variables in Y such that for every satisfier u that satisfies Y in S and X, u also satisfies Z in S and X;
• l is an expression of the form (imply Y Z), where Y and Z are logical expressions such that any satisfier u that satisfies Y in S and X also satisfies Z in S and X;
• there exists a substitution v and an axiom (:- a n1 C1 n2 C2 … nn Cn) in X 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 if there is no strict generalization of C that is also a consequent of S and X.

Let S be a state, X be an axiom list, and C be an ordinary 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 the satisfier. The satisfier u is a most general satisfier (or mgs) if there is no other satisfier that is a strict generalization of u. Note that C can have multiple non-equivalent 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 supermarket 2))

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

Let S be a state, X be an axiom list, and C = (:first C') be a tagged conjunct. If S and X satisfy C’, then the mgs (most general satisfier) for C from S and X is the first mgs for C’ that would be found by a left-to-right depth-first search. For example, if S and X are as in the previous example, then for the tagged conjunct (:first (walking-distance ?y)), the mgs from S and X is ((?y . convenience-store)).

11.2.1 Semantics of Operators

Update note: SHOP3 now supports PDDL operators, which have cleaner (but more restricted) semantics. Their semantics is discussed in many treatments of the PDDL specification. We hope to add an explanation later. See Chapter 7 for discussion of PDDL support in SHOP3. [12 June 2018 – rpg]

The intent of an operator is to specify that the task h can be accomplished at a cost of c, by modifying the current state of the world to remove every logical atom in D and add every logical atom in A if P is satisfied in the current state. In order to prevent plans from being ambiguous, there should be at most one operator for each primitive task symbol. Furthermore, whenever an action is inserted into a plan, it must be ground – there must be no unbound parameters in its task head. [Inserted 12 June 2018 based on discussions with Ugur – rpg]

Let S be a state, X be the list of axioms, L be the list of protected conditions, t be a primitive task atom, and o be a planning operator whose head, precondition, delete list, add list, and cost are h, P, D, A, and c, respectively. Suppose that there is an mgu u for t and h, such that h^u is ground, that none of the ground atoms in D^u are in the list of protected conditions, and P^u is satisfied in S. Then we say that o^u is applicable to t, and that h^u is a simple plan for t. If S is a state, then the state and the protection list produced by executing o^u (or equivalently, h^u) in S and L is the new state:

(S’,L’) = result(S,L,h^u) = result(S,L,o^u) = (S - D^u) U A^u.

where S’ and L’ are obtained by modifying the current state of the world and the list of protected conditions as follows:

• remove every logical atom in D^u from the current state;
• remove every protection condition in D^u from the list of protected conditions;
• for every expression (forall V Y Z) in D^u and every satisfier v such that S and X satisfy Y^v, remove every logical atom in Z^u from the current state;
• for every expression (forall V Y Z) in D^u and every satisfier v such that S and X satisfy Y^v,, remove every protection condition in Z^u from the list of protected conditions;
• add every logical atom in A^u to the current state;
• add every protection condition in A^u to the list of protected conditions;
• for every expression (forall V Y Z) in A^u and every satisfier v such that S and X satisfy Y^v, add every logical atom in Z^u to the current state;
• for every expression (forall V Y Z) in A^u and every satisfier v such that S and X satisfy Y^v, add every protection condition in Z^u to the list of protected conditions.

Here is an example:

(:operator (!set-money ?person ?old ?new)
    ((has-money ?person ?old))
    ((has-money ?person ?old))
    ((has-money ?person ?new)))

(:operator (!set-money john 40 35)
    ((has-money john 40))
    ((has-money john 40))
    ((has-money john 35)))

Here is an example using the forall keyword

 (:operator (!clear-locations)
    ((forall (?l)
        ((location ?l)
        (not (truck-at ?t ?l)))
    ((location ?l))))
    ())

(:operator (!clear-locations)
    (forall (?l)
        ((location ?l)
         (not (truck-at ?t ?l))))
     ((location ?l))
    ())

11.2.2 Semantics of Methods

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 S be a state, X be an axiom list, t be a task atom (which may or may not be ground), and m be the method (:method h C1 T1 C2 T2 … Ck Tk). Suppose there is an mgu (most general unifier) u that unifies t with h; and suppose that m has a precondition C_i such that S and X satisfy C_i^u; if there is more than one such precondition, then let C_i be the first such. Then we say that m is applicable to t in S and X, with the active precondition C_i and the active tail T_i. Then the result of applying m to t is the set of task lists

R = {CALL((T_i^u)^v): v is an mgs for C_i^u from S and X}

where CALL is SHOP3’s evaluation function (the function that evaluates the values of the call terms in the form (call f t1 t2 .. tn)). Each task list r in R is called a simple reduction of t by m in S and X. Here is an example:

 (:method (transfer-money ?p1 ?p2 ?amount)
    ((has-money ?p1 ?m1)
     (has-money ?p2 ?m2)
     (call >= ?m1 ?amount))
    (:ordered (:task !set-money ?p1 ?m1 (call - ?m1 ?amount))
                   (:task !set-money ?p2 ?m2 (call + ?m2 ?amount))))

((has-money john ?m1)
 (has-money mary ?m2)
 (call >= ?m1 5))

(:ordered
     (:task !set-money john ?m1 (call - ?m1 5))
     (:task !set-money mary ?m2 (call + ?m2 5)))

((has-money john 40)
  (has-money mary 30)
  (call >= 40 30))

(:ordered
     (:task !set-money john 40 (call - 40 5))
     (:task !set-money mary 30 (call + 30 5)))

(:ordered
     (:task !set-money john 40 35)
     (:task !set-money mary 30 35))

11.2.3 Semantics of Plans

Recall that a planning domain contains axioms, operators, and methods, and that a planning problem is a 4-tuple (S,M,L,D), where S is a state, M is a task list, L is a protection list, and D is a domain representation.  Let T be the list of tasks in M that have no predecessor (i.e., those tasks can be performed at this time if they are applicable).   If t is a task in T, and S is a state, then a reduction of t in S and D with respect to M and L that results in a new planning problem (S’,M’,L’,D)  is defined as follows:

if t is a primitive task, then

(S’, L’) = result(S,L,t);

M’ = the task list produced by removing t from M

else t is a compound task, then

S’ = S;

L’ = L;

Suppose m is an applicable method to t in S, with unifier u, the active precondition C_i and the active tail T_i.

M’ = the task list produced by replace t with T_i^u in M

endif

If P = (p₁ p₂ … p_n) is a plan, then we say that P solves (S,M,L,D), or equivalently, that P achieves M from S in D (we will omit the phrase "in D" if the identity of D is obvious) in any of the following cases:

Case 1.

both M and P are empty.

Case 2.

T = (t₁ t₂ … t_k) is a list of tasks in M that have no predecessor for which there is a task t_i that has the :immediate keyword and is applicable to the current state S.  Let (S’, M’, L’) = reduction(t_i, S, M, L).  We say P solves(S,M,L,D) if either of the following is true.

• t_i is primitive and  p₁ = t_i and (p₂  p₃ … p_n) solves (S’, M’, L’, D)
• t_i is not primitive, and P solves (S’, M’, L’, D)

Case 3.

T = (t₁ t₂ … t_k) is a list of tasks in M that have no predecessor, where t_i is a task in T that’s applicable to the current state S.  Let (S’, M’, L’) = reduction(t_i, S, M, L).  We say P solves (S,M,L,D) if either of the following is true.

• t_i is primitive and p₁ = t_i and (p₂  p₃ … p_n) solves (S’, M’, L’, D)
• t_i is not primitive and P solves (S’, M’, L’, D)

The planning problem (S,M,L,D) is solvable if there is a plan that solves it. For example, suppose that

(
    (:operator (!do ?operation) nil ((did ?operation)))
    (:method (do-both ?x ?y)
           nil
           (:ordered
               (:task !do ?x)
               (:task !do ?y)))
    (:method (do-both ?x ?y)
        nil
        (:ordered (:task !do ?y)
               (:task !do ?x))))

Then P₁ and P₂ are all of the plans that solve (S,M,L,D).