\NeedsTeXFormat{LaTeX2e}
\documentclass[a4paper,10pt,onecolumn]{article}
% landscape confuses psnup und ist ungewohnt
% article, report, book, letter, slides... (bei a., b., r. Inhaltsverz. mgl.)
% Slides verwendet einen sehr seltsamen Font: in \normalsize fehlen einige
% wichtige mathematische Zeichen!?? Ausserdem: Keine Seitennummern?
% Mögliche Alternative? [12pt]article ist zu klein...

\input colordvi
\usepackage{color} % z.B. \Blue{...} oder \textBlue ...
\usepackage[dvips]{graphicx} % -> \includegraphics{datei}
\usepackage{multicol}

\usepackage{german}
\usepackage[T1]{fontenc} % T1 normal, OML kursiv
\usepackage[latin1]{inputenc}
\selectlanguage{german}

\pagestyle{headings} % nur Seitennummer in der Fusszeile: plain
\pagenumbering{arabic}

\setlength{\parindent}{0pt}          	% erste Zeile im Absatz nicht einrücken

\setlength{\topmargin}{2cm}
\setlength{\oddsidemargin}{1.5cm}
\setlength{\evensidemargin}{1.5cm}

\addtolength{\topmargin}{-1in}       	%
\addtolength{\oddsidemargin}{-1in}   	% Workaround für eine TeX Besonderheit,
\addtolength{\evensidemargin}{-1in}  	% falls KEIN Rand gewünscht wird...

\addtolength{\textwidth}{1in}
\addtolength{\textheight}{1in}

\setlength{\parskip}{1.5ex}		% ex: x Hoehe,  em: m Breite
\setlength{\textwidth}{18cm}		% 21cm - 3cm
\setlength{\textheight}{24.2cm}		% 29.7cm - (4cm, ca. 1.5cm Ueberschrift)

\hyphenation{grössere MAX-PLAN}
% \renewcommand{\contentsname}{{\normalsize Inhalt}} - bei Inhaltsverz...
% mit \clearpage von Hand Seitenwechsel anfordern

\author{Eric Auer}
\title{MAXPLAN \\
 \bigskip \bigskip
 Ein neuer Ansatz für probabilistisches Planen \\
 (Stephen M. Majercik \& Michael L. Littman 1998) \\
 {\bf Ausarbeitung}}


\begin{document}
%
%
%
% \raggedbottom
% \raggedright % Keine Wörter trennen, sieht manchmal besser aus
% \center
\maketitle

\begin{multicols}{2}

\section*{Abstract}

{\small

{\bf Klassische KI-Planungstechniken }
können in grossen deterministischen Welten planen,
{\bf Operations research Techniken }
können mit Unsicherheiten arbeiten, versagen aber für grössere Welten.
{\bf MAXPLAN }
wandelt eine probabilistische Planungsaufgabe in ein {\bf E-MAJSAT} Problem
um, das effizient bearbeitet werden kann.

Die Aufgabenstellung bei einem {\bf E-MAJSAT Problem } lautet:
Finde die Belegung der Wahlvariablen, die bei einer KNF-Formel mit
Wahl- und Zufallsvariablen die Wahrscheinlichkeit der Erfüllung maximiert.
{\bf Bei MAXPLAN }
entspricht die Belegung der Wahlvariablen dem gewählten Plan, die
Zufallsvariablen repräsentieren die Unsicherheit in der Aufgabe.

}

% XXX \tableofcontents % XXX
% \newpage

\section{Problemrepräsentation \\
         bei MAXPLAN }

{\bf Probabilistische Planprobleme } sind Quadrupel aus
einer Zustandsmenge, einem Startzustand daraus, Aktionen und Zielzuständen
(die eine Untermenge der Zustandsmenge darstellen):
$<S,s_{0},A,G>$
(Die von den Aktionen bewirkten Zustandswechsel können probabilistisch sein)

Bei MAXPLAN wird die Aufgabe als sequentieller Effektbaum (ST, sequential
effects tree, sind äquivalent zu two timeslice Bayes networks)
eingelesen und mit einem LISP-Programm in ein E-MAJSAT Problem umgewandelt.

Das E-MAJSAT Problem wird als KNF Formel dargestellt, für die die Belegung
von Wahlvariablen gesucht wird, die unter Berücksichtigung der
Zufallsvariablen die Erfüllungwahrscheinlichkeit der KNF Formel maximiert.

SAT Probleme sind $NP$-vollständig, die bei MAXPLAN vorkommenden 
E-MAJSAT Probleme sind $NP^{PP}$-vollständig, wenn Planhorizont und 
Plangrösse durch ein Polynom der Problemgrösse beschränkt sind
% ### [NP^{PP} sei evtl. leichter als PSPACE ...]
(SAT: Erfüllbarkeitsproblem / E-MAJSAT: Erweiterung von SAT).

\subsection{Beispiel ,,Sandburg-67'' }

Eine Sandburg soll gebaut werden, dabei stehen die Aktionen
$\mathrm{baueBurg}$ und $\mathrm{grabeGraben}$ zur Verfügung.

Der Bau eines Burggrabens erhöht die Erfolgsaussichten des Burgenbaus. 

Die Zustände sind Kombinationen der Prädikate
$\mathsf{Burg}$ und $\mathsf{Graben}$. 

\begin{center}
\begin{tabular}{rl}
$ S = \{ $&$ (\lnot\mathsf{Burg} , \lnot\mathsf{Graben}), \;
             (\lnot\mathsf{Burg} , \mathsf{Graben}), $ \\
          &$ (\mathsf{Burg} , \lnot\mathsf{Graben}), \;
             (\mathsf{Burg} , \mathsf{Graben}) \; \} $ \\
$ s_{ \mathsf{0} } = ( $&$ \lnot\mathsf{Burg} , \lnot\mathsf{Graben} \; ) $ \\
$ G = \{ $&$ (\mathsf{Burg} , \lnot\mathsf{Graben}), \;
             (\mathsf{Burg} , \mathsf{Graben}) \; \} $ \\
$ A = \{ $&$ \mathrm{baueBurg} , \; \mathrm{grabeGraben} \; \} $ \\
\end{tabular}
\end{center}

% -- \medskip
{\bf ST für die Aktion ,,$\mathrm{grabeGraben}$'': }

\begin{itemize}
\item Wirkung auf das Prädikat $\mathsf{Graben}$:

Die Erfolgswahrscheinlichkeit beträgt 0.5 ($d_{1}$), ein schon 
vorhandener Graben bleibt immer bestehen.

\item Wirkung auf das Prädikat $\mathsf{Burg}$:

Die Aktion hat keine Wirkung auf dieses Prädikat.
\end{itemize}

{\bf ST für die Aktion ,,$\mathrm{baueBurg}$'': }

\begin{itemize}
\item Wirkung auf das Prädikat $\mathsf{Burg}$:

Eine schon vorhandene Burg bleibt bestehen, sonst hängt die
Erfolgswahrscheinlichkeit von der Existenz eines Grabens ab.

$\mathsf{Burg}$ muss hier vor $\mathsf{Graben}$ betrachtet werden,
da der neue Wert von $\mathsf{Burg}$ auf den neuen Wert von
$\mathsf{Graben}$ wirkt! Die Ordnung der ST ist also wichtig.
%
\item Wirkung auf das Prädikat $\mathsf{Graben}$: 

Der Versuch, eine Burg zu bauen, kann den Graben zerstören, wenn schon eine 
Burg stand oder aber der Versuch, eine Burg zu bauen, fehlgeschlagen ist 
(hier wird der Wert von $\mathsf{Burg:neu}$ verwendet).
Beim Burgenbau entsteht niemals ein Graben.
\end{itemize}

{\bf Darstellung des ST als Baum: }

\includegraphics[keepaspectratio,width=\columnwidth]{ST}

\subsection{Darstellung des Beispielproblemes \\
            als KNF }

Zunächst wird der ST modifiziert, um die Umwandlung in eine KNF zu
vereinfachen:
Jedes Blatt mit einem Wert $x$ {\bf zwischen} 0.0 und 1.0 wird durch
einen Knoten ersetzt, der über eine 
Zufallsvariable (die mit Wahrscheinlichkeit $x$ wahr ist) zu 
2 Blättern mit den Werten 1.0 und 0.0 verzweigt. 
Danach haben alle Blätter 1.0 oder 0.0 als Wert. 

Für jede Aktion $a_{i}$ und jeden Zeitschritt 
$j$ = $t_{1} \ldots t_{N}$ ($N$ ist der Planungshorizont)
wird eine Variable $a_{i,j}$ eingeführt.

Für jede Zustandsvariable $p_{i}$ und jeden Zeitschritt 
$j$ = $t_{0} \ldots t_{N}$
wird eine Variable $p_{i,j}$ eingeführt.

Ausser für den Zeitpunkt $t_{0}$ werden diese mit Variablen 0.5 
vorbelegt, denn sie sind nicht vollständig von den Aktionen 
determiniert. % ### Hinweis: nur diese Art betrifft Zeitpunkt t_{0} !
Die Gesamtwahrscheinlichkeit jedes Planes sinkt dadurch mit dem
Faktor $0.5^{P*N}$, eine Anpassung der Bewertung ist nötig.

Für jede Zufallsvariable $r_{i}$ und jeden Zeitschritt 
$j$ = $t_{1} \ldots t_{N}$ wird eine Variable $r_{i,j}$ eingeführt.
Damit wird später die Unsicherheit modelliert.

Insgesamt verwendet die E-MAJSAT Repräsentation also
$V = A N + P (N+1) + R N$ Variablen.

$r_{i,x} = r_{i,y}$ für alle $i$ und alle $x,y \in 1 \ldots N$,
Von den $a_{i,j}$ ist pro $i$ immer genau eine wahr, es gibt also 
unnötig viele Variablen -- siehe ,,Zukünftige Verbesserungen''
in Abschnitt \ref{ZukVerb}.

\subsection{ Klauseln in der KNF Darstellung }

{\bf Beispiel: KNF für Sandburg-67 mit 1 Zeitschritt: }

Der Zweck der einzelnen Klauseln wird direkt im Anschluss beschrieben.

{\small

$(\overline{\mathsf{Graben}_{0}})$   \Red{ $\land$ }
$(\overline{\mathsf{Burg}_{0}})$     \Red{ $\land$ }
\Blue{$(\mathsf{Burg}_{1})$}         \Red{ $\land$ } 

$(\mathrm{grabeGraben}_{1} \; \lor \; 
  \mathrm{baueBurg}_{1})$            \Red{ $\land$ } \\
\Blue{$
 (\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \overline{\mathrm{baueBurg}_{1}})$ 
                                   } \Red{ $\land$ } \\
\medskip
\medskip
$(\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \; \lor \;
  \mathsf{Graben}_{1})$              \Red{ $\land$ } \\
\Blue{$
 (\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \mathsf{Graben}_{0} \; \lor \;
  \overline{d_{1,1}} \; \lor \;
  \mathsf{Graben}_{1})$            } \Red{ $\land$ } \\
$(\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \mathsf{Graben}_{0} \; \lor \;
  d_{1,1} \; \lor \;
  \overline{\mathsf{Graben}_{1}})$   \Red{ $\land$ }

\Blue{$
 (\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \; \lor \;
  \overline{\mathsf{Burg}_{0}} \; \lor \;
  \overline{e_{3,1}} \; \lor \;
  \mathsf{Graben}_{1})$            } \Red{ $\land$ }  \\
$(\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \; \lor \;
  \overline{\mathsf{Burg}_{0}} \; \lor \;
  e_{3,1} \; \lor \;
  \overline{\mathsf{Graben}_{1}})$   \Red{ $\land$ } \\
\medskip
\medskip
\Blue{$
 (\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \, \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \overline{\mathsf{Burg}_{1}} \; \lor \;
  \mathsf{Graben}_{1})$            } \Red{ $\land$ } \\
$(\overline{\mathrm{b.B.}_{1}} \, \lor \,
  \overline{\mathsf{Graben}_{0}} \, \lor \,
  \mathsf{Burg}_{0} \, \lor \,
  \mathsf{Burg}_{1} \, \lor \,
  \overline{e_{4,1}} \, \lor \,
  \mathsf{Graben}_{1})$              \Red{ $\land$ }\\
\Blue{$
 (\overline{\mathrm{b.B.}_{1}} \, \lor \,
  \overline{\mathsf{Graben}_{0}} \, \lor \,
  \mathsf{Burg}_{0} \, \lor \,
  \mathsf{Burg}_{1} \, \lor \,
  e_{4,1} \, \lor \,
  \overline{\mathsf{Graben}_{1}})$ } \Red{ $\land$ }\\
\medskip
\medskip
$(\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \mathsf{Graben}_{0} \; \lor \;
  \overline{\mathsf{Graben}_{1}})$   \Red{ $\land$ }

\Blue{$
 (\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \overline{\mathsf{Burg}_{0}} \; \lor \;
  \mathsf{Burg}_{1})$              } \Red{ $\land$ } \\
$(\overline{\mathrm{grabeGraben}_{1}} \; \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \overline{\mathsf{Burg}_{1}})$     \Red{ $\land$ }

\Blue{$
 (\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \overline{\mathsf{Burg}_{0}} \; \lor \;
  \mathsf{Burg}_{1})$              } \Red{ $\land$ } \\
\medskip
\medskip
$(\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \; \lor \;
  \overline{e_{1,1}} \; \lor \;
  \mathsf{Burg}_{1})$                \Red{ $\land$ } \\
\Blue{$
 (\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \overline{\mathsf{Graben}_{0}} \; \lor \;
  e_{1,1} \; \lor \;
  \overline{\mathsf{Burg}_{1}})$   } \Red{ $\land$ } \\
\medskip
\medskip
$(\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \mathsf{Graben}_{0} \; \lor \;
  \overline{e_{2,1}} \; \lor \;
  \mathsf{Burg}_{1})$                \Red{ $\land$ } \\
\Blue{$
 (\overline{\mathrm{baueBurg}_{1}} \; \lor \;
  \mathsf{Burg}_{0} \; \lor \;
  \mathsf{Graben}_{0} \; \lor \;
  e_{2,1} \; \lor \;
  \overline{\mathsf{Burg}_{1}})$     }

} % END kleinere Schrift

\medskip

{\bf Anfangsbedingungen und Ziel: } \\
%
Jeder Variable des Anfangszustandes $p_{i,t_{0}}$ und jeder Zielbedingung 
entspricht eine atomare Klausel.

{\bf Einander ausschliessende Aktionen: } \\
%
Zu jedem Zeitpunkt ausser $t_{0}$ darf maximal und muss minimal 
eine Aktion stattfinden. Das wird mit
$ {A \choose 2} + 1 = \frac{1}{2} (A^{2} + A) + 1 $
Klauseln beschrieben.
% ### [ A über 2, weil alle Paare verboten werden müssen ]

{\bf Bäume: } \\
%
Jeder Pfad durch jeden der Bäume (nach der Anpassung des ST, die ganz
am Anfang stattfindet) wird durch eine Klausel pro Zeitpunkt ausgedrückt.

Wenn wir zum Beispiel graben und noch keinen Graben haben, werden 
wir mit Wahrscheinlichkeit $d_{1,1}$ im nächsten Schritt einen Graben haben.

Das ergibt die Implikation \\
$\mathrm{grabeGraben}_{1} \land \overline{\mathsf{Graben}_{0}} \land d_{1,1} 
 \Rightarrow \mathsf{Graben}_{1} $,
\\
in Klauselschreibweise also \\
$\overline{\mathrm{grabeGraben}_{1}} \lor \mathsf{Graben}_{0} \lor
 \overline{d_{1,1}} \lor \mathsf{Graben}_{1} $

Insgesamt enthält die fertige KNF maximal
$2 P + (1 + {A \choose 2}) N + 2 N \sum^{A}_{i=1} L_{i}$
Klauseln 
($L_{i}$ ist die Anzahl der Blätter im Baum von Aktion $a_{i}$).

Für die Komplexität der KNF ergibt sich damit:
Die Grösse der Klauseln wird von der Pfadlänge der Bäume 
dominiert.
% ??? ({\em welche für die aus den Bäumen gewonnenen 
% ???       Klauseln 2+Pfadlänge beträgt})
Die Anzahl der Klauseln ist ein Polynom niederer Ordnung der 
Problemgrösse.

\section{Der Problemlöser \\
         von MAXPLAN }

MAXPLAN baut auf dem bewährten DPLL-Algorithmus für Erfüllbarkeitsprobleme
(
Davis-Putnam-Logemann-Loveland Verfahren für Erfüllbarkeitstests, entwickelt
1962) auf, welches noch immer der beste Algorithmus ist, den die Autoren
kennen.

Zuerst müssen alle die KNF erfüllenden Belegungen gefunden werden.
Dann wird für jede mögliche Belegung der Wahlvariablen die 
Gesamtwahrscheinlichkeit (für alle Belegungen der anderen Variablen)
berechnet, die KNF zu erfüllen.

Diese entspricht der Erfolgswahrscheinlichkeit des durch die Belegung der 
Wahlvariablen gewählten / beschriebenen Planes.
So kann der Plan mit den besten Erfolgsaussichten gefunden werden.

Die Suche nach den die KNF erfüllenden Belegungen baut einen
Binärbaum auf, in dem jeder Knoten einer Variable entspricht. Es ist
wichtig, nur die ,,interessanten'' Knoten zu expandieren. 

Der Wert eines Knotens ist dabei der durch die Wahrscheinlichkeit gewichtete 
Durchschnitt der Unterbäume, bzw. deren Maximum, wenn es um eine 
Wahlvariable geht.

Einige Begriffsdefinitionen zum Problemlöser:

\begin{itemize}
\item {\bf Aktive Variable: } 
      Variable, der noch kein Wahrheitswert zugewiesen wurde
\item {\bf Aktive Klausel: } 
      Klausel, die noch nicht durch zugewiesene Variablen erfüllt wird
\item {\bf Aktuelle KNF Teilformel: } 
      Wird durch die Menge noch aktiver Klauseln und der darin vorkommenden 
      Variablen beschrieben
\item {\bf Wert einer KNF Teilformel: } 
      Maximum der Erfolgswahrscheinlichkeiten
      $\sum_{S}(\ldots)$ (wobei $S$ die Menge aller die KNF
      erfüllenden Belegungen der Zufallsvariablen ist) für alle möglichen
      Pläne $D$:

 $ \rightarrow \quad
   \max\limits_{D} \sum\limits_{S}{ ( 
   \prod\limits_{v_{i} \in CH}{ \pi_{i}^{\, v_{i}} * 
                                (1 - \pi_{i})^{\mathsf{1}-v_{i}} } 
                                  ) }
 $

 ($D$ sind alle möglichen Belegungen der Wahlvariablen,
   $\pi_{i}$ ist die Wahrscheinlichkeit, dass die Zufallsvariable 
   $v_{i}$ wahr ist.)
\end{itemize}

\subsection{Eliminierung unnötiger \\
            Berechnungen }

\subsubsection{DPLL-Pruningregeln }

DPLL entscheidet mit folgenden 3 Regeln, wann ein Unterbaum nicht mehr
weiterverfolgt werden muss:

\begin{itemize}
\item {\bf Unwichtige Variablen belegen } \\
({\bf IRR}, irrelevant variable elimination):

Einer aktiven Variable, die in keiner aktiven Klausel mehr vorkommt,
wird der Wert True zugewiesen.
%
\item {\bf Atomare Klauseln erfüllen } \\
({\bf UNIT}, unit propagation):

Einer Variablen, die allein eine aktive Klausel bildet, wird der
passende Wert (der diese aktive Klausel wahr macht) zugewiesen.
%
\item {\bf Eindeutige Variablen entscheiden } \\
({\bf PURE}, purification):

Einer aktiven Variable, die in allen aktiven Klauseln nur noch
negiert bzw. nur noch nicht negiert vorkommt, wird der passende
Wert zugewiesen, mit dem alle diesen Klauseln erfüllbar bleiben.
\end{itemize}

\subsubsection{Heuristiken für die Planbewertung }

Wenn kein Pruning möglich ist, muss an einer Variablen verzweigt
werden (bevorzugt an einer Wahlvariable).
Der Wert des Verzweigungsknotens wird aus dem Wert der Unterbäume gemessen 
(bei Wahlvariablen das Maximum aus den Werten der Unterbäume, sonst 
 der durch die Wahrscheinlichkeit gewichtete Durchschnitt).
Die richtige Wahl der Verzweigungsvariablen in dieser Situation ist wichtig 
für die Effizienz der Berechnung.

Drei Verzweigungsheuristiken wurden getestet, Testproblem war Sandburg-67
(gemessen wurde nur die Zeit zur Bewertung eines festen Planes:
 Abwechselnd graben und bauen, letzter Schritt ist bauen):

\begin{itemize}
\item {\bf Zufall (random): }

Wähle die nächste aktive Variable aus einer zu Beginn festgelegten
zufälligen Ordnung der Variablen.
%
\item {\bf Gier (sats most clauses): }

Wähle die aktive Variable, die die meisten Klauseln erfüllen kann.
%
\item {\bf Zeit (time-ordered): }

Wähle die aktive Variable, die als nächste im Plan auftaucht.
\end{itemize}

\subsection{Optimierung des Planbewerters }

Wie erwartet benötigt man bei wachsendem Planhorizont exponentiell mehr Zeit.
Messungen zeigen aber, dass man mit der Zeit-Heuristik in einem vorgegebenen
Zeitraum die längsten Pläne (für Sandburg-67) findet:

\begin{center}
\begin{tabular}{|r|r|r|}
\hline
Heuristik & \multicolumn{2}{|c|}{max. Schritte in} \\
\cline{2-3}
          & 1 Minute & 10 Min. \\
\hline
Zufall    & 8       & 10  \\
Gier      & 11      & 13  \\
Zeit      & 15      & 19  \\
\hline
\end{tabular}
\end{center}

Messungen mit verschiedenen Kombinationen der Pruningregeln (jeweils in
Kombination mit der Zeit-Heuristik) ergeben, dass das Weglassen von Regeln
die Berechnung stark verlangsamt.

Die Rechenzeit bei Verwendung von nur PURE / UNIT, nur UNIT und ganz ohne 
Pruning steigt extrem an. Die Berechnung von 5-Schritt-Plänen brauchte 
bei eingeschränktem Pruning jeweils schon Tage.

Da ein einfacher Algorithmus mit dynamischer Programmierung ({\bf ENUM})
bei der Planbewertung nur zur Planlänge lineare Zeit braucht, 
wurde {\bf Memoisierung} der Teilformeln und ihrer Werte in MAXPLAN 
eingebaut.

Es wurden also Berechnungsergebnisse aufbewahrt, um die wiederholte 
Berechnung gleicher Teilformeln zu vermeiden.
Nun konnten in der gleichen Zeit statt 18 ganze 110 Schritte bewertet 
werden!

Scheinbar behinderte jedoch das Pruning die Wirkung der Memoisierung.
Also wurden Vergleichsmessungen mit eingeschränktem  Pruning durchgeführt, 
,,kein Pruning'' bzw. ,,nur UNIT'' zeigte sich als beste Wahl
(bei anderen Tests übertraf ,,nur UNIT'' ,,kein Pruning''; alle Tests
 mit Memoisierung und Zeit-Heuristik).

\begin{center}
\begin{tabular}{|l|c|c|}
\hline
Pruning-  & Planlänge in  & Rechenzeit für \\
regeln    & 20 Sekunden   & 100 Schritte   \\
\hline
alle DPLL & $\approx$  50 & $\approx$ 140s \\
ohne IRR  & $\approx$  60 & $\approx$  90s \\
\hline
nur UNIT  & $\approx$  95 & $\approx$  25s \\
keine     & $\approx$ 100 & $\approx$  20s \\
\hline
\end{tabular}
\end{center}

Der so optimierte MAXPLAN wurde schliesslich am kompletten Sandburg-67 
Problem bis zu einem Planhorizont von 10 Schritten getestet. 

Der beste Plan mit 10 Schritten ist
 \Blue{G}-B-\Blue{G}-B-B-\Blue{G}-B-\Blue{G}-B-B
(B: $\mathrm{baueBurg}$, G: $\mathrm{grabeGraben}$).
Er hat eine Erfolgswahrscheinlichkeit von etwa 97\%. 
Auf einer Sparc Ultra 1-140 mit 128 MB RAM findet MAXPLAN diesen Plan in 
etwa 12 Sekunden.

\section{Vergleich von MAXPLAN mit anderen Planern }

MAXPLAN wurde mit 3 weiteren Planern verglichen:

\begin{itemize}
\item {\bf BURIDAN}, ein klassischer KI-Planer, Partial-order Planen für
probabilistische Probleme.

\item {\bf ENUM}, Planaufzählung und dynamische Programmierung für die
Planbewertung. % ### [Planaufzählung / dynamische Programmierung erklären/...?]

\item {\bf POMDP}, Lösung teilweise beobachtbarer MDP (Markov Decision Process)
mit dynamischer Programmierung (inkrementelles Pruning).
\end{itemize}

Minimax-Planer kamen nicht in Frage, da auch Probleme gelöst werden sollten, 
für die es keinen 100\% erfolgversprechenden Plan gibt.

Der Vergleich mit BURIDAN erwies sich als schwierig, da bei BURIDAN die
(nicht automatisierbare) Wahl einer zum Problem passenden Methode 
entscheidend für die Leistung ist. In jedem Fall war jedoch MAXPLAN
über 10 mal schneller bei der Lösung des mit BURIDAN beschriebenen 
{\bf ,,Bombe-im-Klo'' Problemes\footnote[1]{
Eins von 2 oder mehr Paketen enthält eine Bombe,
um Bomben zu entschärfen kann man sie ins Klo werfen}}:

MAXPLAN benötigte 0.3 bis 0.7 Sekunden (alle Kombinationen von Pruningregeln
ausser kein Pruning benötigten nur 0.3 Sekunden, zum Beispiel nur UNIT
Pruning).

BURIDAN (auf einer etwas langsameren Maschine) benötigte je nach
Bewertungsmethode 6.9 bis 6736 Sekunden 
(Vorwärts 6.9 Sekunden, Rückwärts 6736 Sekunden, Abfrage 64.9 Sekunden,
 Netzwerk 152 Sekunden).

\subsection{Welcher Planer skaliert besser? }

ENUM und POMDP müssen alle $\mathsf{2}^{P}$ Zustände 
aufzählen und benötigen zur Grösse des Zustandsraumes exponentielle
Resourcen. ENUM bewertet alle $A^{N}$ Pläne und braucht also auch
zum Planhorizont exponentielle Zeit.
{\bf Dennoch ist MAXPLAN nicht immer schneller!}

MAXPLAN versucht nur den nötigen Teil des Problemraumes zu 
erforschen, ohne die Optimalität aufs Spiel zu setzen. 
Bei Sandburg-67 kann es aber die Unbeobachtkeit des Zustandes nicht 
ausnutzen. POMDP kann das und braucht zur Planlänge lineare Zeit, 
MAXPLAN exponentielle.

Die erreichte Plantiefe in Abhängigkeit von der verfügbaren Zeit:

\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Zeit: & POMDP & ENUM & MAXPLAN \\
\cline{2-4}
(Sek.) & \multicolumn{3}{|l|}{Schritte} \\
\hline
0.1 &  6 & 13 & 7 \\
\hline
10  & 50 & 16 & 9 \\
\hline
\end{tabular}
\end{center}

{\bf MAXPLAN kann einfache Probleme ausnutzen:}

Bei dem {\bf Bomben-entschärfen Prolem} kann MAXPLAN für 1 bis 10 Pakete
die Lösung in etwa konstanter Zeit (etwa $\frac{1}{10}$ Sekunde) finden. 
Der optimale Plan besteht immer aus zwei Schritten.

Bei {\bf Bomben-entschärfen} gibt es die Aktionen Untersuchen und Entschärfen, 
wobei Untersuchen alle Bomben findet und Entschärfen alle Bomben zugleich 
entschärft, falls man weiss, in welchen Paketen die Bomben sind.

POMDP und ENUM benötigen zur Anzahl der Pakete trotzdem exponentielle Zeit.
ENUM braucht ab 6 Paketen mehr Zeit als MAXPLAN, POMDP bereits bei 1 Paket.
In $\frac{1}{2}$ Sek. schaffen POMDP und ENUM 5 bzw. 7 Pakete.

\section{Zukünftige Verbesserungen }
\label{ZukVerb}

{\bf Skalierung: } \\
%
Ausser den hier erwähnten wurde noch das rutschiger-Griff Problem und 
Varianten des Bombe-im-Klo Problems (bei der das Klo verstopfen kann) 
untersucht, aber es muss noch weiter geforscht werden. 

Bomben-entschärfen zeigte, dass MAXPLAN {\em einfache} 
Lösungen auch in einem wachsendem Zustandsraum effizient finden kann.

{\bf KNF: } \\
%
Die aus dem Problem gewonnene KNF Formel ist nicht optimal,
die Speicherung der KNF kann auch eleganter gelöst werden.

{\bf Verzweigungsheuristik: } \\
%
Die Zeit-Heuristik wertet alle Variablen eines Zeitschrittes gleich. 
Die Klauseln eines Zeitschrittes bilden aber einen {\bf natürlichen Block},
d.h. sie kommen nur in einem Zeitschritt und dessen direkten Nachbarn vor. 
Das Problem kann in diese natürlichen Teilformeln zerlegt werden 
(Teile-und-herrsche Strategie).

{\bf Memoisierung: } \\
%
Alle Teilformeln und ihre Werte zu speichern ist unnötig und verbraucht 
zuviel Speicher 
(bei Sandburg-67 reicht der Speicher des Testrechners nur für 15 Schritte).

Eine bestimmte Menge Speicher als Cache für Teilformeln zu reservieren
und eine gute Strategie finden, welche Teilformeln gespeichert werden
(z.B. abhängig von ihrer Grösse, Komplexität und Benutzungshäufigkeit)
wäre ein Ausweg.

\subsection{Zukünftige Erweiterungen }

{\bf Verstärkungslernen: } \\
%
Verstärkungslernen kann eine bessere Verzweigungs- und Cache-Heuristik finden.
Dabei wird es aber oft an Trainingsdaten mangeln, so dass das Problem entsteht,
einige ,,typische'' Probleme zu finden, an denen das System trainieren kann.

{\bf Näherungsverfahren: } \\
%
In der Praxis ist es nützlich, schnell eine ungefähre Lösung zu finden und 
sich in der verbleibenden Zeit bis zur Abfrage des Ergebnisses der optimalen 
Lösung weiter zu nähern.

{\bf Belief Networks: } \\
%
Die Variablen der KNF Darstellung können als Knoten eines Belief Network 
gesehen werden -- entsprechende Lösungsverfahren für Belief Networks sind 
also auf MAXPLAN Probleme anwendbar.

{\bf Beobachtbarkeit berücksichtigen: } \\
%
MAXPLAN geht von unbeobachtbaren Problemwelten aus -- es sollte ggf. auch
möglich sein, den Plan der ({\em beobachtbaren}) Entwicklung der Dinge 
anzupassen, statt eine feste Folge von Schritten im Voraus zu planen.

{\bf Pläne mit Schleifen berücksichtigen: } \\
%
Auch Pläne mit Schleifen, die wiederholte Aktionen kompakt darstellen, sind 
eine denkbare Erweiterung.

\section{Zusammenfassung }

MAXPLAN ermöglicht effizientes Planen in nicht vollständig deterministischen
Welten und verbindet damit Vorteile von klassischen Planungstechniken mit
denen von operations research Planern.

Dies wird erreicht, indem das Planproblem in ein Erfüllbarkeitsproblem
umgewandelt wird und der Plan mit den maximalen Erfolgsaussichten (der die
maximale Erfüllungswahrscheinlichkeit bietet) gesucht wird. Eine Reihe
von Heuristiken beschleunigen die Berechnung typischer Probleme wesentlich,
während im schlechtesten Fall natürlich weiterhin exponentielle Zeit
benötigt wird.

Die Untersuchungen von Majercik und Littman zeigen, dass MAXPLAN sich in
der vorliegenden Version mit etablierten Planern messen kann, aber noch
immer eine Reihe von zukünftigen Verbesserungen eine weitere Steigerung
der Effizienz versprechen.

\section{Literatur }

MAXPLAN: A New Approach to Probabilistic Planning (1998)
Stephen M. Majercik and Michael L. Littman, Dept. of Computer Science,
Duke University, Durham, NC 27708-0129.
\copyright American Accociation for Artificial Intelligence (www.aaai.org).
% Decision-Theoretic Planning, Seite 86 -- 93

\begin{center}
\LaTeX\ Layout \copyright by Eric Auer
\end{center}

\end{multicols}

\clearpage % -------------------
%
%
%
\end{document}
