Critically Constrained Planning durch partielle Delete-Relaxierung
Zusammenfassung der Projektergebnisse
Planen ist eines der fundamentalen Teilgebiete der KI. Planungstechnologien lösen eine breite Palette von Problemen, und vereinfachen so die Entwicklungsarbeit erheblich: anstelle 1000er Zeilen Programmcode genügt ein wenige Zeilen grosses Planungsmodell. Aufgrund dramatischer Fortschritte wurde die industrielle Verwendung solcher Techniken um das Jahr 2000 realistisch. Die Kerntechnik sind sogenannte ”delete-relaxation” Heuristiken. Diese schätzen den Abstand zum Ziel mittels einer relaxierten Planungsaufgabe, in der alle negativen Aktionseffekte ignoriert werden. Varianten dieser Technik sind heute weit verbreitet. Trotzdem haben delete-relaxation Heuristiken ernste Schwächen. In vielen Planungsanwendungen müssen unerwünschte Seiteneffekte, wie z.B. Benzinverbauch, begrenzt werden. Die delete relaxation ignoriert solche Seiteneffekte, mit dramatischen Folgen für “kritische” Probleme nahe an der Schwelle zur Unlösbarkeit: keine bisher bekannte Methode konnte hiermit effektiv umgehen. Das Projekt untersuchte zur Lösung dieser Problematik “partial delete relaxation” Techniken, die es erlauben, nahtlos zwischen vollständiger Relaxierung und unrelaxiertem Planen zu interpolieren. Das Projekt trug zwei Techniken dieser Art bei, basierend auf “red-black relaxation”, wo nur eine Teilmenge der Zustandsvariablen relaxiert wird, bzw. auf atomaren Konjunktionen, wo explizit gemacht wird, dass bestimmte Dinge gleichzeitig erreicht werden müssen. Wesentliche Ergebnisse des Projektes sind, unter anderem: die umfassende Erforschung von red-black relaxation Methoden, sowohl um Pläne zu finden als auch um zu beweisen, dass kein Plan existiert; elegante Methoden für “nogood learning” aus unlösbaren Zuständen in einer Zustandsraumsuche, durch Zufügen neuer atomarer Konjunktionen; Verfeinerung von Heuristiken auf lokalen Minima während der Suche, und somit lokale Suchverfahren mit Vollständigkeitsgarantie; sowie Kombinationen dieser Methoden und ein neuer Stand der Kunst im effektiven Finden von Plänen. Wie vorhergesehen werden auch und vor allem kritische Probleme erheblich effizienter gelöst. Dies ist insbesondere für nogood learning der Fall, weshalb diese Methode in Abweichung vom ursprünglichen Projektantrag besonders gründlich erforscht wurde. Das Projekt war wissenschaftlich extrem erfolgreich. Insgesamt publizierte die Arbeitsgruppe des Antragstellers zu den Projektthemen 5 Artikel in international angesehenen Fachzeitschriften und 22 Beitrage in ebensolchen Konferenzen.
