RI | Publications | Hypothesis Pruning and Ranking for Large Plan Recognition Problems

Text only version of this site

Hypothesis Pruning and Ranking for Large Plan Recognition Problems
G. Sukthankar and K. Sycara
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08), June, 2008.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [139 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

This paper addresses the problem of plan recognition for multi-agent teams. Complex multi-agent tasks typically require dynamic teams where the team membership changes over time. Teams split into subteams to work in parallel, merge with other teams to tackle more demanding tasks, and disband when plans are completed. We introduce a new multi-agent plan representation that explicitly encodes dynamic team membership and demonstrate the suitability of this formalism for plan recognition. From our multi-agent plan representation, we extract local temporal dependencies that dramatically prune the hypothesis set of potentially-valid team plans. The reduced plan library can be efficiently processed to obtain the team state history. Naive pruning can be inadvisable when low-level observations are unreliable due to sensor noise and classification errors. In such conditions, we eschew pruning in favor of prioritization and show how our scheme can be extended to rank-order the hypotheses. Experiments show that this robust pre-processing approach ranks the correct plan within the top 10%, even under conditions of severe noise.

Notes

Sponsor: Army Research Labs
Grant ID: W911NF-06-3-0001

Associated center: CIMDS
Associated lab/group: Intelligent Software Agents
Associated projects: IBM ITA: Human-Agent Teamwork Models and AFOSR PRET: Information Fusion for Command and Control: The Translation of Raw Data To Actionable Knowledge and Decision

Number of pages: 6

Text Reference

G. Sukthankar and K. Sycara, "Hypothesis Pruning and Ranking for Large Plan Recognition Problems," Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08), June, 2008.

BibTeX Reference

@inproceedings{Sukthankar_2008_6133,
   author = "Gita Sukthankar and Katia Sycara",
   title = "Hypothesis Pruning and Ranking for Large Plan Recognition Problems",
   booktitle = "Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08)",
   month = "June",
   year = "2008"
}