The tower of Hanoi - a problem for computer and robot scientists and students

Figure 1:  The Tower of Hanoi Problem  

The Tower of Hanoi for computer scientists

The Tower of Hanoi  is a problem that has been known to generations of computer science students. It is an excellent vehicle to study and learn the concept of recursion in algorithm design. The task is to move a pile of disks with the smallest amount of moves from one location to another. While solving the task the following two rules have to be obeyed:

1. Only one disk must be moved at a time.
2. Never must a disk with a larger diameter be placed on top of a disk with a smaller diameter

The second rule enforces that the disks at all three locations are sorted from the bottom to the top with a decreasing diameter. To make the problem solvable without violating the rules, a third auxiliary location is introduced at which disks might be temporarily deposited. In principle, the disks can be arbitrarily moved back and forth between the three locations (initial, goal, auxiliary). An algorithm, which works on a trial and error principle and arbitrarily moves disks back and forth may of course lead to solutions which are everything but optimal. Hence a smart strategy for planning the motion is required.

The Tower of Hanoi for robot scientists

The Tower of Hanoi is not only an excellent problem to teach and learn about the problem of designing optimal algorithms (recursive or iterative), but it is also an important problem for robotics research and education. The fundamental difference is that we are not dealing with a virtual world, but with a real world. Although the above figure suggests a physical instantiation of the problem, computer scientists do not use real disks and do not worry about their geometric shape and their metric position. In contrast, robot scientists do to worry about the physical world. After all, their robots have to move and act in the real world.
Is the Tower of Hanoi problem a real problem for robot scientists or just an artificial toy problem? At first glance it looks very much like the much debated blocks’ world problems in artificial intelligence. However, it does not require much contemplating to see that solving the Tower of Hanoi problem in the real world by a robot is everything but an easy problem. As a matter of fact the Tower of Hanoi problem can serve as an excellent scenario to study some of the most demanding scientific challenges in robotics today. Solving the Tower of Hanoi problem – if done efficiently and fast - requires the seamless integration of:

• perception including object recognition, scene understanding and situation awareness,
• world modeling (in 3D),
• task planning (for mobile manipulation),
• motion planning (for mobile manipulation),
• coordination and control including navigation.

Most of theses topics themselves still pose numerous scientific problems and questions and therefore have been subject of intense research for the past decade(s). Their seamless integration, although a key for any real mobile manipulation, is everything but solved.
In spite of its challenging nature, the Tower of Hanoi problem also has the appeal that it does not overload the problem with too many issues, which for the time being only obstruct the clear view to this seamless integration and complicate the problem even further. It is an excellent vehicle to study the scientific issues listed above not only in isolation, but also in an integrated only manner. It is a vehicle for research and education in mobile manipulation and, last but not least, it yields a perfect setting for a robot contest for students and their teachers inter-ested in mobile manipulation.