Roboter-Simulation

1. Die Arbeitsgruppe

Seit 2000/2001 gibt es für mathemathisch interessierte Schüler im Life-Science-Lab eine Mathematik-AG unter der Leitung von Dr. Michael Winkler.

Neben den Untergruppen Mathe.Optimierung und Mathe.Wettbewerb gibt es für informatik-spezifische Fragestellungen und Programmierung seit dem Lab-Jahr 2003/2004 die Mathe.Simulation-AG. Diese trifft sich in den Computerrüumen des Interdisziplinären Zentrum für Wissenschaftliches Rechnen (IWR) der Universität Heidelberg und wird von Dr. Marco Weismüller geleitet. Weitere Mentoren waren Matthias Janke (studentischer Mentor) und Kai Ueltzhüffer (Schüler-Mentor).

Unsere AG verfolgte eine projekt-orientierte Arbeitsweise. Im ersten Halbjahr Labjahres 2003/2004 war es unser Ziel eine gemeinsame Arbeitsgrundlage zu schaffen. Dazu eigneten sich die neuen Teilnehmer mit der Hilfestellung der Mentoren und der erfahrenen AG-Teilnehmer der vergangenen Jahre die Grundlagen der von uns gewählten Programmiersprache C an. In selbst vorbereiteten Vorträgen wurde von den Teilnehmern zunächst das theoretische Wissen vermittelt, welches danach in der Gruppe durch anspruchsvolle und realitätsnahe Programmierübungen vertieft, gefestigt und diskutiert wurde.

Nachdem die grundlegenden Fertigkeiten in der Programmiersprache C bis Ende Februar erlernt worden waren, und wir bei unserem ersten Programmierwochenende bereits einige Aufgaben aus dem Bundeswettbewerb Informatik gelöst hatten, einigten wir uns auf ein gemeinsames Programmierprojekt, das uns das restliche Lab-Jahr beschäftigen sollte: Eine Roboter-Simulation.

Nachdem wir uns in den vorangegangenen Jahren hauptsächlich mit theoretischen Themen, wie Gen-Alignment (2001/2002) und der Anwendung von neuronalen Netzen zur Klassifizierung arbiträrer Datensätze (2002/2003) beschäftigt hatten, entschieden wir uns nun für eine hardwarenähere Problematik.

 

2. Unsere Zielsetzung

Unser Ziel war es, einen autonomen Roboter zu programmieren, der in der Lage sein sollte, eine anspruchsvolle Aufgabe zu lösen.

Das Durchqueren eines zufällig generierten Labyrinthes schien uns eine passende Herausforderung zu sein. Denn neben den typischen Problemen der Roboterprogrammierung, d.h. dem Verhindern von Kollisionen, dem korrekten Ansteuern der Antriebsmotoren und der Abfrage und Interpretation der Ultraschallabstandssensoren, bot dieses Projekt auch interessante algorithmische Probleme.

Bei Fragen der Algorithmik stand uns zudem die Mathe.Optimierung, unter Leitung von Dr. Michael Winckler, zur Seite.

 

3. Umsetzung

Da uns leider kein physischer Roboter zur Verfügung stand, entschieden wir uns für eine kostenlose und im Quellcode verfügbare Roboter-Simulationsumgebung namens "Saphira".

Die Software besteht aus zwei Komponenten: Der Pioneer-Robotersimulation und dem von uns selbst in der Programmiersprache "C" erstellten Saphira-Steuerprogramm.

Pioneer simuliert die physikalische Welt um den Roboter und den Roboter selbst. Außerdem verbindet sie sich ¨ber ein Standard-Socket mit der Steuersoftware, welche die simulierten Sensoreninputs verarbeitet, Kollisionen mit Hindernissen verhindert, die Wegfindungsroutine ausführt und dem entsprechend die simulierten Motoren ansteuert. Dabei ist die Simulation darauf ausgelegt, dass die entwickelten Programme auch mit realen Pioneer-Robotern der Firma ActivMedia funktionieren würden.

Wie in großen Softwareunternehmen durchaus verbreitet, haben wir uns für folgende Vorgehensweise entschieden: Wir teilten unser Problem in drei unabhüngige Aufgabenstellungen, die von getrennten Gruppen bearbeitet wurden. Durch vorher festgelegte einheitliche Schnittstellen war es anschließend möglich, die einzelnen Programmteile zu einem lauffähigen Programm zusammen zu stellen.

Als sinnvolle Teilprobleme erschienen uns folgende drei Komplexe:

• Für die Verarbeitung der Sensordaten und die Ansteuerung der Motoren auf sehr hardwarenaher Ebene, vor allem zur Kollisionsvermeidung und Erfassung der für die Navigation durch das Labyrinth notwendigen Sensorendaten, waren André Dau und Konrad Herold veranwortlich. Sie bildeten die Gruppe "Sensorik und Motorik".
• Alexander Koch und Christoph Schmidt beschäftigten sich mit der "Navigation", dem Modul, das anhand der abstrahierten Umgebungsdaten einen Weg aus dem Labyrinth heraus berechnet. Um dies zu bewerkstelligen implementierten sie den auf viele Probleme in der Informatik angewendeten so genannten "Backtracking" Algorithmus.
• Als Schnittstelle zwischen den direkten, von der Sensorik und Motorik weitergeleiteten Sensoren-Inputs und der auf abstrakter Ebene arbeitenden Navigationsroutine wurde ein eigenes Datenformat entwickelt. So können z.B. die idealisierte Position der Wände im Labyrinth bestimmt oder die schon besuchten Kreuzungen erkannt werden. Diese "Interne Karte" wurde von Jakob Haufe und Jessica Kaufmann entwickelt.

Nach der Zusammenführung der einzelnen Teile erhielten wir ein Programm, das es einem Pioneer Roboter ermöglicht, von einem beliebigen Punkt innerhalb eines Labyrinthes mit quadratischen Grundraster jeden anderen Punkt des Labyrinthes in endlicher Zeit zu erreichen. Der Roboter nimmt dabei Wände wahr, speichert diese in der "Internen Karte" und zeichnet sie gleichzeitig in das Saphira-Fenster, das seiner Weltsicht entspricht, ein.

 

Die Pioneer-Simulationsumgebung simuliert einen Roboter (schwarzer Kreis) in einem physischen Labyrinth (schwarze Wände).

 

 

4. Resumée

Die Zusammenführung der einzelnen Module zum Steuerprogramm gestaltete sich Dank der vorher festgelegten Schnittstellen sehr einfach. Einziges Problem waren die Funktionen, die zum Testen der einzelnen Module eingeführt wurden. Diese wiesen nach dem Zusammenfügen Fehler auf, die nun im gesamten Programm repariert werden mussten, was sich als langwierig und schwierig erwies. In einem gemeinsamen Kraftakt gelang es uns jedoch auf dem zweiten Programmier-Wochenende diese vollständig zu beseitigten, und den Roboter laufen und sich orientieren, zu lehren.

Die Arbeit in den Kleingruppen hat allen großen Spass gemacht, und uns gerade bei der Fehlersuche sehr zusammengeschweißt. Besonders hervorzuheben ist, dass es uns trotz der anfangs sehr heterogenen Wissensverteilung gelungen ist, dieses Projekt auf einem sehr hohen Niveau gemeinsam zu verwirklichen.