Teilbericht

Gruppe 42: Die Karte

Autoren:

• Jan Kuhlmann, Matr. Nr. 890574

Datum:

• Delmenhorst, den 09.10.1995

Stichworte:

• Gruppe 42
• Karte

Zusammenfassung:

Die Rollstuhlsteuerung und -navigation basiert auf einer Karte. In diesem Bericht werden die Philosophie und die Realisierung derselben vorgestellt.

Am Anfang ist alles graue Theorie

Die Steuerung des Rollstuhls soll mit einer Karte arbeiten, die die Basis für Positionsbestimmung und Navigation bildet. Die Karte soll Informationen von den Sensoren (nach eventueller Vorverarbeitung) bekommen und die Position von Hindernissen abspeichern. Alle weiteren Steuerungseinheiten sollen nach Möglichkeit nicht direkt auf die Sensoren zugreifen, sondern nur auf die in der Karte zentral gespeicherten Daten. In diesem Sinne ist die Karte als Universalsensor aufzufassen, als Schnittstelle zwischen den Sensoren und den Navigationsalgorithmen. Durch die Verwendung einer Karte soll somit die Abfrage der Sensoren zentralisiert und der Zugriff auf ihre Werte vereinfacht werden. Zudem bekommen wir durch die Speicherung der Sensorwerte in der Karte eine bessere Basis für eine Wegeplanung, weil eine solche vollständig vor der ersten Bewegung in der Karte stattfinden kann, so daß bei unveränderter Umgebung und bekannter Position ein unkomfortables Herumfahren und Ausprobieren entfallen kann. Um auch große Wohnungen mit vernünftigem Speicheraufwand darstellen zu können, muß für eine geeignete Speicherstrategie gesorgt werden, die nicht allein von der Größe der Wohnung, sondern von der Vielzahl und Komplexität der Hindernisse abhängt.

Von der Theorie zur Umsetzung

Für unsere Zwecke haben wir uns auf eine metrische Karte mit Elementen der topologischen Karte entschieden: Die Welt wird dargestellt als eine Menge von Räumen, die über Ausgänge miteinander verbunden sind. Jeder Raum kann mehrere Ausgänge haben. Die Räume selbst haben zunächst einen rechteckigen Grundriß, der aber beliebig verändert werden kann (s. Kap. weltdefinition). Die einzelnen Rechtecke haben in der Karte Koordinaten, die mit den tatsächlichen Gegebenheiten im Rahmen einer festzusetzenden Auflösung übereinstimmen müssen. Das bedeutet insbesondere, daß keine zwei Räume gleiche Koordinaten beinhalten dürfen! Dies kann in verwinkelten Wohnungen ein Problem ergeben (s. Kap. weltdefinition). Man nehme also einen Grundriß der Zielwohnung und berechne aus den globalen Maßen mittels Multiplikation mit einem Skalierungsfaktor die Kartenmaße. Man könnte z.B. festlegen, daß 5 cm in der Realität in der Karte gerade noch aufgelöst werden. In diesem Fall würde der Skalierungsfaktor 1/5 sein, und einem Raum der Größe 200 cm mal 300 cm würde ein Rechteck der Größe 40 mal 60 zugewiesen werden. Der Skalierungsfaktor sollte dabei so gewählt werden, daß die Auflösung der Karte groß genug und der Speicheraufwand nicht zu groß wird. Dabei gilt: Je mehr Hindernisse in dem Raum stehen werden, desto größer ist der Speicheraufwand. Bei der ersten Definition der Karte müssen auch die Verbindungen zwischen den Räumen definiert werden. Ausgänge werden durch zwei Rechtecke definiert, von denen das eine vollständig im ersten (Quell-) Raum und das andere vollständig im zweiten (Ziel-)Raum liegen muß. Diese Rechtecke sollten mit der Größe des Rollstuhls und seines Rangierradius' abgestimmt sein, denn diese Rechtecke müssen frei von Hindernissen sein, wenn die Kartenroutinen den Ausgang als benutzbar anerkennen soll. Die Ausgangsrechtecke sollen zudem so angelegt sein, daß der Rollstuhl später bei direkter Ausrichtung vom Mittelpunkt des ersten Rechtecks geradewegs zum Mittelpunkt des zweiten Rechtecks fahren kann. Die Ausgänge sind dabei als Einbahnstraßen definiert, so daß also ein von beiden Seiten benutzbarer Durchgang als Ausgang zweier Räume definiert werden muß. Die Karte kann nun im Rahmen ihrer Auflösung speichern, ob an einer bestimmten Stelle oder in einem bestimmten Bereich ein Hindernis steht oder nicht. Die jeweils gespeicherten Werte stehen für die Sicherheit, mit der sich an einer bestimmten Stelle ein Hindernis befindet. Ein hoher Wert heißt also, daß sich an der besagten Stelle mit hoher Sicherheit ein Hindenis befindet, ein niedrieger Wert deutet auf eine niedrige Sicherheit hin. Der höchste setzbare Wert hat den Namen MAXVALUE und könnte z.B. für ein unverrückbares festes Hindernis stehen. Der Sinn dieser Werte liegt darin, eventuell ungenaue Sensoren zu kompensieren. So könnte zum Beispiel die Karte mit einem hohen Wert belegt werden, wenn ein Sensor ein Hindernis erkennt. Erkennt bei der nächsten Abfrage keiner der Sensoren an der besagten Stelle ein Hindernis, so könnte der entsprechende Kartenwert verkleinert werden. Er sollte nur verringert werden und noch nicht auf null gesetzt werden, da es sein kann, daß es sich um einen Meßfehler handelt. Wenn die nächste Messung wieder kein Hindernis erkennen läßt, wird der Wert wieder verringert usw., bis der Kartenwert wieder null ist. Erst jetzt kann man wieder sicher sein, daß der betrachtete Bereich hindernisfrei ist. Man sollte hier also eine Sicherheitsstrategie entwickeln, die mit der Häufigkeit der Sensorabfragen und der Genauigkeit bzw. Zuverlässigkeit der Sensoren korreliert. Es sollten lieber zu viele Hindenisse in die Karte eingetragen werden, die vielleicht gar nicht (mehr) da sind, als daß man riskieret, gegen ein Hindernis zu fahren. Die Kartenklasse beinhaltet schließlich noch einen Algorithmus, der herausfindet, welche Ausgänge auf dem Weg von einer Position zu einer anderen benutzt werden müssen. Dabei werden nur solche Ausgänge berücksichtigt, deren Quell- und Zielrechtecke frei von Hindernissen sind, so daß es also passieren kann, daß der Algorithmus keinen Weg findet, auch wenn zwei Räume theoretisch durch Ausgänge mitenander verbunden sind.

Die Schnittstelle

Die Kartenklasse stellt folgende Funktionen öffentlich zur Verfügung

WORLD()

Der Konstruktor der Kartenklasse erzeugt eine leere vorinitialisierte Welt ohne Ausdehnung, Räume und Ausgänge.

void AddRoom(RECTANGLE &r)

Der Karte wird ein rechteckiger Raum hinzugefügt. Die Abmessungen des Raumes werden durch das übergebene Rechteck angegeben.

void AddExit(RECTANGLE &r0,RECTANGLE &r1)

Der Karte wird ein Ausgang hinzugefügt. Wie schon beschrieben definiert sich ein Ausgang durch ein Quellrechteck und ein Zielrechteck. Der Ausgang wird von der Funktion FindWay() (s.u.) als frei anerkannt, wenn beide Rechtecke frei von Hindernissen sind. Die Abmessungen der Rechtecke werden durch die überegebenen Rechtecke angegeben. Es ist darauf zu achten, daß Ausgänge nur schon existierenden Räumen zugefügt werden können. Befindet sich das Quellrechteck in keinem bekannten Raum, so kann auch kein Ausgang erzeugt werden.

VALUETYPE GetValue(VECTOR &v)

Der Kartenwert der übergebenen Position wird ermittelt. Befindet sich die übergebene Position nicht in der Welt, so wird MAXVALUE zurückgegeben.

BOOLEAN SetValue(VECTOR &v,VALUETYPE s)

Der Kartenwert der übergebenen Position wird gesetzt. Befindet sich die übergebene Position in der Welt, so wird TRUE zurückgegeben, sonst FALSE.

BOOLEAN SetValue(RECTANGLE &r,VALUETYPE s)

Der Kartenwert aller Positionen im überegebenen Rechteck wird gesetzt. Befindet sich das übergebene Rechteck vollständig in der Welt, so wird TRUE zurückgegeben, sonst FALSE.

BOOLEAN IsFree(RECTANGLE &r)

Es wird ermittelt, ob das überegebene Rechteck frei von Hindernissen ist. Ein Rechteck ist frei von Hindernissen, wenn der Kartenwert jedes Punktes des Rechtecks SEGFREE ist.

LIST<VECTOR> *FindWay(VECTOR &v0,VECTOR &v1)

Es wird ermittelt, welche Punkte in der Karte nacheinander angefahren werden müssen, um vom übergebenen Punkt 1 zum übergebenen Punkt 2 zu gelangen. Zurückgegeben wird eine Liste von Punkten, die leer ist, falls es keinen Weg von Punkt 1 zu Punkt 2 gibt. Bei der Wegbstimmung wird keine Rücksicht auf Hindernisse genommen. Diese Routine ist nur dafür gedacht, von einem Raum in einen anderern zu finden.

LIST<VECTOR> *Navigate(VECTOR &v0,VECTOR &v1)

Es wird ermittelt, welche Punkte in der Karte nacheinander angefahren werden müssen, um vom übergebenen Punkt 1 zum übergebenen Punkt 2 zu gelangen. Zurückgegeben wird eine Liste von Punkten, die leer ist, falls es keinen Weg von Punkt 1 zu Punkt 2 gibt. Bei dieser Art der Wegbstimmung wird Rücksicht auf Hindernisse genommen (zum Algortihmus s. Kap navigation).

BOOLEAN Load(char *n)

Die Welt mit dem übergebenen Namen wird in den Speicher geladen. Im Falle eines Fehlers wird FALSE zurückgegeben, sonst TRUE.

BOOLEAN Save(char *n)

Die Welt wird mit dem übergebenen Namen abgespeichert. Im Falle eines Fehlers wird FALSE zurückgegeben, sonst TRUE.

SaveAsScene(char *n,long s,long o,LIST<VECTOR> *l)

Die Welt wird mit dem übergebenen Namen als SimRobot Szene-File abgespeichert. Im Falle eines Fehlers wird FALSE zurückgegeben, sonst TRUE. Der Parameter s ist ein Skalierungsfaktor, mit dem alle Kartenkoordinaten multipliziert werden, der Parameter o ist ein offset, der auf alle Kartenkoordinaten aufaddiert wird. Diese beiden letzten Parameter dienen dazu, die Karte beliebig zu skalieren und positionieren. Schließlich ist l eine Liste von Vektoren, wie sie von Navigate zurückgegeben wird. Die Liste wird als Navigationspfad interpretiert und in das Szene-File eingetragen.

VECTOR(VECTYPE x,VECTYPE y)

Erzeugt einen Vektor mit den übergebenen Koordinaten.

RECTANGLE(VECTYPE x0,VECTYPE y0,VECTYPE x1,VECTYPE y1)

Erzeugt ein Rechteck mit den übergebenen Koordinaten. Dabei ist zu beachten, daß das Koodinatenpaar x0/y0 die linke obere Ecke des Rechtecks auf dem Grundriß darstellt und das Paar x1/y1 die rechte untere Ecke.

VECTOR *Next

Dies ist einfach ein Zeiger auf den nächsten Vektor in der Liste. Die letzte Position hat keinen Nachfolger, ihr Next-Feld ist 0.

VECTYPE X,Y

Dies sind die Koordinaten des Vektors in der Welt.

Beispiel: Eine Weltdefinition

Es soll nun anhand eines Beispiels die Verwendung der Kartenklasse erklärt werden. Wir stellen uns die in Abb. bild00 dargestellte Wohnung vor. (Abbildung: Grundriß einer Wohnung ) Sofern der Grundriß noch nicht mit Maßen versehen ist, muß die Wohnung zunächst ausgemessen werden, dann sollten die Maße in den Grundriß eingetragen werden (s. Abb. bild01). (Abbildung: Grundriß mit Bemaßung ) Die Innen- und Außenmaße der Wände stehen an den Pfeilen, die Innenkoordinaten relativ zur linken oberen Ecke der Küche als Koordinatenursprung stehen in den Ecken der Räume. Die Maße der Türen sind aus Übersichtlichkeitsgründen nicht mit eingetragen; das Prinzip dürfte aber klargeworden sein. Jetzt können wir anfangen, die Karte aufzubauen. Es sei gefordert: Hindernisse sollen auf 2 cm genau erkannt und aufgelöst werden. Der Umrechnungsfaktor für die Transformation der Wohnungsmaße in die Kartenmaße ist also 1/2. Wir benutzen für die Karte nur die Innenmaße der Räume im Grundriß. Da es sich in diesem Beispiel nur um rechteckige Räume handlt, ist die Definition der Raumrechtecke für die Karte kein Problem. Die linke obere Ecke bekommt die Koordinaten 000/000, die weiteren Daten berechnen sich aus den Daten im Grundriß multipliziert mit dem Umrechnungsfaktor (Tab. tab00).

Navigationsvorteil

Man kann mit mehreren klar voneinander abgegrenzten Räumen auch die Navigation in der Wohnung auf die Navigation in den Räumen reduzieren. Wenn man also von einem Raum durch einen anderen in einen dritten Raum fahren will, teilt sich die Navigation in folgende Abschnitte auf: Navigation von der aktuellen Position zum Ausgang des ersten Raumes, dann Durchfahren des Ausgangs, dann Navigation zum Ausgang des zweiten Raumes, Durchfahren des zweiten Ausgangs, Navigation zum Zielpunkt. Man modularisiert so auf einfache Weise die Navigation, was in einem großen Raum, in dem die Ausgänge nicht klar als Ausgänge deklariert sind, nicht möglich ist.

Effizienzvorteil

Durch voneinander abgegrenzte Räume bietet sich die Möglichkeit, diejenigen Räume, in denen man sich gerade nicht befindet, auf einfache Weise aus dem Speicher auszulagern. Dies kann besonders in sehr großen Wohnungen zu einem wichtigen Vorteil werden. Zum anderen kann durch den durch Auslagerung erzielten Speichergewinn die Auflösung der Karte erhöht werden, ohne daß man Angst haben muß, daß die Wohnung dann nicht mehr in den Speicher passt.

Raumsegmentierung

Schließlich sollen noch ein paar Worte über interessante interne Funktionen verloren werden: Wie bereits beschrieben, ist die Welt in Räume aufgeteilt. Jeder Raum stellt eine eigenständige Einheit dar, die wiederum in Segmente unterteilt ist. Die Zahl der Segmente richtet sich nach Zahl und Anordnung der Hindernisse in dem Raum, und jedes Segment steht für einen Bereich gleicher Kartenwerte, sprich gleicher Hindernissicherheit. Dabei wird jedes Hindernis in möglichst große Rechtecke unterteilt, die als Segment dem Raum zugeordnet werden. Ein Beispiel soll dies veranschaulichen: Ein leerer Raum besteht aus nur einem Segment mit dem Wert null. Steht nun in diesem Raum ein Schrank an einer Wand, so besteht der Raum aus einem Segment für den Schrank, das einen sehr hohen Wert hat, und der Rest des Raumes besteht aus drei weiteren Segmenten, die wieder alle den Wert null haben. Alle vier Segmente decken überschneidungslos die Fläche des Raumes ab. Der Vorteil dieser Segmentierung liegt darin, daß der Speicheraufwand eines Raumes nicht von seiner Größe abhängt, sondern von der Zahl der Hindernisse. Statt nun im obigen Beispiel jeden aufgelösten Punkt des Raumes einzeln zu speichern, werden praktisch nur vier Punkte gespeichert. Abb. bild03 soll dies veranschaulichen: (Abbildung: Segmentierung eines Raumes ) Es handelt sich hier um einen Raum mit drei Wänden. Statt nun jeden aufgelösten Punkt in der Karte zu speichern, wird die Karte wie angedeutet an den gestrichelten Linien segmentiert. Die Wände selbst sind dabei auch Segmente. Aus einem Segment für einen leeren Raum sind so zehn Segmente geworden. Erst bei sehr vielen Hindernissen, die möglicherweise komplexe Formen haben, wird der Speicheraufwand bei der Segmentierung gleich oder sogar größer als bei einer Einzelpunktspeicherung. Der Nachteil dieser Methode ist ein höherer Rechenaufwand. Die Kartenklasse versucht nach jeder Änderung der Karte, den geänderten Bereich in die umliegenden Bereiche einzugliedern, so daß immer möglichst wenige Segmente existieren. Die Praxis muß zeigen, ob dieses Verfahren im Zeitverhalten akzeptabel ist, oder ob die Segmentoptimierung vom Benutzer gesteuert werden sollte.

Navigation

Die Kartenklasse stellt zwei Navigationsroutinen zur Verfügung, nämlich FindWay() und Navigate(). FindWay() erstellt nur eine Liste von Punkten, die angefahren werden müssen, um von einem Punkt zu einem anderen zu gelangen. Dabei werden keine Hindernisse berücksichtigt. Diese Routine ist nur dafür gedacht, Vektoren zu den Ausgängen der Räume zu finden, die auf dem Weg vom Start zum Ziel durchfahren werden müssen. Der erste Vektor in der Liste ist immer der Startvektor, der zweite ist entweder schon der Zielvektor oder aber der Mittelpunkt des Quellrechtecks des zu benutzenden Ausgangs gefolgt vom Mittelpunktsvektor des Zielrechtecks desselben Ausgangs. Danach können weitere Ausgangsvektoren folgen. Abgeschlossen wird die Liste in jedem Fall mit dem Zielvektor. Navigate() ist die weitaus interessantere Routine. Auch sie liefert eine Liste von Vektoren, die angefahren werden müssen, um von einem Punkt zu einem anderen zu kommen. Navigate() jedoch berücksichtigt dabei Hindernisse. Der Alorithmus beruht auf einem Flutungsalgorithmus zur Hindernisvermeidung: Zunächst wird der Weg mittels FindWay() in Wegstücke zerlegt. Betrachtet werden im folgenden nur noch Wegstücke innerhalb eines Raumes. Daraufhin werden die Distanzen aller Segmente vom Zielvektor auf einen Maximalwert initialisiert. Dann wird der Abstand des Zielsegments vom Ziel auf 0 gesetzt. Betrachten wir jetzt die Distanz 0 und nennen wir sie dist. Die Distanz aller Segmente, die Nachbarn von Segmenten mit der Distanz dist sind und kein Hindernis sind, wird nun auf dist+1 gesetzt, wenn ihre bisherige Distanz größer als dist+1 war. Dann wird dist um eins erhöht und die Distanz der Nachbarn der gerade bearbeiteten Segmente auf dist+1 gesetzt usw. Als Nachbarn gelten dabei keine diagonal angrenzenden Segmente. Diese Distanzbestimmung bricht ab, wenn entweder die Distanz des Startsegments bestimmt wurde (in diesem Fall gibt es einen Weg vom Start zum Ziel) oder wenn in einem Durchgang kein neuer Nachbar mehr gefunden oder bearbeitet werden konnte (in diesem Fall existiert kein hindernisfreier Weg vom Start zum Ziel). Falls nun ein Weg existiert, kann man diesen leicht anhand der Distanzen der Segmente vom Ziel bestimmen: Auf dem Weg von einem Segment zum nächsten muß die Distanz immer genau um eins sinken. Man muß also nur denjenigen Nachbarn des aktuellen Segments finden, dessen Distanz kleiner ist als die aktuelle Distanz. Von der aktuellen Position fährt man dann zur Mitte der Grenze zwischen dem aktuellen und dem nächsten Segment. Da man so immer vollständig in hindernisfreien Segmenten fährt, vermeidet man Hindernisse. Problematisch bleiben allerdings sehr spitze Winkel. Um ein Anecken an Hindernisse zu vermeiden, kann man die Hindenisse in der Karte künstlich vergrößern. Der Navigationsalgorithmus wird dadurch 'vorsichtiger'. Diese künstliche Vergrößerung wird voraussichtlich sowieso schon aufgrund ungenauer Sensoren vorgenommen, besonders wenn man die oben dargestellte Sicherheitstaktik beim Eintrag von Hindenissen in die Karte berücksichtigt. Im Idealfall absoluter Sensorgenauigkeit und Positionsbestimmung muß jedes Hindernis in allen Richtungen um die Hälfte des Maximums der Länge und Breite des Rollstuhls aufgebläht werden. Zwei Abbildungen sollen nun die Funktionsweise der Navigate()-Routine verdeutlichen (Abb. bild04 und bild05). (Abbildung: Eine einfache Navigationsaufgabe ) (Abbildung: Eine schwierigere Navigationsaufgabe ) Der große Vorteil der Navigate()-Routine ist seine extreme Einfachheit und große Geschwindigkeit. Der Aufwand ist linear in der Zahl der Segmente. Zu beachten ist jedoch, daß immer der Weg als der Kürzere angesehen wird, der über die wenigsten Segmentgrenzen führt. Dies muß nicht unbedingt der tatsächlich kürzeste Weg sein. Er wird eher der hindernisärmste sein. Man kann den Alorithmus aber bei Bedarf leicht um eine andere Bewertungsfunktion für den kürzesten Weg erweitern.