Semesterprojekt 2012

Software für autonome Roboterteams

Über das Projekt

Das Projekt, dass unter dem Titel „Software für autonome Roboterteams“ lief, wurde im Sommersemester 2012 an Institut für Informatik in Zusammenarbeit mit den Lehrstühlen Kognitive Robotik und Spezifikation, Verifikation und Testtheorie durchgeführt.

NAO

Rahmen hierfür ist das im Bachelorstudiengang Informatik vorgesehene Semesterprojekt, dass im SS12 erstmalig angeboten wurde.

Die ursprüngliche Beschreibung des Projekts lautet folgendermaßen:

Bei Erkundungsaktionen in für Menschen schwer zugänglichen Gebieten – etwa in Katastrophengebieten wie der Region Fukushima – können künftig Teams von autonomen Robotern eingesetzt werden, die miteinander kooperieren. Ein Flugroboter erkundet dabei das Gebiet aus der Luft und gibt den am Boden agierenden Rettungsrobotern Lage- und Geländeinformationen. Damit solch ein Szenario reibungslos funktioniert, müssen eine Reihe software-technischer Probleme gelöst werden, von der Modellierung der Anforderungen über die Implementierung der Kommunikation und Sensorverarbeitung bis hin zur Konstruktion geeigneter Sensorik, Motorik und Verhalten der mobilen Plattformen. In diesem Semesterprojekt soll ein automomes Roboterteam, bestehend aus einem Quadrokopter, humanoiden Nao-Robotern und mehreren NXT-Robotern, entworfen und realisiert werden, welches eine kooperative Aufgabe selbständig in schwer zugänglichem Territorium durchführt. […]

 

 

Betreut wurde das Projekt von Frau Prof. Dr. sc. nat. Verena Hafner und Herrn Prof. Dr. rer. nat. habil. Bernd-Holger Schlingloff, sowie von Marcus Scheunemann vom Lehrstuhl Kognitive Robotik. Durchgeführt wurde das Projekt von Jens Bork, Denis Erfurt, Lorenz Fichte, Robert Fritz, Sebastian Günther, Joseph Hufnagl, Jonathan Sielhorst, Sven Schröder und Cordt Voigt.
Dieser Blog soll sowohl eine Übersicht über das Projekt als auch einen Erfahrungsbericht darstellen. Unter dem Eintrag Media finden Sie sowohl die vollständige Dokumentation des Projekts, als auch Videos von der Mission. Wir freuen uns über Anmerkungen, Kommentare oder Fragen jeglicher Art.

 

Aufgabenstellung und Ablauf der Mission

Die Aufgabenstellung die letztendlich umgesetzt werden sollte lässt sich in etwa folgendermaßen beschreiben:

Ein unbekanntes Gebiet ist mit gewissen Hindernissen versehen und beinhaltet einen Zielpunkt der zunächst durch die NXT’S lokalisiert werden soll und anschließend vom NAO „gelöscht“ wird (Ein Becher wird an der Zielposition abgestellt). Die Roboter starten gemeinsam an festgelegten Startpunkten. Wichtig ist insbesondere der autonome Ablauf der Mission, d.h. nach dem Start, agieren die Roboter völlig eigenständig. Die gesamte Kommunikation und der Ablauf werden zentral vom Mission Control Center, kurz MCC, gesteuert. Der genaue Ablauf kann den folgenden Status der Mission entnommen werden:

  1. Initial muss sichergestellt werden, dass der NAO, der im weiteren Verlauf für die Kalibrierung der NXT’s wichtig ist, seine eigene Position genau kennt. Das ist notwendig, da bereits das Aufstehen eine Abweichung verursacht. Die Kalibrierung des NAO wird mit Hilfe von zwei NXT’s durchgeführt, die unbewegt startbereit sind.
  2. Die Autonomic Exploration ist die erste Phase in der das unbekannte Gebiet erkundet wird. Zur Erkundung verwenden die NXT’s verschiedene Explorationsalgorithmen mit dem Ziel, innerhalb einer vorgegebenen Zeit einen möglichst großen Bereich zu erkunden. Die Zeit die für diese Phase veranschlagt ist beträgt 5:00 Minuten. Dieser Wert ist allerdings sehr von der gestellten Aufgabe abhängig – je nach Größe des zu erkundenden Gebietes sollte der Wert entsprechend angepasst werden, damit nach Ablauf der Zeit ein adequater Bereich erkundet wurde.
  3. In der Guided Exploration wird zielgerichtet versucht, nicht erkundete Gebiete von den NXT’s abfahren zu lassen. Da nicht bekannt ist, wie groß das gesamte zu erkundende Gebiet ist oder welche Ausmaße es hat, muss man Areale, die noch abgefahren werden sollen, nach gewissen Kriterien aussuchen. Die Punkte die dann letztendlich noch abgefahren werden sollen, werden direkt vom MCC an die entsprechenden NXT’s geschickt. Maßgeblich für den Übergang in die nächste Phase ist, dass das Ziel gefunden wurde. Mögliche Adaptionen sind bei Kenntnis des Gebietsumfangs die Erkundung bis ein bestimmter Schwellwert an erkundetem Gebiet relativ zum Gesamtgebiet überschritten wird und das Vorhandensein eines ausreichend großen Weges zum Ziel.
  4. Nach der zweiten Erkundungsphase wird der vom MCC berechnete Pfad zum Ziel (s. hierzu Pfad zum Ziel) durch einen NXT verifiziert. Es soll dabei sichergestellt werden, dass der berechnete Weg ausreichende Ausmaße hat, um vom NAO abgelaufen zu werden. Sollte der Weg als ungenügend erkannt werden, wird zur vorigen Phase zurück gesprungen. In dieser kann zielgerichtet versucht werden entweder den berechneten Pfad zu ändern, einen Neuen zu finden oder ein größeres Gebiet zu erkunden, um neue Wege zu finden.
  5. In der letzten Phase wird der NAO von einem NXT zum Ziel geführt. Der NXT wird dabei vom NAO als Fixpunkt genutzt und bewältigt die Strecke abschnittsweise.

 

Die exakte Aufgabenstellung ist in der Anforderungserhebung (s.Dokumentation) festgehalten, die im Allgemeinen die Grundlage eines Projekts darstellt.

 

MCC – Mission Control Center

Kalibrierung – Korrektur der Abweichung

Bei der Arbeit mit Robotern gehört die Erkennung, Verminderung oder sogar Behebung von Fehlern zu den grundlegenden Aufgaben bei der Lösung von Problemstellungen, die mit der Feststellung der Position des Roboters verbunden sind. Da es eine wesentliche Teilaufgabe dieses Problems ist eine simple, aber doch möglichst genaue Karte der Umgebung zu erstellen, ist die Bestimmung der Position, bzw. Abweichungen während der Bewegung, von essentieller Wichtigkeit.

Grün: Tatsächlich gefahrene Strecke
Rot: Vermutete Strecke
Blau: Interpolierte Strecke

Als Ausgangspunkt kann festgehalten werden, dass jeder der Roboter mit jeder Bewegung einen gewissen Fehler, im Bezug auf seine tatsächliche Position und die Position an der er sich selbst vermutet, erzeugt. Es kann weder davon ausgegangen werden, dass der Fehler unerheblich ist, noch dass er sich über einen gewissen Zeitraum oder gewisse Distanzen im Mittel selbst auslöscht. Um diesen Fehler zu verringern, werden die einzelnen NXT’s zu gewissen Zeitpunkten durch den NAO kalibriert. Anhand der Position die der NXT für seine aktuelle hält und der vom NAO berechneten Position, kann eine relative Abweichung berechnet werden. Zum einen ist dies wichtig, damit ausgehend von dieser Position der NXT wieder bei einem Fehler von annähernd 0 startet (natürlich ist auch die Berechnung des NAO’s in der Regel fehlerbehaftet), des Weiteren wird diese Abweichung verwendet um die gesamte, seit der letzten Kalibrierung oder dem Start abgefahrene Strecke, zu korrigieren. Der Algorithmus unterteilt dazu die seit der letzten Kalibrierung gefahrene Strecke in äquidistante Abschnitte und verschiebt die einzelnen Abschnitte in Richtung des bei der Kalibrierung ermittelten Wertes. Hierbei wird die Strecke in sofern gewichtet, als das Abschnitte nahe dem Startpunkt nur sehr wenig korrigiert werden und Abschnitte nahe dem Endpunkt sehr stark korrigiert werden. Diese Gewichtung erfolgt gleichmäßig über die gesamte Strecke, wobei am Startpunkt keine Verschiebung statt findet und der Endpunkt vollständig zu dem bei der Kalibrierung ermittelten Wert geschoben wird.

 

Geführte Erkundung

Die größte Schwierigkeit dieser Phase besteht darin festzustellen, welche Bereiche des noch nicht erkundeten Gebiets für den weiteren Verlauf der Mission relevant oder am „nützlichsten“ sind. Unter der vereinfachenden Annahme, dass sich die NXT’s zumindest ungefähr im Zielbereich aufhalten, wird in bei der geführten Erkundung versucht das bereits gefahrene Gebiet so zu erweitern, dass eine möglichst zusammenhängende erkundete Fläche entsteht.

Noch zu erkundendes Gebiet
Noch zu erkundendes Gebiet

 

Der Algorithmus ermittelt ausgehend vom Zentrum des bereits erkundeten Gebiets, kreisförmig noch nicht befahrene Punkte bis zu einem gewissen Schwellwert und teilt das so ermittelte Gebiet möglichst zusammenhängend unter den NXT’s auf.

 

 

 

 

 

Pfad zum Ziel

Der Algorithmus der den Pfad berechnet, der letztlich durch den NAO abgelaufen wird kann grob in drei Schritte unterteilt werden:

  1. Eine Breitensuche, die dafür sorgt einen gütigen Pfad vom Start- zum Endpunkt zu finden
  2. Die Repositionierung des Pfades um einen möglichst großen Abstand zu den Hindernissen zu erreichen
  3. Die Pfadoptimierung, bei der die Anzahl der abzufahrenden Punkte minimiert werden soll

 

  1. Breitensuche
    Ausgehend vom Startpunkt wird jedem Punkt eine Entfernung von diesem zugewisen, indem nach dem Prinzip der Breitensuche expandiert wird. Jeder benachbarte Punkt erhält somit die Entfernung des Vorgängers +1. Ist der Zielpunkt erreicht, so wird ausgehend von diesem ein Pfad ermittelt, indem immer ein benachbarter Punkt mit der kleinsten Entfernung zum Startpunkt hinzugenommen wird.
  2. Repositionierung
    Um evtl. Hindernissen entlang des ermittelten Weges gerecht zu werden, muss der ermittelte Pfad so korrigiert werden, dass er einen Mindestabstand zu nicht erkundeten (also möglicherweise besetzten) Punkten auf der Karte hat. Innerhalb des Weges werden dazu Kreise positioniert deren Fläche nicht von angrenzenden „Wänden“ überschnitten werden darf (s. Bild)
  3. Pfadoptimierung
    In der Optimierungsphase wird aus den Kreisen eine möglichst minimale Anzahl von Punkten ermittelt die letztlich den Pfad zum Ziel angeben.

 

Pfad zum Ziel: Breitensuche
Pfad zum Ziel: Breitensuche
Pfad zum Ziel: Repositionierung
Pfad zum Ziel: Repositionierung
Pfad zum Ziel: Optimierung
Pfad zum Ziel: Optimierung

 

 

 

 

 

 

 

 

 

 

NAO

 

Inhalte folgen…

 

NXT

 

Inhalte folgen…

29. Oktober 2012 | Veröffentlicht von Cordt Voigt | Kein Kommentar »
Veröffentlicht unter Allgemein

Media

Hier finden Sie verschiedene Dokumente zum Semesterprojekt:

Projektdokumentation
Die abschließende Dokumentation des Projekts

Videos

Autonome Exploration
Ein Video das die autonome Exploration der NXT’s zeigt

Kalibrierung durch den NAO
Ein Video das die Kalibrierung durch den NAO, bzw. die Berechnung der Position von drei NXT’s zeigt

Präsentationen

Servicerobotik
Projektmanagement & Softwaretechniken
Requirements (Anforderungserhebung)
Demo (Präsentation zur Demonstration des Systems)

29. Oktober 2012 | Veröffentlicht von Cordt Voigt | Kein Kommentar »
Veröffentlicht unter Allgemein