Abstraction Refinement für klassische Planungsprobleme

Klassisches Planen, ein Teilgebiet der Künstliche-Intelligenz-Forschung, befasst sich mit der Suche nach Plänen für ein gegebenes Planungsproblem. Dieses wird meist als Startzustand, einer Menge von Variablen und Operatoren und einer Zielbeschreibung formalisiert. Obwohl mehrere Ansätze bei der Suche nach einer Operatorfolge möglich sind, die uns vom Start- in einen Zielzustand bringt, hat sich in den letzten Jahren die heuristische Suche im Zustandsraum als sehr effiziente Suchmethode herausgestellt. Wie der Name suggeriert, besteht die heuristische Suche aus zwei Teilen, dem Suchalgorithmus und der Heuristik, die den Algorithmus intelligent durch den Suchraum lenkt.

In meinem Projekt werde ich eine neue Heuristik entwickeln, deren Grundgedanke aus dem Forschungsgebiet des Model Checking kommt und dort als "Counterexample-Guided Abstraction Refinement" bezeichnet wird. Die grundlegende Idee des Abstraction Refinement ist, dass man den Zustandsraum des Planungsproblems nicht in vollem Detail repräsentieren muss, um eine gute heuristische Abschätzung für den Zielabstand eines Zustands zu bekommen. Ausgehend von der größtmöglichen Abstraktion, nur einem Zustand für das Planungsproblem, wird hier der abstrakte Zustandsraum immer wieder dort iterativ verfeinert, wo eine abstrakte Lösung im Konkreten noch nicht anwendbar ist. Durch diese Vorgehensweise benötigt man wenig Speicherplatz für eine gut funktionierende Heuristik, die eine effiziente Suche ermöglicht.