Critically Constrained Planning durch partielle Delete-Relaxierung

• Antragsteller: Professor Dr. Jörg Hoffmann
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2014 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 252282745

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, von erfolgreichen Forschungsprototypen bis zur Anwendung.Trotzdem haben delete-relaxation Heuristiken ernste Schwächen. Viele Planungsanwendungen sind "constrained", unerwünschte Seiteneffekte (wie Benzinverbauch) müssen limitiert werden. Die delete-relaxation kann dies nicht berücksichtigen. Die Folgen sind dramatisch für Probleme ("critically constrained") bei denen das Limit nah an der Schwelle zur Unlösbarkeit ist: Keine der bekannten Approximationen liefert hier wertvolle Informationen, und die Suche wird im wesentlichen blind. Unser Ziel ist es, die Performanz auf solchen Problemen zu verbessern, insbesondere für unlösbare Probleme, was bisher in der Planungsforschung vernachlässigt wurde. Zu diesem Zweck untersuchen wir Techniken, die es erlauben, gleichmässig zwischen voll-relaxiertem (keine deletes) und unrelaxiertem (alle deletes) Planen zu interpolieren.Wie solche "partial delete relaxation" zu bewerkstelligen ist war 10 Jahre lang offen, und wurde in den Vorarbeiten des Antragstellers beantwortet. "Conjuncts compilation" berechnet delete-relaxation Heuristiken innerhalb einer kompilierten Planungsaufgabe, in der eine ausgewählte Menge C von Konjunktionen explizit repräsentiert ist. "Red-black planning" relaxiert nur eine Teilmenge der Zustandsvariablen. Vor Beginn dieses Projektes waren beide Methoden vielversprechend, ihr Potenzial jedoch bei weitem nicht ausgeschöpft. Das Projekt zielt darauf ab, dieses zu tun. Während der ersten Bewilligungsphase wurde erarbeitet: ein besseres Verständnis von conjuncts compilation; erfolgreiche online C-learning Methoden; red-black planning Methoden zum Nachweisen von Unlösbarkeit; und eine Verbindung zum Erkennen von Sackgassen im probabilistischen Planen. Die vorgeschlagene Projektverlängerung (i) komplettiert unsere Basismethoden durch "variable merging" sowie eine neue Generalisierung von red-black planning, "trace-memory variable relaxation"; (ii) entwickelt "sparse search methods" welche akkurate Approximationen als Templates, anstelle heuristischer Funktionen, verwenden, und welche Unlösbarkeit nachweisen durch die intelligente Verwendung von schweren vs. leichten Approximationen; (iii) untersucht Anwendungen über klassisches Planen hinaus, im over-subscription planning sowie in der Analyse von Zielerreichbarkeits-Wahrscheinlichkeit.

• DFG-Verfahren: Sachbeihilfen