Improving observation-based modeling of other agents using tentative stereotyping and compactification through kd-tree structuring

Article type: Research Article

Authors: Denzinger, Jörg | Hamdan, Jasmine

Affiliations: Department of Computer Science, University of Calgary, 2500 University Drive, Calgary, AB, Canada, T2N 1N

Note: [] Corresponding author. Tel.: +1 403 241 6315; Fax: +1 403 284 4707; E-mail: [email protected]

Abstract: In this paper, we propose two improvements to modeling other agents based on Observed Situation-Action Pairs and the Nearest Neighbor Rule – reevaluative stereotyping with switching and compactification of observations through kd-tree structuring and the Pseudo-Approximate Nearest Neighbor search. On the one hand, tentative stereotype models allow for good predictions of a modeled agent's behavior even after few observations. Periodic reevaluations of the chosen stereotype and of the stereotyping process itself, in addition to the potential for switching between different stereotypes or to the observation based model aids in dealing with very similar (but not identical) stereotypes and agents that do not conform to any stereotype. On the other hand, reducing comparisons for the Nearest Neighbor Rule by observation compactification keeps the application of the model efficient even after many observations have been made. Our experiments show that tentative stereotyping significantly improves cases in which the original method performs badly and that reevaluations and switching fortify stereotyping against the potential risk of using an incorrect stereotype. For compactification, our experiments show that using the kd-tree for compactifying observations and the Pseudo-Approximate Nearest Neighbor search for retrieving a Nearest Neighbor improves modeling efficiency when observations are abundant, but is sometimes coupled with a loss of accuracy.

Keywords: Opponent modeling, learning of cooperative behavior, case-based reasoning

Journal: Web Intelligence and Agent Systems: An international journal, vol. 4, no. 3, pp. 255-270, 2006