• English
    • Deutsch
  • English 
    • English
    • Deutsch
  • Login
View Item 
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Hierarchical planning under uncertainty

Thumbnail
dissertation_richter ... (5.881Mb)
Erstveröffentlichung
2018-01-05
Authors
Richter, Felix
Referee
Biundo-Stephan, Susanne
Schwenker, Friedhelm
Dissertation


Faculties
Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
Institutions
Institut für Künstliche Intelligenz
Institut 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
License
CC BY 4.0 International
http://creativecommons.org/licenses/by/4.0/

Metadata
Show full item record

DOI & 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 >



Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsPersonsInstitutionsPublication typesUlm SerialsDewey Decimal ClassesEU projects UlmDFG projects UlmOther projects Ulm

My Account

LoginRegister

Statistics

View Usage Statistics

Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement