View Original PDF

WrightEagle Simulator Team

Bin Yang, Yang Yang, Xiaoping Chen, Zhenyu Li

AI Center, University of Science and Technology of China, Hefei, China

Abstract One of the crucial problems facing designers of RoboCup Simulator teams – artificial systems capable of effective, rational behavior in dynamic and unpredictable environments – is to ensure agents to have the ability to make decisions both appropriately and timely. This paper describes our work in the pursuit of this hybrid system, focusing on two aspects: (1) How to construct a proper and effective agent model that bears a rational balance between deliberative planning and reactive control. (2) How to build a RoboCup Simulator team based on such a model.

Introduction

One of the crucial problems facing designers of RoboCup Simulator teams – artificial systems capable of effective, rational behavior in dynamic and unpredictable environments – is to ensure agents to have the ability to make decisions both appropriately and timely. In such domains, classical AI search and planning methods are time-consuming and hard to meet the requirement of practical use. Though purely reactive systems are capable of effective behavior in some dynamic environments, they can't guarantee that in unanticipated situations. It is generally believed [1] that the hybrid from deliberative planning and reactive system will help to solve these problems. This paper describes our work in the pursuit of this hybrid system, focusing on two aspects: (1) How to construct a proper and effective agent model that bears a rational balance between deliberative planning and reactive control. (2) How to build a RoboCup Simulator team based on such a model.

The Agent Architecture

We divide our agent's decision-making model into four layers: Team Strategy Layer, Group Tactics Layer, Individual Tactics Layer and Individual Skill Layer. We adopt BDI model in constructing the top three layers. While in the Individual Skill layer, we use reactive model to realize agent's basic skills such as run, kick etc.

Desires represent the world states that agent hopes to achieve. Also, they can be seen as tasks that agent should do. In this model, each layer has its own desire generator whose function is to observe the environment and submit tasks to agent accordingly. Inside the model,

  • The Team Strategy Layer is in charge of the whole team's strategy at each offence or defense.
  • The Group Tactics Layer deals with the tactics of a small group of players.
  • It is the Individual Tactics Layer's responsibility to reasoning about behaviors concern about individual.

As we can see from figure 1, each layer gets input from the previous layer as its desire and sends its sub-goal to the next layer. After three layers' decomposition and reasoning, the final result will be sent to the Individual Skill Layer as agent's action.

Figure 1: Layered Planning
Figure 1: Layered Planning

Reasoning based on BDI Model

Inside each layer, we adopt BDI model. Figure 2 shows the detailed structure.

Belief module describes the knowledge of the agent, including the understanding of the system environment and some experience parameters to certain situations. Inside the model, desires are described with many appending attributes such as priors and time-bounded. Desire Selection Module will select proper desire as intention according to these attributes. Desire Maintenance Module's responsibility is to maintain desires' effectiveness inside the Desire Set. It will delete the desires that are completed or cannot be completed. Intention Module will execute the reasoning process to acquire appropriate plan according to the current intention.

Figure 2 BDI Model Inside Each Layer
Figure 2 BDI Model Inside Each Layer

Belief: Use Expectation-based Prediction (EBP) to Improve Knowledge Acquisition

At regular intervals agents can get sensor information from soccer server. The information is only partial and discrete. But by base rules, we can use these information $S^*$ to reconstruct the whole continuous ground model $S$ [2], and a variable conf is used to describe how believable the information is. By this method agents can get more complete knowledge about the environment where they are, but this is not enough. Agents can not only obtain knowledge from the environment, but also affect the environment. And the results can be predicted, so agents can change the environment to what they want it to be. While there is some other agents in the environment and their behaviors cannot be foreseen. Here we can assume they always take optimum actions, just as we predict. We call it the expectation-based prediction system (EBPS) [3]. Through this kind of prediction, we improve the methods by which knowledge obtained, thus agents have more strong belief to achieve their goal more efficient. Such subjective prediction can also use the variable conf to describe its reliability.

The Implementation of Intention Model

When Desire module selects a suitable desire as current intention, Intention module employs the belief the agent obtained to get the next plan. In a certain state, each intention can be realized through many kinds of methods. The use of Intention module is to find the best plan as the next plan. So for every intention, agents can get a candidate set B, for each behavior $b_i \in B$, there is a evaluation function to get its evaluation $E^i$ according to the belief they have, and the behavior which have the highest evaluation is the next action plan.

For the environment is real-time and complicated, it is hard to define a rational evaluation function. So we should use different function in different instances, such as attack, defense. And according to Decision-Theory we can calculate the probability $p_{ij}$ and the utility $\mu_{ij}$ of each result $r_j$ of each plan $b_i$ separately. Then use the formula (1) we can get the best behavior.

$$\max \sum p_{ij} * \mu_{ij} \to b_{best}$$

The Implementation of Attack

When attack, scoring is a simple intention for the player who handles the ball, and other teammates just find a good place to help scoring according to their roles. Based on such an intention, the player who handles the ball can choose dribble (dr), pass (pa), or shoot (sh). Thus we can get a rational behavior set B

$$B = {dr(pos, vel), pa(pos, vel), sh(dir, vel)}$$

where pos is the position of object, vel is the velocity of ball, dir is the direction of ball.

Based on the knowledge obtained, agent can calculate the probability of success p (the other result is fail and the utility is 0, so no need to consider) and the utility $\mu$ of each behavior. Then using formula (1), agents can get the best behavior as the next action plan. Other teammates can also find the best place using this theory to help attack.

The Implementation of Defense

In our defense the situation in the field becomes fuzzy concept abstractly and our player agents make decision on the basis of the fuzzy concept. Above all of the agents dynamically divide the defended area (Area) into m blocks at first and the division is according to the distribution of the opponent attacking player. The restraint of the field (FE) and the distributions of the opponent player (PE) are taken into account in the division.

$$Area = { f_i(FE_i, PE_i) \mid i = m }$$

The situation that defended area might run into can be divided into three kinds: Defending player insufficient, defending player proper and defending player redundant. For the division of these three kind situations, we can simply judge. If in a certain area the players that can defend is less than the opponent attacking players, we think the defending players is insufficient in the area; On the contrary the defending players in a certain area is more than the attacking players, then we think defending players in this area is redundant. In the whole field, we can make the quantity of player in the area balanced to enable defending by increasing number of the defending players or adjusting the positions of defending players according to defense tactics of our team.

After the divisions of defending area are finished we get the basic way of the opponent attacks in fact. We can determine the basic defending tactics, such as 'player against player', zonal defense and so on. The defending tactics may use the settings of default or the settings changed temporarily by the online coach, certainly all tactics were tested.

Each player can get all the possible behaviors of the teammates in the same area and one's own after making the own area and the basic defending tactics sure. Of course we can get the effect and the cost of all the behaviors. All the behaviors are evaluated according to the effect and the cost. The result of evaluation is a numerical value. Our choice is the highest one.

Five types of defense behaviors are defined in our defense system: Tackle, Mark, Block, Position and Assist Defending. Tackling is the behavior of tending to get ball directly; Marking is keeping up with a single opponent without ball so that the opponent cannot get the ball passed to him. Blocking is limiting the acting of the opponent with ball. Positioning is just running to the favorable defense position. Assisting defending is to save the ball when teammate have made mistake. Players choose the feat behavior in the five according to one's own area, basic defense tactic and the special situation in the area. The choice and switch of the five behaviors make the individual defense.

Conclusions

By using this hybrid architecture and multi-layered BDI model, we obtained more clear specification for our team. We expect it can help to implement our team more efficiently.

References

[1] M. Wooldridge and N. R. Jennings, Intelligent agents: Theory and practice, Knowledge Engineering Review, Vol.10, No.2, 1995 [2] Peter Stone, Patrick Riley, Mannuela Veloso. The CMUnites-99 Champion Simulator Team, http://www.research.att.com/~pstone, 1999 [3] Bin Yang, Xiaoping Chen, Yang Yang, The description of Simulation Team WrightEagle2001 (to appear)