Caspian 3D Team Description 2006

Bardia Aghabeigi, Mohammad Jafar Abdi, Mostafa Rokooie, Kamran Tirdad, Majid Sadeghi, Arsalan Mousavian, Mohammad Reza Kangavari, Seyyed Ali Mohammad Sayyah

Intelligent Systems Lab, Computer Engineering Department Iran University of Science and Technology, Tehran, Iran

http://caspian.iust.ac.ir

Abstract In this paper we introduced our soccer 3D simulation team structure, main ideas and fundamentals used to support them. We have used FCSP based approach and fuzzy controller methods to develop our team. The main idea behind this paper is using fuzzy algorithms in multi-agent system development. The inference method in decision making and control method in skill development are based on fuzzy concepts that will be described in details.

Introduction

Simulated environments are a commonly used method for researching artificial intelligence methods in physical multi-agent systems. Simulation are specially useful for too different types of problems: (1) to experiment with different sensors, actuators or morphologies of agents and (2) to study team behavior with the set of given agents. Additionally the connection between both types of problems is an interesting research problem [1].

In this paper, team development is divided to two modules. The first module, skill development, has its special challenges that we have suggested fuzzy controllers as a general solution. In the second module, the decision making problem, a goal-based approach is introduced and FCSP reasoning method is used to choose the action that best satisfies the defined goals.

In the remaining of this paper we have described fuzzy solutions about the two described problems.

Fuzzy solutions

In decision making problem, the FCSP approach is used and in skill development problem, fuzzy controllers are the basic methodology for design and implementation of robust skills. In the following sections we first describe the theory behind our solutions and then our transition to these concepts in great details.

Decision-making

Constraints are mathematical objects used to make explicit the logic behind a problem. They are used to model decision making problems of e.g. design, planning or scheduling. [3]

Constraint Satisfaction is the process of identifying a solution to a problem which satisfies all specified constraints. Classical constraint satisfaction supports hard constraints which are imperative (a valid solution must satisfy all of them) and inflexible (constraints are either wholly satisfied or wholly violated). In reality, problems rarely exhibit this rigidity of structure. Classical CSP has been extended to incorporate different types of 'soft' constraint often found in real problems. One successful example is Fuzzy CSP (FCSP). Rather than enforcing binary satisfaction /dissatisfaction, it provides a more graded viewpoint through a fuzzy set-based representation and aggregated via fuzzy conjunction to obtain a satisfaction degree for each satisfaction [2]

We have used the OWA operator to aggregate the constraints, because the behavior of the OWA operator family is often better suited for multiple criteria decision making in real world situations where multistage inference steps are necessary in order not to dilute knowledge excessively. [3]

The general definition given for this n-array operator is restated here, with $a_1,...,a_n$, $w_1,...,w_n \in [0,1]$, $\sum w_i = 1$, and $b_i$ is the $j^{th}$ largest element in the collection $a_1,...,a_n$:

$$OWA_{w}(a_{1},...,a_n) = \sum_{i=1}^{n} w_i.b_i$$

Also we have defined the weight vector:

$$W_i = \frac{2i}{n(n+1)}$$

For instance, n=4 results in $w_4 = (0.1, 0.2, 0.3, 0.4)^T$

Often criteria do not all have the same importance in real-world applications. It is thus reasonable to consider the relative priorities of constraints when instantiations are evaluated and compared. An intuitive requirement is that as a constraint becomes more important, it should play a more significant role in determining the overall decision function. A solution is to order constrains with respect to each other by giving them a priority degree. A coefficient $w \in [0, 1]$ is attached to each constraint, with a higher w indicating a comparatively higher importance. These priorities are transformed, without any loss of information, into constraint satisfaction degrees [3]:

$$\mu_{soft, w(x_1, ..., x_k)} = \max(1 - w, \mu_{soft(x_1, ..., x_k)})$$

The decision making structure we have developed is as follow:

First, we generate an array of special points. Then we evaluate each point over the constraints we have defined. Then we choose the point that best satisfies the constraints and kick the ball to that point.

The points we generate include the points around the player itself (for dribbling), the points around the other teammates (to pass to teammates), the points that is far from our goal (to clear the ball) and some heuristic points. However all of these points are in the distance that the player can kick the ball to that point with maximum power.

The constraints we have defined are:

• Far from our goal
• Near to the opponent goal
• Far from the opponent players
• Near to our teammates

The weights of these constraints will be calculated by means of fuzzy rules. The premises of these rules are combinations of conditions and the consequences are weights of the constraints.

The conditions we have defined are:

• Ball is in our penalty area
• Ball is close to the opponent goal
• Ball is in midfield area
• An opponent player is close to the agent
• …

Each condition is a fuzzy variable and has a membership function that assigns a value between zero and one to that condition. We can change our team strategy by changing these rules appropriately. After determining the weights of the constraints, we can then evaluate each point over the constraints using the OWA operator. Then we choose the best point and kick the ball to that point.

Fuzzy Skills

Recently, fuzzy control has become a popular research in the control engineering .The fuzzy logic controller has made itself available not only in the laboratory work but also in industrial applications, mostly based on the knowledge and experience of a human operator .In recent years, theoretical development of fuzzy control have been proposed and the construction and the use of fuzzy controllers have explored [5].

The theory behind fuzzy control is not outlined in this paper for theoretical details regarding the fuzzy logic control and fuzzy logic controllers, the reader is referred to the introductory and tutorial papers [6], or published books [7].

Most of the control applications of fuzzy logic can be generalized by means of a simple structure shown in fig 1.

Let us briefly discuss the main stages of the control scheme demonstrated in Fig 1.

Fuzzification

Fuzzification is a transformation of the crisp data into a corresponding fuzzy set before the data can be fuzzified however it should first be normalized to meet the range of the universe of discourse suitable for the controller input.

Fuzzy Inference

To discuss fuzzy inferencing in great detail let us recall the fuzzy system characterized by the linguistic description in the form of fuzzy implication rules [4]:

R₁: IF A1 is $A_1^K$ AND IF A2 IS $A_1^2$ AND... AND IF AK IS $A_1^K$ THEN B1 IS $B_1^1$ AND B2 IS $B_1^2$ AND ... BL IS $B_1^L$ ALSO

R₁: IF A1 is $A_2^1$ AND IF A2 IS $A_2^2$ AND... AND IF AK IS $A_2^K$ THEN B1 IS $B_2^1$ AND B2 IS $B_2^2$ AND ... BL IS $B_2^L$ ALSO

Where A1,…,AK represent the input variables , ¹Ai , ²Ai ,…, ᴷAi represents the input memberships functions, B1,…,BK represents the output variables and ¹Bi , ²Bi ,…, ᴷBi represents the output membership functions .

The inference mechanisms employed in fuzzy logic controllers are generally based on various reasoning schemes. The inference result can be obtained using different algorithms .The common methods are listed bellow:

• 1. Mamdani's strategy-mamdani fuzzy reasoning method is based on Max-Min inference operator.
• 2. Larsen's strategy-Larsen fuzzy reasoning method is based on product inference operator.
• 3. Takagi and sugeno's strategy-Takagi and sugeno fuzzy reasoning method is based on a distinct model description

In this model the control variables are characterized by functions of the process state variables.

Defuzzification

Generally defuzzification describes the mapping from a space of fuzzy control action to a nonfuzzy control action.

Defuzzification produces a non fuzzy action that best represents the inferred fuzzy output. Sometimes after the defuzzification a denormalization procedure is required for practical applications.

Our skill transition to fuzzy control system is based on the above concepts. For example in implementation of MoveToPos skill that is one of the necessary low level skills we defined four linguistic variables that are listed below, with their related linguistic terms:

Details of lingustic variables that have been used in the fuzzy controller

The skeleton of our fuzzy controller for this skill is shown in fig2.

Future Works

To reach adaptive solutions in dynamic environments which conditions varied time to time, we need adaptive methods that can be combined with our current solutions and improve them as more as possible. Using reinforcement learning and genetic algorithms in our solution frameworks are our main goals in the future.

References

1. Oliver Obst and Markus Rollmann. SPARK -- A Generic Simulator for Physical Multiagent Simulations. In Gabriela Lindemann, Jörg Denzinger, Ingo J. Timm, and Rainer Unland, editors, Multiagent System Technologies -- Proceedings of the MATES 2004 , pp. 243–257, Lecture Notes in Artificial Intelligence 3187, Springer, September 2004
2. I. Miguel and Q. Shen. Fuzzy rrDFCSP and Planning. Artificial Intelligence 148 (1- 2), pages 11-52, 2003.
3. SLANY, W -"Scheduling as a fuzzy multi-criteria optimization problem"- Fuzzy Sets and Systems. Vol 78, 1996. pp 197-222.
4. Marek J. Patyra, Janos L Grantner and Kirby Koster," Digital Fuzzy Logic Controller: Design and Implementation", IEEE Transactions on Fuzzy Systems, Vol 4, No. 4, Nov., 1996. pp 439-459.
5. S. Bentalba, A. El Hajjaji, A. Rachid,Fuzzy path tracking control of a vehicle, Proc. IEEE Intl. Conf. Intelligent Vehicles (IEEE IV 98), Stuttgart, Germany, pp. 195-200, Oct. 1998.
6. C.C. Lee, Fuzzy logic in control system: fuzzy logic controller, IEEE Trans. Systems Man Cybernet. 20 (1990) 408-435.
7. Dimiter Driankov, Hans Hellendoorn, and Michael Reinfrank,"An Introduction to Fuzzy Control", Springer-Verlag, New York, 1993.