Wir befinden uns in der Endphase der KI-Vorlesung und beschäftigen uns mit Planungsalgorithmen

und steigen da noch mal so ein bisschen in die Verästelungen der Algorithmen ab.

Wir hatten uns das letzte Mal unterhalten über Komplexität von Planung und über

Planungsalgorithmen, die diese Komplexitäten realisieren.

Wir sollten noch mal ganz kurz daran erinnern, wir haben zwei Arten von Planenproblemen,

einmal das erfüllende Planung, das heißt man möchte einen Plan finden, der das Planproblem

löst, also oder erfüllt und wir haben das optimale Plan, wo wir uns dafür interessieren optimale

Pläne zu finden. Und wir hatten schon gesehen, dass wenn wir diese Relaxierungstechniken nehmen,

die die Heuristiken berechnen, indem sie Pläne für die relaxierten Probleme finden und dann deren

Länge zählen, das ist ja was wir gemacht haben, dann interessiert man sich selbst,

wenn man auf der oberen Ebene erfüllend plant für optimale Pläne unten, weil wir sonst

unzulässige Heuristiken kriegen. Unzulässige Heuristiken machen uns Probleme auf der oberen

Ebene, deswegen diese beiden Arten von Problemen Satisfying und optimales Planen.

Und sie hängen über diese Relaxierungstechniken für uns jetzt im Moment zusammen.

Wenn man die sich mal anguckt, dann kann man Problemklassen definieren, so wie man das in

der Komplexitätstheorie macht, dann hat man das Plan X Problem, was einfach die Existenz

eines Problems ist, also das ist Satisfying Planning und wir haben Plan Len, das im Wesentlichen

betrifft, wie lange sind die optimalen Pläne, das ist was wir für die untere Ebene brauchen.

Und dann kann man das noch relaxieren, indem man so eine polynomialen Unschärfe einführt,

die einem manchmal das Leben vereinfacht. Wir haben uns über Komplexitäten angeguckt,

Plan X ist P-Space Hard, das heißt dadurch ist es gleich NP-Hard und wir haben uns auch

angeguckt, dass Plan X NP-Space ist, also damit ist Plan X P-Space vollständig. Dann haben

wir uns Plan Len angeguckt und wir haben im Wesentlichen dieselbe Situation, wir haben

P-Space komplett und wir sehen, dass Polyplan Len tatsächlich besser ist. Warum ist das

interessant? Das ist interessant im Wesentlichen deswegen, weil unsere Probleme im Planen groß

werden. Blocksworld kann beliebig groß werden und kompliziert werden. Dieses hier ist im

Übrigen relativ typisch für so etwas wie diesen Hafen in Singapur. Wenn man planen

will, wie lässt man die Schiffe durch ein, die in verschiedensten Wartepositionen sind,

wie kriegt man die durch irgendwelche kleinen Nadelöre durch. Wir haben das beim Aufzugssystem

angeguckt und uns ein Bild davon gemacht, dass das nicht ganz trivial ist und sind dann

in die Algorithmen übergegangen. Die Idee hierbei ist, die wir ja auch schon vorher

gesehen hatten, ist, dass wir heuristische Suche machen und heuristische Suche an sich

ist relativ einfach. Man hat einen Baum mit Möglichkeiten und schmeißt die weg, die einem

nicht gut erscheinen und macht dann im Wesentlichen Vorwärtssuche oder so etwas. Das haben wir

vorher gesehen gehabt und die Idee ist, dass wenn man eine gute Heuristik hat, dann kann

man abschätzen, wie weit es noch zum Ziel ist und kann das als Präferenz machen. Diese

Heuristiken sind wirklich eine absolut drastische Verbesserung. Im Prinzip, was wir hier die

ganze Zeit machen, ist einmal so durchzuspielen, was man heutzutage im Modernen macht, um

Heuristiken zu bekommen. Sie werden sehen, dass wir einen riesigen Aufwand treiben, im

Prinzip, um Heuristiken zu bekommen. Die meiste Zeit, die wir rechnen, berechnen wir nur,

um eine Heuristik zu kriegen, denn wenn wir eine gute Heuristik haben, dann ist die Suche

gut. Und sonst haben wir keine Chance. Und die ganze Sache bei den Algorithmen, wo die

Musik im Moment spielt, ist, dass man die Balance hat beim Berechnen der Heuristiken,

dass man genau richtig viel da reinsteckt, dass man interessante, gut voraussagende Heuristiken

kriegt, die trotzdem noch polynomial berechnenbar sind. Und das werden wir heute, wie sagen,

bis knapp an die Forschungsfront führen. Wir machen 3D-Search oder A-Sternsuche, je nachdem.

Das ist auch im Wesentlichen das Gleiche. Man muss nur an der Heuristik etwas drehen. Und

wir machen Delete Relaxation. Die haben wir uns besonders angeguckt. Was wir uns heute

noch etwas mehr angucken, ist diese H-Plus-Heuristik. Die wird sich herausstellen als NP-vollständig.

Das heißt, im Prinzip ist das eine schlechte Heuristik, weil sie einfach zu aufwendig