planner [state  goal  operators]



Development notes:

1.    this planner has been tested with 3 different sets of operators but is still in "apha" release. It has not been packaged or name-spaced.

2.    the documentation below is thin (if you are using the planner & want more documentation please send me an email, it will rise up my todo list. Better still send me some improved documentation :)


planner provides a simple approach to planning based on means-end analysis/STRIPS/GPS. It uses a stack based algorithm which is considerably more efficient than algorithms based on search. The computational cost of running the planner is (roughly) linearly proportional to the length of the plan it produces. Before reading this guide it is (probably) a good idea to read about ops-search.



planner takes the following arguments...

·         state          - a start state

·         goal           - a minimally specified goal state (see below)

·         operators    - a collection of planner operators



ops-search returns a map showing...

·         the goal state it reached

·         any comands to send to another subsystem

·         a textual description of the path



Note: it is possible to use planning operators without the pattern matcher but its use is then highly restricted. For this guide we assume the pattern matcher will be used.



Goals are minimally specified so any state which is a superset of the goal is deemed a goal state.





Planner operators are specified in a map which should associate the operator name with its definition. Planner operators definitions describe preconditions and effects (effects in terms of deletions and additions). They also define other attributes (see below).


NB: the operators used in the examples below are based on a tuples but you can use other representations.


Planning operators can have all of the slots in the following example which is expanded below...

{ :name put-on

  :achieves (on ?x ?y)

  :when   ( (at ?x ?sx) (at ?y ?sy) (:guard (not= (? sx) (? sy))) )

  :post   ( (protected ?sx) (protected ?sy)

            (cleartop ?x) (cleartop ?y) (hand empty) )

  :pre ()

  :del ( (at ?x ?sx) (cleartop ?y)

         (protected ?sx) (protected ?sy) )

  :add ( (at ?x ?sy) (on ?x ?y) )

  :cmd ( (pick-from ?sx) (drop-at ?sy) )

  :txt (put ?x on ?y)





{ :name     put-on         ;; operator name

  :achieves (on ?x ?y)     ;; the goal this op can solve

  :when     ;; the conditions for considering this operator

            ;; this exmple is suitably applied when ?X and ?y

            ;; are on different stacks (?sx ?yy) – note :guard

            ( (at ?x ?sx) (at ?y ?sy)

              (:guard (not= (? sx) (? sy))) )

  :post     ;; sub-goals to be achieved before this operator is

            ;; applied. See explanation of protected later

            ( (protected ?sx) (protected ?sy)

              (cleartop ?x) (cleartop ?y) (hand empty) )

  ;; the remaining slots are the same as those used with ops-search operators

  ;; - see ops-search documentation

  :pre ()

  :del ( (at ?x ?sx) (cleartop ?y)

         (protected ?sx) (protected ?sy) )

  :add ( (at ?x ?sy) (on ?x ?y) )

  :cmd ( (pick-from ?sx) (drop-at ?sy) )

  :txt (put ?x on ?y)




Planner operaors  are processed as follows...


goal <- (pop goal-stack)

match (:achieves op) goal

  match (:when op) BD

    push( expand op , goal-stack )

    push-all( expand (:post op), goal-stack )


protected goals


To understand why it is necessary to protect goals/preconditions please read around GPS/STRIPS. To understand why/how we choose to implement protections as sub-goals ask SL (or attend a relevant lecture).


The implementation of protections as sub-goals requires a separate operator as follows...



  { :name protect-x

    :achieves (protected ?x ?c)

    :add  ((protected ?x ?c)  )