Direct Collocation

Auch genannt: collocation, direct transcription
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: trajectory-optimization, optimal-control, nonlinear-programming, motion-planning, dynamics

Eine Methode der Trajektorienoptimierung, die Zustände und Steuerungen zu abgetasteten Zeitpunkten als Variablen behandelt und die Dynamik als Nebenbedingungen zwischen benachbarten Abtastpunkten erzwingt.

Definition

Direkte Kollokation (direct collocation) ist ein Weg, ein Optimalsteuerungsproblem, also die Suche nach den Steuereingaben über die Zeit, die ein System mit minimalen Kosten vom Start zum Ziel bewegen, in ein endliches nichtlineares Programm zu überführen, das ein Standardlöser bewältigen kann. Die Trajektorie wird in eine Anzahl von Zeitpunkten zerlegt, die Stützstellen (knot points) heißen. Sowohl der Zustand als auch die Steuereingabe an jeder Stützstelle werden zu Entscheidungsvariablen, und die Dynamik des Systems wird als Gleichheitsnebenbedingungen erzwungen, die Defektbedingungen (defect constraints) heißen und verlangen, dass benachbarte Zustände mit einer Integrationsregel wie der Trapez- oder der Hermite–Simpson-Regel konsistent sind. Pseudospektrale Verfahren sind eine verwandte Familie, die Polynome höherer Ordnung über die gesamte Trajektorie verwendet.

Das unterscheidet sich von Shooting-Verfahren, bei denen nur die Steuerungen Entscheidungsvariablen sind und die Zustände durch Vorwärtssimulation der Dynamik gewonnen werden. Kollokation erzeugt ein größeres, aber sehr dünn besetztes Problem, das mit Lösern für dünn besetzte nichtlineare Programme wie IPOPT oder SNOPT gelöst wird. Ihre Vorteile: Grenzen für Zustände, etwa Gelenkbereiche, Hindernisabstand oder Kontaktbedingungen, lassen sich leicht direkt vorgeben; der Löser kann von einer Schätzung ausgehen, die physikalisch nicht konsistent ist, etwa einer Geraden durch die Hindernisse; und sie verhält sich bei langen Horizonten und instabilen Systemen tendenziell besser als einfaches Shooting.

Eine Folge dieser Struktur ist, dass Zwischeniterationen die Dynamik nicht einhalten müssen: Der Löser darf die Defektbedingungen anfangs verletzen und erfüllt sie erst bei Konvergenz. Formulierungen, die Dynamik- oder Kollisionsbedingungen in Strafterme verschieben, machen das explizit und lassen die Lösung durch unzulässige Bereiche laufen, bevor der Strafterm sie zurückdrängt. Diese Idee wurde im Roboterlernen übernommen, etwa indem man einen simulierten Roboter zunächst mit einer Strafe durch Hindernisse hindurchgehen lässt und später harte Kollisionen erzwingt. Wie die meiste Trajektorienoptimierung findet die direkte Kollokation lokale Optima, daher hängt das Ergebnis von der Anfangsschätzung ab.

Warum es wichtig ist

Die direkte Kollokation ist eines der wichtigsten Arbeitspferde der Trajektorienoptimierung für Laufroboter, Drohnen und Manipulatoren, weil sie gut mit Nebenbedingungen umgeht und leicht von groben Schätzungen startet. Wer sie versteht, versteht auch eine nützliche Entwurfsidee im Roboterlernen: die Physik zuerst lockern und dann schrittweise erzwingen.

Wichtige Anwendungen

Trajektorienoptimierung für Sprünge, Salti und Gangarten von Laufrobotern
Zeit- und energieoptimale Trajektorien für Manipulatoren und Drohnen
Planung von Such- und Abdeckungstrajektorien für mobile Roboter
Erzeugung von Referenzbewegungen für gelernte Policies und Folgeregler
Trajektorienentwurf für Raumfahrzeuge und Flugzeuge

In der Praxis

Ein Ingenieur, der in Drake oder CasADi einen Sprung für einen Laufroboter plant, stellt ein Problem mit beispielsweise einer festen Anzahl von Stützstellen über den Sprung auf, von denen jede den Zustand des Roboters und die Gelenkmomente enthält. Die Defektbedingungen verknüpfen aufeinanderfolgende Stützstellen über die Dynamik des Roboters, zusätzliche Nebenbedingungen halten die Momente innerhalb der Motorgrenzen und die Füße in der Standphase am Boden, und die Kostenfunktion bestraft Aufwand und Endfehler. Er initialisiert mit einer einfachen Interpolation zwischen Start- und Landepose, die die Dynamik verletzt, und lässt IPOPT eine konsistente Trajektorie finden. Scheitert der Löser, fügt er Stützstellen hinzu, skaliert die Variablen oder verbessert die Anfangsschätzung. Die resultierende Trajektorie wird dann von einem Rückführregler verfolgt oder als Referenz für eine gelernte Policy verwendet.

Häufige Missverständnisse

Jede Iteration des Lösers ist eine physikalisch gültige Trajektorie — die Dynamik ist erst bei Konvergenz erfüllt; Zwischenlösungen können sie verletzen
Die direkte Kollokation findet die global beste Trajektorie — sie löst ein nichtkonvexes Problem lokal, daher können verschiedene Anfangsschätzungen verschiedene Antworten liefern
Kollokation und Shooting lösen verschiedene Probleme — sie sind zwei Transkriptionen desselben Optimalsteuerungsproblems mit unterschiedlichem numerischem Verhalten

Wer das wissen sollte

Ingenieure für Trajektorienoptimierung und Bewegungsplanung
Entwickler von Regelungen für Laufroboter und Drohnen
Forschende im Roboterlernen, die optimierte Referenzbewegungen nutzen
Robotikstudierende, die Optimalsteuerung lernen

Open Source Robotics