Abschlussarbeit über Constraint-Programmierung

Übersicht

Ein Simulator untersucht wiederholt viele Bedingungen, je mehr mögliche Ereignisse es gibt. Wenn man nun anhand des Fortschritts beurteilen kann, dass eine Bedingung „nie wieder erfüllt werden wird“, könnte man diese Überprüfung dann sicher einstellen? Eine Methode, die anhand der Richtung der Werteänderung nicht mehr benötigte Bedingungen aus der laufenden Suche ausschließt, wurde für die Modellierungssprache HydLa von hybriden Systemen entworfen und implementiert.

Im Bewertungsmodell wurde die Ausführungszeit auf etwa die Hälfte der bisherigen Zeit verkürzt, ohne die Simulationsergebnisse zu verändern. Wichtig ist nicht, dass alle Berechnungen einheitlich schneller gemacht wurden. Es geht darum, mithilfe der Struktur des Problems die zu berücksichtigenden Möglichkeiten selbst zu reduzieren.

Die in dieser Studie erlernte Denkweise der Constraint-Programmierung bildet die Grundlage für das heutige Meine Designphilosophie. Dabei geht es nicht darum, die Ergebnisse einzeln direkt anzugeben, sondern Regeln, Prioritäten und Grenzen zu definieren und Lösungen von innen heraus abzuleiten, die diese erfüllen.

Problem — Je mehr Möglichkeiten es gibt, desto langsamer wird die Berechnung

HydLa ist eine Sprache, um "hybride Systeme", die kontinuierliche Veränderungen und diskrete Ereignisse kombinieren, als mathematische und logische Einschränkungen zu beschreiben. Ohne die Reihenfolge aller Prozeduren zu schreiben, kann man durch Deklaration dessen, was erfüllt sein sollte, Verhaltensweisen simulieren, die die Bedingungen erfüllen.

Auf der anderen Seite überprüft der Simulator bei Modellen, bei denen viele Regeln je nach Bedingungen wirksam werden, wiederholt eine große Anzahl von Kandidaten. Da Bedingungen, die bereits überschritten wurden und in der Zukunft nicht erfüllt werden, weiterhin als Kandidaten bestehen bleiben, wächst mit der Größe des Modells die unnötige Berechnung.

Thema – Ein System, in dem Kontinuierliches und Diskretes gemischt sind

Ein springender Ball ist ein leicht verständliches Beispiel für ein Hybridsystem. In der Luft ändern sich seine Position und Geschwindigkeit kontinuierlich, und im Moment des Aufpralls auf den Boden tritt ein diskretes Ereignis auf, nämlich das Abprallen. Thermostate, Autos und Roboter besitzen ebenfalls, wenn auch in unterschiedlichem Umfang, diese beiden Arten von Veränderungen.

Für die Bewertung wurde ein Modell verwendet, bei dem eine horizontal bewegende Kugel auf einer in mehrere Bereiche unterteilten Fläche abprallt. Für jeden Bereich der Fläche gibt es eine bedingte Regel: "Wenn die Kugel in diesen Bereich kommt, prallt sie ab." Je mehr Bereiche hinzugefügt werden, desto mehr Objekte können dargestellt werden, aber gleichzeitig steigen auch die Bedingungen, die der Simulator prüfen muss.

Engpass – Die Anzahl der Bedingungen treibt den Rechenaufwand in die Höhe

Regeln, die nur wirksam werden, wenn bestimmte Bedingungen erfüllt sind, nennt man 'mit Wachen versehene Einschränkungen'. Im Evaluierungsmodell gilt die Rückprallregel eines Bereichs nur, wenn der Ball den Boden erreicht und seine horizontale Position innerhalb dieses bestimmten Bereichs liegt.

Wenn die Anzahl der Bereiche von 10 auf 200 erhöht wird, wurde der herkömmliche Simulator etwa proportional zum Quadrat der Anzahl der Bereiche langsamer. Bei groß angelegten Modellen wird dasselbe Problem größer, da die Anzahl der Objekte, Kontaktbereiche und möglichen Ereignisse zunimmt.

Untersuchung — Wo lagen 96 % der Bearbeitungszeit?

Wenn die Verarbeitungszeit gemessen wird, wurde bei einem Modell mit 100 Abschnitten 96 % der Gesamtzeit für FindMinTime verwendet. Dies ist der Prozess, bei dem aus den Kandidaten das „früheste nächste Ereignis“ gesucht wird. Dabei wurden alle Schutzbedingungen wiederholt ausgewertet.

Die Stellen, die verbessert werden müssen, sind klar geworden. Anstatt die gesamte Berechnungsmethode neu zu erstellen, genügt es, die Kandidaten, die an FindMinTime übergeben werden, sicher zu reduzieren. Das Ziel war, nur die Möglichkeiten auszuschließen, die nicht untersucht werden müssen, ohne die Simulationsergebnisse zu verändern.

Ansatz – Bedingungen sicher entfernen, die nie wieder erfüllt werden

Stellen Sie sich einen Ball vor, der die Treppe hinunterhüpft. Wenn der Ball eine Stufe passiert und weiter nach vorne rollt, kann diese Stufe den Ball nicht mehr beeinflussen. Menschen, die das Diagramm betrachten, ignorieren sofort die Stufen hinter dem Ball. Der ursprüngliche Algorithmus überprüfte jedoch jede einzelne weiterhin.

Schwierig ist die Seite, die zeigen muss, dass ein entfernter Schutz später nicht benötigt wird. Wenn man ihn nur deshalb entfernt, weil er jetzt falsch ist, könnte er, wenn er wieder wahr wird, stillschweigend falsche Ergebnisse liefern. Daher nutzt die vorgeschlagene Methode die Monotonie – ob garantiert werden kann, dass eine Variable über einen bestimmten Zeitabschnitt hinweg weiterhin steigt oder fällt.

Wenn sich die Richtung der Veränderung nicht ändert

Die erste Maßnahme gilt, wenn eine Variable während der gesamten Simulation in eine Richtung bewegt wird. In einem Modell mit geteilter Fläche nimmt die horizontale Position des Balls stets zu. Wenn er einen Abschnitt überschreitet, werden die Bedingungen dieses Abschnitts nie wieder erfüllt. Diese Eigenschaft kann vor der Simulation mithilfe von Model-Checking-Techniken überprüft werden, sodass nicht mehr benötigte Schutzvorrichtungen im Verlauf der Ausführung sicher entfernt werden können.

Wenn sich die Richtung der Veränderung unterwegs ändert

Viele reale Systeme bewegen sich nicht ewig in eine Richtung. Variablen können zunehmen, die Richtung ändern und wieder abnehmen. In der Arbeit wurde daher die zweite Vorgehensweise gezeigt. Zuerst wird eine Richtung angenommen, diese Annahme mit Assertions überwacht, und wenn sich die Richtung ändert, wird der Abbauprozess von diesem Zeitpunkt an neu gestartet. Guard-Statements, die für ein monotones Intervall entfernt wurden, werden wieder eingesetzt, wenn das nächste Intervall beginnt.

Ergebnis – die Ausführungszeit des Bewertungsmodells auf etwa die Hälfte reduziert

Wir haben eine Umsetzung zur Bewältigung einheitlicher Monotonie entwickelt und das Modell mit unterteilten Flächen bewertet. Sowohl der ursprüngliche Algorithmus als auch die vorgeschlagene Methode benötigen mehr Zeit, je mehr Segmente es gibt. Allerdings war der Arbeitsaufwand bei der vorgeschlagenen Methode durchgehend geringer. Wenn man die angepassten Kurven vergleicht, sinkt der Koeffizient der höchsten Ordnung von 1,1463 auf 0,6083, wodurch sich in diesem Benchmark die gesamte Simulationszeit etwa halbierte.

Dies ist keine Behauptung, dass jedes HydLa-Modell doppelt so schnell wird. Es zeigt vielmehr, wo diese Methode wirksam ist – nämlich bei Modellen, die viele Guards haben, deren Richtungsänderung nachgewiesen werden kann und bei denen die Guards während der Ausführung dauerhaft irrelevant werden.

Die Perspektive, die aus dieser Forschung gewonnen wurde

Was in dieser Forschung gemacht wurde, war nicht, einzelne Berechnungen ein wenig schneller zu machen. Es ging darum, das, was über das Verhalten des Systems bekannt ist, zu nutzen, um die Menge der zu betrachtenden Möglichkeiten zu verkleinern. Die Idee, den Suchraum zu verkleinern, ohne das Ergebnis zu verändern, ist die Stärke der Constraint-Programmierung.

Was implementiert und bewertet wurde, ist der Fall, dass sich eine Variable in eine Richtung weiterbewegt. Wenn sich die Richtung der Veränderung zwischendurch ändert, bleibt dies bis zum Entwurf beschränkt, und die Bewertung bleibt als zukünftige Aufgabe bestehen. Es besteht auch die Möglichkeit, weitere unnötige Einschränkungen zu finden, indem man Eigenschaften außer der Monotonie nutzt.

Dass ich als gegenwärtiges Ich versuche, nicht direkt die Ausgaben der KI zu gestalten, sondern die Bedingungen und Grenzen zu entwerfen, innerhalb derer die KI erkunden kann, hängt ebenfalls mit dieser Erfahrung zusammen. Wenn man mit komplexen Ergebnissen umgeht, ist es ebenso wichtig zu definieren, was nicht bedacht werden muss, wie zu bestimmen, was berechnet werden soll.