CSCI 5260 – Artificial Intelligence
The Towers of Hanoi is a mathematical game. It consists of three pegs, and a number of discs of different sizes
which can slot onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg,
smallest at the top, thus making a conical shape.
The object of the game is to move the entire stack to another peg, obeying the following rules:
a) Only one disc may be moved at a time.
b) A disc can only be placed onto a larger disc (it doesn’t have to be the adjacent size, though: the smallest
disc may sit directly on the largest disc).
Step 1 – PDDL
Write the Towers of Hanoi domain in PDDL using the following methods. For this example, we have three discs
as pictured. Add your PDDL code into the Lab 8 Word Document.
Initial State Goal State
o T1, T2, T3 – The three towers
o D1, D2, D3 – The three discs, in order of increasing size
o clear(X) which is true if tower X is empty
o on(A, B or Y) which is true if disc A is on top of disc B or tower Y
o smaller(A, B) which is true if disc A is smaller than disc B
CSCI 5260 – Artificial Intelligence Page 2
o move(A, B/X, C/Y) which relocates disc A from disc B or tower X to disc C or tower Y. Note
empty would indicate the first peg that is empty.
Step 2 – Solution
Using your PDDL definition, generate a solution. You may use http://editor.planning.domains to solve the
problem. Paste your solution into the Lab8 Word Document.
Step 3 – Plan Graph
Draw the first four levels (two steps past S0 and two actions past S0) of the plan graph for the problem.
Step 4 – Heuristic
Given the information you have just devised, can you describe a heuristic that would help you solve the problem?
If you say “no,” you need to justify why. If you say “yes,” describe the heuristic.
Create a Word Document named Lab8.docx with your responses. If you write it out on paper rather than
electronically, pictures or scans are fine.
Submit to the Lab 8 dropbox at or before Monday, March 29, 2021 by 11:59 PM.
A letter grade will be assigned for each response. The letter grades are based on both correctness and the
adequacy of answers. Points are assigned as follows:
A B C D F Zero
Average Average Below
Average Poor No Attempt
10 8 6 4 2 0
Hanoi in PDDL