Bézier Curve

Auch genannt: Bezier curve
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: trajectory-optimization, splines, path-planning, geometry, motion-planning

Eine durch Kontrollpunkte definierte Polynomkurve: Sie beginnt am ersten, endet am letzten und wird zu den dazwischenliegenden hingezogen; weit verbreitet für Roboterpfade, Trajektorien und Strichformen.

Definition

Eine Bézierkurve (Bézier curve) vom Grad n ist eine Polynomkurve, die durch n + 1 Kontrollpunkte P₀ … Pₙ und einen Parameter t, der von 0 bis 1 läuft, definiert ist: B(t) = Σ C(n, i) (1 − t)ⁿ⁻ⁱ tⁱ Pᵢ, wobei die Gewichte die Bernstein-Basispolynome sind. Die Kurve beginnt bei P₀ und endet bei Pₙ, und ihre Tangente an jedem Ende zeigt entlang der ersten bzw. letzten Strecke des Kontrollpolygons; die inneren Kontrollpunkte formen die Kurve, liegen aber im Allgemeinen nicht auf ihr. Kubische Kurven mit vier Kontrollpunkten sind am verbreitetsten. Die Form wurde in den 1960er-Jahren in der französischen Automobilindustrie von Pierre Bézier bei Renault und unabhängig davon von Paul de Casteljau bei Citroën entwickelt.

Mehrere Eigenschaften machen Bézierkurven in der Robotik praktisch. Die gesamte Kurve liegt innerhalb der konvexen Hülle ihrer Kontrollpunkte, sodass das Halten der Kontrollpunkte innerhalb eines konvexen hindernisfreien Bereichs garantiert, dass auch die Kurve darin bleibt; damit wird Kollisionsvermeidung zu linearen Nebenbedingungen, wie bei der Trajektorienoptimierung über Graphen konvexer Mengen. Die Ableitung einer Bézierkurve ist eine weitere Bézierkurve mit einem um eins niedrigeren Grad und den Kontrollpunkten n(Pᵢ₊₁ − Pᵢ), sodass sich auch Geschwindigkeits- und Beschleunigungsgrenzen, konservativ, an den Kontrollpunkten vorgeben lassen. Der De-Casteljau-Algorithmus wertet Kurven durch wiederholte lineare Interpolation numerisch stabil aus und teilt sie.

Es gibt Grenzen, die man beachten sollte. Der Parameter t ist weder Zeit noch Bogenlänge, daher braucht eine als Trajektorie verwendete Kurve noch eine Zeitparametrierung, und gleiche Schritte in t ergeben keine gleichen Abstände entlang der Kurve. Das Verschieben eines Kontrollpunkts verändert die gesamte Kurve, daher werden lange Pfade meist aus mehreren Segmenten niedrigen Grades aufgebaut, die mit Stetigkeitsbedingungen für Position, Tangente und Krümmung verbunden sind, oder mit B-Splines dargestellt, die lokale Kontrolle bieten. Eine Erhöhung des Grades, um komplexe Formen anzupassen, macht Kurven schwerer zu formen und numerisch weniger gutartig.

Warum es wichtig ist

Bézierkurven bieten eine kompakte, glatte und leicht mit Nebenbedingungen zu versehende Darstellung für Pfade und Trajektorien, von Fahrzeug- und Drohnentrajektorien bis zu Werkzeug- und Pinselstrichen. Ihre Eigenschaften bezüglich konvexer Hülle und Ableitungen machen Sicherheits- und Dynamikgrenzen zu einfachen Nebenbedingungen an einer Handvoll Punkten, weshalb sie in vielen optimierungsbasierten Planern vorkommen.

Wichtige Anwendungen

Erzeugung glatter Trajektorien für Drohnen und mobile Roboter
Pfadglättung nach graphensuch- oder stichprobenbasierter Planung
Spurwechsel- und Parkpfade für autonome Fahrzeuge
Werkzeug-, Pinsel- und Stiftstriche für Mal-, Zeichen- und Dosierroboter
Bewegungsplanung mit Graphen konvexer Mengen
Schwungbeintrajektorien für Laufroboter

In der Praxis

Ein Drohnenplaner zerlegt eine Route durch ein Lager in eine Kette konvexer Freiraumbereiche und ordnet jedem Bereich ein Bézier-Segment zu. Er verlangt, dass die Kontrollpunkte jedes Segments in seinem Bereich liegen, verknüpft die letzten Kontrollpunkte eines Segments mit den ersten des nächsten, sodass Position, Geschwindigkeit und Beschleunigung an den Übergängen übereinstimmen, und begrenzt die Kontrollpunkte der Ableitungskurven, um Geschwindigkeits- und Beschleunigungsgrenzen einzuhalten. Da alle diese Nebenbedingungen in den Kontrollpunkten linear sind, ist das gesamte Problem ein konvexes Programm, das schnell gelöst wird. Ein letzter Schritt bildet den Parameter t jedes Segments mit einer gewählten Dauer auf die Zeit ab; eine kürzere Dauer skaliert jede Geschwindigkeit und Beschleunigung, die die Drohne erreichen muss, nach oben.

Häufige Missverständnisse

Eine Bézierkurve geht durch alle ihre Kontrollpunkte — nur der erste und der letzte liegen auf der Kurve; die inneren ziehen sie an, ohne berührt zu werden
Der Parameter t ist die Zeit — t ist ein Formparameter zwischen 0 und 1; eine separate Zeitskalierung legt Geschwindigkeiten und Beschleunigungen fest
Für komplexe Pfade ist ein höherer Grad immer besser — Kurven hohen Grades verlieren die lokale Kontrolle; Ketten von Segmenten niedrigen Grades oder B-Splines sind meist vorzuziehen
Begrenzte Kontrollpunkte ergeben exakte Geschwindigkeitsgrenzen — Schranken für die Kontrollpunkte der Ableitung sind hinreichend, aber konservativ, sodass das tatsächliche Maximum meist unter der Schranke liegt

Wer das wissen sollte

Ingenieure für Bewegungs- und Bahnplanung
Entwickler autonomer Fahrzeuge und Drohnen
Roboterprogrammierer für Lackieren, Schweißen und Dosieren
Ingenieure für die Fortbewegung mit Beinen, die Schwungbeintrajektorien entwerfen

Videos

The Beauty of Bézier Curves: Freya Holmér

Open Source Robotics