Bachelorarbeit über Constraint-Programmierung
Juni 2019
Überblick
Als Bachelorstudent der Informatik ging ich einer praktischen Frage nach: Wenn ein Simulator viele mögliche Bedingungen ansammelt, wie bringt man ihn dazu, jene nicht mehr zu prüfen, die gar nicht mehr eintreten können? Ich entwickelte und bewertete für HydLa ein Verfahren, das die Richtung nutzt, in die sich ein Wert verändert, um überflüssig gewordene Bedingungen aus der Suche zu nehmen. Im Referenzmodell sank die gesamte Simulationszeit auf etwa die Hälfte.
Diese Arbeit ist ein frühes Fundament meiner Designphilosophie. Die Constraint-Programmierung hat mich gelehrt, dass komplexe Ergebnisse nicht immer direkt festgelegt werden müssen: Sie können aus einem sorgfältig definierten Raum von Regeln, Prioritäten und Grenzen hervorgehen. Dieses Denken trägt heute meine Art, im Zeitalter der KI aus Beschränkungen heraus zu gestalten — die Bedingungen zu gestalten, innerhalb derer ein generatives System frei handeln darf.
Zusammenfassung
HydLa ist eine Modellierungssprache für hybride Systeme: Systeme, in denen kontinuierliche Veränderung und diskrete Ereignisse zusammenwirken. Ihr auf Beschränkungen beruhender Entwurf erlaubt es, solche Systeme knapp zu beschreiben und mit hoher Genauigkeit zu simulieren. Der Preis dafür ist, dass ein großes Modell den Simulator sehr viele bedingte Regeln prüfen lässt, auch wenn manche davon längst gegenstandslos sind.
Diese Forschung schlug vor, jene bewachten Beschränkungen zur Laufzeit zu reduzieren. Erkennt der Simulator monotones Verhalten — einen Wert, der sich weiterhin in eine Richtung bewegt —, kann er feststellen, dass bestimmte Wächterbedingungen künftig nie mehr wahr werden, und ihre Prüfung gefahrlos einstellen. Besonders wirksam war der Ansatz bei einem Modell mit vielen gleichartig bewachten Objekten: Die gemessene Laufzeit fiel auf etwa die Hälfte des ursprünglichen Werts.
1. Einleitung
Ein hybrides System verbindet kontinuierliches Verhalten mit diskreten Ereignissen. Ein springender Ball ist ein einfaches Beispiel: Position und Geschwindigkeit ändern sich stetig, solange er in der Luft ist, doch der Augenblick, in dem er auf eine Fläche trifft, erzeugt ein diskretes Ereignis, das seine Richtung ändert. Thermostate, Fahrzeuge und Roboter enthalten dieselbe Mischung in folgenreicheren Ausprägungen.
In HydLa lassen sich solche Systeme mit mathematischen und logischen Beschränkungen beschreiben, statt eine einzige prozedurale Abfolge auszuschreiben. Der Simulator HyLaGI rechnet symbolisch und damit ohne Rundungsfehler und kann mit unbestimmten Parametern umgehen. Diese Ausdruckskraft schafft jedoch ein Größenproblem: Enthält ein Modell viele Regeln, die nur unter bestimmten Bedingungen greifen, muss der Simulator immer wieder für jede einzelne fragen, ob sie die nächste eintretende sein könnte.
2. Bewachte Beschränkungen in der Simulation
Eine bewachte Beschränkung ist eine Regel, die erst aktiv wird, wenn ihre Wächterbedingung erfüllt ist. Im Referenzmodell oben hat jeder Abschnitt der Fläche seine eigene Regel: Erreicht der Ball die Höhe null, während seine waagerechte Position innerhalb dieses Abschnitts liegt, greift die Abprallregel. Je feiner die Fläche geteilt wird, desto mehr Wächterbedingungen muss der Simulator also durchsehen.
Im Experiment wurde die Zahl der Abschnitte von 10 bis 200 variiert. Der ursprüngliche Simulator wurde ungefähr mit dem Quadrat dieser Zahl langsamer. Das reicht über das Spielbeispiel hinaus: Ein größeres Modell kann viele physische Objekte, Kontaktbereiche oder mögliche Ereignisse genau in dieser bewachten Form darstellen.
3. Wo der Engpass liegt
Die Profilierung zeigte, dass sich die Verlangsamung nicht gleichmäßig über den Simulator verteilte. Bei 100 Flächenabschnitten entfielen 96 % der gemessenen Laufzeit auf FindMinTime, jene Operation, die das früheste mögliche nächste Ereignis sucht. Sie wertete die Wächterbedingungen sämtlicher in Frage kommender Beschränkungen immer wieder neu aus.
Damit war das Ziel der Optimierung genau benannt: die Zahl der Wächterbedingungen verringern, die FindMinTime betrachten muss, und dabei das simulierte Verhalten exakt gleich lassen.
4. Reduktion bewachter Beschränkungen
Man stelle sich einen Ball vor, der eine Treppe hinunterspringt. Sobald der Ball eine Stufe passiert hat und weiter vorwärts läuft, kann diese Stufe ihn nicht mehr beeinflussen. Wer die Zeichnung ansieht, blendet die Stufen hinter dem Ball sofort aus; der ursprüngliche Algorithmus prüfte weiterhin jede einzelne davon.
Schwierig ist der Nachweis, dass eine verworfene Wächterbedingung später nicht doch gebraucht wird. Sie nur deshalb zu entfernen, weil sie gerade falsch ist, könnte still ein falsches Ergebnis erzeugen, sobald sie wieder wahr wird. Der Vorschlag stützt sich deshalb auf Monotonie: darauf, ob garantiert ist, dass eine Variable über ein Zeitintervall hinweg weiter wächst oder weiter fällt.
4.1 Ansatz für gleichmäßige Monotonie
Der erste Ansatz greift, wenn sich eine Variable während der gesamten Simulation in eine Richtung bewegt. Im Modell mit geteilter Fläche wächst die waagerechte Position des Balls immer. Hat er einen Abschnitt hinter sich gelassen, kann dessen Bedingung nie wieder erfüllt werden. Verfahren der Modellprüfung können diese Eigenschaft vor der Simulation nachweisen, sodass überflüssig gewordene Wächterbedingungen im Lauf der Ausführung gefahrlos entfernt werden dürfen.
4.2 Ansatz für wechselnde Monotonie
Viele reale Systeme bewegen sich nicht für immer in eine Richtung. Eine Variable kann wachsen, umkehren und dann fallen. Die Arbeit skizzierte deshalb einen zweiten Ansatz: mit einer angenommenen Richtung beginnen, diese Annahme durch Zusicherungen überwachen und die Reduktionslogik ab dem Punkt neu starten, an dem die Richtung wechselt. Wächterbedingungen, die für ein monotones Intervall entfernt wurden, werden zu Beginn des nächsten wiederhergestellt.
5. Experimentelle Ergebnisse
Ich habe den Ansatz der gleichmäßigen Monotonie implementiert und am Modell mit geteilter Fläche bewertet. Sowohl der ursprüngliche als auch der vorgeschlagene Algorithmus brauchten mit wachsender Abschnittszahl weiterhin länger, doch die vorgeschlagene Fassung leistete durchgehend weniger Arbeit. Im Vergleich der angepassten Kurven fiel der führende Koeffizient von 1,1463 auf 0,6083; für diesen Referenzfall halbierte sich die gesamte Simulationszeit ungefähr.
Das ist keine Behauptung, jedes HydLa-Modell werde doppelt so schnell. Es zeigt, wo das Verfahren hilft: bei Modellen mit vielen bewachten Objekten und einer beweisbaren Richtung der Veränderung, in denen Wächterbedingungen während eines Laufs dauerhaft gegenstandslos werden.
6. Fazit und weitere Arbeit
Die Forschung zeigte, dass Wissen über ein Modell — und nicht nur schnelleres Rechnen auf niedriger Ebene — eine Simulation effizienter machen kann. Indem HyLaGI mit Hilfe der Monotonie erkennt, welche Möglichkeiten unmöglich geworden sind, kann es seine Menge aktiver Beschränkungen verkleinern, ohne das Ergebnis zu verändern.
Das umgesetzte Experiment deckte die gleichmäßige Monotonie ab. Die Arbeit ließ zwei Richtungen für später offen: das auf Zusicherungen gestützte Verfahren für wechselndes Verhalten zu bewerten und andere Invarianten als die Monotonie zu nutzen, um weitere gefahrlos entfernbare Beschränkungen zu finden.
Takafumi Horiuchi und Kazunori Ueda: „Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa“. 33. Jahreskonferenz der Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02.