Mixed-Integer Programming

Auch genannt: MIP, MILP, MIQP, MICP
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

Optimierung, bei der einige Variablen ganzzahlige Werte annehmen müssen, oft 0 oder 1, sodass ein Problem diskrete Entscheidungen mit kontinuierlichen Größen verbinden kann.

Definition

Gemischt-ganzzahlige Programmierung (Mixed-Integer Programming, MIP) ist Optimierung über eine Mischung aus kontinuierlichen Variablen und auf ganze Zahlen beschränkten Variablen, meist binären Variablen, die den Wert 0 oder 1 annehmen. Die binären Variablen kodieren diskrete Entscheidungen: durch welche Region ein Pfad führt, welcher Fuß als Nächstes aufsetzt, ob ein Kontakt aktiv ist, welcher Roboter welche Aufgabe übernimmt. Die kontinuierlichen Variablen tragen den Rest, etwa Positionen, Geschwindigkeiten und Kräfte. Gängige Klassen werden nach der Form des verbleibenden Problems benannt: gemischt-ganzzahlige lineare Programme (MILP), gemischt-ganzzahlige quadratische Programme (MIQP) und allgemeiner gemischt-ganzzahlige konvexe Programme (MICP).

Diese Probleme sind im Allgemeinen NP-schwer, doch moderne Löser bewältigen viele praktische Instanzen gut. Sie verwenden Branch-and-Bound: die kontinuierliche Relaxation ohne die Ganzzahligkeitsforderungen lösen, eine Variable wählen, die gebrochen herauskam, in zwei Teilprobleme aufteilen, die sie nach unten bzw. oben zwingen, und jeden Zweig abschneiden, dessen Relaxation bereits schlechter ist als die beste gefundene ganzzahlige Lösung. Schnittebenen verschärfen die Relaxation unterwegs. Kommerzielle Löser wie Gurobi und CPLEX und quelloffene wie SCIP, HiGHS und CBC implementieren diese Methoden.

Wie ein Problem formuliert wird, zählt ebenso viel wie die Wahl des Lösers. Logische Bedingungen werden oft mit Big-M-Nebenbedingungen (big-M constraints) kodiert, die eine Nebenbedingung mit einer binären Variablen und einer großen Konstante ein- oder ausschalten; eine zu große Konstante schwächt die Relaxation und verursacht numerische Probleme. Formulierungen mit scharfen Relaxationen lösen sich viel schneller, was ein Grund dafür ist, dass strukturierte Ansätze wie Graphen konvexer Mengen so entworfen werden, dass ihre Relaxation nahe am eigentlichen Problem liegt.

Warum es wichtig ist

Viele Planungsprobleme in der Robotik sind teilweise diskret: links oder rechts an einem Hindernis vorbei, eine Kontaktfolge wählen, Aufgaben zuweisen. Gemischt-ganzzahlige Programmierung behandelt diese Entscheidungen exakt innerhalb einer Optimierung, oft mit einer Schranke dafür, wie weit die Antwort vom Optimum entfernt ist, statt sich auf handgemachte Heuristiken oder Stichproben zu verlassen.

Wichtige Anwendungen

Schritt- und Kontaktfolgenplanung für Laufroboter
Trajektorienplanung durch konvexe Regionen für Drohnen und Arme
Aufgabenzuweisung und Ablaufplanung für Roboterflotten
Hybride modellprädiktive Regelung mit diskreten Modi
Aufgaben- und Bewegungsplanung mit diskreten Aktionsentscheidungen

In der Praxis

Ein Team, das Schritte für einen Humanoiden über Trittsteine plant, stellt die begehbare Fläche jedes Steins als konvexes Polygon dar. Für jeden der nächsten Schritte fügt es binäre Variablen hinzu, die auswählen, auf welchem Polygon der Fuß landet, mit Nebenbedingungen, die nur für das gewählte Polygon aktiv sind, dazu kontinuierliche Variablen für die Fußpositionen und Grenzen für Schrittlänge und Drehung. Die Kostenfunktion belohnt Fortschritt in Richtung Ziel und bestraft ungünstige Schritte. Ein gemischt-ganzzahliger Löser liefert eine Schrittfolge, meist innerhalb eines für die Neuplanung gesetzten Zeitlimits, zusammen mit der Lücke zwischen der besten gefundenen Lösung und der besten Schranke. Sind die Lösungszeiten zu lang, verringert das Team die Zahl der auf einmal geplanten Schritte, verschärft die Big-M-Werte oder startet warm vom vorherigen Plan aus.

Häufige Missverständnisse

Gemischt-ganzzahlige Programme sind für die Robotik immer zu langsam — kleine, gut formulierte Probleme lassen sich schnell genug für Online-Neuplanung lösen
Das Runden der kontinuierlichen Relaxation ergibt die optimale ganzzahlige Lösung — Runden kann unzulässig oder weit vom Optimum entfernt sein, wenn die Relaxation nicht scharf ist
Jeder große Wert für M funktioniert in Big-M-Nebenbedingungen — übermäßig große Werte schwächen die Relaxation und verursachen numerische Schwierigkeiten
Ein Löser, der an seinem Zeitlimit stoppt, ist gescheitert — er liefert meist die bisher beste Lösung und eine Optimalitätslücke, die angibt, wie gut sie ist

Wer das wissen sollte

Ingenieure für Bewegungs- und Schrittplanung
Entwickler für Flotten-Ablaufplanung und Aufgabenzuweisung
Forschende in optimierungsbasierter Regelung
Robotikstudierende, die Optimierung lernen

Videos

Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

Wikipedia

Ganzzahlige lineare Optimierung

Open Source Robotics