Warum Planner-Programmierung erstaunlich ist

 (hillelwayne.com)
2 Punkte von GN⁺ 2024-02-22 | 1 Kommentare | Auf WhatsApp teilen
  • Das planner-Modul von Picat geht über Logikprogrammierung hinaus, die Wertzuweisungen findet, und beschreibt Probleme als Sequenzen von Zustandsänderungen bis zu einem Zielzustand
  • Definiert man einen Startzustand Start, Übergangsregeln action(From, To, Action, Cost) und eine Abschlussbedingung final(S), findet best_plan(Start, Plan) einen Plan mit minimalen Kosten bis zum Endzustand
  • Im Beispiel der Pfadsuche auf einem Gitter werden Bewegungen, Begrenzungen, das Umgehen von Hindernissen und der Besuch mehrerer Ziele allein durch Änderungen an action und final behandelt; auch die Reihenfolge der Zielbesuche kann fest vorgegeben oder frei gewählt werden
  • Die Planungsfunktion lässt sich mit Constraint Solving kombinieren, sodass sich auch Probleme ausdrücken lassen wie: beim Partition Problem Elemente entfernen, um die größte Teilliste zu finden, die in zwei Gruppen mit gleicher Summe aufgeteilt werden kann
  • Picat ist eine Forschungssprache und hat daher wenig Dokumentation und schwache Fehlermeldungen, kann als werkzeugartige Sprache zum schnellen Lösen bestimmter Rechenprobleme aber knappere Lösungen liefern als allgemeine Programmiersprachen

Grundidee von Picat und Planner-Programmierung

  • Picat ist eine Forschungssprache, die Logikprogrammierung, imperative Programmierung und Constraint Solving verbinden will
  • In gewöhnlicher imperativer und funktionaler Programmierung schreibt man Algorithmen, die aus Eingaben Ausgaben erzeugen; Logikprogrammierung und Constraint Solving suchen dagegen Wertzuweisungen, die Relationen erfüllen
  • In Picat sind nicht-funktionale Bezeichner, die mit einem Kleinbuchstaben beginnen, Atome wie a, b, c; Bezeichner, die mit einem Großbuchstaben beginnen, sind Variablen
  • Auch bei Ausdrücken wie member(Y, Arr), die eine noch nicht definierte Variable Y enthalten, kann Picat Werte finden und zuweisen, die den Ausdruck wahr machen
    • Wenn Arr = [a, b, c, a] ist, kann Y eines von a, b, c sein
    • Fügt man anschließend eine Bedingung wie X != Y hinzu, wird die Menge möglicher Werte weiter eingeschränkt
    • Selbst wenn die Liste selbst noch unbekannt ist, etwa bei member(a, Z), kann Picat Z als Liste instanziieren

Planung sucht Zustandsänderungen statt Wertzuweisungen

  • Planung (planning) sucht nicht Werte für Variablen, die eine Gleichung erfüllen, sondern eine Sequenz von Variablenänderungen, die einen bestimmten Endzustand erreicht
  • Ein Planungsproblem in Picat benötigt drei Elemente
    • einen Startzustand Start
    • action-Funktionen, die Zustandsübergänge beschreiben
    • final(S), um zu entscheiden, ob ein Zustand ein Endzustand ist
  • Picats action-Funktionen müssen alle den Namen action haben und vier Parameter akzeptieren
    • aktueller Zustand
    • nächster Zustand
    • Aktionsname
    • Kosten
  • best_plan(Start, Plan) weist Plan einen Plan mit den wenigsten Schritten oder den niedrigsten Kosten bis zum Endzustand zu
    • Setzt man alle Kosten auf 1, entsprechen die Kosten des Plans der Gesamtzahl der Bewegungsschritte
    • Wenn irgendein Plan genügt, unabhängig von seiner Länge, kann man plan(Start, Plan) verwenden

Beispiel: Pfadsuche auf einem Gitter

  • Das Beispielproblem besteht darin, dass ein Marker auf einem Gitter vom Ursprung (0, 0) startet und eine Zielkoordinate erreicht
    • In jedem Schritt kann er sich um ein Feld nach oben, unten, links oder rechts bewegen
    • Er darf das Gitter nicht verlassen
    • Sobald er die Zielkoordinate erreicht, ist das Ziel erfüllt
  • Der Startzustand enthält aktuelle Position und Ziel gemeinsam, etwa {Origin, Goal}
    • Picats {a, b} ist Array-Syntax und wird praktisch wie ein Tupel verwendet
  • Mit Pattern Matching lässt sich die Endbedingung etwa als final({Pos, Goal}) => Pos = Goal. ausdrücken
    • Ohne Pattern Matching müsste man den Zustand zuerst in {Pos, Goal} zerlegen
    • Gibt es mehrere final-Bedingungen, ist die Planung erfolgreich, sobald eine davon wahr ist
  • Eine Bewegungsaktion wählt eine der vier Richtungen {-1,0}, {1,0}, {0,-1}, {0,1} und prüft, ob die neue Koordinate im Bereich 0..10 liegt
    • member({Dx, Dy}, Dir) wird verwendet, um mögliche Richtungswerte zu finden
    • member(Tx, 0..10) und member(Ty, 0..10) werden genutzt, um zu prüfen, ob die Koordinaten innerhalb der Grenzen liegen
    • Für reine Prüf-Prädikate, die keine Werte zuweisen, gibt es auch membchk
  • Der Ergebnisplan wird als Liste aus Bewegungsaktionen und neuen Koordinaten ausgegeben, etwa {move,{1,0}}, {move,{2,0}}
    • Der Pfad lässt sich mit einem Raku-Skript visualisieren
    • Fügt man eine Bedingung wie {Tx, Ty} != {2, 1} hinzu, ist auch Hindernisvermeidung möglich

Mehrere Ziele und Kostenminimierung

  • Um mehrere Ziele zu besuchen, wird Goal von einer einzelnen Koordinate in eine Zielwarteschlange wie [{2, 2}, {3, 4}] geändert
  • Wenn ein Ziel erreicht wurde, fügt man eine neue action hinzu, die diesen Eintrag aus der Zielliste entfernt
    • [Head|Tail] teilt eine Liste in erstes Element und Rest auf
    • Goal = [Pos|Rest] ist nur dann wahr, wenn die aktuelle Position Pos dem ersten Eintrag der Zielliste entspricht
    • Setzt man den neuen Zustand auf {Pos, Rest}, wird das erreichte Ziel entfernt
  • Ob alle Ziele besucht wurden, entscheidet final({Pos, Goal}) => Goal = [].
    • Nicht die Frage, ob die aktuelle Position einem bestimmten Ziel entspricht, ist die Endbedingung, sondern ob die Zielliste leer ist
  • Ziele in einer festen Reihenfolge zu besuchen, ergibt nicht immer den insgesamt kürzesten Pfad
  • Um die Zielreihenfolge zu ignorieren und den Gesamtpfad zu minimieren, ändert man die mark-Aktion
    • Statt Goal = [Pos|Rest] prüft member(Pos, Goal), ob die aktuelle Position irgendwo in der Zielliste enthalten ist
    • Mit To = {Pos, delete(Goal, Pos)} wird das besuchte Ziel aus der Liste entfernt
    • In dieser Variante kann Picat das nächste Ziel auswählen und die Gesamtlänge des Pfads minimieren

Kombination von Planung und Constraint Solving

  • Picats Planungsfunktion ist in andere Picat-Funktionen integriert, und Planung lässt sich gemeinsam mit Constraint Solving verwenden
  • Das als Beispiel behandelte Partition Problem ist ein NP-vollständiges Problem, bei dem eine Zahlenliste in zwei Gruppen mit gleicher Summe aufgeteilt wird
  • Dieses Programm entfernt Elemente aus einer Zahlenliste und findet so die größte Teilliste, die sich in zwei Gruppen mit gleicher Summe aufteilen lässt
    • Das Entfernen von Elementen aus der Eingabeliste wird als Planungsaktion modelliert
    • final(Numbers) prüft, ob es für diese Zahlenliste eine gültige Partition-Lösung gibt
    • Mit Constraints aus dem cp-Modul wird für jedes Element über eine 0..1-Variable dargestellt, ob es in die linke oder rechte Gruppe kommt
    • Die Constraints erzwingen, dass die Gesamtsumme das Doppelte der Summe einer der beiden Gruppen ist
  • In der Beispielausgabe kann nach dem Entfernen von [5,17] die verbleibende Liste in zwei Gruppen aufgeteilt werden, die jeweils die Summe 1108 ergeben
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Dieser Ansatz löst nicht nur direkt gültige Constraints, sondern beschreibt auch die Änderungen, die nötig sind, um einen gültigen Constraint-Zustand zu erreichen, als Plan

Grenzen und geeignete Einsatzbereiche von Picat

  • Picat ist eine Forschungssprache und wird nicht für den Produktionseinsatz empfohlen
  • Es gibt nicht viele Komfortfunktionen, und auch gute Dokumentation oder klare Fehlermeldungen fehlen
    • Wenn es keinen lösbaren Plan gibt, erscheint ein Fehler wie *** error(failed,main/0)
  • Dass Picat unter Windows lauffähig ist, wird im Vergleich zu vielen Forschungssprachen positiv bewertet
  • Picat ist weniger eine Sprache, in der man wartbaren oder gemeinsam genutzten Code schreibt, sondern eher eine Toolkit-Sprache zum Lösen bestimmter Arten von Rechenproblemen
  • Einige Probleme, die mit allgemeinen Programmiersprachen und Constraint Solvern schwer zu behandeln waren, lassen sich mit Picat ziemlich elegant lösen

Andere Planungssprachen und verwandte Konzepte

  • Planung wurde ursprünglich in Robotik und KI entwickelt, wird heute aber in der KI von Videospielen häufig unter dem Namen Goal Oriented Action Planning (GOAP) verwendet
  • PDDL ist eine Planungsbeschreibungssprache, die eigenständige Planner als Eingabe verwenden
    • Sie erfüllt eine ähnliche Rolle wie DIMACS als Beschreibungsformat für SAT

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-02-22
Hacker-News-Kommentare

  • Habe den Planungsmodus von Picat in der Praxis verwendet
    Ich habe einen Prototyp für ein System gebaut, das die Wartung mehrerer Gerätegruppen koordiniert. Dabei gibt man nicht ein, „wie“ etwas gemacht werden soll, sondern „was“ man will, „welche Aktionen möglich sind“ und „welche Constraints einzuhalten sind“
    In kleinen Beispielen erzeugte es gute optimale Pläne, aber als es auf reale Größenordnungen anwuchs, brach es erwartungsgemäß zusammen. Planungsprobleme liegen letztlich in EXPTIME, die Grenzen waren also erheblich
    Picat bietet mit der Definition von Heuristiken einen Ausweg; ich ließ Random Forests über Zustandsprädikaten und Naive-Bayes-Klassifikatoren vielversprechende Pfade vorhersagen. Aber selbst mit Symmetry-Breaking-Constraints und hierarchischer Planung war es viel zu viel Handarbeit
    In klassischen GOFAI-Problemfeldern scheint der KI-Winter noch nicht vorbei zu sein
    Vielleicht gilt das nicht, wenn man Planungsprobleme so umformuliert, dass sie einen „polynomialzeitlichen Generator zurückgeben, der potenziell exponentiell lange Pläne erzeugt“

    • Kommerzielle Solver sind Open-Source-Lösungen in Sachen Performance weit überlegen und leeren auch den Geldbeutel deutlich schneller
      CPLEX, Xpress, GUROBI und Hexaly fallen mir ein; Hexaly ist besonders gut für Scheduling- oder Vehicle-Routing-Probleme
      Normalerweise greift man über APIs für in der Branche verbreitete Sprachen darauf zu. Das ergibt aus meiner Sicht viel mehr Sinn als spezialisierte Solver-Sprachen, die für allgemeine Aufgaben schwach sind
      GUROBI aus Python aufzurufen ist sehr einfach, und man kann die normalen Python-Funktionen unverändert nutzen
      Mosek ist deutlich günstiger als GUROBI, aber beide APIs sind sehr Low-Level, und die Performance reicht nicht an GUROBI heran
    • In diesem Fall hätte etwas wie CP-SAT(https://developers.google.com/optimization/cp) möglicherweise gut skaliert
      Dieser Solver verarbeitet absurd viele Variablen und Constraints problemlos, und die eingebauten Heuristiken sind hervorragend
    • Frühere Planner reduzierten den Suchraum mit Metaregeln oder Heuristiken, die festlegten, welche Regeln anzuwenden sind
      Manche Systeme teilten das Problem in unterschiedliche Repräsentationen auf und koppelten spezialisierte automatische Solver daran
      Jahob Analysis System und Cyc fallen mir ein
      Aus praktischer Sicht war das Procedural Reasoning System das sauberste Design der klassischen KI; ich würde gern eine neu aufgelegte Version sehen, deren Schwächen mit modernen Methoden ausgeglichen werden
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Ich frage mich, warum es keine hochwertigen Open-Source-Solver gibt
      In anderen Bereichen des numerischen Rechnens ist der Stand der Technik oft Open Source; ich habe mich immer gefragt, warum es gerade bei Optimierung anders ist
    • Was Ergebnisse oder Performance angeht, frage ich mich, ob das nicht im Grunde einer grob zusammengeschriebenen Tiefensuche ähnelt, die vage an Prolog erinnert

  • Es gibt eine Website von hakank, einem in der Constraint-Programming-Community aktiven HN-Nutzer, also Hakan Kjellerstrand, auf der viele Picat-Materialien und Beispiele gesammelt sind: http://www.hakank.org/picat/

  • Wie üblich möchte ich Prolog empfehlen
    Es ist elegant, leicht zu verstehen und ausgereifter; wenn man Constraint Solving über endlichen Bereichen will, reicht die Grundausstattung schon aus
    Außerdem ist MiniZinc ein hervorragendes Interface zu vielen auf unterschiedliche Zwecke spezialisierten Solvern, sodass man als Nicht-Experte wahrscheinlich näher an das gewünschte Ergebnis kommt
    Prolog hat viele Vorteile, aber das nötige „mechanische Gefühl“ für gute Performance kann schnell ziemlich anspruchsvoll werden
    Wenn man etwas in Picat geschrieben hat, lohnt es sich, darüber nachzudenken, wie man dasselbe in anderen Sprachen schreiben würde
    Solche Spielzeugprobleme sind auch in anderen Sprachen einfach, und in den meisten funktionalen Sprachen braucht Dijkstra oder A* nur ein paar Zeilen; am Ende geht es oft nur darum, den Zustandsraum des Suchalgorithmus zu definieren

  • Ich habe mich gefreut, Predrag als Reviewer zu sehen, war aber zugleich überhaupt nicht überrascht
    Das Firebase technical screen wäre mit so einem Tool wohl viel einfacher gewesen; letztlich war es ebenfalls ein weiteres Optimierungsproblem
    Ich bekomme Lust, es noch einmal mit Picat zu lösen
    Er macht auch interessante Arbeit im Bereich Programmiersprachen: https://github.com/obi1kenobi/trustfall

  • Mein erster Gedanke war: „Das ist wie ein Typsystem, das man selbst lösen muss“
    Ich habe versucht, es naiv in TypeScript auszudrücken, aber a, b, c konnten alle gleich sein, also löste das gar nichts
    Beim Versuch, es korrekt auszudrücken, kam ich bis zu einer Form, die einigermaßen brauchbar wirkte, musste aber immer noch Assertions verwenden und konnte auch den Typ von Y nicht richtig ausdrücken
    Dieser Prozess zeigt eher, wie mächtig Programme im Planner-Stil in puncto Einfachheit und Kürze sind
    TypeScript scheint nicht mächtig genug zu sein, um diese Art von Constraints auszudrücken
    Link zum experimentellen TS Playground: http://tinyurl.com/3p2pzdtn

  • Schön, GOAP wieder erwähnt zu sehen
    Es war die geheime Zutat, die die Gegner in F.E.A.R. so interessant machte, und Jeff Orkins Paper zur Funktionsweise ist gut lesbar und unterhaltsam

  • Ich nutze Prolog und etwas CLPFD tatsächlich beruflich, und es ist wirklich großartig
    Ich wünschte, es wäre überall; genauer gesagt hätte ich gern einen logischen Kern, der Reinheit betont, während imperative Abläufe an den Rand gedrängt werden
    Es ist schade, dass die Branche offenbar in so schlechten Tools feststeckt

  • Sieht Prolog ähnlich und interessant aus

  • Diese Art zu programmieren ist an sich nicht völlig neu
    An der Uni habe ich Prolog gelernt, und es sieht ziemlich ähnlich aus, allerdings hatte Prolog keine Planner-Funktionalität
    Ein Planner ist jedoch eine sehr elegante und einfache Art, Probleme zu lösen
    Der Videospiel-Teil am Ende des Artikels macht mich neugierig
    Die Planner-Funktionalität erlaubt es, Probleme mit wenigen Zeilen klaren Codes sehr einfach zu lösen, aber wie sieht die Performance im Vergleich zu imperativ geschriebenen Algorithmen aus?
    Picat scheint im Vergleich zu ähnlichen Sprachen recht effizient zu sein [1], aber einen Vergleich mit „Standard“-Sprachen habe ich nicht gefunden
    [1]: https://arxiv.org/abs/1405.2538

  • Ich habe auch den Traum, dem Computer nur den Zustand mitzuteilen, den er erreichen soll
    Mit der Planning-Community oder Solvern kenne ich mich nicht gut aus und habe nur naiv mit ortools herumgespielt, aber ich habe einmal Codegenerierung mit A* umgesetzt, um von einem Zustand zu einem Zielzustand zu gelangen
    Dabei wurden Assembly-Instruktionen erzeugt, um zwischen Zuständen zu wechseln, und sogar versteckte Zustandsübergänge von Funktionsaufrufen gefunden, um das Ziel zu erreichen
    Um die Suche zu beschleunigen, habe ich sie mit Python multiprocessing parallel ausgeführt; da jeder Thread andere Nachbarn erzeugte, nutzte ich dynamische Nachbarschaftserzeugung
    In meinem ursprünglichen Versuch war A* schwer zu parallelisieren, daher war Sharding nötig
    Der Traum hinter meinem Experiment ist, dem Computer mitzuteilen, „was ich jetzt habe“ und „was ich will“, damit er selbst den richtigen Weg dorthin findet
    Persönlich sehe ich Programmieren eher als Logistik, wie Factorio oder eine Fabrik
    Deshalb nenne ich es „sliding puzzle“, weil es ein Puzzle ist, bei dem man Dinge hin und her schieben muss, um das richtige Bild zu sehen
    GitHub-Repository und Notizen: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3