RoboCup 2010 – Rescue Simulation League Team Description SBCe_Saviour

Eslam Nazemi, Mohammad Goodarzi, Reza Emami, Seyed Ali Ahmadnejad, Nazanin Calagar, Zahra Hoseini, Mohammad Mahdi Javanmard

Department of Electrical and Computer Engineering Shahid Beheshti University Tehran, Iran

http://www.sbcee.net

Abstract This paper describes the main ideas and new methods implemented in SBCe_Saviour team in order to participate in RoboCup2010 competitions. Recently, RoboCup Rescue Simulation server has changed in a way that it becomes more realistic. Our target in 2010 competitions is to handle the new features added to server recently and overcome the problems our team faced during the yesteryear competitions. Improving our agents' coordination and communication system in order to be efficient in the case of center less and communication less scenarios is our first concern. Afterwards, new nature inspired decentralized decision making system for police force agents based on swarm intelligence and theory of response thresholds and some new changes in fire brigades strategy regarding to new vector based scoring system are our next priorities.

1. Introduction

SBCe_Saviour's first target for RoboCup2010 competitions is to improve the agents' communication system which released in 2008 [1] in order to handle the "center less" and "communication less" scenarios. The main idea for agents' communication and coordination is to devise an integrated method of Genetic Algorithms and Fuzzy Logic. The GA-Fuzzy system is an offline intelligent system that is capable of deciding which part of the percept information is more useful in any unknown situation [2]. Agents' network model is also a challenging issue in communication system. We are using our old network model [1] for the "ordinary" scenarios and have some improvements on it for "center less" and "communication less" scenarios with using TTL values and information tokens' history.

Considering the new scenarios used in the competitions from 2009, we believe that the desirable performance can be obtained by decentralized task allocation methods. Therefore as the first step a method based on theory of swarm intelligence and response thresholds concept is devised and implemented for Police Force agents' task allocation [3].

Moreover, the new RoboCup Rescue server has a lot of new features (e.g. new ignition simulator, new implementation for channel-based communication and etc). Our focus is to first have a precise survey on the new features and then overcome the new conceivable scenarios by implementing suitable strategies.

In part 2, agents' coordination and communication system based on GA-Fuzzy method and agents' network model are proposed. Part 3, 4 and 5 describe police force agents, fire brigade agents and ambulance team agents' strategies respectively.

2. Agents Coordination and Communication System

Rescue simulation is a large, dynamic and stochastic multi-agent system [4]. Therefore, agents are not capable to percept the whole information exists in the environment in each cycle and moreover agents cannot share all the percept information because of message sending constraints considered in RoboCup Rescue server. Thus, having an efficient decision making system to select the most important pieces of information to send with respect to different situation and also appointing the most efficient agents to get the information can lead to considerable improvement in agents' overall performance [2].

2.1. Previous Strategy

Until 2009, due to the standard scoring method used in competitions, rare use of "center less" scenarios and new presentation of "communication less" scenarios, SBCe_Saviour's strategy was to focus on ordinary scenarios. Decision making algorithm was based on predefined "message types" and performed in each cycle for each individual agent. Each message contains several message types. The list below shows the message types sorted by their priority for attending in a sending message. Obtained messages were finally propagated through the team regarding to agents' communication network and message channels released by us in 2008 [1].

1. Alive Report
2. Position Report
3. Target Report
4. New Target Victim Report
5. No Target Victim Report
6. Rescue Report
7. Rescue Finished Report
8. Civilian Report
9. Block Report
10. Fire Report
11. Unclear Report
12. Clear Report
13. Empty Building Report

2.2. Strategies for 2010 Competition

Number of sent messages is one of the parameters defined in RoboCup Rescue new scoring method called "score vector" and has a direct effect on the final score [5]. Moreover, maximum number of agents in new rescue scenarios will be increased to 30 for each type of agent in the following competitions. Our strategy is to reduce the number of sent messages and omit the unnecessary ones. This matter can be done with sharing percept information which is most useful regarding to the happened situation in the map. Based on the different situations, message types' priorities change and more efficient message packets will be produced.

In our new approach we first categorize all the percept data to a set of message types just as our previous method. Using the message types and utilizing an offline decision making method based on Genetic Algorithms [7] and Fuzzy Logic [8] allow us to decide which part of information is more useful in current situation happened in the map. With defining some parameters and their variation range we are able to obtain a set of communication based scenarios which includes all conceivable situations [2]. Table 1 show the parameters which we applied to our method.

Table 1. Parameters used to define distinct rescue situations and their variation range

The GA-Fuzzy approach is to first extract message types' priorities for each training map using Genetic Algorithms and then uses the gained results as the training data for a Fuzzy Logic generalizing system to obtain a general result for each unknown situation happened in most new scenarios.

2.2.1. Genetic Algorithms

The GA part of the method is responsible for extracting the best answer (set of message types' priorities) for a given situation.

Chromosomes' structure is an array of values that indicates message types' weights in the sending packet and the chromosome's size is equal to the number of message types. Summation of each chromosome's genes is equal to one.

$$\sum_{i=1}^{n} gene(i) = 1 \qquad (1)$$

"Score vector" scoring system is used as GA's fitness function in order to study all aspects of scoring team's performance in rescue simulation environment.

While the chromosome's structure is an array of values, it is a simple structure and does not need complex crossover and mutation algorithms. Two parents are selected and two new children are generated from them for crossover operation. Break points in each parent chromosome are selected randomly and segments between these break points are substituted by parents to generate new individual children. For the mutation process random genes are selected and their values are changed regarding to a value called "mutation constant" which is equal to maximum valid value of mutation operation.

Roulette wheel method [6] is used for the selection part of the algorithm. The main idea of this model is to select individuals stochastically from one generation to create the next generation. In this process, the most appropriate individuals have more chance to survive and go forward to the next generation. However, the weaker individuals will also have a probability to select.

2.2.2. Fuzzy Logic

By finding some solutions to the whole rescue system using the GA part, a set of message types' weights gained which are proper in specific learned situations. A fuzzy logic modeling system based on Takagi-Sugeno fuzzy modeling system [9] is used to obtain general result for message types' priorities in unknown situations. Figure 1 shows achieved fuzzy sets and membership functions of system's parameters considering their valid definition range after passing the training phase.

2.2.3. Agents Network Model

In order to have the efficient communication system, message packets should arrived to the most appropriate agents which exactly need the information placed in the message. Therefore, having a network model consist of agents as nodes and channels as edges is inevitable. We released a network model in which agents connected with each other in a form of binary tree structure [10]. The released model is based on center agents and is yet efficient in the case of ordinary scenarios. However, in the case of center less and communication less scenarios the model lost its efficiency.

Our approach to these two scenarios is to make mobile ad-hoc network between agents and distribute the information through the team. Information tokens which start to propagate through the network have a TTL (Time to Live) value and a history. TTL value expresses the number of token's circulation and the history saves the path that token pass through and prevents the token to trap in loops. Undoubtedly implementing such a network needs major changes in the whole team's planning and strategies (e.g. path planning and agents routing algorithms).

3. Police Force Agents

The major task of police force agents is to connect the separated parts of the city caused by debris. This work should be done in the less possible time. Our previous strategies for police force agents are very useful and efficient [11]. However, with new major changes in RoboCup Rescue server and new scenarios with large number of agents, civilians, fire points and blockades the previous methods lost their performance. According to our researches in nature inspired task allocation methods, we believe that in a large, complex and stochastic system like Rescue Simulation, centralized decision making is not applicable because of the following reasons:

1. Entire changes in the environment cannot percept by agents in each cycle. Therefore, the team loses a fraction of information. This also leads to some kind of uncertainty in the percept data through the time.
2. Communication limitations and network bandwidth does not allow agents to transfer all the information they percept to the decision making center. However, this center is also not capable of processing this large amount of information and assign tasks to each agent in a very short time.

3.1. Decentralized Approach to Police Force Task Allocation

One solution to decentralized decision making is the models based on social insects' behavior [12] and response threshold theory [13]. In our method each individual agent has a set of roads that should be cleared. Dynamic and environment-dependent values called stimulus are assigned to each task. While the need of doing a specific task is more required, task's stimulus level increases consequently. We considered the number of clear requests received from the team mates as the task's stimulus value in our method.

Moreover, each individual agent has a set of values called thresholds which indicates the minimum level of tendency to involve in respective task. Generally agents are more likely to engage in a task when the level of stimulus associated with that task exceeds task's related threshold.

Each agent a has a set which holds threshold values for each. Each task j has a stimulus value with 0 < $S_j$ < $S_{max}$, $S_j$ > 0. Probability T of involving in a task for each individual agent is obtained from the equation (2):

$$T_{\theta_{a,j}}(S_j) = \frac{S_j^n}{S_j^n + (\theta_{a,j})^n}, n \ge 2 \tag{2}$$

Where $T_{\theta_{a,j}}$ is the probability of involving agent a in task j. Using above equation, if the level of stimulus is equal to threshold value; the probability of involving in the related task is 1/2.

Response threshold values can be considered in two separate approaches, Fix and Variable. We use variable thresholds for our task allocation system. In this approach, threshold values can be dynamically evaluated according to system elapsed time and the current involved task [13]. Using variable threshold values lets the agent to dynamically adjust thresholds. As an example for this approach, if task i is performed by agent a, its threshold decreased by $\theta_L$ in each cycle and other tasks' threshold values are increased by $\theta_H$.

$$\theta_{a,i} = \theta_{a,i} - \theta_L$$

$$\theta_{a,j} = \theta_{a,j} + \theta_H \quad \text{for each } 0 < j < n, j \neq i$$

$\theta_{a,i}$: Threshold value of task i for agent a. n: Number of tasks for agent a.

4. Fire Brigade Agents

The main ideas and list of effective parameters in fire brigades decision making algorithm is presented in our 2008 and 2009 team description papers. However, we found out that our agents' performance can improve by defining some new parameters such as "Fire Zones" and "Fire Prediction".

4.1. Fire Zones

Fire zone is a set of adjacent buildings which are delimited by wide roads. The goal of using this concept is to use fire prediction idea to reduce fire propagation. In fact, this idea helps us to select the building with most priority by first selecting the target fire zone regarding to fire zone's material and total area of buildings inside the fire zone and then inside the selected fire zone. The most prior building is selected with the measures below:

• Building's fieriness
• Building's area
• Adjacency to civilians' center
• Being border building of fire zone
• Building's material type

4.2. Fire Prediction

The main reason for using the Fire Prediction method is to prevent the conduction of fire between adjacent fire zones. Conduction of fire among buildings inside a fire zone happens much faster in comparison to the conduction between two fire zones. Therefore, it is very important to stop the fire in one zone and prevent the fire propagation to its neighbor zones. Also regarding the importance of message centers, the Fire Prediction helps fire brigades to extinguish the buildings around before the fire is conducted to a message center itself.

In order to perform the fire prediction process, we first need to divide the city into a grid. Then the fire prediction will be able to give us the current and next temperature of each grid partition. The next temperature for each point of the city is obtained from equation (3):

$$NextAirTemp(x,y) = AirTemp(x,y) + \left(AverageTemp(x,y) - AirTemp(x,y)\right) * C \tag{3}$$

where AverageTemp is the effect of neighbor cells' temperature and relevant building temperature and the parameter C is obtained from AIR_TO_AIR_COEFFICIENT and TIME_STEP_LENGTH.

5. Ambulance Team Agents

Our focus for 2010 competitions is not to devise new strategies for ambulance team agents. Therefore, our new changes for the following competitions include resolving few bugs we faced in previous competitions. A summary of our ambulance team agents' strategies and decision making methods are described in this part.

The implementation of our ambulance team is based on state machines and automata theory. In an ideal situation, the cyclic process of rescuing and transferring a victim to the refuge involves the following six states in the Fig 1. It is obvious that surveying these steps is dependent on the circumstances that can occur in every step.

References

1. SBCe_Saviour Team Description Paper for RoboCup Rescue Simulation League, Shahid Beheshti University, Iran (2008)
2. Goodarzi, M., Radmand, A., Nazemi, E.: An Optimized Solution for Multi-Agent Coordination Using Integrated GA-Fuzzy Approach in Rescue Simulation Environment, 2nd International Workshop on Agent Technology for Disaster Management (ATDM) during the 12th International Conference on Principles in Multi-Agent Systems (PRIMA), Nagoya, Japan (2009)
3. Goodarzi, M., Sedighi Gilani, M.H, Emami, R., Nazemi, E.: Response Thresholds as a Model for Decentralized Task Allocation in Rescue Simulation Environment, submitted to RoboCup2010 Symposium, 2010
4. Kitano, H. Tadokoro, S.: RoboCup Rescue: A Grand Challenge for Multi-agent and Intelligent systems, ICMAS-2000, (2000)
5. Siddhartha, H., Sarika, R., Karlapalem, K.: Score Vector: A New Evaluation Scheme for RoboCup Rescue Simulation Competitions 2009, Rescue Simulation Technical Committee, (2009)
6. Al Jaddan, O., Rajamani, L.: Improved Selection Operator for GA, Journal of Theoretical and Applied Information Technology, pp. 269-277, (2005)
7. Banzhaf, W., Nordin, P., Keller, R., Francone, F.: Genetic Programming An Introduction, Morgan Kaufmann, San Fransisco, CA, (1998)
8. Dubois, D., Prade, H.: Fuzzy Sets And Systems: Theory and Applications, Kluwer Academic Publishers, Boston, second edition, (1991)
9. Takagi, T., Sugeno, M.: Fuzzy Identification of Systems and Its Application to Modeling and Control, IEEE Transactions on systems, man and cybernetics, Vol. SMC-15, No 1, (1985)
10. SBCe_Saviour Team Description Paper for RoboCup Rescue Simulation League, Shahid Beheshti University, Iran (2009)
11. Radmand, A., Nazemi, E., Goodarzi, M.: Integrated Genetic Algorithmic and Fuzzy Logic Approach for Decision Making of Police Force Agents in Rescue Simulation Environment, Proceeding of RoboCup2009 Symposium, (2009)
12. Price, R., Tino, P.: Evaluation of Adaptive Nature Inspired Task Allocation Against Alternate Decentralized Multiagent Strategies, Parallel Problem Solving from Nature-PPSN VIII, (eds) X. Yao et al. pp. 982-990, Lecture Notes in Computer Science, Springer-Verlag, (2004)
13. Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems, Oxford University press, edition 1,(1999)