Recognizing Teams and Their Plans: General Plan Recognition in Multi-Agent Domains

摘要

The ability to observe the actions of individual agents and from those to infer which are working together as teams and what they are attempting to accomplish is the focus of Multi- Agent Plan Recognition (MAPR) research. MAPR is a subset of the Plan, Activity, and Intent Recognition (PAIR) research topic in Artificial Intelligence (AI). Most current MAPR solutions tend to target recognizing activities in specific domains, rely on matching observations to human generated libraries of "sequences to look for", depend on base rates, and/or forensically analyzing the structures of complete synchronized traces. Our contributions avoid all of these simplifications to the MAPR challenge while focusing on persistent non-interfering teams and team-level goal-oriented plans.;In this research, we extend MAPR research by introducing three new recognition algorithms that are application independent (i.e., general), match observations to planning domain descriptions, and provide on-line recognitions after every serial observation. Our initial algorithm, Event Sequence Alignment (ESA) generates its own plan library and compares it to observations. Our second and third algorithms extend Plan Recognition as Planning (PRAP) to multiple agents with discrete and probabilistic versions of Multi-Agent PRAP (MAPRAP). For each algorithm we detail its design and evaluate its recall, precision, and accuracy as a function of time (i.e., observations) and across three multi-agent domains. We introduce our framework for evaluating and several methods for predicting performance.;Our results show that when agent traces are optimal, MAPRAP and P-MAPRAP achieve perfect recall over the entire trace, ensuring that early-stage recognition does not miss the correct interpretation, and increasing accuracy and precision levels. For ESA, we show previously unreported challenges with a prior plan libraries that are amplified with multiagent scheduling. For P-MAPRAP we evaluate online MAPR in non-ideal condition such as dropped observations and suboptimal team plans. We present differences in recognition approach, domain, team compositions, and degree of error.