Date of Award

Winter 2018

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml

Second Advisor

Marek Petrik

Third Advisor

Joerg Hoffmann

Abstract

In real-time planning, an agent must select the next action to take within a fixed time bound.

Many popular real-time heuristic search methods approach this by expanding nodes using time-limited A* and selecting the action leading toward the frontier node with the lowest f value. In this thesis, we reconsider real-time planning as a problem of decision-making under uncertainty. We treat heuristic values as uncertain evidence and we explore several backup methods for aggregating this evidence. We then propose a novel lookahead strategy that expands nodes to minimize risk, the expected regret in case a non-optimal action is chosen. We evaluate these methods in a simple synthetic benchmark and the sliding tile puzzle and find that they outperform previous methods. This work illustrates how uncertainty can arise even when solving deterministic planning problems, due to the inherent ignorance of time-limited search algorithms about those portions of the state space that they have not computed, and how an agent can benefit from explicitly meta-reasoning about this uncertainty.

Download

Share

COinS