Building simple planners in Lisp

This is the home of a few simple Lisp planning systems intended for classroom use. The first is a partial-order planner for propositional actions, simple-POP; the second is an extension of simple-POP to accommodate first-order actions (i.e., actions with variable bindings); the third is a straightforward Lisp implementation of the GraphPlan algorithm, simple-GP. These planners were developed for teaching a class using Peter Norvig's Paradigms of AI Programming: Case Studies in Common Lisp (PAIP). The design of the planners follows Chapter 11 of Stuart Russell and Peter Norvig's Artificial Intelligence: A Modern Approach, 2nd edition (AIMA). The incremental development of the planners reflects the discussion in AIMA. The planners run using the Lisp code supplied with either PAIP or AIMA.

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, 80 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 the PAIP or AIMA Lisp code, or without either. The planners have been most extensively in OpenMCL (Mac OS X) and Lispworks Personal 5.0 (Mac OS X), where they run apparently correctly on a variety of solvable toy problems. The planners have been tested in the past on other Lisp implementations, including CMUCL-19d (Mac OS X), Lispworks Personal 5.0 (Windows XP), and Allegro 8.0 Free Express (Windows XP), but testing of the current release has been sporadic. It should be trivial to port the code if it does not run already.

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

Get the code for the simple planners:
http://www.csc.ncsu.edu/faculty/stamant/simple-planners.zip
Follow the installation instructions in simple-README.txt.

Start your Lisp environment. Load the system and test the planners. A few domains and problems are loaded automatically with the system. Two domain examples, plus associated problems:

;;; In simple-problems.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-problems.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.

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

simple-pddl-processing.lisp: This file contains functions for handling PDDL. PDDL parsing is very fragile; using domains and problems from other sources may require a bit of work to translate them into an appropriate form.

simple-problems.lisp: This file contains a small number of problems and their associated domains, for testing the planners.

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.

standalone.lisp, aima-compatibility.lisp, paip-planners.lisp, paip-compatibility.lisp, and paip-problems.lisp: These files contain code specific to different code bases, to allow the planning systems to run in standalone form or to run on top of the PAIP or the AIMA code base.