h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Optimal planning modulo theories



Verantwortlichkeitsangabevorgelegt von Francesco Leofante, Master of Science

ImpressumAachen 2020

Umfang1 Online-Ressource (96 Seiten) : Illustrationen, Diagramme


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

  1. Lehrstuhl für Informatik 2 (Softwaremodellierung und Verifikation) (121310)
  2. Fachgruppe Informatik (120000)

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:
Download fulltext 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

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Publication server / Open Access
Faculty of Computer Science (Fac.9)
Public records
Publications database
120000
121310

 Record created 2020-06-09, last modified 2023-04-11


OpenAccess:
Download fulltext PDF
(additional files)
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)