Overview
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:
- Only one disc may be moved at a time.
- 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 |
- Elements:
- T1, T2, T3 – The three towers
- D1, D2, D3 – The three discs, in order of increasing size
- Predicates: o clear(X) which is true if tower X is empty
- 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
- Action:
- 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.
