Sequential plan recognition: An iterative approach to disambiguating between hypotheses

摘要

Plan recognition algorithms output hypotheses about an agent's plans from its observed actions. Due to imperfect knowledge about the agent's behavior and the environment, it is often the case that there are multiple hypotheses about an agent's plans that are consistent with the observations, though only one of these hypotheses is correct. This paper addresses the problem of how to disambiguate between hypotheses during the recognition process, by querying the acting agent about whether a given plan is part of the correct hypothesis. The main contribution is a sound and complete process for reducing the set of possible hypotheses called Sequential Plan Recognition (SPR). SPR iteratively queries the user and revises the set of possible hypotheses according to the outcome of the query. Several policies are provided for choosing which plans to query the agent. These policies address the problem of how to reduce the number of hypotheses during the recognition process using a minimal number of queries. The proposed policies include policies that use maximum likelihood and information gain measures.