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.
In this assignment we consider a generalization we call the directed ring puzzle.
  • We have n disks just like the traditional Tower of Hanoi problem.
  • We have m rods, where it is possible that m ≥ 3.
  • Unlike the traditional problem, there are extra constraints on which moves are possible. You must satisfy the original rules on the sizes of the disks but, additionally, there is a (directed) graph formed with rods as vertices. A move is permitted between rod X and Y if and only if there is an arc connecting X to Y.

Project Infrastructure

You will be asked to submit a specification of the directed ring puzzle in PDDL; in order to do so, you would need to use a planner that solves problems specified in that description language. There are several pieces of software that can solve planning problems available, but we'll be using the following online planner: http://editor.planning.domains/#.

Getting Started with PDDL

In addition the linked documents below, here's another example for you to use to better understand PDDL. The textbook gives an example problem in the Air Cargo Domain. To understand how that abstract version (with syntax involving symbols not on your keyboard) can be translated into PDDL syntax, look at these two pieces of PDDL:

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.

I'm also told (but haven't checked myself) that there is a useful VSCode Plugin for PDDL which uses the planner in planning.domains as a backend. You might find that useful too.

A hint and a useful trick

You will need to define actions other than ones which describe disk movements. Specifically, you'll need some for managing extra properties. You can use these actions to ensure only sound plans (i.e., those satisfying the constraints of the puzzle) be produced.

These extra actions just described can clutter the plan output, so once you're happy they're working, you can rename them to start with an underscore and they'll be dropped from the plan output. For instance if LOAD and UNLOAD were renamed _LOAD and _UNLOAD respectively, then only the FLY actions would appear in the output (though the cargo loading and unloading would still be calculated and used in finding the plan).

Potentially Useful Links

Submission

The due date is April 26, 2024.

Extra credit: You can get 100% for this assignment if your definitions correctly represent the directed ring problem in PDDL. The naïve expression for N disks and M requires O(N2 + A + M) rules in the instance file, where A is the number of arcs (so is itself O(M2) in the worst case). You can get an extra 20% if your solution for the N disk and M rod problems only requires O(N + A + M) rules appear in the problem instance definition.

Submit your assignment via TAMU Canvas using these submission instructions. 

You may discuss this openly with your friends and classmates, but are expected to write your own code and debug 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.