4. Übungszettel: Kartografierung und Selbstlokalisation

Ausgabe: 8. Januar 2003
Abgabe: 22. Januar 2003

1. Triangulation (20%)

Drei Landmarken spannen ein Dreieck auf, dessen Längen und Winkel vollständig bekannt sind. Ein gedachter Roboter kann die Marken anpeilen und erhält die Winkel zwischen den drei Peilungen. Um seine Position und Orientierung zu bestimmen, braucht er aber auch Entfernungen zu Landmarken.

Rechnet die Entfernung zu einer der Landmarken aus (die anderen beiden könnten dann analog bestimmt werden). Macht auf jeden Fall eine Zeichnung und gebt den Rechenweg an.

2. Begriffe (20%)

Grenzt die folgenden Begriffe voneinander ab und erläutert sie:

• Kartografierung - Selbstlokalisierung
• Lokale Karte - Globale Karte
• Relative Selbstlokalisierung - Absolute Selbstlokalisierung
• Reduktionsfilter - Projektionsfilter

3. Histogramme und Korrelationen (30%)

Implementiert ein Histogramm, mit dem man eine Statistik über die Häufigkeit von Werten in einem bestimmten Bereich aufbauen und die beste Korrelation zwischen zwei Histogrammen ermitteln kann. Realisiert es als Klasse Histogram mit mindestens folgender Signatur:

Histogram(int numberOfCells, double minValue, double maxValue)

Mit dem Konstruktor definiert man den Wertebereich des Histogramms, sowie die Anzahl der Zellen, in die dieser Bereich diskretisiert wird.

void insert(double fromValue, double toValue, double amount)

Mit dieser Funktion trägt man Werte in das Histogramm ein. amount gibt dabei die Größe an, die in das Histogramm eingefügt (also zu Zellen hinzugezählt) wird, fromValue und toValue geben den Bereich an, über den amount verteilt wird. Fallen sowohl fromValue als auch toValue in dieselbe Zelle des Histogramms, wird amount einfach zu dieser Zelle addiert. Ansonsten wird amount anteilig über alle betroffenen Zellen verteilt. Es wird nur der Teil des Bereichs in das Histogramm eingetragen, der auch innerhalb der Histogramm-Grenzen liegt.

double getMostFrequentValue() const

Die Funktion liefert den häufigsten Wert im Histogramm zurück, d.h. einen Wert, der der Zelle zugeordnet würde, in der sich der größte amount aufsummiert hat.

double correlate(const Histogram& other,double range) const

Die Funktion sucht nach der besten Korrelation zwischen diesem Histogramm und einem weiteren und liefert die optimale Verschiebung zwischen den beiden Histogrammen zurück. In range wird der zu testende Bereich der Verschiebungen angegeben (d.h. -range ... range). correlate() soll die Histogramme als zyklisch ansehen, d.h. jedem Wert in einem Histogramm wird immer genau ein Wert im anderen zugeordnet.

Konstruiert Testfälle und stellt den Inhalt der Histogramme sowie die optimale Korrelation zwischen zwei Histogrammen grafisch dar. Beachtet die Sonderfälle von insert(). Es ist wichtig, die Klasse Histogram ausgiebig zu testen, bevor ihr mit der nächsten Aufgabe beginnt!

4. Scan-Überdeckung (30%)

In dieser Aufgabe geht es darum, mit dem Roboter einen Entfernungs-Scan aufzunehmen, den Roboter zu versetzen, einen weiteren Scan aufzunehmen und aus den beiden Scans den Versatz der Aufnahmepositionen zu bestimmen. Die Scans sollen dabei bereits in Strecken zerlegt worden sein (vgl. Aufgabe 1 des 2. Übungsblatts).

Bei dieser Aufgabe sollte man Schritt für Schritt vorgehen und Zwischenergebnisse grafisch darstellen. Zu jedem Scan sollten die segmentierten Strecken sowie die Aufnahmeposition (mit Orientierung) visualisiert werden. Nach der Überdeckung sollte einer der beiden Scans relativ zur ermittelten Verschiebung gezeichnet werden, so dass die Strecken der beiden Scans übereinander liegen.

Die Überdeckung läuft in drei Schritten ab:

Rotationsversatz bestimmen

• Um die Verdrehung zwischen den beiden Aufnahmepositionen zu bestimmen, muss für beide Scans ein Winkelhistogramm aufgebaut werden. Dazu wird die Orientierung jeder Strecke bestimmt und ihre Länge unter dieser Orientierung in das Histogramm eingetragen. Danach werden beide Histogramme korreliert. Das Ergebnis ist die Verdrehung zwischen den beiden Aufnahmepositionen.
• Welchen Wertebereich muss das Winkelhistogramm abdecken?
• Für die weitere Verarbeitung ist es notwendig, einen der beiden Scans um diese Verdrehung zu rotieren, damit beide Scans dieselbe Orientierung haben.

Ersten Translationsversatz bestimmen

• Um den ersten Translationsversatz zu bestimmen, muss zuerst die sog. Hauptrichtung der Scans bestimmt werden, das ist die Richtung, in die die meisten Strecken orientiert sind. Dann werden beide Scans so gedreht, dass die Hauptrichtung entlang der x-Achse verläuft.
• Für beide Scans wird ein Histogramm über die Verteilung der y-Koordinaten der Strecken aufgebaut. Als amount werden dazu die Ausdehnungen der Strecken in x-Richtung verwendet. Beide Histogramme werden korreliert und die beste Korrelation ist Verschiebung der Aufnahmepositionen quer zur Hauptrichtung.

Zweiten Translationsversatz bestimmen

• Für den zweiten Translationsversatz wird vereinfachend davon ausgegangen, dass die zweite Hauptrichung senkrecht auf der ersten steht. Beide Scans werden dazu um 90° gedreht und das Prozedere des vorherigen Schrittes wiederholt. Damit ist die Verschiebung entlang der Hauptrichtung bekannt.
• Es ist zu beachten, dass die beiden Verschiebungen noch in die Hauptrichtung gedreht werden müssen, um die korrekte Verdrehung und Verschiebung zwischen den Aufnahmepositionen der Scans zu erhalten.