Hierarchical planning under uncertainty

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.