Goal and Plan Recognition Design for Plan Libraries
Open Access
- 23 January 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Intelligent Systems and Technology
- Vol. 10 (2) , 1-23
Abstract
This article provides new techniques for optimizing domain design for goal and plan recognition using plan libraries. We define two new problems: Goal Recognition Design for Plan Libraries (GRD-PL) and Plan Recognition Design (PRD). Solving the GRD-PL helps to infer which goal the agent is trying to achieve, while solving PRD can help to infer how the agent is going to achieve its goal. For each problem, we define a worst-case distinctiveness measure that is an upper bound on the number of observations that are necessary to unambiguously recognize the agent’s goal or plan. This article studies the relationship between these measures, showing that the worst-case distinctiveness of GRD-PL is a lower bound of the worst-case plan distinctiveness of PRD and that they are equal under certain conditions. We provide two complete algorithms for minimizing the worst-case distinctiveness of plan libraries without reducing the agent’s ability to complete its goals: One is a brute-force search over all possible plans and one is a constraint-based search that identifies plans that are most difficult to distinguish in the domain. These algorithms are evaluated in three hierarchical plan recognition settings from the literature. We were able to reduce the worst-case distinctiveness of the domains using our approach, in some cases reaching 100% improvement within a predesignated time window. Our iterative algorithm outperforms the brute-force approach by an order of magnitude in terms of runtime.Keywords
This publication has 13 references indexed in Scilit:
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- Visualizing expert solutions in exploratory learning environments using plan recognition2014
- Plan Recognition and Visualization in Exploratory Learning EnvironmentsACM Transactions on Interactive Intelligent Systems, 2013
- The ChemCollective—Virtual Labs for Introductory Chemistry CoursesScience, 2010
- A probabilistic plan recognition algorithm based on plan tree grammarsArtificial Intelligence, 2009
- Towards Collaborative Intelligent Tutors: Automated Recognition of Users’ Strategies2008
- Generating Artificial Corpora for Plan RecognitionLecture Notes in Computer Science, 2005
- The lexical nature of syntactic ambiguity resolution.Psychological Review, 1994
- Deterministic parsing of ambiguous grammarsCommunications of the ACM, 1975
- Strips: A new approach to the application of theorem proving to problem solvingArtificial Intelligence, 1971