Effizientes Planen mit zustandsabhängigen Aktionskosten

• Antragsteller: Dr. Robert Mattmüller
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 405834399

• Erstellungsjahr: 2022

Zusammenfassung der Projektergebnisse

Planung ist die Kunst und Praxis des Denkens vor dem Handeln und ist ein zentrales Gebiet in der Künstlichen Intelligenz. Bei der klassischen Planung besteht das Ziel darin, einen Handlungsablauf zu finden, der es einem intelligenten Agenten ermöglicht, aus jeder Situation, in der er sich befindet, in eine Situation zu gelangen, die seine Ziele erfüllt. Während in der probabilistischen Planung und anderen Planungsformalismen eine prägnante Kodierung von Handlungskosten oder Belohnungen seit langem Standard ist, ist es in der klassischen Planung üblich, eine potentiell exponentiell größere Repräsentation mit fixen Handlungskosten zu betrachten. Mit dem von der DFG geförderten Projekt EPSDAC wollten wir diese Lücke schließen, indem wir die Planung mit zustandsabhängigen Kosten untersuchten und effiziente Methoden zur Generierung von Handlungsplänen unter Berücksichtigung solcher Handlungskostenfunktionen entwickeln. Im Laufe des Projekts haben wir eine umfassende Klassifikation der Kompilierbarkeit und Nicht-Kompilierbarkeit von zustandsabhängigen Handlungskosten für Kombinationen von Handlungskostenfunktionen und möglichen Kostenmaßen für die Kompilationen aufgestellt und gezeigt, dass es hilfreich oder sogar notwendig sein kann, diese nicht wegzukompilieren, sondern im Modell zu belassen und nativ in Algorithmen zu unterstützen. Unter Berücksichtigung dieses theoretischen Ergebnisses haben wir untersucht, wann und wie komplexe Handlungskostenfunktionen auftreten können, mit dem Ergebnis, dass abgeleitete Prädikate in der Praxis oft solche komplexen Kostenfunktionen verursachen. Darüber hinaus haben wir empirisch untersucht, welche Auswirkungen die Berücksichtigung bzw. Nichtberücksichtigung zustandsabhängiger Handlungskosten hat, mit dem Ergebnis, dass die Lösungsqualität stark von der Domäne abhängt. Unter Berücksichtigung der zustandsabhängigen Kosten haben wir eine teilmengengesättigte Transitionskostenpartitionierung eingeführt, bei der die Kosten direkt den Transitionen zugeordnet werden und somit zustandsabhängig sind. Die daraus resultierenden Heuristiken sind empirisch informativer als andere kostenpartitionierte Heuristiken. Schließlich haben wir die symbolische Suche auf der Basis von Entscheidungsdiagrammen als State-of-the-Art-Technik für die Planung mit zustandsabhängigen Handlungskosten entwickelt und etabliert. Das Projekt war ein durchschlagender Erfolg in Bezug auf die wissenschaftlichen Ergebnisse: 13 von Experten begutachtete Veröffentlichungen auf hochrangigen internationalen Konferenzen, 4 von Experten begutachtete Workshop-Publikationen und 3 angemeldete Patente, die aus der Arbeit an den Projektthemen resultieren.

Projektbezogene Publikationen (Auswahl)

• An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning. Lecture Notes in Computer Science, 123-130. Springer International Publishing.
  Corraya, Sumitra; Geißer, Florian; Speck, David & Mattmüller, Robert
  
• Symbolic Planning with Axioms. Proceedings of the International Conference on Automated Planning and Scheduling, 29, 464-472.
  Speck, David; Geißer, Florian; Mattmüller, Robert & Torralba, Álvaro
  
• Symbolic Top-k Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9967-9974.
  Speck, David; Mattmüller, Robert & Nebel, Bernhard
  
• When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 30, 263-271.
  Speck, David; Geißer, Florian & Mattmüller, Robert
  
• Learning Heuristic Selection with Dynamic Algorithm Configuration. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 597-605.
  Speck, David; Biedenkapp, André; Hutter, Frank; Mattmüller, Robert & Lindauer, Marius
  
• On the Compilability and Expressive Power of State-Dependent Action Costs. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 358-366.
  Speck, David; Borukhson, David; Mattmüller, Robert & Nebel, Bernhard
  
• Subset-Saturated Transition Cost Partitioning. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 131-139.
  Drexler, Dominik; Seipp, Jendrik & Speck, David
  
• Symbolic Search for Optimal Total-Order HTN Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11744-11754.
  Behnke, Gregor & Speck, David
  
• Symbolic Search for Oversubscription Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11972-11980.
  Speck, David & Katz, Michael
  
• Trial-Based Heuristic Tree Search for MDPs with Factored Action Spaces. Proceedings of the International Symposium on Combinatorial Search, 11(1), 38-47.
  Geißer, Florian; Speck, David & Keller, Thomas