Date of Award
Doctor of Philosophy (PhD)
Goal Recognition Design (GRD) is the problem of finding the least amount of environment modifications to force an acting agent to reveal its goal as early as possible. Figuring out an agent’s goal by observing its behavior is a problem studied in Psychology, Economics, and Artificial Intelligence, where it is known as goal recognition. Contrary to most common approaches where the focus is on finding faster algorithms to detect the goal, GRD takes an offline approach and focuses on environment design to facilitate goal recognition. This thesis investigates GRD problems when action outcomes are stochastic, which is the case of most physical world interactions. I propose the Stochastic GRD (S-GRD) problem and study its specific characteristics, challenges, and limitations. Under this umbrella, we analyze partially-observable and suboptimal cases and provide a novel way to redesign the environment for partially-observable settings. This thesis presents the problem formulation and novelalgorithms to solve the problem. Additionally, empirical evaluations show that S-GRD helps reduce the complexity of a goal recognition problem in all cases.
Chien-Ju Ho, Erez Karpas, Alvitta Ottley, Yevgeniy Vorobeychik,