Plan recognition algorithms infer agents' plans from their 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, by querying the acting agent about whether a candidate plan in one of the hypotheses matches its intentions. This process is performed sequentially and used to update the set of possible hypotheses during the recognition process. The paper defines the sequential plan recognition process (SPRP), which seeks to reduce the number of hypotheses using a minimal number of queries. We propose a number of policies for the SPRP which use maximum likelihood and information gain to choose which plan to query. We show this approach works well in practice on two domains from the literature, significantly reducing the number of hypotheses using fewer queries than a baseline approach. Our results can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.
■ Automated planning technology has become mature enough to be useful in applications that range from game playing to control of space vehicles. In this article, Dana Nau discusses where automated-planning research has been, where it is likely to go, where he thinks it should go, and some major challenges in getting there. The article is an updated version of Nau’s invited talk at AAAI-05 in Pittsburgh, Pennsylvania. Recent applications of plan recognition face several open challenges: (i) matching observations to the plan library is costly, especially with complex multi-featured observations; (ii) computing recognition hypotheses is expensive. We present techniques for addressing these challenges. First, we show a novel application of machine-learning decision-tree to efficiently map multi-featured observations to matching plan steps. Second, we provide efficient lazy-commitment recognition algorithms that avoid enumerating hypotheses with every observation, instead only carrying out bookkeeping incrementally. The algorithms answer queries as to the current state of the agent, as well as its history of selected states. We provide empirical results demonstrating their efficiency and capabilities. 