Pfadplanungskonzept

Welche Planungsverfahren gibt es?

Um die Komplexität des Pfadplanungsproblems zu reduzieren, wird der Konfigurationsraum normalerweise zuerst diskretisiert. 

Bei der Diskretisierung gewinnt man eine diskrete Teilmenge aus einer kontinuierlichen Daten- oder Informationsmenge. Das Ziel dabei ist die Behandlung kontinuierlicher Objekte (bspw. geschwungener Linien) in endlicher Zeit und mit endlichem Speicherplatz.

Danach kann ein Suchalgorithmus auf den diskretisierten Konfigurationsraum angewandt werden, um einen optimalen Pfad zu finden. Die Diskretisierung des Konfigurationsraums kann entweder durch die Spannung eines Graphs oder durch die Zellunterteilung realisiert werden.

Graphkarte

In der Graph-Darstellung wird der Konfigurationsraum durch eine Wegekarte aufgespannt. Jeder Knoten kennzeichnet eine gültige freie Konfiguration des Fahrzeugs. Falls eine Linie zwischen zwei benachbarten Knoten vollständig im freien Konfigurationsraum liegt, wird eine Kante zwischen den zwei Knoten gebildet. Gibt es eine Kante, darf sich das Fahrzeug von einem Knoten zu seinem benachbarten Knoten bewegen. Die Pfadplanung reduziert sich damit auf das Verbinden von Start und Endpunkt zu einem nächstgelegenen Knoten im Graph und anschließender Wegesuche im Graph.

Der Bildungsprozess von einem Graph kann mit verschiedenen Algorithmen automatisch realisiert werden.

Zellengraphkarte

Neben der Graph-Diskretisierung gibt es auch Zellunterteilungsverfahren für die Extrahierung des Konfigurationsraums. Die Grundidee ist es, den Konfigurationsraum in viele kleine benachbarte Zellen zu zerlegen. Eine Zelle wird als frei bezeichnet, falls sie sich komplett im freien Konfigurationsraum befindet, sonst wird die Zelle als besetzt markiert. Jede zwei benachbarte freie Zellen werden mit einer Kante verbunden. Alle Zellen und Kanten bilden einen Zellengraph (Abbildung 7). Das Pfadplanungsproblem ist eigentlich auch ein Wegesuchproblem auf einem Zellengraph.

Mit diesem Verfahren können die Hindernisse mit beliebiger Form durch die Auswahl einer geeigneten Zellgröße modelliert werden. Mit steigender Auflösung kann der Suchraum jedoch zu groß werden. Dieses Problem lässt sich durch Zellen mit unterschiedlichen Größen entschärfen. Im zweidimensionalen Konfigurationsraum können die unterschiedlichen Größen der Zellen durch die Verwendung von QuadTrees modellieret werden. Eine Pfadsuche entspricht dann der Suche in einem binären Baum. Im dreidimensionalen Konfigurationsraum können die Zellen mit einem Octotree (Hornung, Wurm, Bennewitz, Stachniss, & Burgard, 2013) realisiert werden.

Die freien Zellen werden weiß markiert. Die von Hindernissen besetzten Zellen werden schwarz markiert. Ein Pfad von Startpunkt S zum Zielpunkt G wird als grüne Linie dargestellt.

Im Standard-Zellengraph sind Zellen nur über die Zentren miteinander verbunden. Das führt dazu, dass ein Pfad nur über das Zentrum der Zelle verlaufen kann und an manchen Stellen nicht stetig ist (Abbildung 8, Links).

In der Praxis ist ein unstetiger Pfad normalerweise ineffizient oder sogar nicht ausführbar. Ähnlich wie beim PPT Verfahren, haben die Autoren in (Montemerlo, et al., 2008) den Zellengraph mit zwei zusätzlichen Dimensionen erweitert: der Orientierung des Fahrzeugs und der Einschränkung der Bewegungsrichtung. Die nächste mögliche Folgepose ist dann nicht mehr auf das Zentrum der Nachbar-Zelle beschränkt, sondern kann mit Berücksichtigung der Bewegungseinschränkung auf einer beliebigen Position einer Nachbar-Zelle landen. Damit kann ein stetiger Pfad über den gesamten Konfigurationsraum (Abbildung 8 Rechts) generiert werden. Die Autoren haben dieses Verfahren als Hybrid A* bezeichnet.

Pfadplanungskonzept

Was ist der Konfigurationsraum?

Das efeuCampus- Fahrzeug bewegt sich zwar in einem dreidimensionalen euklidischen Raum, hat aber nur 3 Freiheitsgrade: x, y und θ in einer flachen Ebene. Um unnötigen Aufwand bei der Planung zu vermeiden, wird das Fahrzeug im zweidimensionalen euklidischen Raum modelliert. 

Dafür kann das Transportfahrzeug entweder als ein Kreis oder als ein Rechteck modelliert werden. Die Modellierung als Kreis hat den Vorteil, dass die Pfadplanung sehr effizient durchgeführt werden kann. Aufgrund der Größe und der Dimension des Fahrzeuges, kann ein Pfad mit Kreismodellierung in einer engen Stelle nicht gefunden werden. Deshalb eignet sich eine Rechteckmodellierung für unser Projekt besser.

Eine Konfiguration für das Fahrzeug ist also ein zweidimensionales Rechteck. Die Breite und Länge des 2D-Rechtecks entsprechen der Dimension des Fahrzeugs in der zweidimensionalen Ebene. Die Position und Orientierung des 2D-Rechtecks wird mit einer Pose im zweidimensionalen euklidischen Koordinatensystem dargestellt. Der Konfigurationsraum beinhaltet dann alle möglichen Konfigurationen des Fahrzeugs innerhalb des efeuCampus- Testgebiets.

Um die Komplexität des Suchproblems zu reduzieren, soll der Konfigurationsraum noch diskretisiert bzw. abstrahiert werden. Eine Straßennetzkarte ist für eine so große Umgebung besonders gut geeignet. Deswegen wird die Pfadplanung zuerst auf einer Straßennetzkarte durchgeführt.

Straßennetzkarte

Das efeuCampus Fahrzeug soll hauptsächlich auf Fußwegen fahren. Bei Bedarf (z.B. um eine Straße zu überqueren), kann das Fahrzeug auch kurzzeitig auf der Straße fahren. Daher soll eine Straßennetzkarte ausführliche Geoinformation über Fußwege, Fahrradwege und Straßen enthalten.

Die Nutzung von OpenStreetMap

OpenStreetMap ist ein freies Projekt, das die Geoinformation sammelt und strukturiert. Die Daten stehen unter einer freien Lizenz (Open Database License) und sind offen zugänglich. Aus diesen Daten können sowohl freie als auch kommerzielle Landkarten erstellt werden. Die Daten können weiter kostenfrei für Navigationssoftware genutzt werden, ohne durch restriktive Lizenzen beschränkt zu sein. Gemäß der Lizenz ist die Nennung von OpenStreetMap als Datenquelle und die Unterstellung der Abänderung des Datensatzes unter dieselbe Lizenz erforderlich (Wikipedia, 2019).

Die Geoinformation von OpenStreetMap ist hauptsächlich für PKW-Navigation gedacht. Deswegen kann es sein, dass kleinere Wege in manchen Bereichen nicht abgebildet sind (Abbildung 9). In diesen Fall sollen in diesem Projekt verwendete, kleine Wege in der Straßennetzkarte ergänzt werden. 

Abbildung 9: Visualisierung eine Straßenkarte in XML Format von OpenStreetMap. Für manche Bereiche (gelbe gepunktete Rechteck) gibt es keine Wegeabbildung von der Hauptstraße (rote Linie) zu den Wohngebäuden (blaue Rechtecke). 

Zellengraphkarte mit semantischen Informationen

Eine Straßennetzkarte ist eine grob extrahierte Datenstruktur und kann den Arbeitsraum nicht komplett abdecken. Deswegen kann es sein, dass Start- oder Zielpunkt nicht direkt auf dem Straßennetz liegen. Dabei soll die Pfadplanung auf die 3D- Umgebungskarten zurückgreifen, um einen Pfad zum nächstgelegenen Anschlusspunkt zur Straßennetzkarte zu finden. Dafür sollen zuerst alle befahrbare Bereichen aus der 3D- Karte extrahiert werden. Danach kann eine Zellengraphkarte über befahrbare Bereiche mit Hilfe des Hybrid A* Verfahrens erzeugt werden. Die Pfadplanung läuft dann zuerst von einen Startpunkt zu einem Anschlusspunkt über die Zellengraphkarte und dann über den Straßennetzkarte zum Ziel.

Damit generiert die Pfadplanung einen Weg in einem nahezu kompletten freien Raum. Dabei kann das Problem auftauchen, dass ein Pfad über eine verbotene Zone, bspw. einen Parkplatz, eine Hauptstraße oder einen reservierten Bereich für Rettungsdienst, geplant wird. Um solche Probleme zu vermeiden, soll die Zellengraphkarte die verbotene Zone mitberücksichtigen. Dafür kann diese Zone im Zellengraph als Hindernis manuell eingezeichnet werden oder aus der semantischen Karte automatisch extrahiert und in den Zellengraph eingepflegt werden.

Verkehrsregeln

Die Outdoor-Navigation muss immer mit anderen Verkehrsteilnehmern rechnen und adäquat reagieren. Dafür soll das Transportahrzeug die Verkehrsregeln berücksichtigen und das entsprechende Verhalten in den Pfad mit einplanen. Die Verkehrsregeln für das efeu-Fahrzeug sind an die Verkehrsregeln der StVO angelehnt. Ziel ist es, dass andere Verkehrsteilnehmerinnen und -teilnehmer, die mit den Verkehrsregeln der StVO vertraut sind, das Verhalten des Systems abschätzen und nachvollziehen können.

Die in §1 StVO (Abs. 1) beschriebenen Grundregeln fordern von den Verkehrsteilnehmenden ständige Vorsicht und gegenseitige Rücksicht. Neben der Vermeidung von Schaden sollen andere Verkehrsteilnehmerinnen und -teilnehmer weder behindert noch belästigt werden (Abs. 2). Zur Erhaltung dieser Grundregeln sind folgende Maßnahmen erforderlich:

• Erkennung anderer Verkehrsteilnehmender: Das System kann zwischen aktiven Verkehrsteilnehmerinnen und -teilnehmern und anderen Hindernissen unterscheiden. 
• Defensive Fahrstrategien: Bewegen sich Personen im direkten Umfeld, wird die Fahrgeschwindigkeit und das Verhalten angepasst.
• Erkennbarkeit des Verhaltens für andere Verkehrsteilnehmende: Besonders in beengen Verkehrssituationen muss das Gegenüber verstehen, welche Fahrbewegungen das Fahrzeug durchführt.

Das efeu-Fahrzeug benutzt vorwiegend Gehwege. Die Fahrbahn wird nur zur Überquerung der Straße benutzt, wobei das Transportfahrzeug die Fahrbahn auf dem kürzesten Weg überfährt (vgl. §25 StVO „Fußgänger“). 

Rechtsfahrgebot: Damit andere Verkehrsteilnehmer das Verhalten abschätzen können, fährt das Fahrzeug möglichst auf der rechten Seite. Dies betrifft sowohl Straßen, Gehwege als auch Kreuzungen (vgl. Abs. 1 & 2, §2 StVO). 

Die maximale Fahrgeschwindigkeit beträgt maximal 1,6 m/s, also ca. 5,67 km/h. Darüber hinaus muss die Geschwindigkeit reduziert werden, wenn die Sensoren Rückschlüsse auf schlechte Straßen- oder Wetterverhältnisse geben. Ohne einen triftigen Grund (z.B. Störung, Witterung) sollte die Fahrgeschwindigkeit hoch genug sein, um andere Verkehrsteilnehmer z.B. Fußgänger nicht zu behindern (vgl. §3 StVO).

Das Fahrzeug muss einen Sicherheitsabstand einhalten, um sicher anhalten zu können, wenn ein Verkehrsteilnehmer oder eine Verkehrsteilnehmerin davor bremst bzw. stehen bleibt (vgl. §4 StVO). Bei der Festlegung des erforderlichen Sicherheitsabstandes müssen die Reaktionszeiten der Sensor- und Steuerungssysteme sowie der Bremsweg berücksichtigt werden (EN ISO 13855). 

Beim Vorbeifahren an stehenden Personen oder haltenden Fahrzeugen wird mittels Sensorik überprüft, ob kein entgegenkommender Verkehrsteilnehmer oder Verkehrsteilnehmerin behindert wird. Im Zweifel wird der entgegenkommende Verkehrsteilnehmer bzw. die Verkehrsteilnehmerin durchgelassen, bevor die Fahrt fortgeführt wird. Das Transportfahrzeug führt keine Überholvorgänge durch (vgl. §5, §6 StVO).

An Kreuzungen befolgt das Fahrzeug die „Rechts vor Links“-Regel. Dies gilt nicht, sofern das Fahrzeug von einem privaten Gelände auf eine öffentliche Straße einfährt, ein (abgesenkter) Bordstein überfahren wird oder andere Verkehrszeichen die Vorfahrt regeln. Die Verkehrszeichen werden in der Fahrzeugkarte abgebildet und berücksichtigt. Das Gewähren der Vorfahrt sollte durch die anderen Verkehrsteilnehmenden erkennbar sein, um Unsicherheiten und Beeinträchtigungen zu vermeiden (vgl. §8 StVO).

Beim Abbiegen erfolgt die Richtungsanzeige rechtzeitig durch optische Signale. Hierbei wird vor und während dem Abbiegevorgang überwacht, ob sich andere Verkehrsteilnehmer (überholende oder entgegenkommende) in der Abbiegerichtung befinden. Bei Kollisionsgefahr wird der Abbiegevorgang unterbrochen. Wenden und Rückwärtsfahren ist in vordefinierten Bereichen erlaubt – ansonsten bewegt sich das Fahrzeug entlang der vorgegebenen Bewegungsrichtung entlang des Verkehrsweges (vgl. §8 StVO). 

Halten (eine gewollte Fahrtunterbrechung, die nicht von der Verkehrslage veranlasst ist) und Parken (eine längere Fahrtunterbrechung) sind nur an vordefinierten Positionen vorgesehen (vgl. §12 StVO). Die Positionen für das Halten umfassen Wartepositionen, z.B. um auf das Freiwerden einer Übergabestation zu warten. Diese Positionen werden in der Karte festgelegt und ggf. auch in der Umgebung als solche markiert. 

Sorgfaltspflichten beim Ein- und Ausladen erfordern technische Maßnahmen, um die Gefährdung und die Störung von anderen Verkehrsteilnehmerinnen und -teilnehmern zu reduzieren (vgl. §14 StVO). Im Rahmen von efeuCampus umfasst dies technische Schutzmaßnahmen an Fahrzeug und der Infrastruktur sowie die Kennzeichnung von Gefahrenstellen.

Die Ladung, Transportbehälter, muss so im Fahrzeug verstaut werden, dass diese bei einer Sicherheitsbremsung oder einer Kurvenfahrt nicht verrutscht. Die Ladung befindet sich innerhalb der Fahrzeugkontur (vgl. §22 StVO). 

Die Nutzung von Fußgängerüberwegen ist für die Überquerung von Straßen vorgesehen. Befindet sich das Fahrzeug auf der Fahrbahn, muss Personen das Überqueren von Fußgängerüberwegen ermöglicht werden (vgl. §26 StVO). 

Die Konfiguration der Verkehrsregeln soll durch den Betreiber, mithilfe eines Tools, durchgeführt werden. Das Tool ist durch einen Workshop zu definieren.

Schnittstelle zur Routenplanung

Die Pfadplanung bekommt eine Zielzuweisung von der Routenplanung (PTV), und meldet den Zustand des Fahrzeugs zurück. Dabei soll die Schnittstelle zwischen den beiden Komponenten definiert werden. Eine wichtige Aufgabe ist dabei, ein einheitliches Referenzsystem zu definieren. Die heutzutage am häufigsten verwendeten Referenzsysteme für Außenbereich sind:

Geografisches Koordinatensystem WGS 84

Das Geographische Koordinatensystem ist ein Kugelkoordinatensystem. Die Koordinate besteht aus Breite und Länge. Die Werte können in zwei Zahlensystemen angegeben werden: im Sexagesimalsystem mit Grad, Minuten und Sekunden oder im Dezimalsystem mit Grad (Dezimalgrad). Ja nach den Anforderungen an die Genauigkeit kann die Zahl der Nachkommastellen der Werte frei gewählt werden. Tabelle 1 zeigt die unterschiedlichen Genauigkeiten für Breitenangabe in Dezimalgrad und entsprechenden Sexagesimalgrad an.

Tabelle 1: Breiteangabe in Dezimalgrad mit verschiedenen Nachkommastellen

UTM-Koordinatensystem auf WGS84-Basis 

Für die Navigation in kleinen Bereichen ist ein kartesisches Koordinatensystem besser geeignet. Dabei muss die gekrümmte Oberfläche der Erde auf eine flache Ebene projektiert werden. Es sind über 400 verschiedene Projektionen bekannt (Wikipedia, 2019), aber keine Projektion kann die Anforderungen an Winkel-, Längen-, Fläche- und Richtungstreue gleichzeitig erfüllen. 

Die bedeutendste Projektion darunter ist die transversale Zylinderprojektion (liegende Zylinderachse, Abbildung 10 Links) (Wikipedia, 2019). Diese Projektion ist winkeltreu und in kleinen Bereichen ist der Längenmaßstab in allen Richtungen gleich. Mit dieser Eigenschaft findet diese Projektion in der Praxis in großem Umfang Anwendung, wie z.B. in der universalen transversalen Mercator-Projektion (UTM) (Wikipedia, 2019).

Das UTM-System ist ein globales Koordinatensystem. Es teilt die Erdoberfläche (von 80° Süd bis 84° Nord) streifenförmig in 6° breite vertikale Zonen auf, die einzeln mit der jeweils günstigsten transversalen Mercator-Projektion verbindet und mit einem kartesischen Koordinatensystem überzogen wird (Wikipedia, 2019). Abbildung 10 rechts zeigt die UTM-Zonenaufteilung für Europa.

Abbildung 11: Links: Die transversale Zylinderprojektion. Rechts: UTM-Zonenaufteilung für Europa (Wikipedia, 2019)

Meldegitter im UTM-Abbildungssystem (UTMREF)

Das UTMREF ist ein Planquadrat-orientiertes geografisches Meldesystem und basiert auf dem UTM-Koordinatensystem (Wikipedia, 2019). Die Meridianstreifen des UTM-Referenz-Koordinatensystems werden in Planquadrate mit 100 km Seitenlänge gegliedert. Diese Planquadrate werden mit einem zweistelligen Buchstaben-Code identifiziert.

Abbildung 11: UTMREF 100-km-Planquadrat Zonenaufteilung für Deutschland (Wikipedia, 2019).

Die Ortangabe kann mit verschiedenen Koordinatensystemen dargestellt werden. Abbildung 12 zeigt ein Beispiel für einen Knoten in Straßennetzkarte von OpenStreetMap. Die Koordinaten zwischen den drei Koordinatensystemen kann ineinander umgerechnet werden.

Abbildung 12: Ortsangabe für ein Knoten in der Straßenkarte mit verschiedenen globalen Koordinatensystemen.