Ph.D Thesis

Ph.D StudentKeren Sarah
SubjectGoal Recognition Design
DepartmentDepartment of Industrial Engineering and Management
Supervisors PROF. Avigdor Gal
Full Thesis textFull thesis text - English Version


Goal recognition is the task of understanding the goal of acting agents by the online observation of their behavior. Goal recognition design (GRD), presented here, facilitates goal recognition by the analysis and redesign of goal recognition models. In a nutshell, given a model of a domain and a set of possible goals, a solution to a GRD problem determines: (1) to what extent do actions, performed by an agent within the model, reveal the agent's objective? and (2) what is the best way to modify the model so that the objective of an agent is revealed as early as possible? GRD answers these questions by offering a solution for assessing and minimizing the maximal progress of any agent in the model before recognition is guaranteed. This approach is relevant to any domain for which quickly performing goal recognition is essential and in which the model design can be controlled. Applications include intrusion detection, assisted cognition, computer games, and human-robot collaboration.

Typically, a GRD problem has two components, namely the analyzed goal recognition setting and a design model, specifying the possible ways to modify the environment in which agents act in order to facilitate recognition. This work formulates a general framework for GRD and offers a toolbox of solutions for assessing and optimizing model quality for various GRD settings. Specifically, for evaluation, we suggest the worst case distinctiveness (WCD) measure, which represents the maximal cost of a path an agent can take in a system before his goal can be inferred by a goal recognition system.

For settings in which agents are bounded sub-optimal, we offer novel compilations to classical planning for calculating WCD. For minimizing WCD, we suggest methods to search for an optimal redesign strategy among the space of possible modifications and use pruning to increase efficiently. We support our approach by an empirical evaluation that measures WCD in a variety of GRD settings and the efficiency of our compilation-based methods for computing WCD. We also examine the ability to reduce WCD via redesign and the performance gain brought by our proposed pruning strategy.