The Tower of Hanoi for Robotics
A contest for mobile manipulation for undergraduate and graduate robotics students during
IEEE/RSJ Int. Conf. on Intelligent Robots and Systems
October 7-12, 2012
Vilamoura, Algarve, Portugal
1. The Tower of Hanoi – a problem for computer and robot scientists and students
1.1 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.
Figure 1: The Tower of Hanoi Problem.
1.2 The Tower of Hanoi for robot scientists
The Tower of Hanoi is not only an excellent problem to teach and study the problem of designing optimal algorithms (recursive or iterative). It is also a very nice 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 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 interested in mobile manipulation.
2. Robot contest Tower of Hanoi
2.1. Contest setup
A possible set up for the robot contest Tower of Hanoi is visualized in Figure 2. We assume a confined contest area, which is typically around 2.5 x 2.5 sqm large. In cases, where the size of a participating robot takes up to much space of the contest area it will be adjusted to ensure that all robots stand an equal chance. The contest area will contain three distinguished locations related to the task: one will serve as a target location to erect the final tower the two others will serve as initial and auxiliary location. A fourth location will be the home positions of the robot from where it will start and to which it has to return after the task is accomplished. The exact positions of these locations will be announced at the beginning of a run. The locations will be marked by clearly visible, distinguishable markers.
Figure 2: Tower of Hanoi as robot contest.
To simplify the problem of grasping difficult objects such as thin disks stacked on a rod we use cubes instead. The cubes will have a size and a weight such that a small-scale robot like the humanoid robots NAO or DAR-win-OP or the mobile manipulator KUKA youBot can easily grasp and lift them. There will be no other objects or other robots in the workspace.
We further use a color code to distinguish the objects and also to establish an order in which they must be stacked or be placed with respect to each other. We use three different colors: red, yellow, green. The relation between the objects, which must be obeyed, are explained below.
Variations of the set up (to be decided one month before the qualifications):
- Use of cuboids rather than cubes;
- Placement of additional obstacles in the contest area;
- Use more or less objects than shown in Figure 2;
- Use different color code.
In general we allow any robot, which qualifies as mobile manipulators. This means that the robot
- has to move on the ground and has to be capable of navigating in unknown environments;
- has to be capable of perceiving and localizing objects, and
- has to be capable of manipulating objects.
The robots may be self-designed and self-built or commercial off-the-shelf products.
The robots should neither require any specific floor covering nor damage the floor covering in the contest area. The latter would lead to a disqualification.
The task is to move the objects from their current locations to the target location and to stack them there in a certain order to form a tower in the fastest way possible. While doing so the robot has to obey certain rules:
- The "color code" from the bottom to the top of a stack must be green < yellow < red. This means, for ex-ample, that a green object must never be placed on top of a yellow or red one or a yellow one must never be placed on top of a red one;
- Objects on one level of a stack must always be of the same color. This means that objects of different colors must never be placed besides each other. For example, a red object be must never be placed next to a yellow one;
- Objects must be placed only within the marked locations. All locations apart from the home location can be used as temporary storage place for the objects. An accidental drop of an object is not considered as a violation of this rule, provided the lost object is immediately grasped again;
- The robot must never transport more than 2 objects at a time;
- The task is accomplished once all objects are stacked in the target location such that rule 1 and 2 are satisfied.
At the beginning of a run the objects are typically stacked at the initial location obeying rule #1 and #2.
Variations (to be decided one month before qualifications):
- The robot is allowed to carry more than two objects;
- A run starts with an arbitrary configuration of objects obeying rule #1 and #2.
2.4. Additional rules
Besides the rules directly related to the task, there are a few additional rules the violation of which will lead to immediate disqualification:
- The task must be solved fully autonomously. Communication or physical or virtual interaction with human operators or team members are strictly prohibited. Remote computing through wireless is allowed, provided there is no human intervention;
- No auxiliary facilities supporting the robots’ onboard recognition, navigation, or manipulation are allowed other than those provided by the contest organizers;
- During the contest runs team members are not allowed to enter the contest area.
- Team members are not allowed to modify the contest set up provided by the organizers;
- The robots must not place objects outside the areas specified in Section 2.3 item 3.
The primary criterion for the performance evaluation of a team is time. A team that solves that task in a shorter time naturally receives higher scores than a team, which needs longer.
There will be a time limit for every trial. The time limit will be announced before the contest. Should a team not finish within the given time limit, the criteria to evaluate the performance will be the number of correct / optimal moves, which the team has made already towards solving the task.
For example, if the time is used up and a team has only two blocks left to move for the final configuration then the performance will be scored as n – 2, where n is the number of optimal moves. So, the further away the team is from the final configuration the lower its scores.
In a nutshell the ranking of the teams will be as follows:
- A team that finishes the task in time is higher ranked than a team that does not finish the task in time;
- For teams who managed to solve the task in time, the ranking will be according to the time, which the teams needed to solve the task, the shorter the time the higher the rank;
- For those teams who do not manage to solve the task within the time limit, the ranking will be reciprocal to the number of moves left to solve the problem; the more moves a team would have to make the lower the ranking.
2.6. Course of contest
The contest event itself will consist of a preliminary, a semifinal and a final. The contest will take place in two adjacent contest areas, so that two teams can perform at a time. The two teams, however, will not directly compete against each other in a K.O. manner, but only race against time. In every round each team has two trials, of which only the better one counts. The trials are organized in two subsequent series. Should a team fail to finish its trail for whatever reason – hardware failure, software failure, power loss – the trial counts as a regular run. There will be no extra chance. The two preliminaries and the final will follow the model just described.
All teams, which pass the qualification rounds, will be allowed to participate in the preliminary. The best eight teams in the preliminary will reach the semifinal. In the semifinal, the best four teams out of these eight will be selected for the finals.
Depending on the number of teams the contest will take place on two subsequent days. The preliminary will take place in the first day, the semifinal and the final will take place in the second day.
Submission details are described here.
4. Technical Committee
- Walter Nowak, Locomotec, Germany;
- Erwin Prassler, Bonn-Rhein-Sieg University, Germany;
- Rainer Bischoff, KUKA Laboratories, Germany;
- Albert Amos, Robert Bosch GmbH, Germany (to be confirmed).