Date of Award

Winter 2014

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml

Second Advisor

Radim Bartos

Third Advisor

R. D. Bergeron

Abstract

In real-time heuristic search, a search agent must simultaneously find and execute a solution to a search problem with a strict time bound on the duration between action emissions and thus the duration of search between said emissions. Because these searches are required to emit actions before their desirability can be guaranteed, resulting solutions are typically sub-optimal in regards to total solution cost, but often superior in terms of the time from start of search to arrival at the goal. Metareasoning is the process of deliberating about the search process, including where to focus it and when to do it. Many modern real-time searches optimistically (and somewhat naively) direct the search agent to some state for which the estimated total solution cost appears low at the end of the most recent iteration of search. By employing metareasoning practices, we can hope to replace this optimism with an appropriate amount of skepticism, embracing the already sub-optimal nature of real-time search in such a way that known or expected sub-optimal actions are taken in an effort to direct the agent more effectively in the future. In this thesis we pursue this research direction by presenting and analyzing previous search algorithms and then proposing several metareasoning approaches which show promise in the form of both empirical results and rationalized intuition for minimizing the expected time until arrival at the goal. We evaluate the performance of these approaches thoroughly in order to highlight their strengths and their failings. Finally, we present a number of issues in metareasoning in real-time search which came to light in researching this topic, with the intent of guiding future research along promising avenues.

Download

Share

COinS