As an undergraduate I participated in a yearlong robotics project in which we programmed ERS-210 and ERS-7 robotic dogs made by Sony to compete in the Standard Platform League (SPL) of the international RoboCup competition. Our technical report [1] provides an in-depth look into the core challenges of teaching robots to play soccer, the solutions developed by our team, and the involved support infrastructure. As part of the GermanTeam – a collaboration between the universities of Berlin, Bremen, Darmstadt, and Dortmund – we won the world championship in the SPL as well as the SPL Open Challenge in 2004.

My main contribution was the development of a decentral scheduling algorithm that allows multiple robots to coordinate their behavior to achieve a common goal in a challenging, dynamic environment where communication might be intermittent and the number of robots might change without prior notice [2,3]. The behavior of the robots is described by a set of tasks that each robot can perform and a set of task configurations that describe which tasks can or should occur simultaneously. Each robot continously evaluates how well it can execute each of the tasks according to its current state. For example, a task might be move_to(x,y). If the robot is already close to position (x,y) it rates the task with a high value. If the robot is unable to reach position (x,y) it will assign a value of 0 to this task. Once a robot has rated all tasks, it broadcasts these ratings to the other robots, e.g., with a single UDP broadcast packet. All robots that receive this broadcast will update an internal table that holds the task ratings of all robots and use this table as the most up-to-date estimate how well each robot of the robot team can execute each possible task. The scheduling algorithm can now calculate a score for every task configuration permutation. The task configuration that has the highest score is then used to decide, which robot is assigned which task. As this decision is deterministic, no further coordination between the robots is needed.

Using this decentral scheduling approach we arrive at a system that can coordinate a team of robots while being synchronization free, using only low-bandwidth broadcast communication, degrading gracefully in case of communication outages and loss of team members, and performing continuous replanning. The scheduling algorithm was successfully used during the RoboCup 2004 competition winning the Standard Platform League Open Challenge (see Video 1).

References

 1  J. Ziegler, I. Dahm, M. Hülsbusch, and J. Kerdels,
Virtual Robot - Adaptive Ressource Management in Robot Teams,
In: Technical Report 0204. presented at International RoboCup Worldchampion, Lissboa, July 2004. University of Dortmund, 2004,
[pdf|bibtex]

 2  Ingo Dahm, Matthias Hebbel, Walter Nistico, Christoph Richter, Dr. Jens Ziegler, Damien Deom, Jörn Hamerla, Mathias Hülsbusch, Jochen Kerdels, Thomas Kindler, Hyung-Won Koh, Tim Lohmann, Manuel Neubach, Claudius Rink, Andreas Rossbacher, Frank Roßdeutscher, Bernd Schmidt, Carsten Schumann, and Pascal Serwe,
Virtual Robot: Automatic Analysis of Situations and Management of Resources in a Team of Soccer Robots,
In: Tech. rep. PG 442 Final Report. University of Dortmund, 2004,
[pdf|bibtex]

 3  I. Dahm, M. Hebbel, M. Hülsbusch, J. Kerdels, W. Nistico, C. Schumann, and M. Wachter,
Decentral control of a robot-swarm,
In: Autonomous Decentralized Systems, 2005. ISADS 2005. Proceedings, pp. 347–351, 2005,
[pdf|doi|bibtex]