tower_of_hanoi - BRICS challenges and contests

The Tower of Hanoi for Robotics

A contest for mobile manipulation for undergraduate and graduate robotics students
London Science Museum, London, UK.
Dec. 2 & 3, 2011 during 1st European Robotics Week


The Tower of Hanoi for computer scientists

The 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.

TowerHanoi.png
©
Figure 1: The Tower of Hanoi Problem

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 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 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

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.

Robot contest Tower of Hanoi


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.

robotics_toh.png
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 DARwin-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)

Robots

In general we allow any robot, which qualifies as mobile manipulators. This means that the robot

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.

Task

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:

  1. The "color code" from the bottom to the top of a stack must be green < yellow < red. This means, for example, 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.

  2. 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.
  3. 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.
  4. The robot must never transport more than 2 objects at a time.
  5. 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):

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

  1. 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.
  2. No auxiliary facilities supporting the robots’ on-board recognition, navigation, or manipulation are allowed other than those provided by the contest organizers.
  3. During the contest runs team members are not allowed to enter the contest area.
  4. Team members are not allowed to modify the contest set up provided by the organizers.
  5. The robots must not place objects outside the areas specified in Section "Task" item 3.

Scoring

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:

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 described below, will be allowed to participate in the preliminary. The eight best 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 on the first day, the semifinal and the final will take place on the second day.

Qualifications

The qualifications will take place four weeks before the actual contest and will be organized as a cyber-contest. Technical and organizational details of this cyber-contest will be announce in due time.

Teams, which participate with their own robots, will be invited to demonstrate the performance of their system at their own sites. To allow a jury to evaluate their performance they will have to broadcast their trial via some video-conferencing or life-stream facility to the organizer’s site. Time will be taken at the organizers site.

Teams, which do not have their own hardware and instead use the hardware provided by the sponsors will have to develop and test their system in simulation first. Several simulators and simulations of the avail-able hardware will be provided free of cost to the participants (see Section Hardware and Software Support). These teams will get access to the hardware either physically at the site of the organizer or remotely in due time to test their software on the real robot and prepare for the qualification. For the qualification their software will be run and demonstrated on the sponsored hardware by staff at the organizers site.

Prizes and grants


All teams that pass the qualification and manage to get into the semifinals will receive a travel grant of 1.000 EUR each. In addition the best three teams will receive a monetary prize.

Patronage of the event


The event takes place under the auspices of the

Organizers


Hardware and software support


The European Commission strongly supports the open source movement in general, but also in the field of robotics. The Commission has therefore requested to the organizers to provide free access to hardware and software wherever possible to allow also such teams to participate in the contest, which do not have a sufficient budget to do this on their own cost.

Robot platforms

The following robot manufacturers are willing to provide free access to robot hardware for testing and experimentation and for the final contest:

The hardware will be made available at one or two yet to be defined central locations. Teams can access the hardware at these locations either physically or remotely. Access times have to be negotiated with the event secretariat.

Teams who want to access the hardware remotely will first have to prove in simulation (for simulators see section below) that their software functions properly. Upon such verification the teams will receive an IP address to where they can upload and install their software. Staff of the event secretariat will then perform the actual testing and evaluation. The tests will be broadcasted back to the team via video conferencing.

Hardware and staff to operate it and perform the remote trials will be available also for the qualifications (see description above). Two days before the contest the hardware will then be available physically at the contest venue.

Simulators

The following companies are willing to provide free license for their simulation software for the purpose of the contest:

Software

The software packages below contain open source software that may be useful for the contestants:

Participation and registration


Participation will be free. Travel costs have to be covered by participants themselves. Registration is required. To register for the event, please, send an email to the event secretariat before the registration deadline.

Venue and schedule


Venue

The preliminaries and the final of the contest will take place at the London Science Museum.

Schedule

15. Oct. 2011

Deadline for registration

01.-25.Nov. 2011

Remote access, testing and evaluation

09.-10. Nov. 2011

Qualifications

02.-03. Dec. 2011

Contest

Event secretariat


Locomotec UG

Nobelstraße 15

70569 Stuttgart, Germany

Email:

tower_of_hanoi (last edited 2011-09-07 12:04:10 by zimmermann)