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

Der Zweck der automatischen Handlungsplanung ist es, automatisch eine Aktionsabfolge zu finden, welche den aktuellen Zustand der Welt in einen gewünschten Zielzustand transformiert. Die verfügbaren Aktionen, der aktuelle Zustand der Welt sowie die Zielbeschreibung sind als Teil des Modells gegeben. In der klassischen Handlungsplanung haben alle Aktionen einheitliche Kosten. Während dieses Modell relativ gut verstanden ist, gilt dasselbe für viele sinnvolle Erweiterungen nicht. In diesem Projekt wollen wir die Verallgemeinerung auf Aktionen untersuchen, deren Kosten von dem Zustand abhängen, in dem sie angewandt werden. Diese Verallgemeinerung ist aus der Perspektive eines Domänenmodellierers wegen ihrer Natürlichkeit und geringen Fehleranfälligkeit bedeutsam, während sie aus Berechnungssicht wichtig ist, da Algorithmen nun vorhandene Struktur in Kostenfunktionen ausnützen können. Ferner haben zustandsabhängige Aktionskosten Anwendung in der Handlungsplanung selbst und in benachbarten Feldern, wie etwa beim Planen mit Präferenzen, beim numerischen Planen, und beim Lösen von MDPs, falls die Reward-Funktionen zustandsabhängig sind.Eine bedeutende Herausforderung besteht darin, solche Kosten akkurat innerhalb von Zieldistanz-Heuristiken widerzuspiegeln. In früheren Arbeiten konnten wir zeigen, dass dieser Herausforderung begegnet werden kann, indem man Kostenfunktionen als spezielle Entscheidungsdiagramme, sogenannte kantenbewertete mehrwertige Entscheidungsdiagramme (EVMDDs) repräsentiert. Wir konnten zeigen, dass dieser Ansatz zu informativen und nützlichen Heuristikfunktionen führt.Es bestehen jedoch noch eine Reihe offener Fragen im Zusammenhang mit dem Planen mit zustandsabhängigen Aktionskosten: erstens ist die Größe eines solchen Kosten-EVMDDs im schlechtesten Fall exponentiell in der Anzahl der Zustandsvariablen, von denen die Kostenfunktion abhängt; zweitens wurden viele klassische Heuristiken noch nicht in diesem Zusammenhang untersucht, und Heuristikwerte können unnötigerweise uninformativ werden, wenn das Zusammenspiel zwischen zustandsabhängigen Kosten und bedingten Effekten nicht angemessen berücksichtigt wird. In diesem Projekt werden wir uns mit diesen Fragen beschäftigen, indem wir statische und dynamische Variablenordnungen für EVMDDs sowie sogenannte EVMDD-Relaxierungen untersuchen, Heuristiken und ihre Invarianz unter Kompilierungen studieren, und eine uniforme Behandlung von zustandsabhängigen Kosten und bedingten Effekten betrachten.

• DFG-Verfahren: Sachbeihilfen
• Mitverantwortlich: Professor Dr. Bernhard Nebel