Also wir wollten also Fragestunde und sowas in den Übungen. Die Klausur, ich nehme an das interessiert Sie alle sehr,

wird im wesentlichen Säulen wie die Probeklausur, wenn da etwas besonders problematisch dran war,

bitte bekannt geben. Wir werden dann versuchen darum zu arbeiten. Und natürlich ist die Klausur diesmal nicht online,

sondern wir haben zwei Hörsäle, weil man irgendwie ausreichend Platz braucht. Das heißt wir werden sie irgendwie

aufteilen müssen. Das müssen wir uns auch noch alles überlegen, wie wir das machen. Gibt es irgendwelche Fragen oder Anmerkungen?

Wir hatten uns beschäftigt mit Planung. Planung im Wesentlichen als das endgültige symbolische Problemlöserverfahren.

Das ist im Prinzip, worauf wir hingearbeitet haben die ganze Zeit. Es ist ein bisschen wie Suche, aber nicht Blackbox-Suche,

mit der wir angefangen hatten. Das war das einfache Zeug, sondern in gewisser Weise Whitebox-Suche. Wir haben eine Sprache,

mit der wir uns Sprachen geben, mit denen wir Zustände beschreiben können. Und wir geben uns eine Sprache, und das ist auch tatsächlich

die einzige Sprache, die so betrachtet wird. Möglicherweise verträgt er diesen heute nicht.

Das ist im Wesentlichen die einzige Sprache, die wir so verfennen. Das ist der Strips-Formalismus.

Das ist eine relativ einfache Idee. Wir haben eine Sprache zum Zustände beschreiben. Und wir haben die Aktionen,

die wir auch beschreiben können. Und im Wesentlichen haben wir eine Liste pro Aktion. Die Aktionen beschreiben wir dadurch,

dass sie Vorbedingungen haben. Das sind Ausdrücke in dieser Sprache. Dass sie eine Adlist haben, was nach der Aktion gilt,

und eine Delitlist, was nach der Aktion nicht mehr gilt. Ein typisches Beispiel ist, wenn ich mit dem Zug von Erlangen nach Nürnberg

fahren will, dann brauche ich als Vorbedingung nicht in Erlangen sein, sonst klappt das nicht. Ich brauche außerdem eine Fahrkarte,

sonst klappt das nur bedingt gut. Und die Adliste wäre, dass ich jetzt in Nürnberg bin, und die Delitliste ist, dass ich nicht mehr

in Erlangen bin. Das heißt, der Fakt der Weltbeschreibung, so tragiere ich. Das ist im Prinzip alles. Das andere ist genau gleich

wie bei einem Suchproblem. Wir haben initiale Zustände, wir haben Zielzustände. Nur, dass wir jetzt diese initialen

und Zielzustände als Faktenmengen beschreiben können. Sie sind also nicht mehr Black Box. Das ist der große Unterschied.

Und damit wir uns das Leben einfacher machen, nehmen wir Kosten an, die Einheitskosten sind. Jeder Aktion kostet das Gleiche.

Das ist aber wirklich nur eine Vereinfachung, damit uns das nicht mehr stört. Die Kostenfragen und Optimalität und alles um Krempel

haben wir uns bei den Suchalgorithmen hinreichend angeguckt. Ich probiere es vielleicht doch nochmal.

Wir hatten uns Beispiele angeguckt, wie Traveling Salesman in Australien. Das ist ja auch interessant.

Und wir hatten Strips eine Semantik gegeben, die im Wesentlichen darin besteht, dass wir sie abbilden auf ein Suchproblem.

Zustände sind Faktenmengen, initiale und Zielzustände sowieso. Und da muss man nur noch sich überlegen,

was die Anwendbarkeit von Aktionen ist. Und das ist gerade, wenn die Vorbedingungen eine Teilmenge des jetzigen Zustandes sind.

Und man macht die offensichtlichen Dinge mit der Erd- und der Delid-Liste. Und dann kann man loslegen und rumplanen.

Und in ganz einfachen Situationen, wie zum Beispiel in diesem massiv vereinfachten Planungsproblem,

kriegt man auch irgendwie so einen Teil eines Zustandsgrafes. Und in diesem Fall kriegt man einen Plan dafür,

dass wenn man in Sydney anfängt, dass man irgendwo sowohl in Adelaide als auch in Brisbane als auch in Sydney war

und hinterher wieder in Sydney ist. Bei uns ist die Planung einfach, zumindest wenn wir so ein wahnsinnig kleines Problem haben.

Und dann kann man jetzt natürlich dahin gehen und das Ganze praktikabel machen. Und dann geht man von diesen Strips paradigma,

wo man im Wesentlichen nur Aussagenlogik hat zur Beschreibung, in so eine Art milde First-Order-Beschreibung.

Und dann kann man jede Menge Spaß haben. Und das wurde standardisiert in dieser PDDL-Sprache und so weiter und so fort.

Das ist alles nicht wahnsinnig spannend, außer wenn Sie wirklich mal einen Planer anschmeißen wollen.

Dann müssen Sie Ihren Krempel oder den Doh aufschreiben. Gut. Das nächste, worüber wir gesprochen hatten, war Komplexitätsanalyse.

Und ich habe versucht, Sie davon zu überzeugen, dass Komplexitätsanalyse wichtig ist.

Speziell in solchen algorithmischen Fragen, wie wir Sie jetzt als nächstes für das Planen uns angucken,

nämlich wenn wir Heuristiken bauen wollen fürs Planen. Wir werden das genauso machen, wie wir in der Suche das schon mal vor exerziert haben,

nur halt eben in einem etwas komplexeren Gebiet. Wir werden ein Planungsproblem haben.

Und wir werden Heuristiken bauen, dadurch, dass wir die Probleme vereinfachen,

auf diesen vereinfachten Problemen exakt lösen und dann daraus eine Heuristik bauen und die wiederum zur Suchsteuerung nutzen.

Als wir darüber gesprochen haben beim Suchen, hatte ich immer so ein bisschen mit Handway gesagt, naja, es ist halt Mist, wenn so eine Heuristik genau so lange dauert,

wie das Hauptproblem. Und das können Sie sich vorstellen. Da gewinnt man nicht.

Und das möchte ich jetzt hier ein klein bisschen ausbauen und auf wissenschaftliche Füße stellen.

Bei den nächsten Folien ging es mir darum, dass man ein exponentielles Problem hat in der Suche. Das wissen wir.

Und das wird auch durch Planung und Beschreibung der Knoten und Kanten und so etwas. Das Zustandsraum ist nicht besser.

Die Probleme bleiben exponentiell. Das heißt, sie sind NP-hart. Und die Frage ist, was können wir denn machen für solche Heuristiken?

Und was sollte für die Heuristiken gelten? Und die Idee ist im Wesentlichen, dass Heuristiken polynomial sein sollten.