Discovering tactical behavior patterns supported by topological structures in soccer agent domains

ABSTRACT

Behaviors in soccer-agent domains can involve individual plays, several players involved in tactical plays or the whole team trying to follow strategies supported by specific formations. The discovery of such behaviors needs the tracking of both the positions of players at any instant of the game and relevant relations able to represent particular interactions between players. Nevertheless, the tracking task becomes very complicated because the dynamic conditions of the game implying drastic changes of positions and interactions between players. We propose in this work a model able to manage the constant changes occurring in the game, which consists in building topological structures based on triangular planar graphs. Thus, based on this model tactical behavior patterns have been discovered even the dynamic conditions. Experimental results show that the proposed model is able to manage the constant changes of the world and discover tactical behaviors patterns. For that, an important number of matches have been analyzed from the RoboCup Simulation league.

REFERENCES

• 1: C. Berge. Graphes. Guathier-Villars, 1983.
• 2: Andraz Bezek , Matjaz Gams , Ivan Bratko, Multi-agent strategic modeling in a robotic soccer domain, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160717]
• 3: H. Freeman. On the encoding of arbitrary geometric configurations. In IRE Transactions, editor, 1973.
• 4: G. A. Kaminka, M. Fidanboylu, A. Chang, and M. M. Veloso. Learning the sequential coordinated behavior of teams from observations. In G. A. Kaminka, P. U. Lima, and R. Rojas, editors, RoboCup, volume 2752 of Lecture Notes in Computer Science, pages 111--125. Springer, 2002.
• 5: Hiroaki Kitano , Milind Tambe , Peter Stone , Manuela M. Veloso , Silvia Coradeschi , Eiichi Osawa , Hitoshi Matsubara , Itsuki Noda , Minoru Asada, The RoboCup Synthetic Agent Challenge 97, RoboCup-97: Robot Soccer World Cup I, p.62-73, January 1998
• 6: G. Kuhlmann, P. Stone, and J. Lallinger. The ut austin villa 2003 champion simulator coach: A machine learning approach. In D. Nardi, M. Riedmiller, C. Sammut, and J. Santos-Victor, editors, RobuCup, volume 3276 of Lecture Notes in Computer Science, pages 636--644. Springer, 2004.
• 7: A. D. Lattner, A. Miene, U. Visser, and O. Herzog. Sequential pattern mining for situation and behavior prediction in simulated robotic soccer. In A. Bredenfeld, A. Jacoff, I. Noda, and Y. Takahashi, editors, RoboCup, volume 4020 of Lecture Notes in Computer Science, pages 118--129. Springer, 2005.
• 8: Ranjit Nair , Milind Tambe , Stacy Marsella , Taylor Raines, Automated Assistants for Analyzing Team Behaviors, Autonomous Agents and Multi-Agent Systems, v.8 n.1, p.69-111, January 2004 [doi>10.1023/B:AGNT.0000009411.79208.f4]
• 9: Taylor Raines , Milind Tambe , Stacy Marsella, Automated Assistants to Aid Humans in Understanding Team Behaviors, RoboCup-99: Robot Soccer World Cup III, p.85-102, January 2000
• 10: Luís Paulo Reis , Nuno Lau , Eugenio Oliveira, Situation Based Strategic Positioning for Coordinating a Team of Homogeneous Agents, Balancing Reactivity and Social Deliberation in Multi-Agent Systems, From RoboCup to Real-World Applications (selected papers from the ECAI 2000 Workshop and additional contributions), p.175-197, January 2001
• 11: Ubbo Visser , Christian Drücker , Sebastian Hübner , Esko Schmidt , Hans-Georg Weland, Recognizing Formations in Opponent Teams, RoboCup 2000: Robot Soccer World Cup IV, p.391-396, January 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Theory

Keywords:
pattern recognition, tactics, topological structures