Planner-Programmierung: Eine Überraschung

 (hillelwayne.com)
2 Punkte von GN⁺ 2024-02-22 | 1 Kommentare | Auf WhatsApp teilen

Die magischen Fähigkeiten der Programmiersprache Picat

  • Picat ist eine Forschungsprache, die versucht, logische Programmierung, imperative Programmierung und Constraint-Solving zu kombinieren.
  • Das planner-Modul von Picat ist eines der interessantesten Programmiermodelle.

Eine kurze Erklärung zur logischen Programmierung

  • In der imperativen und funktionalen Programmierung schreibt man Algorithmen, die aus einer Eingabe eine Ausgabe erzeugen.
  • In der logischen Programmierung und beim Constraint-Solving gibt man stattdessen eine Reihe von Gleichungen vor und findet eine Zuweisung, die diese Beziehungen erfüllt.

Problemdefinition

  • Es geht darum, einen Marker auf einem Gitter zu platzieren und ihn vom Startpunkt (Ursprung) zur Zielkoordinate zu bewegen.
  • In jedem Schritt kann man sich um ein Feld in eine der vier Richtungen bewegen, ohne dabei die Grenzen des Gitters zu verlassen.
  • Das Programm ist erfolgreich, wenn der Marker auf der Zielkoordinate steht.

Erste Implementierung

  • Man muss den Startzustand Start, eine Folge von action-Funktionen, die Zustandsübergänge darstellen, und die final(S)-Funktion bereitstellen, die den Endzustand bestimmt.
  • Durch Aufruf von best_plan(Start, Plan) wird Plan die kürzeste Folge von Schritten zugewiesen, die benötigt werden, um den Endzustand zu erreichen.

Mehrere Ziele hinzufügen

  • Der Planner muss alle Ziele nacheinander erreichen.
  • Man ergänzt eine neue action, die ein erreichtes Ziel aus der Warteschlange entfernt.

Kostenminimierung

  • Ziele in gegebener Reihenfolge zu erreichen bedeutet nicht immer den kürzesten Gesamtdurchmesser.
  • Wenn man unabhängig von der Reihenfolge der Ziele den kürzesten Pfad finden möchte, kann man action so ändern, dass der Planner das nächste Ziel auswählt und dadurch die Gesamtlänge des Pfades minimiert.

Weitere Varianten

  • Picat unterstützt viele Varianten für die Planung.
  • best_plan(S, Limit, Plan) begrenzt die maximalen Kosten auf Limit.
  • sequence(P, Action) beschränkt die möglichen Aktionen entsprechend dem aktuellen Teilplan.

Einsatz von Picat

  • Picat ist eine Forschungsprache, und es fehlen Komfortfunktionen wie gute Dokumentation oder klare Fehlermeldungen.
  • Picat ist als eine 66Werkzeug2 Sprach (Werkzeug)-Sprache nützlicher, wenn es darum geht, bestimmte Rechenprobleme zu lösen.

Anhang: Weitere Planungs 3rachen

  • "Planung" wurde für Robotik und KI entwickelt, wird aber hauptsächlich in der KI von Videospielen als "Goal-Oriented Action Planning" (GOAP) verwendet.
  • PDDL ist eine Planungsbeschreibungssprache, die ein eigenständiger Planner als Eingabe nutzt.

Meinung von GN⁺

  • Innovation im Programmiermodell: Das planner-Modul von Picat eröffnet eine neue Dimension in der Programmierung. Es ist besonders leistungsstark, wenn es darum geht, schwierige Probleme wie die Suche nach einem Pfad zu lösen.
  • Pädagogischer Wert: Picat hat pädagogischen Wert im Kontext von Programmiersprachen, da es beim Erlernen der Konzepte der logischen Programmierung und Constraint-Solving helfen kann.
  • Spezifische Problemlösung: Picat ist wertvoll als Werkzeug zur Lösung bestimmter Rechenprobleme. Es bietet einen neuen Ansatz für Probleme, die sich mit herkömmlichen Programmiersprachen schwer lösen lassen.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-02-22
Hacker News-Kommentare

  • Praxisbeispiele für den Einsatz des Planungsmodus von Picat

    • Entwicklung eines Systemprototyps für die Gerätewartung
    • Dem System sagen, was zu tun ist, nicht wie es zu tun ist
    • Mit Picat wurde ein optimaler Plan erstellt, bei Skalierung auf große Größenordnungen traten jedoch Probleme auf
    • Da Planung EXPTIME ist, gibt es erwartungsgemäß Grenzen in der Skalierbarkeit
    • Trotz Einsatz von Heuristiken, Naive-Bayes-Klassifikator und Symmetrieeinschränkungen ist weiterhin viel Verwaltung nötig
    • Im klassischen GOFAI-Problemraum gilt weiterhin ein KI-Winter

  • Informationen zu Picat-Ressourcen und -Beispielen

    • Auf der Website von Hakan Kjellerstrand, einem aktiven Mitglied der Constraint-Programming-Community, werden Picat-Materialien und -Beispiele bereitgestellt

  • Empfehlung von Prolog und MiniZinc

    • Prolog ist eine reife Sprache mit leicht verständlichem Ansatz zur Constraint-Lösung
    • MiniZinc ist eine Schnittstelle, um auf verschiedene spezialisierte Solver zuzugreifen
    • Für bessere Performance in Prolog ist ein beachtliches Verständnis erforderlich
    • Es wird empfohlen zu prüfen, ob sich ein in Picat geschriebener Code leicht in andere Sprachen übertragen lässt

  • Kommentar zu Firebase-Technikinterviews

    • Ein Firebase-Interview wäre vermutlich leichter, wenn man Werkzeuge wie Picat einsetzen könnte
    • Freude darüber, dass Predrag als Gutachter auftritt

  • Vergleich von Typsystemen und Programmiersprachen

    • Ähnlich wie das Typsystem in TypeScript, nur dass man die Lösungen selbst ausarbeiten muss
    • TypeScript ist nicht stark genug, um Nebenbedingungen vollständig auszudrücken
    • Die Kompaktheit und Einfachheit des planerorientierten Programmierstils wird betont

  • Erwähnung von GOAP (Goal-Oriented Action Planning)

    • GOAP, das in der KI der Gegner im Spiel F.E.A.R. eingesetzt wurde und dort für mehr Spaß sorgt
    • Der Artikel über GOAP von Jeff Orkin wurde als leicht lesbar und unterhaltsam bewertet

  • Bewertung der Planungsfunktion in Picat

    • Picat ist ähnlich wie Prolog, ergänzt um Planungsfunktionen
    • Die Planungsfunktionen können Probleme sehr einfach lösen, aber die Performance sollte gegenüber imperativer Programmierung verglichen werden

  • Die Vision, dem Computer nur den Endzustand vorzugeben und ihn lösen zu lassen

    • Codegenerierung und Zustandswechsel mit dem A*-Algorithmus
    • Wenig Erfahrung mit Planungs-Communitys oder Solvern, dafür Experimente mit OR-Tools
    • Programmierung wird als Logistik betrachtet und mit einem "Sliding Puzzle" verglichen

  • Zusätzlicher Kommentar zur prolog-ähnlichen Syntax

    • Bei einer prolog-ähnlichen Syntax wurde vorgeschlagen, mit true. zu schließen, was als elegantere Lösung als „comma first“ gilt

Diese Zusammenfassung berücksichtigt verschiedene persönliche Meinungen und gibt die jeweiligen Perspektiven neutral wieder. Die technischen Inhalte zu Programmiersprachen werden für Einsteiger im Software Engineering klar und knapp erklärt.