Deklaratives Planen basierend auf Logischer Programmierung

Forschungsprojekt P 14781 Deklaratives Planen basierend auf Logischer Programmierung Nicola LEONE27.11.2000 In der Fachwelt wurden kürzlich deklarative Ansätze für Planungsaufgaben vorgeschlagen; diese Ansätze zeichnen sich dadurch aus, daß der Benutzer ein Planungsproblem mittels eines logikbasierten, deklarativen Formalismus spezifiziert. Das Finden von Plänen wird dabei auf generische Probleme (zum Beispiel Erfüllbarkeitsprobleme) reduziert, die von effizienten Systemen der computationalen Logik gelöst werden. Das Hauptziel dieses Projektes ist, diese Ansätze weiterzuverfolgen und ein ausgereiftes deklaratives Planungssystem zu erstellen, das einige wesentliche Mängel bei bisherigen Systemen dieser Art beheben soll. Insbesondere soll es möglich sein, Pläne zu berechnen, die optimal bezüglich bestimmter Kriterien, wie zum Beispiel Kosten von Aktionen oder Güte von Zuständen, sind. Dabei soll die Berechnung solcher Pläne auch in Szenarien möglich sein, in denen das Wissen über die Gegebenheiten im Planungsuniversum unvollständig ist. Das vorgeschlagene System wird auf logischer Programmierung basieren, die nötige Ausdruckskraft wird durch eine geeignete Planungssprache erzielt werden. Die geplanten Forschungsaktivitäten gliedern sich in die folgenden Teilziele: (i) Die Entwicklung einer ausdrucksstarken deklarativen Planungssprache; (ii) das Design und die Entwicklung eines deklarativen Planungssystems, das die entwickelte Sprache unterstützt; und (iii) die Anwendung des Systems in verschiedenen Problembereichen. Um diese Ziele zu erfüllen, können wir von dem Wissen und der Erfahrung profitieren, die wir in vergangenen Projekten, dazu zählt auch das erfolgreiche FWF Projekt P11580-MAT, gesammelt haben. Wir planen, das DLV System als effizientes Kernsystem zu verwenden, das die Basis der Systemimplementierung bilden soll. DLV ist ein auf dem letzten Stand der Forschung stehendes System für disjunktives logisches Programmieren, das im genannten Projekt entwickelt wurde.

Seit den Anfängen der Forschung im Bereich der Künstlichen Intelligenz ist Automatisches Planen ein wichtiger Forschungsgegenstand. Als das "klassische Planungsproblem`` bezeichnet man hier das Auffinden einer Folge vordefinierter Aktionen um von einem gegebenen Anfangszustand in einen gewünschten Zielzustand zu gelangen, wobei lediglich das Repertoire an Aktionen, sowie deren Vorbedingungen und Effekte bekannt sind. Konkrete Problemstellungen reichen hier von der klassischen Routenplanung bis hin zur automatischen Zusammenstellung von Web-Services zur Erledigung einer bestimmten Aufgabe, etc. Während klassische Planungssprachen wie beispielsweise STRIPS oder PDDL von einem vollständig definierten Anfangszustand sowie deterministischen Effekten aller Aktionen ausgehen, gelten diese Annahmen in realistischen Szenarien oft nicht. Im vorliegenden Proejkt wurde eine ausdrucksstarke Planungssprache, Kc, entwickelt, die es auch erlaubt nicht-klassisches Planen unter unvollständigem Wissen zu modellieren. Allerdings bringt die höhere Ausdrucksstärke dieser Sprache auch eine höhere Komplexität bei der Berechnung von Plänen mit sich: Klassische Suchalgorithmen können zum Lösen von Planungsproblemen, die in Kc formuliert sind, nicht mehr ohne weiteres angewandt werden. Hier bieten sich stattdessen deklarative Methoden an, beispielsweise Methoden der deklarative logischen Programmierung. Im Projekt P-14781wurde auf diese Problemstellungen in mehrerlei Hinsicht eingegangen. Die entwickelte Planungssprache Kc wurde um Konzepte aus dem Bereich der deklarativen Logikprogrammierung erweitert. Die Sinnhaftigkeit dieser Erweiterungen wurde anhand zahlreicher Beispiele demonstriert. Für das Planen unter unvollständigem Wissen wurden verschiedene Semantiken eingeführt: optimistische Pläne sind Aktionsfolgen, die den Zielzustand nur möglicherweise erreichen, während sichere Pläne das Erreichen des Zielzustandes unter allen Umständen garantieren. Weiters wurde auf die Erweiterung dieser beiden Semantiken um Aktionskosten eingegangen, wobei jeder Aktion ein bestimmter Kostenfaktor zugeordnet werden kann. Wir sind dabei sowohl auf die Frage eingegangen, optimale Pläne zu berechnen, als auch auf die Berechnung von Plänen, die unter einer bestimmten Kostenschranke bleiben. Daneben wurde die Komplexität verschiedener auftretender Berechnungsprobleme analysiert und neue Übersetzungen zur Lösung von Planungsproblemen mittels disjunktiver logischer Programme entwickelt. Diese Übersetzungen wurden im Planungssystem DLVK implementiert, welches sich bezüglich Performanz und Ausdrucksstärke als konkurrenzfähig gegenüber bestehenden Ansätzen erweist. Als praktisches Anwendungsszenario konnte die Verwendbarkeit der entwicklten Methoden im Bereich der Überwachung und des Designs von Multi-Agenten-Systemen gezeigt werden.