Dubins Car

Auch genannt: Dubins vehicle
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, kinematics, nonholonomic, fixed-wing, path-planning

Ein ebenes Fahrzeugmodell, das sich mit konstanter Geschwindigkeit und beschränkter Drehrate vorwärts bewegt; seine kürzesten Wege zwischen zwei Posen bestehen aus höchstens drei Bögen und geraden Segmenten.

Definition

Das Dubins-Fahrzeug (Dubins car) ist ein kinematisches Modell eines Fahrzeugs, das sich nur mit fester Geschwindigkeit vorwärts bewegen und nicht enger als mit einem Mindestradius wenden kann. Sein Zustand ist die Position (x, y) und der Kurswinkel θ, und seine Bewegung folgt ẋ = v cos θ, ẏ = v sin θ, θ̇ = u mit |u| ≤ v / R_min. Verglichen mit dem Unicycle-Modell, das jede Vorwärtsgeschwindigkeit sowie Anhalten, Rückwärtsfahren und Drehen auf der Stelle erlaubt, hat das Dubins-Fahrzeug eine konstante Geschwindigkeit und eine beschränkte Krümmung, sodass es weder anhalten noch auf der Stelle drehen kann. Wie das Unicycle unterliegt es einer nichtholonomen Zwangsbedingung: Es kann sich nicht seitwärts bewegen.

Das Modell ist nach Lester Dubins benannt, der 1957 bewies, dass der kürzeste Weg beschränkter Krümmung zwischen zwei Posen in der hindernisfreien Ebene aus höchstens drei Segmenten besteht, jeweils entweder eine Gerade (S) oder ein Kreisbogen mit Mindestradius, der nach links (L) oder rechts (R) dreht. Nur sechs Kombinationen können optimal sein: LSL, RSR, LSR, RSL, LRL und RLR, sodass ein Planer jeden Kandidaten in geschlossener Form berechnen und den kürzesten behalten kann. Reeds und Shepp (1990) erweiterten das Ergebnis auf ein Fahrzeug, das auch rückwärts fahren kann, und erhielten das Reeds-Shepp-Fahrzeug mit einer größeren Familie optimaler Wege.

Dubins-Wege sind ein Standardbaustein der Planung für Starrflügelflugzeuge, Boote und fahrzeugähnliche Roboter. Sampling-basierte Planer wie RRT und RRT* nutzen sie als lokale Steuerfunktion, und Planer für Flächenabdeckung und Routing nutzen sie, um Wegpunkte unter Krümmungsgrenzen zu ordnen. Dreidimensionale Erweiterungen, oft Dubins-Flugzeug genannt, fügen die Höhe mit beschränkter Steig- oder Sinkrate hinzu. Das Modell hat Grenzen, die man kennen sollte: Reale Fahrzeuge können nicht augenblicklich zwischen vollem Linkseinschlag, Geradeausfahrt und vollem Rechtseinschlag wechseln, daher müssen Krümmungssprünge an den Segmentübergängen vom Regler geglättet oder durch Planung mit Klothoiden oder anderen Wegen stetiger Krümmung vermieden werden, und Wind oder Strömungen verändern die Geschwindigkeit über Grund auf eine Weise, die das reine Modell ignoriert.

Warum es wichtig ist

Viele Fahrzeuge, darunter Starrflügeldrohnen, Boote und Autos bei höherer Geschwindigkeit, sind tatsächlich auf Vorwärtsbewegung und einen Mindestwenderadius beschränkt. Das Dubins-Fahrzeug erfasst dies im einfachsten möglichen Modell und liefert kürzeste Wege in geschlossener Form, was es zu einem Bezugspunkt für Planung und Regelung solcher Fahrzeuge macht.

Wichtige Anwendungen

Bahnplanung für Starrflügel-UAVs
Steuerfunktionen in sampling-basierten Planern für fahrzeugähnliche Roboter
Wegpunkt-Routing für Wasserfahrzeuge
Krümmungsbeschränkte Abdeckungs- und Inspektionswege
Routingprobleme mit Wendegrenzen, etwa das Dubins-Problem des Handlungsreisenden

In der Praxis

Eine Starrflügel-Vermessungsdrohne muss eine Liste von Wegpunkten mit jeweils vorgegebenem Kurs durchfliegen. Der Planer berechnet den Dubins-Weg zwischen aufeinanderfolgenden Wegpunktposen mit dem Mindestwenderadius des Flugzeugs bei Reisegeschwindigkeit, zuzüglich einer Reserve für Wind, und verkettet die Ergebnisse zu einer Route, der ein Führungsgesetz dann Segment für Segment folgt. Wenn sich mehrere solcher Flugzeuge koordinieren müssen, wie in Arbeiten zur verteilten Pfadverfolgung, die Starrflügelflugzeuge als 3D-Dubins-Fahrzeuge modellieren, muss das Koordinationsgesetz ohne die Möglichkeit auskommen, bis zum Stillstand abzubremsen oder auf der Stelle zu warten.

Häufige Missverständnisse

Das Dubins-Fahrzeug und das Unicycle-Modell sind dasselbe — das Unicycle kann seine Geschwindigkeit ändern, anhalten und auf der Stelle drehen, während sich das Dubins-Fahrzeug mit konstanter Geschwindigkeit und beschränkter Krümmung vorwärts bewegt
Reale Fahrzeuge können Dubins-Wegen exakt folgen — sie enthalten sprunghafte Krümmungsänderungen, die reale Lenkung oder Querneigung glätten muss
Dubins-Lösungen sind auch zwischen Hindernissen optimal — das Ergebnis mit sechs Wegen gilt in der hindernisfreien Ebene; mit Hindernissen sind Dubins-Segmente nur lokale Verbindungen innerhalb eines umfassenderen Planers

Wer das wissen sollte

Ingenieure für Führung und Planung von Starrflügel-UAVs
Forscher in der Bewegungsplanung
Entwickler von Wasser- und autonomen Fahrzeugen
Robotikstudierende, die nichtholonome Planung lernen

Open Source Robotics