Kontrollwissen für domänen-unabhängige Planungssysteme
Final Report Abstract
Das Gebiet der Handlungsplanung befasst sich mit der automatischen Erzeugung von Aktionsfolgen (Plänen), die den handelnden Agenten von einer gegebenen Anfangssituation zu einer gewünschten Zielsituation führen. Man unterscheidet domänenunabhängige und domänenspezische Planungssysteme. Domänenunabhängige Planer lösen ihnen gestellte Planungsaufgaben allein aufgrund einer deklarativen Beschreibung der Anfangssituation, der Aktionsmöglichkeiten und der Ziele. Domänenspezische Planer benötigen zusätzlich von Experten formuliertes domänenspezisches Kontrollwissen, welches den Raum der möglichen Aktionsfolgen einschränkt und so die Lösungsfindung erleichtert. Domänenunabhängige Systeme sind flexibler als domänenspezische, aber letztere sind (mit geeignetem Expertenwissen) deutlich effzienter und damit in vielen Anwendungen unverzichtbar. Ziel dieses Projekts war es, den Abstand zwischen domänenunabhängigen und domänenspezischen Planungssystemen zu reduzieren, indem automatische Verfahren für die Erzeugung von Kontrollwissen und dessen Nutzung in einem domänenunabhängigen Planungssystem entwickelt werden. In Hinblick auf dieses Ziel wurden im Rahmen des Projektes folgende Fortschritte erzielt: 1. Es wurde ein verbindender Rahmen gefunden, in dem sich vormals als heterogen angesehene Klassen von Kontrollwissen (unter anderem: Invarianten, Landmarken und Zielordnungen) generalisieren lassen. Diese Generalisierung erlaubt eine homogene Behandlung dieser Arten von Wissen und bildet die Grundlage für eine uniforme Nutzung im Rahmen effzienter heuristischer Planungssysteme. 2. Eine Vielzahl existierender Verfahren zur Generierung von Invarianten, einer weiteren Klasse von Kontrollwissen, wurde im Rahmen des Projekts hinsichtlich ihrer Mächtigkeit untersucht, wobei sich zeigte, dass die Verfahren von Haslum und Geffner sowie von Rintanen zueinander äquivalent und beweisbar mächtiger als die anderen untersuchten Verfahren sind. Die Verwendung dieser Verfahren hat zu erheblichen Verbesserungen auf dem Gebiet der Handlungsplanung durch symbolische Suche geführt. 3. Die Verwendung von Landmarken, einer speziellen Art von Kontrollwissen, entwickelte sich während des Projektzeitraums zu einem wissenschaftlichen Durchbruch auf dem Gebiet der domänenunabhängigen Handlungsplanung, sowohl was praktische Verfahren für die optimale oder suboptimale Lösung von Planungsaufgaben als auch was die zugrunde liegende Theorie der Handlungsplanung betrifft. An diesem Durchbruch war das Projekt mit einer Reihe von Publikationen im Zusammenhang mit der Landmarken-Schnitt-Heuristik massgeblich beteiligt.
Publications
- Optimal Planning for Delete-free Tasks with Incremental LM-cut. In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), pp. 363-367, 2012
Florian Pommerening and Malte Helmert
- Incremental LM-Cut. In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 162-170, 2013
Florian Pommerening and Malte Helmert
- Safe, Strong and Tractable Relevance Analysis for Planning. In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), pp. 317-321, 2013
Patrik Haslum, Malte Helmert and Anders Jonsson
- Optimal Planning in the Presence of Conditional Effects: Extending LM-Cut with Context-Splitting. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pp. 765-770, 2014
Gabriele Röger, Florian Pommerening and Malte Helmert
