Using Recursive Agent Models Effectively

José M. Vidal and Edmund H. Durfee

This paper is also available in a PostScript version that includes the missing pictures.

Abstract:

We present an algorithm that an agent can use for determining which of its nested, recursive models of other agents are important to consider when choosing an action. Pruning away less important models allows an agent to take its ``best'' action in a timely manner, given its knowledge, computational capabilities, and time constraints. We describe a theoretical framework, based on situations, for talking about recursive agent models and the strategies and expected strategies associated with them. This framework allows us to rigorously define the gain of continuing deliberation versus taking action. The expected gain of computational actions is used to guide the pruning of the nested model structure. We have implemented our approach on a canonical multi-agent problem, the pursuit task, to illustrate how real-time, multi-agent decision-making can be based on a principled, combinatorial model. Test results show a marked decrease in deliberation time while maintaining a good performance level.

• Introduction
  • The Recursive Modeling Method
  • Limited Rationality
  • The Pursuit Task
• Theory
  • Notation and Formalisms
• Algorithm
  • Time Analysis
  • Implementation Strategies
• Implementation of Pursuit Task
  • Results
• Conclusions
• References