Plan-based plan recognition models for the effective coordination of agents through observation.

Abstract

Our research is aimed at providing agents with the ability to use observations of actions taken by others not only to recognize current actions but also to infer ongoing plans and goals, a process called plan recognition. Once our agents can recognize the plans and goals of others, they can then employ a number of techniques for coordinating their planned actions with those of others. Multi-agent coordination has typically been performed using explicit communication between agents. Plan recognition offers several potential advantages over explicit communication however, including lower communication overhead, higher reliability, greater information content, and robustness in the face of agents who are not forthcoming about their plans. On the other hand, it also has potential disadvantages, including the fact that agents need to know how other agents act in pursuit of their goals, that actions might not be accurately observable or might support multiple possible plans, and that inferring the plans of others can be more time consuming than being told explicitly by them. In this research, we have developed a probabilistic plan recognition model called a plan recognition network (PRN) and a computational system called ASPRN (Automated Synthesis of Plan Recognition Networks) that can automatically construct a PRN from a plan model. PRNs provide an observing agent with a wide range of inferred information and handle the uncertainty associated with plan recognition and observations in a natural, robust manner. We demonstrate that plan recognition can be done in a competitive, real-time, simulated environment such that plan recognizing agents win up to 90% of the time, despite the inherent overhead and uncertainty of the recognition process. Our experiments reveal that even though PRNs provide numeric information, they may currently be more amenable to symbolic reasoning method than decision-theoretic approaches. Other experiments highlight that waiting for plan recognition information to become more certain before acting upon it reduces coordination performance because of the delay before imitation of coordination activities. Analysis of our experiments also highlights that the temporal distribution of observations while performing plan recognition has a distinctly negative impact upon the observing agent's ability to effectively coordinate as the distribution is pushed later toward the end of plan execution. Lastly, our experiments show us that coordinating agents can take advantage of plans with early plan disambiguation points and that plans with late plan disambignation points may hinder effective plan recognition-based coordination.