Building simple planners in Lisp

The focus of the planners is on clarity, rather than time or space efficiency; they should offer a reasonable introduction to planning as well as to Lisp programming. Excluding comments, documentation, PAIP/AIMA code, data structure definitions, and utilities (i.e., just focusing on the algorithms), there are around 135 lines in the propositional simple-POP algorithm, 90 lines in the first-order extension, and 180 lines in the simple-GP algorithm. Simple-POP and simple-GP are thus small enough that the code can be presented in the classroom. I expect that students with half a semester of Lisp instruction might usefully test and modify the systems in homework assignments or projects. The tradeoff (aside from functionality--the planners are stripped to the essentials) is that the planners are horrendously slow. For example, some problems that UCPOP solves in tenths of a second can take simple-POP tens of seconds. While simple-GP is faster than simple-POP and can thus handle larger problems, it's also slow in comparison with more sophisticated implementations of GraphPlan.

All three planners can be used with either the PAIP or AIMA Lisp code. The planners have been most extensively tested using the PAIP code base, in OpenMCL (Mac OS X), CLisp (Mac OS X), Lispworks Personal 5.0 (Mac OS X, Windows XP), CMUCL-19d (Mac OS X), and Allegro 8.0 Free Express (Windows XP), where they run apparently correctly on a variety of solvable toy problems.

If you have questions about the code, would like to contribute changes or bug fixes, or would simply like to say that you find it useful, please send email to the author, Rob St. Amant (stamant@csc.ncsu.edu).

Getting started

1. Get the AIMA or PAIP source code:

   AIMA: http://aima.cs.berkeley.edu/lisp/doc/overview.html

   PAIP: http://www.norvig.com/paip/README.html

2. Get the code for the simple planners:

   http://www.csc.ncsu.edu/faculty/stamant/simple-pop.zip

3. Extract all the files from the archive and follow the installation instructions in simple-README.txt.

4. Start your Lisp environment. Load the system and test the planners. A number of domains and problems can be found in simple-pddl-domains.lisp and are loaded automatically with the system. Two domain examples, plus associated problems:

   ;;; In simple-pddl-domains.lisp [AIMA, p. 388]
   (define (domain socks-and-shoes)
     (:action Right-Shoe :precond Right-Sock-On :effect Right-Shoe-On)
     (:action Right-Sock :precond nil :effect Right-Sock-On)
     (:action Left-Shoe :precond Left-Sock-On :effect Left-Shoe-On)
     (:action Left-Sock :precond nil :effect Left-Sock-On))
   
   (define (problem put-on-shoes)
       (:domain socks-and-shoes)
     (:init)
     (:goal (and Right-Shoe-On Left-Shoe-On)))
   
   ;;; In simple-pddl-domains.lisp [AIMA p. 380]
   (define (domain cargo)
     (:action Load
              :parameters (?c ?p ?a)
              :precond (and (At ?c ?a) (At ?p ?a) (Cargo ?c) (Plane ?p) (Airport ?a))
              :effect (and (not (At ?c ?a)) (In ?c ?p)))
     (:action Unload
              :parameters (?c ?p ?a)
              :precond (and (In ?c ?p) (At ?p ?a) (Cargo ?c) (Plane ?p) (Airport ?a))
              :effect (and (At ?c ?a) (not (In ?c ?p))))
     (:action Fly
              :parameters (?p ?from ?to) 
              :precond (and (At ?p ?from) (Plane ?p) (Airport ?from) (Airport ?to))
              :effect (and (not (At ?p ?from)) (At ?p ?to))))
   
   (define (problem deliver-no-return)
     (:domain cargo)
     (:objects C1 SFO P1 JFK)
     (:init (At C1 SFO) (At P1 SFO)
            (Cargo C1) (Plane P1)
            (Airport JFK) (Airport SFO))
     (:goal (At C1 JFK)))
   
   (define (problem back-and-forth)
     (:domain cargo)
     (:objects C1 C2 SFO P1 P2 JFK)
     (:init (At C1 SFO) (At C2 JFK) (At P1 SFO) (At P2 JFK)
            (Cargo C1) (Cargo C2) (Plane P1) (Plane P2)
            (Airport JFK) (Airport SFO))
     (:goal (and (At C1 JFK) (At C2 SFO))))
   

   Given such domain and problem definitions, you can paste the following into a Lisp listener/REPL:

   (plan (make-instance 'propositional-POP-planner) 'put-on-shoes :domain 'socks-and-shoes)
   ;;; returns #<Plan: Left-Sock, Left-Shoe, Right-Sock, Right-Shoe>
   ;;; Steps are linearized for printing.
   
   (plan (make-instance 'POP-planner) 'put-on-shoes :domain 'socks-and-shoes)
   ;;; returns #<Plan: Left-Sock, Left-Shoe, Right-Sock, Right-Shoe>
   
   (plan (make-instance 'GP-planner) 'put-on-shoes :domain 'socks-and-shoes)
   ;;; returns #<Plan: [Right-Sock, Left-Sock]; [Right-Shoe, Left-Shoe]>
   
   ;;; or, in a domain with first-order actions:
   
   (plan (make-instance 'POP-planner) 'deliver-no-return :domain 'cargo)
   ;;; returns #<Plan: Load(C1 P1 SFO), Fly(P1 SFO JFK), Unload(C1 P1 JFK)>
   
   (plan (make-instance 'f-POP-planner) 'deliver-no-return :domain 'cargo)
   ;;; returns #<Plan: Load(C1 P1 SFO), Fly(P1 SFO JFK), Unload(C1 P1 JFK)>
   
   (plan (make-instance 'GP-planner) 'back-and-forth :domain 'cargo)
   ;;; returns #<Plan: [Load(C1 P1 SFO), Load(C2 P2 JFK)]; [Fly(P2 JFK SFO), Fly(P1 SFO JFK)]; [Unload(C2 P2 SFO), Unload(C1 P1 JFK)]>
   
   

   There are minor differences in the plans returned by the planners, as shown (e.g., linearized steps in simple-POP plans; levels of unordered actions in simple-GP plans). The repeated creation of planner instances above is not necessary for handling different problems or domains.

Notes on the files

simple-README.txt: This file explains where the code for the planners should be installed and how the planners can be loaded.

aima-compatibility.lisp: This file contains conditionalizations that allow the planning code to run based either on the PAIP or the AIMA code base.

simple-utilities.lisp: This file contains general utility functions and macros used by the simple-POP and simple-GP planners.

simple-pddl-domains.lisp: This file contains a small number of problems and their associated domains, for testing the planners. For the PAIP code base, GPS problem specifications have been translated into PDDL: *school-ops*, *banana-ops*, *maze-ops*, and propositional blocks world. PDDL parsing is fragile; using domains and problems from other sources may require a bit of work to translate them into an appropriate form.

simple-data-structures.lisp: This file contains data structure definitions for the simple-POP and simple-GP planners: steps, actions, and plans, along with supporting utility functions.

simple-planners.lisp: This file contains a consistent way of invoking the planners, with a separate class definition for each planning algorithm: propositional-POP-planner, POP-planner, and GP-planner. The method plan sets up the appropriate variable bindings and handles planner-specific pre-processing.

simple-pop.lisp: This file contains the code for the propositional partial-order planner. The top-level function is simple-POP, though calls to plan as above are probably more convenient.

simple-pop-with-bindings.lisp: This file contains methods that extend simple-POP to handle planning with variable bindings. While several new methods are needed, the basic planning algorithm and its core functions, including the function simple-POP, remain unchanged.

simple-gp.lisp: This file contains the code for GraphPlan, including the top-level function, simple-GP, though calls to plan as above are probably more convenient.