2020
Dissertation, RWTH Aachen University, 2020
Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
;
Tag der mündlichen Prüfung/Habilitation
2020-05-14
Online
DOI: 10.18154/RWTH-2020-06076
URL: https://publications.rwth-aachen.de/record/792387/files/792387.pdf
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
automation (frei) ; optimisation (frei) ; planning (frei) ; satisfiability checking (frei)
Thematische Einordnung (Klassifikation)
DDC: 004
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.Planning for real-world applications requires algorithms and tools with the ability to handle the complexity such scenarios entail. However, meeting the needs of such applications poses substantial challenges, both representational and algorithmic. On the one hand, expressive languages are needed to build faithful models. On the other hand, efficient solving techniques that can support these languages need to be devised. A response to this challenge is underway, and the past few years witnessed a community effort towards more expressive languages, including decidable fragments of first-order theories. In this work we focus on planning with arithmetic theories and propose Optimal Planning Modulo Theories, a framework that attempts to provide efficient means of dealing with such problems. Leveraging generic Optimization Modulo Theories (OMT) solvers, we first present domain-specific encodings for optimal planning in complex logistic domains. We then present a more general, domain-independent formulation that allows to extend OMT planning to a broader class of well-studied numeric problems in planning. To the best of our knowledge, this is the first time OMT procedures are employed in domain-independent planning.
OpenAccess:
PDF
(additional files)
Dokumenttyp
Dissertation / PhD Thesis
Format
online
Sprache
English
Externe Identnummern
HBZ: HT020487499
Interne Identnummern
RWTH-2020-06076
Datensatz-ID: 792387
Beteiligte Länder
Germany
|
The record appears in these collections: |