Assimilation in Plan Recognition via Truth Maintenance with Reduced Redundancy

Description

Plan recognition is the recognition of an agent's plan from the agent's actions. Recognizing the agent's plan can help predict the agent's next action; in a natural language setting it can help to form a cooperative response. Most artificial intelligence research into plan recognition relies on a complete set of pre-stored plans, a form of the closed world assumption. Faced with a novel plan, these systems simply fail. Our approach for giving up this assumption entails (1) providing new planning information on demand, and (2) incorporating the new information into the candidates that are proposed as the agent's current plan. We focus on task (2). Most plan recognition settings require timely responses. So as new information is provided, the candidates should be be repaired rather than recalculated. We found that existing truth maintenance systems, such as de Kleer's ATMS, were unsuitable for candidate repair. They introduce extra search and redundancy to handle the disjunctions that arise in plan recognition. We provide a refinement of linear resolution that reduces redundancy in general. Based on this refinement we provide a new truth maintenance system that does not introduce extra search or redundancy. We then use this truth maintenance system as the basis for a plan recognition system which incorporates novel information through candidate repair.