Pfadplanung
Die Navigation für autonomes Fahren im Außenbereich plant für eine anstehende Transportaufgabe den optimalen Pfad zum Ziel und fährt diesen ab.
Ein solches System besteht aus den in der nachfolgenden Systemübersicht aufgeführten Bestandteilen.
Die Pfadplanung
Eine wichtige Komponente dabei ist die Pfadplanung. Sie hat die Aufgabe, einen globalen kollisionsfreien Pfad unter Berücksichtigung bekannter statischer Hindernisse zum Ziel zu bestimmen. Hierzu benötigt die Pfadplanung zuerst ein Modell der Umgebung. Dieses Modell ist eine Umgebungskarte, in der alle mögliche Positionen des Fahrzeugs und alle statischen Hindernisse verzeichnet sind. Ein solches Modell wird als Konfigurationsraum bezeichnet.
Der Konfigurationsraum
Das Fahrzeug bewegt sich in einem physischen kontinuierlichen dreidimensionalen euklidischen Raum.
Als euklidischer Raum wird in der Mathematik zunächst der „Raum unserer Anschauung“ bezeichnet.
Alle Punkte, die das Fahrzeug in dieser realen Welt erreichen kann, bilden einen Arbeitsraum. Für die Pfadplanung soll dieser Arbeitsraum durch ein mathematisches Modell präsentiert werden. Dabei kann das Fahrzeugs zuerst durch eine vereinfachte geometrische Form modellieret werden.
Basierend auf einer konkreten Modellierung, kann eine sogenannte Konfiguration abgeleitet werden. Eine Konfiguration ist eine Spezifizierung des Fahrzeugmodells bezüglich eines festen Koordinatensystems. Die Menge aller möglichen Konfigurationen nennt sich „der Konfigurationsraum“ (Choset, et al., 2005).
Zum Beispiel kann ein kleiner runder Staubsauger-Roboter durch die Form eines Kreises modelliert werden. Eine Konfiguration beschreibt die Position des Roboters mit einem kleinen Radius. Für einen komplizierten Roboterarm kann die Form des Roboterarms durch eine kinematische (die Geometrie einer Bewegung beschreibende) Kette modellieret werden. Die kinematische Kette besteht aus starren Körpern, die durch Gelenke verbunden sind. Die Konfiguration beschreibt dann einen Zustand aller Gelenke und Aktoren des Roboterarms.
Hindernisse sind Objekte innerhalb des Konfigurationsraums, die sich mit der Konfiguration des Fahrzeugs in einen beliebigen Punkt überschneiden. Eine Überscheidung mit Hindernis im Konfigurationsraum wird als Kollision bezeichnet. Die Teilmenge des Konfigurationsraums, die keine Kollisionen mit statischen Hindernissen haben, wird als freier Konfigurationsraum bezeichnet.
Ein Pfad besteht aus den kontinuierlichen Konfigurationen im freien Konfigurationsraum, der Startkonfiguration mit Zielkonfiguration verbindet. Die Pfadplanung beschreibt das Problem der Suche als einen kollisionsfreien Pfad von Start zum Ziel im gegebenen Konfigurationsraum. Es wird also ein Pfad gesucht, auf dem es keine Hindernisse für das Fahrzeug gibt.
Das Pfadplanungsproblem
Ja nach Komplexität des Modells, kann das Pfadplanungsproblem zu verschieden Komplexitätsklassen zugeordnet werden. Wenn ein Fahrzeug als ein Kreis modelliert werden kann, kann das Pfadplanungsproblem in einem zweidimensionalen euklidischen Raum mittels gitterbasierter Algorithmen sehr effizient gelöst werden.
Wenn es sich jedoch um eine komplizierte 2D-Form (z.B. Polyeder) handelt, kann das Pfadplanungsproblem hoch komplex sein.