Hierarchical planning under uncertainty

Erstveröffentlichung
2018-01-05Authors
Richter, Felix
Referee
Biundo-Stephan, SusanneSchwenker, Friedhelm
Dissertation
Faculties
Fakultät für Ingenieurwissenschaften, Informatik und PsychologieInstitutions
Institut für Künstliche IntelligenzInstitut für Neuroinformatik
Abstract
The recent years have seen significant progress in the fields of computer science and the engineering sciences, leading to a plethora of systems and services aimed at simplifying the organization of everyday life. The great potential of these utilities is however hindered by their complexity as well as the complexity of their interplay. Automated assistance systems can help users overcome this challenge.
At the core of these systems lies planning functionality, needed for automatically generating courses of action, or policies, that represent, e.g., step-by-step instructions. Often, planning requires accounting for uncertainty inherent in a given application domain, making the process of generating such instructions computationally difficult. Fortunately, many assistance tasks exhibit hierarchical structure that allows understanding planning tasks as a hierarchy of subtasks, each of which can be solved using a limited number of solution recipes. The Hierarchical Task Network planning approach can already exploit such structures in deterministic planning domains by representing subtasks and recipes using abstract actions and methods, respectively, and generating plans by iteratively refining an initial abstract plan.
The main goal of this thesis is to create a similar planning approach suited for planning domains that exhibit uncertainty, modeled as Partially Observable Markov Decision Processes. Based on a newly introduced suitable policy representation formalism called logical finite state controllers, the concepts of abstract actions and methods are reintroduced to create the Partially Observable Hierarchical Task Network planning approach. Next, Monte-Carlo tree search in the space of partially abstract controllers is identified as a suitable means for planning. The approach is then empirically evaluated on four domains by comparing it to search in the space of histories, a state-of-the-art non-hierarchical planning approach also based on Monte-Carlo tree search. This reveals that, with comparable computational effort, the proposed approach leads to policies of superior quality, and that it scales well with problem size.
Two further techniques are then proposed enhance the presented approach: one that further reduces the required controller construction effort during search by refining controllers only selectively where required, and one that combines hierarchical and non-hierarchical search in order to combine the advantages of both.
Date created
2017
DFG Project THU
TRR 62 / Eine Companion-Technologie für kognitive technische Systeme / DFG / 54371073
Subject headings
[GND]: Künstliche Intelligenz | Mensch-Maschine-Kommunikation[LCSH]: Uncertainty; Mathematical models | Computer networks; Planning | Artifical intelligence | Human-computer interaction
[Free subject headings]: POMDPs | Hierarchical planning | HTN planning | Finite state controllers | Monte-Carlo tree search
[DDC subject group]: DDC 004 / Data processing & computer science
Metadata
Show full item recordDOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-5243
Richter, Felix (2018): Hierarchical planning under uncertainty. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-5243
Citation formatter >