Optimal planning modulo theories

Leofante, Francesco; Ábrahám, Erika (Thesis advisor); Tacchella, Armando (Thesis advisor)

Aachen (2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Die Lösung von Planungsproblemen für realistische Anwendungen erfordert Algorithmen und Programme, welche mit der inhärenten Komplexität umgehen können, die solche Anwendungen mit sich bringen. Die Erfüllung dieser Anforderungen stellt große Herausforderungen an sowohl Datentypen und Repräsentationen aber auch an die zu entwickelnden Algorithmen. Auf der einen Seite werden ausdrucksstarke Modellierungssprachen benötigt, um sinnvolle Modelle beschreiben zu können. Andererseits werden effiziente Lösungsverfahren benötigt, die mit der Ausdrucksstärke dieser Sprachen umgehen können. Die Forschungsgemeinschaft arbeitet an einer Antwort auf diese Herausforderungen, in den letzten Jahren konnte ein Bestreben zu ausdrucksstärkeren Modellierungssprachen, insbesondere zu entscheidbaren Fragmenten der Logiken erster Ordnung beobachtet werden. In dieser Arbeit konzentrieren wir uns auf Planungsprobleme unter arithmetischen Theorien und präsentieren einen Ansatz zur Optimalen Planung unter Theorien (OPT), welcher eine effiziente Herangehensweise an die Problemstellung verspricht. Der Ansatz nutzt generische Lösungsverfahren für Probleme aus dem Bereich "Optimierung unter Theorien" (OMT), als erstes stellen wir eine domänenspezifische Kodierung für optimale Planung in Logistik-Domänen vor. Anschließend präsentieren wir eine verallgemeinerte Darstellung, welche es erlaubt OPT-Planung auf eine breitere Klasse von wohlbekannten numerischen Planungsproblemen anzuwenden. Soweit wir wissen ist dies der erste Ansatz für die Lösung domänenunabhängiger Planungsprobleme, der auf OMT-Lösungsverfahren basiert.