Europe

This project is designed to enable the user to remotely play the puzzle towers of hanoi by interacting with a robotic arm. The use case is to solve this problem with three disks. While the user can interact with the game through the robo-arm and execute moves, the application can also autonomously find the best movement of disks and perform actions accordingly to reach a desired goal state. By applying constraint satisfaction, the application can reach the goal state from any given state. 

Problem Statement

The problem to tackle is how to design a system which can reach a desired goal state from a given initial state and let the application decide on its own what move to execute to reach this goal. The ideal solution to this problem is to find the shortest sequence of valid moves to move all the disks to a specific stack. For any given valid placement of disks there is, this sequence can to be found.  

Knowledge Engineering Concept

The solution to this problem can be solved with the help of a constraint satisfaction system, but we have seen problems that the disks take the wrong places to be placed and thus become stuck in a position that they can’t get out of. We have thus decided to solve this problem with a sequence of where and how the robot arm should move and where the disks should be placed. You also have the option of playing the game yourself by moving the disks manually with the robot arm to the designated areas. 

Towers of Hanoi is a mathematical puzzle which consists of a number of disks n with ascending values and three stacks on which the disks can be placed. The goal is to move all disks from one stack to another. The following rules have to be applied for the basic puzzle: 

1. Only on disk can be moved per turn
2. Only the top disk of a stack can be moved
3. For a given disk ?d? with value ?v? only disks with values less dann ?v? can be placed on top of it

The number of moves required to move all disks from one stack to another and by applying these rules is 2n-1. By formulating the puzzle as a Constraint Satisfaction Problem we can find the shortest sequence of moves for any given valid state of the puzzle. 
We therefore designed the problem as follows: 

1. Variables 1,2,3 represent the different disks
2. Domain D = {0,1,2,3,4,5,6,7,8,9} specifies the different positions on the 3x3 board.
3. In addition to the three previously defined constraints we also defined that a given disk which has been previously moved from a position ?p? to another position, it is not valid anymore to move the disk back to p. This constraint avoids sequence loops.

By applying a breadth-first search in combination with constraint propagation we can find all possible valid sequences to move all disks from a given state to a predefined goal state. When solving the puzzle the algorithm finds every valid move for a given board state and executes it and updates the information about what moves have been performed already. This is done recursively until a goal state is reached. 

The picture below shows the search space for all valid pisk position for a game with 3 disks. The characters define the stack on which a certain disk is placed. Assuming we are starting in the position marked green we want to find the shortest path to reach the goal state in red.

https://en.wikipedia.org/wiki/Tower_of_Hanoi#/media/File:Tower_of_Hanoi-3.svg 

As the picture depicts, the solution to the problem can be done in at maximum 7 steps. In general for any given number of disks n the goal state can be reached in  2^n - 1 steps.  

The majority of validation was done without the use of the robo arm and by only monitoring the game in a virtual space. Tests in the Knowledge Engineering lab focused on finding the right positions and coordinates for the arm movement as well as final validation of the project.