AT Humboldt 2004 & AT Humboldt 3D Team Description

Ralf Berger, Michael Gollin, Hans-Dieter Burkhard

Humboldt University Berlin, Department of Computer Science

http://www.ki.informatik.hu-berlin.de/RoboCup

Abstract Our last years Soccer Simulation team AT Humboldt 2003 was mainly designed as a research testbed for long-term deliberation and real-time reasoning, cooperative behavior in MAS, CBR-aided decision making and scalable behavior control mechanisms. The main goal was to implement and to evaluate the double pass architecture (DPA). This was always done with regard to the transition of the Simulation League towards the next generation soccer server (3D-Server).

In 2004 we intend to participate in both competitions, 2D and the new 3D Soccer Simulation.

The new 3D-Soccer Server will create an even more dynamic agent environment compared to the old simulation system. Thus we expect to show the full potential of our architecture with the new team AT Humboldt 3D.

1 Introduction

Our group's general research focus encompasses agent-oriented techniques, case-based reasoning, knowledge management, intelligent robotics, cognitive science and socionics. We investigate agent architectures and deliberation concepts that allow to build rational, scalable, dynamic and cooperative multi agent systems, with applications in e-commerce, medicine and industry [6],[9],[10].

We have found RoboCup to be an interesting and challenging domain for the development of new techniques and we participate in two leagues: the Soccer Simulation league and the Sony four-legged robots league.

We are members of the DFG (German research foundation) programme "Cooperating teams of mobile robots in dynamic environments" [5], with a particular focus on agent architectures. A lot of our work in RoboCup is strongly linked to current work in the fields of our other research topics, for instance: Case Retrieval Nets as a mean for efficient and flexible retrieval in Case Based Reasoning, Social modelling with multi agent systems or Belief-Desire-Intention models (BDI [11]) to go beyond emergent and allow cooperative behavior.

In return ideas from soccer team development have often been fruitful for projects outside RoboCup, for example in cognitive robotics. Furthermore our work in RoboCup is a great teaching platform for practical exercises in our AI and robotics courses.

2 3D Soccer Simulation

By introducing the new SoccerServer [8] there are two important conceptual changes that have to be taken into account for agent design.

1. three-dimensional world modeling

The old SoccerServer simulates the game of soccer in a 2D world, making it seem more like a game of table hockey with soccer rules. By simulating it three-dimensional, the set of tactic and strategic behavior possibilities will drasticly increase. Furthermore cooperation and context-based decision making become more important.

A typical example is shown in figure 1: (3 attacker vs. 3 defender)

In the 2D-world the actual gameplay takes places within a very small area that is determined by the maximum reliable pass distance. Two defenders are needed to prevent attacker A from dribbling towards the goal-line. The third defender makes a pass to attacker B or C unsafe. All players can reach a behavior decision by evaluating their local situation; usually ballcorrelated positioning, covering, dribbling or passing.

In the 3D-world passes over opponent players are possible. Thus attacker B could run towards the ball to tie up defender 3 and enable attacker C for creating an open space for a possible cross. In that the most important players are B and C. This move can hardly be achieved by an individual decision with a global positioning method. It is a cooperative long-term behavior, whereby the decisions of the players are usefull and producible only in the special context of this intended behavior.

2. more realistic time modeling

The timing model of the new SoccerServer will go far beyond the current 100ms steady-state discrete world simulation. The thinking time of each agent will determine the amount of time the world will advance. Fast reactive behavior on changing situations (without thinking) is necessary because the world is moving on. The challenging task is, that these actions

should consider the committed individual and social goals as much as possible. In addition perception and acting will be possible in much shorter time-intervals than the duration of the agents reasoning-process. However, it is not necessary to shorten the agents thinking time, but to decouple perception, thinking and acting.

3 Double Pass Architecture

A comprehensive description of the architecture is given in [4] and [2].

Classical layered architectures show some problems and limitations in highly dynamic environments which result from their fixed-layer structure and the coupling between behavior levels and the control directives.

The double pass architecture does not have these limitations and is able to fulfill the following demands:

• – time independent long-term deliberation of complex behavior with free time horizon
• – least commitment of all possible data to execution time
• – scalability in number of behavior options
• – scalability in the timing resolution and computational expenditure
• – realtime capability on all control layers, even realtime changing/replanning of high level goals
• – persistency of high level individual and cooperative goals against small world changes
• – control of coordinated behavior involving more than one player

We will now illustrate the key-concepts of our approach:

Hierarchical organized behavior levels

If we describe complex behavior patterns we will often find some natural hierarchies. Extensive individual or cooperative actions can be modeled as a combination of more elementary actions, whereby combination can mean either choice or concatenation. All these sub-behaviors can further be described as a combination of other behaviors.

The result spans a tree of options with abstract options near the root, like 'play soccer', and basic actuator commands, like 'kickToPos', at the leaves.

Unlike other layered architectures we don't have a fixed number of abstraction layers like physical layer, skill-layer, knowledge layer and social layer. Instead, an arbitrary number of layers is permitted in the tree, whereby the different layers itself do not have a predefined abstraction model but every node reflects a certain context. This context can be determined e.g. by a class of world situations, a social goal, a local role assignment or an individual mental state of an agent. This multi-level hierarchical structure provides a number of advantages:

Evaluating only the possible actions within the context of one node instead of comparing all possibilities of a certain layer of abstractness reduces the

complexity of evaluation (local evaluation vs. global evaluation methods) and makes comparing utilities much easier. Having this tree of possible behavior modes for every single agent, it can also be used by other agents as a common knowledge pool which makes cooperation without negotiation much easier.

Decoupling of behavior and control

Our approach is based on a strict separation between long-term deliberation and reactive execution (both considered on all levels), whereby all layers are invoked in every time step. For this reason the double pass architecture uses two independent top-down passes:

Deliberator-Pass

The deliberator performs long-term planning¹ to prepare and monitor behavior according to individual and social goals and persistent strategies. The deliberators main task is to choose the goals and to prepare all the context of the nodes which is necessary to decide how to realize these goals according to the current situation. Deliberation starts in the root-option and evaluates available suboptions by analyzing current or subsequent game-situations to determine their associated utilities. Furthermore it performs the precalculation of abstract parameters described in the plans. To avoid recursion, the behavior tree has to be organized in a way that the evaluation mechanisms can be performed locally in the context of the current node. The result is a pre-arranged partial plan – a set of evaluated options in the tree, that corresponds to desires and intentions in the BDI-methodology [11, 12]. Following the least commitment idea, the plan is continuously updated and completed as time goes on. Additionally, the deliberator provides alternative options/plans that are instantly available if an exception occurs at execution time. The deliberator is independent from the actual run-time demands; it has to be ensured however that at any time enough information is prepared for execution of sensible actions.

Executor-Pass

The executor generates the reactive actuator commands that will fulfill the goals selected by the deliberator. The main tasks are checking of the options consistency and transition conditions and resolving of symbolical data based on the most recent sensory information. The executor is called whenever a timer component decides that it is necessary to perform an action. Along this way the executor checks all the pre-, post- and break-conditions, resolves abstract parameters to actual values and collects control instructions that are generated by the deliberator or are steady components of the tree (e.g. communication strategies). Based on the preparatory work of the deliberator, the executor has to perform only a minimum of computational work (the data that has been left open for least commitment) and thus can be delayed to get the latest possible perception.

Mental models for cooperation

It is well known, that a kind of persistency is necessary for complex cooperation between agents which cannot negotiate their behavior because of

¹ not meant as the classical term of planning or means-end reasoning, but the preparation of a set of intentions, which can generate a long-term behavior

communication constraints and which cannot deduct others behavior because of incomplete world knowledge. Explicit mental states are a particularly efficient way to achieve persistency. Normally these states include knowledge of former decisions and therefore reduce the space and complexity of following evaluations and ensure stable decisions.

The mental states of our agents include (apart from the worldmodel) commitments to individual and cooperative long-term and short-term behaviors and strategic modes, the global role of the agent itself and all teammates, the task association in local cooperative behaviors and the progression state of current plans.

Flow of data and control compared to classical 2–pass layered architectures is shown in figure 2.

4 Case Based Reasoning

AT Humboldt 2003 successfully used case-based-reasoning (CBR) techniques [7, 3] in the decision making process. The chosen scenario was a quite simple decision task for the goalie. The case database was automatically build up with a set of logfiles from RoboCup German Open 2003 as initial data.

For 2004 we plan to make use of CBR for describing and evaluating standard situations. This time we want to build up the cases manually from descriptions,

examples and training models by soccer domain experts.

Last years experiments have shown that the challenging task is finding a suitable similarity and relevance measure. Furthermore we have seen that an intuitive search-retrieval through the database is far away from realtime computing. Therefor we have to develop retrieval mechanisms which provide high speed access to similar cases to a given game situation.

5 Outlook

While much work for 2004 is still in progress a detailed description of new results will appear in the final team description paper.

Things we plan to do in 2004 are for instance:

• – come up with a competitive team for the 3D-Soccer-Simulation competition
• – further development on our double pass architecture, e.g. explicit time representation in long-term partial plans of the deliberator
• – more and advanced use of case-based-reasoning for deliberation tasks
• – evaluation of some learning techniques for low-level skills (reinforcement learning & genetic algorithms)
• – much more sophisticated use of the coach, including strategic in-game changes of formation, player-roles and game system
• – extensions to our development tool ADT
• – better visualization of our symbolic behavior description
• – build up a framework for interactive developing role and formation data without knowledge about the underlaying system and code

References

1. Website of team AT Humboldt. http://www.ki.informatik.hu-berlin.de.
2. R. Berger, H.-D. Burkhard, and M. Gollin. Two Passes design of a powerful architecture for behavior control in MAS. Submitted to RoboCup–2004: Robot Soccer World Cup VIII, 2005.
3. R. Berger, M. Gollin, and H.-D. Burkhard. AT Humboldt 2003 Team Description. In RoboCup–2003: Robot Soccer Word Cup VII, LNAI. Springer, 2004.
4. H.-D. Burkhard, J. Bach, R. Berger, B. Brunswiek, and M. Gollin. Mental models for robot control. In M. Beetz et al., editors, Plan Based Control of Robotic Agents, number 2466 in Lecture Notes in Artificial Intelligence. Springer, 2002.
5. Website of DFG Programme 1125 "Cooperating teams of mobile robots in dynamic environments". http://ais.gmd.de/dfg-robocup/.
6. A. Hübner, M. Lenz, R. Borch, and M. Posthoff. Last minute travel application. AI Magazine, 21(4):58–62, 2002.
7. J. Kolodner. Case-Based Reasoning. Morgan Kaufmann, Cambridge, Mass., 1993.
8. K. Kögler and O.Obst. Simulation League: The Next Generation. In RoboCup–2003: Robot Soccer Word Cup VII, LNAI. Springer, 2004.
9. M.Minor and M.Lenz. Textual cbr im e–commerce. KI, (4), 2000.
10. I. Münch and G. Lindemann. Charitime–concepts of analysis and design of an agent oriented system for appointment management. Fundamenta Informaticae, (43).
11. A. S. Rao and M. P. Georgeff. Modeling Agents Within a BDI-Architecture. In Proc. of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR91), pages 473–484, Cambridge, Mass., apr 1991. Morgan Kaufmann.
12. A. S. Rao and M. P. Georgeff. BDI Agents: From Theory to Practice. In Victor Lesser, editor, Proceedings of the 1st International Conference on Multi-Agent Systems (ICMAS), pages 312–319, San Francisco, CA, 1995. MIT Press.