Poseidon Team Description Paper Robocup 2009, Graz

Afsoon Afzal, Mozhdeh Arian Nezhad, Zahra Mosadegh, Melika-Shah Hoseini, Mostafa Vafadoost

Farzanegan High School Tehran, Robotics Research Group No. 56, Shahid Sarparast St., Taleghani Ave. Tehran, Iran

Abstract This paper describes contributions of the Poseidon Team to technical explorations of optimum solutions in simulation of rescue agents. Each section clearly defines mathematical model and discusses Poseidon's approach to solve them while explaining the bases of the used method. This version of Poseidon team is a developed version of Poseidon 2007 containing new ideas. We have used artificial intelligence algorithms and probabilistic methods in order to solve the existing problems in simulation of the rescue team and make them more efficient. Other than that, a method has been developed to minimize the number of tells and improve the telecommunication system.

1 Introduction

The main goal in rescue simulation league is to minimize both life and financial loss in a large urban disaster. This goal will be achieved by use of police teams, ambulance teams and fire fighters. The main duty of the police teams is opening the closed roads and the main duty of the ambulance team is saving lives and fire extinguishing is the main duty of the fire fighters. In addition, all the agents are responsible to facilitate the other team's tasks. Like in the real world, efficient and easy communication system among above-mentioned agents and consistency among them are very effective on the results. In this regard, Poseidon tries to consider this issue more by improving the previous works and providing new methods for every section.

In communication system among the rescue teams, information exchange has been optimized. In cases that wireless system is not available some new ideas have been proposed to compensate the lack of data from environment and possible inconsistency between agents. Also some new algorithms have been proposed for the agents' decision-making.

Police force zoning has been implemented by using simulated annealing, thus police forces will be more efficient considering that actions have been ordered to the agents equally. Furthermore, a new method for civilian search was proposed. It is based on probabilistic methods as a result of which, finding injured civilians will be faster. Consequently ambulance teams will be able to find injured civilians more quickly. In order to decrease the moving time and solve the hesitation problem in decisions for ambulance team, ant colony optimization was used and in order to distinguish the best direction for fire fighters we used computational geometry.

2 Communications

One of the most important factors in teams' decision making is Information exchange. Regarding that each individual agent has a limited amount of information, sharing that information will help the others to do the right job. We have used Impossibles08 [1] idea to choose radar as the proper communication system. The information passes to the agent teams in three steps. Regarding some changes in the server and also cons of extreme use tells, some constrains for agent's information have been applied. Categories of the required information for each team are shown in table 1.

Table 1. Required information for agent teams

2.1 No Communication

In addition to decreasing the amount of required information exchange, for places that there is no communication in between, new ideas have been proposed by Poseidon as follows:

2.1.1 Information Center

There should be some data transmitting centers that each agent transfers its new data to them. Each agent could recourse to these centers if they need more information. Information centers can be perpetual or it can be essential generated in time. Centers can be more than one and their information will be interchanged regularly.

This center can be refuge to inform agents of new information while they are doing their ordinary responsibilities. But if this center turns to refuge, it may take place far away and agents like police that move to refuge much less than other agents in ordinary situation, should take a long way.

For data exchange among the information centers, we use the agents who have less important duties in the rescue plan.

2.1.2 Zoning

In order to decrease the number of mistakes and compensate the lack of information, we propose to divide the city into several zones. Each agent is responsible for its section of the city. One option is to have the information center at the center of a circle and each segment of the circle selected as a zone. Dimensions of the zones can be determined by different bases such as the number of civilians in the zone, etc. dividing of the city will solve the communication system problem among the information centers but in a disastrous situation, the use of planned zones might be unfair, as some zones need more help. Therefore it is essential to choose another mechanism to decide about the necessary agents in each zone. In the above-mentioned mechanism, the number of the meetings in the information centers should be minimized and every agent's decision be based on the information of its

own zone. In case of transferring agents between zones, related information of the destination zone should be passed to the agents.

2.1.3 Continuous Information Exchange

In this method information will be passed to the agent during their routine tasks and takes a little time. Thus every agent is doing its own tasks and police force searching algorithm is in the manner that they see each other regularly. For example every two police forces see each other regularly and exchange the information, also other agents know about their paths in order to meet them on the way and get the required information. But the paths' information is not precise and agents may have been awaited some cycles. There are some methods in this regard as follows:

• Some locations of the city like main crosses will be selected to have police force stops there. In this way possibility of the existence of the police force close to the other agent will be higher.
• Using minimum spanning tree for opening the roads and path finding in this method will be helpful. Therefore agents can be informed about the open roads.

Combination of both above methods, (i.e. main points determination and moving paths determination in the way that MST are at the main points along the paths) will lead to increase the possibility of facing police force to each other during the searching task. Studying the results of the four finalists in world champion 2008 in china, observed that more than 75% of agent's tasks in most maps was move action. If this moving take places in the specified paths, the possibility of seeing each other will be increased.

2.2 Poseidon No Communication Approach

In final conclusion of the mentioned ideas, the most practical method is to combine zoning the city with having one information center for each zone. Police force will open the roads that MSTs are along with. Agents will exchange the information in main locations at specified periods and held the meetings when they are required. In case that information centers have more people than enough, they send messengers to the agents in order to pass the information, inside and outside the zones. Also it is possible to perform the zoning of the city based on the sectors. Implementation of this idea has not completed yet.

3 Ambulance Team Agent

Due to the importance of the civilians' life in real world, when simulating, one of the most important purposes is to reduce the number of victims by improving rescue and ambulance service. This must be carried out by ambulance performance. The main issue is that the ambulance team be able to keep alive as many civilians as possible, with the least damage.

The outcome of the ambulances' performance depends on the decision-making algorithm. In the process of decision-making, the agents may decide autonomously (distributed), or the commanding center may decide for them (centralized). Other than that, the ambulances can be sent to the civilians' rescue in groups or individually. The decision-making process will be more complicated if we consider environmental and other issues such as estimating the time each civilian takes to die, the time that is needed for the agents' movement in the city, and the time that the fire takes to spread and burn the civilians.

The algorithm of selecting the best civilian case to rescue in the given situation, depending on the decisionmaking algorithm, has a crucial role in keeping the most possible number of civilians alive.

To utilize all of the ambulance power, increase the rescue action and make the maximum possible use of the ambulances, it was decided to allocate as many of ambulances as necessary to save civilians' lives.

3.1 Injured Civilian Selection

Poseidon explained the ambulance problem in a way that a schedule of the tasks and the civilians each ambulance must rescue, needs to be planned in a manner that they rescue the most possible number of people. When we studied the ambulance issue thoroughly we realized that this has many similarities to the resourceleveling problem. Resource Leveling is a project management process used to schedule a project for an unbalanced use of resources over time. In the ambulance issue there is a number of civilians that can only be rescued in a specific time and each civilian, in order to be alive, needs a certain number of ambulances while the number of ambulances on the other hand, is limited. Planning for rescuing civilians and for the number of ambulances they need is similar to planning for the activities in the resource-leveling problem. In which the number of resources and the start time of each activity is estimated in a way that the most number of activities be carried out with the limited number of resources.

One way to solve this problem is the use of global search algorithms [2]. We studied the ways of solving the resource-leveling problem and decided to use Ant Colony Optimization (ACO) to solve the ambulance problem. The general purpose of our ACO in solving this problem is to use ant algorithm for determining the start time for rescuing the selected injured.

In ACO, several generations of artificial ants search for good solutions. Each ant of a generation builds a list of the civilians that must be rescued, and determines rescue start time of them. The following ants of the next generations are attracted by the pheromone and this causes them to search for answers close to the previous ants'.

To determine the start rescue time of each selected injured we use the two parameters of heuristic information and pheromone information. These two parameters are indicators of how good it is to rescue the civilian in that given time.

Heuristic information is shown by $\eta$ and determines the value of each civilian according to the greedy Algorithm. According to their death time, buriedness, and distance from fire and refuge, injured civilians have priorities. Base on these priorities civilians have been sorted. Pheromone information is shown by $\tau$ and is calculated according to the previous ants' solutions. Pheromone information is updated after each solution is made, as following:

$$\tau = \rho.\tau_{cv,t-1} + L_k \tag{1}$$

Where $\rho$ is the evaporation rate and $L_k$ is the number of the fitness civilians rescued by determinant ant. $\rho$ parameter is used to avoid the accumulation of pheromone and it enables the algorithm, to dismiss previous bad choices

Following is how we calculate the probability of selecting Civilian cv in t time:

$$p_{cv,t} = \frac{(\tau_{cv,t}^{\alpha})(\eta_{cv,t}^{\beta})}{\sum_{i=1}^{t} (\tau_{cv,t}^{\alpha})(\eta_{cv,t}^{\beta})} \tag{2}$$

The more $p_{cv,t}$ , the more is the probability of choosing cv in the time of t.

Here is pseudo-code of our civilian selection algorithm:

procedure Injured Civilian Selection
      while (not termination)
           for i=0 to "number of civilians"
                 setHeuristicInformation(civilian(i));
                 //This function will set value of each
                 //injured by greedy algorithm
           end for
                 generateListOfInjured();//This function will set probability by
                 //(2) and choose the best one
                pheromoneUpdate();//This function will
                 //update pheromone information by (1)
     end while
     chooseTheBestList();
end procedure

3.2 Poseidon Ambulance Results

The results of the comparison of the two different versions of Poseidon are shown in table 2. Each figure in the table represents the mean of the results of 10 simulations on each map.

Table2. Poseidon average number of rescued civilians over ninety simulations on nine maps. Version I is a version with greedy algorithm. Version II is a hybrid version combining ACO and greedy algorithm.

4 Police Force Agent

It is clear that the duty of the police force agents is not only opening the roads, but also helping the other two agents. This includes searching of the city. Using this way, the police force indirectly causes decrease in both financial and life losses For example according to ambulance death time estimation, if police force doesn't acquit his path clearing responsibility, in addition to civilian death, some noticeable time will be wasted.

In case of the closed roads even enough number of ambulances will be wasted. This will be applied to the fire brigade agents. Therefore the following priorities have been defined for the police force agents:

• Opening the roads for other agents
• Searching for civilians and opening the fire path
• Gathering the civilian information for improving the ambulance tasks

4.1 Opening the Roads

The first priority of the police force agents is opening the roads as it facilitates other agent's tasks. For this purpose we have modeled the city as a graph in which agents are the graph's vertices and roads between polices and stuck agents are the graph's edges. We do believe that there should be a path from each vertex of the graph to at least a police to make agents able to move easily within the city. Weight of each vertex is the required time for carrying the way in between. Using weighted matching algorithm, the optimal edges will be selected according to the least weight summation.

4.2 Searching for the Civilians and Opening the Fire Paths

After opening the roads for the agents, police will work on searching for the civilians and opening the fire paths. For this purpose city has been segmented to some groups of police agents. Each police team shall do its duties in the selected segment of city. This combines searching of injured civilians and opening the fire paths together. The basis is a combination of zoning the city and Poseidon's probabilistic searching algorithm.

4.2.1 New Zoning Method

Initially, city will be divided to equal rectangular sections. Numbers of the zones are the same as number of police forces. The sections will be modified by the use of the simulated annealing algorithm [3]. In each step according to zones' property one zone will be combined with the neighbor zones and will be scored based on the results. The main goal is to distribute the tasks to the agents fairly. The number of the buildings and their area, the number of the civilians, and the number of the fired buildings in this method are tried to be kept about the average. Considering this, every zone will be ranked. Finally the situation of the buildings and fire for every zone will be the same. (Fig 1) Zoning process will be repeated several times during the simulation, based on changing the situations.

4.2.2 Search for the Injured

The next step is to search for the injured in the whole zone. In order to accelerate this step, Poseidon, tried to use a new and probabilistic solution that we find buildings which should be entered to reveal the entire zone by minimal by a Greedy algorithm (dominating set). According to different maps and also to human social characteristics, we decided to find civilians' colonies. During the search process, based on our observation in each cycle, we obtain distance for next solution. If we find a civilian, we decrease the distance because the probability of finding another one around the area is more. This way, all the civilians will be discovered simply and rapidly. And if there are no civilians, we increase the distance for the next station. This helps to find further civilians and causes the rate of finding civilians to increase. Another effective factor for determination of distance to the next station is the distance from fire. Fire decreases distance because buildings next to fire should be searched sooner. When a police agent finishes searching its zone sooner, it should help other police agents and partake in their zones. Comparison between two versions of Poseidon is shown at Fig 2.

4.3 Data Gathering from Found Civilians

After search accomplishment, the police are responsible to inform the ambulances of precise information about the civilians in its zones. This has a great effect on ambulances' working results and their estimations. Therefore, Police agents come and go among civilians in their own zone. Each police agent, depending on a civilian's serious state of affairs, comes over and updates the information. If information updating of a civilian is so crucial to the ambulances, they will come over in shorter intervals.

5 Fire Brigade Agent

Fire agent is one of the most effective agents in simulation. Its main role is to prevent fire spread in the city.

Poseidon has solved fire problem by dividing city into some sections named Zone. Each zone is a specific area in city which fire spreads in with high speed. To do this, 3 major parts of algorithm are as follows:

• Choosing the best afire parts to be extinguished.
• Choosing the most important buildings of zone
• Method of cooperation among fire brigade to extinguish buildings

The number of needed firefighters determines according to parameters such as buildings area, buildings substance, buildings fieriness and distance from zones and burning buildings.

To find the most appropriate building to extinguish, the fire building area, building materials, area of unburned neighboring buildings and location of building in the zone should be considered. To control the fire in appropriate direction and not to move too much in different parts of the zone, we have been considered factors like the general direction of fire control in each area, direction of fire spreading, existing of civilians, distance from the center of city and effect of burned buildings to near burned ones (speed of fire).

5.1 Choosing the Best Afire Parts

Poseidon 2006 [4], zones are defined by the effects of each building on the other. Buildings which have more effects on each other were introduced as a zones building.

This idea is not appropriate in plans in which buildings are close together. So distance factor is considered in zones to get the best result.

To choose the most appropriate zone, we used the effects of several factors:

• Afire area of zone
• Unburned area of zone
• Amount of spreading fire in zone
• Number of existing civilians in the zone
• Time that is consumed to extinguish or control the fire in the zone
• Amount of agents which are essential to extinguish the fire
• To consider whether control or extinguish the fire is in an appropriate direction or not.

5.2 To Identify the Directions of Fire Extinguishing

Poseidon uses geometric algorithm for recognizing the most proper direction to extinguish the fire [5]. Initially, we divide the city into some convex polygons. Each of them has one of the following situations:

• Fire: Most of the points in this polygon have ignited. Gradually, as a result of fire expansion this polygon could be enlarged.
• Civilian: This kind of polygon is used for saving civilian groups. Actually, this is a convex hull around civilian groups. Ambulance activities or ignition of city induce smaller polygon.
• Normal: For keeping unburned buildings normal polygon is used.

We assign priority to the polygons according to their importance, their area and the type of polygons. Suppose a force exist between the fire polygon and the two other civilian and normal polygons. This force determines according to the cases such as polygon priority, the amount of fire expansion, the amount of building compaction, the number of civilians, Extinguish activity is entering force indirection of inverse vectors. Each vector contains some amount of damages. We try to choose a set of vectors which resisting them contains minimum amount of damages. This idea is not completed and we tried to improve it.

6 Future Works

Some of mentioned algorithms have not been implemented yet. Poseidon is going to complete the job for best results in order to present in Graz 2009 competition. In addition, Poseidon team has some other ideas to improve the work.

In communication field, regarding to score scheme changes, we have agreed to reduce transmitting information and optimize the mentioned information. In maps with no telecommunication, we want to add "continues information exchange" idea to agents' algorithms as much as possible.

Estimating death time of civilians by ambulance team agent has a great effect on efficiency of this agent. Therefore we have planned to improve estimating death time of civilians and estimating needed time for reaching them. About police force agent, our aim is to advance the mentioned probabilistic search. In fire brigade part, to define better direction for controlling fire, the algorithm we have demands some changes and we want to improve it.

References

1. Habibi, J., Hassas Yeganeh, S., Habibi, M., Malekzadeh, A., Mortazavi, S.H., Salehe, M., Vafadoost, M., Zolghadr, N.: Impossibles Team Description, 2008: Heuristic Mechanisms: Radar.
2. Xiong, Y. & Kuang, Y.P. (2006) The CRIOCM 2006 International Symposium on "Advancement of Construction Management and Real Estate": ANT COLONY OPTIMIZATION ALGORITHM FOR RESOURCE LEVELING PROBLEM OF CONSTRUCTION PROJECT. Beijing Jiaotong University.
3. Ingber, L.: Simulated annealing: Practice Versus Theory. Lester Ingber Research, 1993.
4. Mostafazade, N., Ardeshiri, S., Movaghati, S., Hariri, S., Jahanzad, Z., Fathi, A., Valipour, M.: Poseidon Team Description, 2006.
5. De Burg, M., Van Krefeld, M., Overmars,M., Schwarzkopf, O., Computational Geometry: Algorithms and Applications, Springer; 2nd edition 2000.
6. Mirhassani, R., Najafi Ardabili, S., Shariati, Z., Torkashvand, F., Yousefi, M., Tavakoli Ghinani, M.: Poseidon Team Description, 2007.