Sequential plan recognition: An iterative approach to disambiguating between hypotheses

Reuth Mirsky, Roni Stern, Yakov Gal, Meir Kalech

Research output: Contribution to journalArticlepeer-review

Abstract

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.
The paper provides a complexity analysis of the SPR process and the proposed query policies. It demonstrate its efficiency on two known domains from the literature, describing how performance and runtime are affected by features in the domain. Our results can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users
Original languageEnglish
Pages (from-to)51-73
Number of pages23
JournalArtificial Intelligence
Volume260
Early online date3 Apr 2018
DOIs
Publication statusPublished - 1 Jul 2018

Fingerprint

Dive into the research topics of 'Sequential plan recognition: An iterative approach to disambiguating between hypotheses'. Together they form a unique fingerprint.

Cite this