Takafumi Horiuchi

Bachelorarbeit zur Constraint-Programmierung

Überblick

Je mehr mögliche Ereignisse eine Simulation umfasst, desto mehr Bedingungen muss sie wiederholt auswerten. Doch wenn ihr Verlauf erkennen lässt, dass eine Bedingung nie wieder erfüllt werden kann, lässt sie sich dann gefahrlos überspringen? Für HydLa, eine Modellierungssprache für hybride Systeme, habe ich ein Verfahren entworfen und implementiert, das anhand der Änderungsrichtung von Variablen Bedingungen entfernt, die nicht mehr geprüft werden müssen.

Im untersuchten Modell verkürzte das Verfahren die Laufzeit auf ungefähr die Hälfte der Laufzeit des ursprünglichen Algorithmus, ohne die Simulationsergebnisse zu verändern. Diese Verbesserung entstand dadurch, dass die Struktur des Problems genutzt wurde, um die Zahl der zu berücksichtigenden Möglichkeiten zu verringern.

Die Perspektive der Constraint-Programmierung, die ich in dieser Forschung entwickelt habe, prägt heute meinen Ansatz für die Projekte in meinem Portfolio: Statt jedes Ergebnis direkt vorzugeben, werden Regeln, Prioritäten und Grenzen definiert und daraus Lösungen abgeleitet, die diese erfüllen.


Problem: Mehr Möglichkeiten bedeuten längere Laufzeiten

HydLa beschreibt hybride Systeme, die kontinuierliche Veränderungen und diskrete Ereignisse verbinden, durch mathematische und logische Constraints. Anstatt jeden Verfahrensschritt vorzugeben, legt das Modell die Bedingungen fest, die gelten müssen. Der Simulator ermittelt ein Verhalten, das sie erfüllt.

Bei Modellen mit vielen bedingten Regeln prüft der Simulator wiederholt eine große Menge möglicher Kandidaten. Darin verbleiben auch Bedingungen, die nicht mehr erfüllt werden können. Mit wachsendem Modell verursachen diese unnötigen Prüfungen zusätzlichen Rechenaufwand.

Modell: Kontinuierliche und diskrete Veränderungen verbinden

Ein springender Ball ist ein einfaches Beispiel für ein hybrides System. In der Luft verändern sich Position und Geschwindigkeit kontinuierlich; der Kontakt mit dem Boden löst ein diskretes Aufprallereignis aus. Auch Thermostate, Autos und Roboter verbinden diese beiden Arten von Veränderung, jeweils in anderen Größenordnungen.

Für die Auswertung wurde ein Modell verwendet, in dem sich ein Ball horizontal bewegt und über eine in Segmente unterteilte Fläche springt. Jedes Segment besitzt eine bedingte Regel, die den Ball abprallen lässt, sobald er diesen Bereich erreicht. Zusätzliche Segmente ermöglichen die Darstellung weiterer Objekte, erhöhen aber auch die Zahl der vom Simulator zu prüfenden Bedingungen.

HydLa-Quellcode für einen Ball, der sich horizontal bewegt und auf einer in N benachbarte Segmente unterteilten Fläche springt.
Ein kurzes HydLa-Modell beschreibt einen Ball und eine in N Segmente unterteilte Fläche. Jedem Segment ist ein Guarded Constraint zugeordnet.

Engpass: Mehr Bedingungen verlängern die Laufzeit

Eine Regel, die erst bei erfüllter Bedingung aktiv wird, heißt Guarded Constraint. Im untersuchten Modell wird die Abprallregel eines Segments nur dann aktiv, wenn der Ball den Boden erreicht und seine horizontale Position innerhalb dieses Segments liegt.

Als die Zahl der Segmente von 10 auf 200 stieg, wuchs die Laufzeit des ursprünglichen Simulators ungefähr quadratisch mit dieser Zahl. Größere Modelle können dieses Problem verstärken, weil sie mehr Objekte, Kontaktbereiche und mögliche Ereignisse enthalten.

Untersuchung: Wohin gingen 96 % der Laufzeit?

Eine Laufzeitanalyse des Modells mit 100 Segmenten zeigte, dass FindMinTime 96 % der gesamten Laufzeit beanspruchte. Diese Routine bestimmt das frühestmögliche nächste Ereignis, indem sie wiederholt alle infrage kommenden Guard-Bedingungen auswertet.

Daraus ergab sich ein gezielter Ansatz zur Verbesserung: die an FindMinTime übergebene Kandidatenmenge sicher verkleinern. Es sollten nur Möglichkeiten übersprungen werden, die nicht mehr geprüft werden mussten; die Simulationsergebnisse sollten erhalten bleiben.

Ansatz: Bedingungen entfernen, die nicht erneut erfüllt werden können

Man stelle sich einen Ball vor, der eine Treppe hinunterspringt. Sobald er eine Stufe passiert hat und sich weiter vorwärtsbewegt, kann diese Stufe ihn nicht mehr beeinflussen. Wer die Abbildung betrachtet, lässt die Stufen hinter dem Ball sofort außer Acht; der ursprüngliche Algorithmus prüfte weiterhin jede einzelne.

Eine rote Bahn zeigt einen Ball, der schwarze Treppenstufen hinunterspringt. Die schraffierten Stufen hat er bereits passiert; sie können ihn nicht mehr beeinflussen.
Während sich der Ball nach rechts bewegt, kann die Guard-Bedingung einer schraffierten Stufe hinter ihm übersprungen werden.

Die Schwierigkeit liegt im Nachweis, dass ein entfernter Guard später nicht wieder gebraucht wird. Ihn allein deshalb zu entfernen, weil er gerade nicht erfüllt ist, könnte unbemerkt zu einem falschen Ergebnis führen, falls er später wieder erfüllt wird. Das vorgeschlagene Verfahren nutzt deshalb Monotonie: Lässt sich garantieren, dass eine Variable über ein bestimmtes Intervall hinweg weiter zunimmt oder abnimmt?

Wenn die Änderungsrichtung gleich bleibt

Der erste Ansatz gilt für Variablen, die sich während der gesamten Simulation nur in eine Richtung ändern. Im Modell mit der segmentierten Fläche nimmt die horizontale Position des Balls stets zu. Hat er ein Segment passiert, kann dessen Guard nie wieder erfüllt werden. Mit Model-Checking-Verfahren lässt sich diese Eigenschaft vor der Simulation nachweisen. Dadurch können Guards während der Ausführung sicher entfernt werden, sobald sie irrelevant werden.

Eine rote Linie steigt von α zum Zeitpunkt 0 bis β am Ende der Simulation. Sie stellt eine Variable dar, die über das gesamte simulierte Intervall zunimmt.
Durchgängige Monotonie bedeutet, dass die Änderungsrichtung über das gesamte simulierte Intervall erhalten bleibt.

Wenn sich die Änderungsrichtung umkehrt

Viele Systeme ändern sich nicht unbegrenzt in dieselbe Richtung: Eine Variable kann zunächst zunehmen, ihre Richtung umkehren und anschließend abnehmen. Deshalb wurde in der Arbeit ein zweiter Ansatz vorgeschlagen. Er nimmt eine Änderungsrichtung an und überwacht diese Annahme mit Assertions. Bei einem Richtungswechsel beginnt die Reduktion erneut; dabei werden die im vorherigen monotonen Intervall entfernten Guards wiederhergestellt. Dieser Ansatz wurde im Projekt entworfen, aber weder implementiert noch evaluiert.

Fünf Diagramme zeigen ein zunächst angenommenes steigendes Intervall, eine verletzte Assertion, ein neues fallendes Intervall, eine weitere Verletzung und die schrittweise Bestimmung monotoner Intervalle.
Verletzte Assertions unterteilen den Verlauf in Intervalle, die jeweils als monoton behandelt werden können.

Ergebnis: Ungefähr halbierte Laufzeit im untersuchten Modell

Ich habe den Ansatz für durchgängige Monotonie implementiert und am Modell mit der segmentierten Fläche evaluiert. Bei beiden Algorithmen nahm die Laufzeit mit der Zahl der Segmente zu, doch das vorgeschlagene Verfahren war durchgehend schneller. In den angepassten Kurven sank der Koeffizient der höchsten Potenz von 1.1463 auf 0.6083. Insgesamt wurde die Simulationszeit in diesem Benchmark ungefähr halbiert.

Dieses Ergebnis gilt für den untersuchten Benchmark. Das Verfahren ist dann nützlich, wenn ein Modell viele Objekte mit Guards enthält, die Änderungsrichtung nachgewiesen werden kann und Guards während der Ausführung dauerhaft irrelevant werden. Daraus folgt nicht, dass jedes HydLa-Modell doppelt so schnell ausgeführt wird.

Simulationszeit in Abhängigkeit von N, der Zahl der Flächensegmente. Bei 10 bis 200 Segmenten ist das vorgeschlagene Verfahren durchgehend schneller. Für N = 200 benötigt es etwa 250 Sekunden, gegenüber etwa 470 Sekunden beim ursprünglichen Algorithmus.
In den untersuchten Modellen benötigt das vorgeschlagene Verfahren (Quadrate) ungefähr halb so viel Zeit wie der ursprüngliche Algorithmus (Kreise).

Erkenntnisse

Diese Forschung nutzte bekannte Eigenschaften des Systemverhaltens, um die Menge der vom Simulator zu berücksichtigenden Möglichkeiten zu verkleinern. Den Suchraum einzugrenzen und dabei die Ergebnisse zu erhalten, ist eine Stärke der Constraint-Programmierung.

Implementierung und Auswertung beschränkten sich auf Variablen, die sich fortlaufend in eine Richtung änderten. Die Behandlung von Richtungswechseln blieb im Entwurfsstadium und musste noch evaluiert werden. Auch andere Eigenschaften als Monotonie könnten helfen, unnötige Constraints zu erkennen.

Diese Erfahrung prägt mein heutiges Interesse daran, die Bedingungen und Grenzen zu gestalten, innerhalb derer KI nach Lösungen suchen kann. Bei komplexen Ergebnissen ist es ebenso wichtig festzulegen, was sicher außer Acht gelassen werden darf, wie zu bestimmen, was berechnet werden soll.

Takafumi Horiuchi und Kazunori Ueda. „Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.“ Tagungsband der 33. Jahrestagung der Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02