Programming Assignment 7: Planning and PDDL

---

Table of Contents

• Problem Domain
• Project Infrastructure
• Potentially Useful Links
• Submission

Overview: Problem Domain

The Tower of Hanoi problem is a puzzle of the following form: we are given three rods, and a collection of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a stack in a conical shape owning to their ascending ordering of size on one rod. The objective is to move the entire stack of disks to another rod, obeying the following rules:

1. Only one disk may be moved at a time.
2. Each move involves taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.

Paul Stockmeyer wrote a paper entitled "Variations on the Four-Post Tower of Hanoi Puzzle" (appearing in Congressus Numerantium volume 103, pages 3--12, 1994) which poses a generalization called the Star Puzzle. He defines the puzzle this way:

"This new puzzle consists of three posts, labeled A, B, and C, arranged in an equilateral triangle, and a fourth post, labeled O in the middle. Every disk move must be either to or from post O; direct moves between any two posts A, B, and C are prohibited. Thus the allowable move graph is a star. The task is to transport a tower of n disks from post A to, say, post C."

Project Infrastructure

You will be asked to submit a specification of the Star Puzzle in PDDL; in order to do so, you would need to use a planner that solves problems specified in that description language. I recommend using the online planner: http://editor.planning.domains/#

Textbook Example: Air Cargo Domain

The textbook gives an example problem in the Air Cargo Domain. This can be written in PDDL in two pieces:

The Domain Definition File (cargo-domain.pddl)

;; STRIPS domain of the Air cargo transport

(define (domain air-cargo)
  (:requirements :strips)
  (:predicates (In ?obj ?place)
    (At ?obj ?place)
    (Cargo ?obj)
    (Plane ?obj)
    (Airport ?obj))
  (:action LOAD
    :parameters (?c ?p ?a)
    :precondition (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)
    :precondition (and (In ?c ?p) (At ?p ?a)
      (Cargo ?c) (Plane ?p) (Airport ?a))
    :effect (and (not (In ?c ?p)) (At ?c ?a)))
  (:action FLY
    :parameters (?p ?from ?to)
    :precondition (and (At ?p ?from)
      (Plane ?p) (Airport ?from) (Airport ?to))
    :effect (and (not (At ?p ?from)) (At ?p ?to)))
)

The Problem Instance Definition File (cargo-instance.pddl)

;; STRIPS Instance problem for the Air cargo transport

(define (problem pb1)
  (:domain air-cargo)
  (:objects C1 C2
    P1 P2
    SFO JFK)
  (:init
   ;; types
   (Cargo C1) (Cargo C2)
   (Plane P1) (Plane P2)
   (Airport SFO) (Airport JFK)

  ;; locations
  (At C1 SFO) (At C2 JFK) (At P1 SFO) (At P2 JFK))

  (:goal
   (and (At C1 JFK) (At C2 SFO))))


Using the planner to compute a plan

Point your browser to http://editor.planning.domains/#. Download the two PDDL files above and then use the File | Load menu option to load both of these PDDL specifications. You can modify those files directly in that interface.

To solve the problem, click the Solve menu option. Make sure the domain is the cargo-domain.pddl file, and the instance is the cargo-instance.pddl file. Then click Plan. This should produce a new entry in the editor list (on the left pane) that says "Plan (I)". It will give you a sequence of actions that solves the problem.

Your task

Specify the four-post Towers of Hanoi problem described above: describe the domain (in PDDL), and make planning instances (in PDDL) with 4, 5, and 6 disks. If your specification is correct, the planner should output a valid plan to solve the problem.

You can get 80% of the credit, if your description for N disks has Ω(N²) statements. To get full credit, your PDDL description for N disks should have O(N) statements.

Potentially Useful Links

• PDDL by Example: A simple tutorial
• Pointers on writing PDDL
• Wikipedia's entry on the Planning Domain Definition Language