Programming Assignment 5: Planning


Table of Contents


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 recomment using the online planner: web-planner.herokuapp.com

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

The Domain Definition File

;; 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

;; 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))))

If you paste the domain into the left window pane, and the instance into the middle one, then clicking "Plan" on the bottom of the right, should generate output: a plan that solves the air cargo planning problem.



Submission

Submit your assignment via TAMU eCampus using these submission instructions

  • Files to include in zip file:
    • The code you wrote for this assignment. This should be your pddl files with
      • A domain definition of the star puzzle;
      • Definitions for the problem with 4, 5, and 6 disks.
    • A short README.txt file with the following information:
      • Name: (Your name)
      • UIN: (Your TAMU UIN)
      • A description of how to run the submission.
      • A list of the resources used (e.g., online forums, links to example code on the web, etc.).
      • A statement of the Aggie Code of Honor.
      • Additional comments: ...

You may discuss this openly with your friends and classmates, but are expected to write your own code and compile your submission independently. If in doubt about whether a resource you used should be included in the list of resources, err on the side of caution and include it.


Academic Integrity: "An Aggie does not lie, cheat, or steal, or tolerate those who do." For additional information please visit: http://student-rules.tamu.edu/aggiecode

Getting Help: You are not alone! If you find yourself stuck on something, contact the TA for help. Office hours are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don't know when or how to help unless you ask.