Contents
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: |
|
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 |
- • 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. |
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. |
|
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. |
- • 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
Robots
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. |
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: |
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.
- 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. |
- • The robot is allowed to carry more than two objects.
- • A run starts with an arbitrary configuration of objects obeying rule #1 and #2.
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’ on-board 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 "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. |
- 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.
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. |
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. |
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
- European Commission
- Directorate E: Digital Content and Cognitive Systems
E.5:
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: |
KUKA Laboratories GmbH, Germany, will provide a number of KUKA youBot mobile manipulators
(contact the event secretariat if you want to use a KUKA youBot for the 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. |
Simulators
The following companies are willing to provide free license for their simulation software for the purpose of the contest: |
- Cyberbotics, Switzerland, will provide free licenses to their simulator Webots
(animation of contest)
- V-REP, Switzerland, will provide free licenses to their simulator V-REP
(animation of contest)
- youBot Store GmbH, Germany, will provide an open source Gazebo/ROS simulation for the KUKA youBot
Software
The software packages below contain open source software that may be useful for the contestants: |
KUKA youBot API:
- A Robot SDK that will support the contestants is currently being developed. It will be made available as soon as possible.
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: |