Selber planen lassen ...

... mit Buridan

Buridan ist in Allegro Common LISP geschrieben und muß innerhalb des Allegro Composers laufen.

Vorbereitung

Zunächst einmal in das Buridan Verzeichnis wechseln und die Lisp-Umgebung aufrufen - dazu die folgenden Befehle eingeben:

> cd /usr/local/buridan
> setup acl
> composer

Anschließend innerhalb der Lisp Umgebung noch zwei Files laden:

> USER(1): (load "load-buridan.lisp")

und

> USER(2): (load-buridan)

Planen

Um zu Planen, muß man ein File laden, das die entsprechenden Domänen enthät. Dies ist z.B. das File `examples.lisp' (im Buridan-Verzeichnis /usr/local/buridan):

USER(3): (load "examples.lisp")

Dieses File enthät u.a. eine Domäne für das "Slippery Gripper" Problem. Eine Lösung wird generiert durch

USER(4): (test1)

Um eine eigene Domäne zu schreiben, sieht man sich das File "example.lisp" am besten etwas genauer an. Die Syntax ist nicht sehr schwer und wird anhand der Beispiele ausreichend klar. Eigene Domänen-Files können ohne weiteres aus dem eigenen Home-Verzeichnis geladen werden.

... mit GOLOG

GOLOG (alGOl in LOGic) ist eine logische Programmiersprache mit einer Situationskalkülsemantik und läuft unter Prolog bzw. Eclipse.

>> setup eclipse
>> eclipse

Compilierung

Vor der Complilierung eines GOLOG Programms muß stets der GOLOG Interpreter (golog.pl) compliert werden. Dies geschieht am einfachsten dadurch, daß man ``:- golog.'' (ohne Anführungszeichen) als erste Zeile in das GOLOG Programm einfügt und dieses (z.B. elevator.pl) dann mit

>> [eclipse 1]: compile(elevator).

compiliert (dafür muß natürlich golog.pl im richtigen Verzeichnis liegen).

Man kann ein GOLOG Programm auch dadurch compilieren, daß man Eclipse den Programm-Namen als Kommandozeilen-Parameter übergibt:

>> eclipse -b elevator.pl

In jedem Fall sollte das System mit ``yes'' antworten - ist dies nicht der Fall, so müssen die aufgetretenen Fehler erst beseitigt werden - viel Spaß.

Ausführung

In einem GOLOG Programm gibt es oft mehrere Prozeduren - im Elevator Beispiel (elevator.pl) sind dies z.B. ``control'' oder auch ``serve_a_floor''. Um eine Prozedur auszuführen, gibt man ein:

>> [eclipse 2]: do(procname,s0,S).

Man übergibt also dem Prädikat ``do'' drei Parameter: den Namen der auszuführende Prozedur, den Anfangszustand (``s0'') und eine Zustandsvariable (``S''), für die eine Bindung erzeugt werden soll. So erhält man für das elevator Beispiel durch den Aufruf

>> [eclipse 2]: do(control,s0,S).

folgende Bindung:

S = do(open, do(down(0), do(close, do(open, do(turnoff(5), do(up(5), do(close, do(open, do(turnoff(3), do(down(3), s0))))))))))

Von innen nach außen gelesen ergibt das den folgenden Plan:

down(3)
turnoff(3)
open
close
up(5)
turnoff(5)
open
close
down(0)
open

Um zu verstehen, wie ein GOLOG Programm aufgebaut ist, schaut man sich am besten unter /usr/local/golog das File elevator.pl genau an - es enthält die wichtigsten syntaktischen Strukturen wie z.B. While-Schleifen, Test-Aktionen und nichtdeterministische Auswahl und ist ausreichend kommentiert.

... mit UMCP

UMCP ist ein in Allegro Common LISP geschriebener HTN-Planer.

>> setup acl
>> setup umcp
>> cd /usr/local/umcp
>> composer

Nach einer Weile sieht man den LISP Prompt USER(1): Nun innerhalb von Lisp die folgenden Kommandos eintippen:

>> (load "load-umcp.lisp")
>> (load-umcp)
>> (in-package :umcp)

Um nun z.B. das File sample.lisp zu laden, gibt man ein:

>> (load "sample.lisp")

Dadurch wird u.a. das Planungsproblem definiert - im Beispiel sample.lisp geschieht dies durch die Funktion sussman-anomaly. Um das Problem zu lösen, gibt man nun ein:

>> (sussman-anomaly)
>> (search-for-plan goal :strategy :bestfs)

Dadurch wird der folgende Plan zur Lösung der Sussman-Anomaly berechnet: Weitere Informationen, insbesondere zum Schreiben eigener Planungsaufgaben, findet man auf der Manual Page von UMCP. Diese werden dann vom eigenen Verzeichnis z.B. mit (load "/home/hatzack/umcp/my-domain.lisp") geladen. Sample.lisp enthält noch weitere Blocksweltbeispiele, die man zum Beispiel auch mit verschiedenen Strategien lösen kann (siehe manual page).

... mit SATPLAN

SATPLAN kodiert Planungsprobleme als aussagenlogische Formeln und löst diese dann mit Hilfe von verschiedenen SAT-Prozeduren (z.B. Tableau oder Walksat).

>> setup satplan

Ähnlich wie bei IPP gibt es auch hier Operator- und Faktenfiles. Am besten kopiert man sich ein paar Beispiele aus /usr/local/satplan/examples/ in das eigene Verzeichnis, z.B. bw_orig.ops und reversal.facts und ruft SATPLAN anschliessend wie folgt auf:

>> satplan -o bw_orig.ops -f reversal.facts

Dadurch wird eine SAT-Kodierung des Planungsproblems generiert (reversal.cnf). Um nun dieses SAT Problem zu lösen, gibt man

>> solve reversal.cnf

ein. Dadurch wird man zunaechst nach dem Namen des Files gefragt, in dem die Lösung gespeichert werden soll - mit Return bestätigt man den default Namen (reversal.out). Anschliessend kann man zwischen drei SAT Solvern wählen:

> solver (t=tableau, w=walksat, n=ntab, default t):

Nachdem man einen ausgewählt hat, wird das Lösungsfile (reversal.out) erzeugt, das anschliessend mit

>> interpret reversal

interpretieren muss. Das Ergebnis steht dann im File reversal.interp.

... mit Graphplan

>> setup graphplan

Graphplan ist in C geschrieben und man startet es direkt vom Betriebssystem. Am besten geht man in

>> cd /usr/local/graphplan/domains

Wichtig: Graphplan hat für jede Operatormenge und jedes Problem eine separate Datei.

Nun kann man das System mit

>> .. /graphplan.sparc

starten. Es folgt ein Dialog, um Beispiele einzugeben oder man kann auch gleich sagen:

>> .. /graphplan.sparc -o blocks_ops -f blocks_facts4

Dabei ist es wichtig, immer den vollständigen Dateinamen anzugeben. Auch hier folgt ein Dialog, den man mir immer mit CR beantworten kann.

Bei "X animation? ( for no): yes" gibt es anschliessend eine beeindruckende animierte Darstellung des Suchprozesses auf dem Graphen.

Eine Beschreibung des Systems mit weiteren Hinweisen findet sich auf der Originalhomepage .

Eigene Beispiele schreiben: Extra Datei für Operatoren und Problem anlegen. Es gibt 3 Syntaxvarianten, die man am besten auf der Originalhomepage studiert. Es ist egal, welche Variante man nimmt, aber man muss sie konsequent durchhalten. Syntax heisst hier (leider) auch, dass die Operatoren mit unterschiedlicher Semantik verarbeitet werden! Nährere Erklärungen finden sich wieder auf der Graphplan homepage. Es gibt in diesem System keine atomare Negation und keine CWA, das heisst, der Ausgangszustand muss vollständig beschrieben werden (auch das was nicht gilt, angeben) und negative Fakten umschreibt man durch neue Prädikatsnamen. Anstelle von "not open" schreibt man "closed" oder aber zum Beispiel not-open.

... mit UCPOP

UCPOP ist in Allegro Common LISP geschrieben und muss innerhalb des Allegro Composers laufen.

>> setup acl
>> setup ucpop
>> cd /usr/local/ucpop
>> composer

Man sieht den LISP Prompt USER(1): Nun innerhalb von Lisp das Hauptfile laden:

>> (load "loader.lisp")

Hier sollte man sehen

USER(1): (load "loader.lisp")
; Loading loader.lisp.
T
USER(2):

Nun das ganze system laden
>> (load-ucpop)
und in den Bereich des LISP systems gehen, wo der Planer ist
>> (in-package "UCPOP")
Jetzt schaltet man am besten die Suchstrategie ZLIFO an
(turn-zlifo-on)
und gibt dem Planer einen ordentlichen Suchraum (Anzahl der partiellen Pläne)
(setq *search-limit* 100000)

Nun kann es losgehen:
(bf-control 'fixit)

Dieses Beispiel rechnet das TYREworld problem von Stuart Russel. Es dauert ca. 70 s auf einer SPARC 4. bf-control steht für Breite-Zuerst suche. Wichtig: Nicht das QUOTE vergessen! Man kriegt den folgenden POP plan. Die Namen von vorhandenen Planungsproblemen findet man in der Datei /usr/local/ucpop/domains/domains.lisp, sowie in anderen Dateien im domains-Verzeichnis. In allen LISP-Funktionen, die mit (define (problem "name"): domain ... anfangen, wird ein Planungsproblem definiert, d.h. (bf-control 'name) rechnet das Problem.

Hat man sich vertippt, kriegt einen LISP Fehler und ist kein LISP Experte, dann am besten CONTROL-D eintippen. Im schlimmsten Fall solange bis man wieder im UNIX ist.

Eigene Beispiele schreiben: Hier hilft nur ein gründliches Studium und vorsichtiges Editieren des domains.lisp files und natürlich das Zählen von Klammern. Wichtig: Jedes File beginnt mit

(in-package "UCPOP")

dann kommt der Name der Domain und die Operator-Definition

(define (domain blocks-world-domain)
(:operator puton
....
))

jetzt kommen die einzelnen Planungsprobleme:

(define (problem test)
  :domain 'blocks-world-domain
  :inits ((block A) (block B) (block C) (block Table)
	  (on C B) (on B A) (on B Table) (on A Table)
	  (clear Table))
  :goal (and (on B A) (on A Table) (on C B)))

Vom eigenen Homedirectory läd man seine Beispieldatei z.B. mit (load "/home/koehler/my-domain.lisp"). Das UCPOP Handbuch steht unter /usr/local/ucpop/doc/manual.ps.

UCPOP verwendet CWA, man gibt also nur positive Fakten im Ausgangszustand an. Beginnt LISP mit Garbage Collection, kann man das Problem mit CONTROL-D, CONTROL-C abbrechen, weil der Speicher voll ist und wohl kaum noch ein Plan gefunden wird. Nach dem Ende einer LISP Sitzung bitte prüfen ob der composer keinen zombie erzeugt hat und alle noch rumhängenden Prozesse abschiessen.

... mit Prodigy

Prodigy auch in LISP implementiert, aber ist im Unterschied zu UCPOP ein total-order Planer, der auf iterativer Tiefensuche basiert.

>> setup acl
>> setup prodigy
>> cd /usr/local/prodigy
>> composer

Das Verzeichnis /usr/local/prodigy enthält auch das Handbuch manual.ps

Nun kann wieder innerhalb von LISP gearbeitet werden:

>> (load "loader.lisp") läd diesmal das ganze System

Nun kann man eine Domäne laden

>> (domain 'blocksworld)

Prodigy organisiert Domänen in Unterverzeichnissen von /usr/local/prodigy/domains. Jedes Verzeichnis ist eine Domäne und enthält das Verzeichnis "probs", in dem die Dateien stehen, die die einzelnen Planungsaufgaben enthalten. Zum Beispiel ist das Problem "suss" in /usr/local/prodigy/domains/blocksworld/probs/suss.lisp. Prodigy verwaltet die Pfade bei den vordefinierten Problemen selbständig. Nach dem Laden der Domäne läd man ein einzelnes Problem

>> (problem 'suss)

Ein bisschen umständlich, aber .... nun tippt man nur noch

>> (run)

und bekommt einen total geordneten plan. Bei grösseren Problemen muss man vorher die Tiefe des Suchraums erweitern mit

>> (setq *depth-bound* 50) oder einer anderen Zahl < 100 (mehr macht keinen Sinn)

Eigene Beispiele schreiben: Es empfiehlt sich, die Struktur /domains/<domain>/probs/<file> beizubehalten. Die Operatoren stehen in /domains/<domain>/<ops>.lisp und das einzelne Planungsproblem in <file>.lisp. Hinweise finden sich im Handbuch und in den Beispielen. Beim Laden der Files muss dann der gesamte Filename angegeben werden, z. B. (domain '/home/koehler/meine-domain).

... mit IPP

Unser eigener Planer IPP ist in C geschrieben und relativ einfach zu benutzen. Sämtliche Hinweise stehen auf der System homepage. Starten wieder mit

>> setup ipp
>> ipp -o "ops" -f "facts"

Operator-Dateien heissen .ops, Problemdateien heissen .fct. Die Extension wird beim Aufruf weggelassen! Alle Beispiele stehen unter /usr/local/ipp/domains und sind dort in Unterverzeichnissen angeordnet. Man kann sie auch von der Homepage als tar-file laden. Zu IPP gibt es auch ein schönes interaktives Interface XGV, mit dem man sich Planungsgraphen näher ansehen kann. Um sich einen Graphen anzusehen, ruft man IPP mit option -W auf. Dann werden im aktuellen Verzeichnis zwei Dateien graph.facts und graph.opers angelegt. Man startet nach dem Planer nun xgv und ruft ueber das Menü File die Funktion Open... aus und klickt in der Auswahl eine der beiden Dateien an. Dann wird der Graph geladen und angezeigt. Im Menü Options kann man sich den generierten Plan anzeigen lassen und im Menü Search nach bestimmten Fakt- und Aktionsknoten suchen.