Poseidon Team Description Paper

Romina Abadi, Bahar Behazin, Mahta Ramezanian, Zohre Rezayat, Niousha Mazaheri, Anooshik Vartanian, Melika Shah-Hosseini, Mostafa Vafadoost

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

Abstract The script explains the algorithms that we used in Poseidon 2010's program following and improving Poseidon 2009's codes. Some Parts of the later code specially the algorithms that we used for the first time for the better effect and adjusting it to recent server changes. The main changes were in Fire brigade agents zoning algorithm, implementing the rest of the ACO algorithm for ambulance agents and improving the communication between the forces. Police's main algorithm is still the same and there were some changes made to improve the performance of this agent.

1. Introduction

After all the harsh natural events such as earthquakes, if people don't plan any organized strategy to manage the such disasters, Its consequences which could be correctly predicted and controlled can have more compensation than the main crisis .

Such great catastrophes have different results such as: Destruction of total or partial capacity and lines of communication channels such as telephone, Internet and radio, demolition reduction of traffic capacity in the streets and alleys, the destruction of bridges and airports and transport networks, to cut power lines, fuel rarity and finally a large amount of city may burn. Moreover, all these are just examples of distress caused in such natural events.

Disaster managing headquarters should Predict and supervise all of these pinches and challenges.

This project focuses on the part, which directly reduce the number of victims and rescuing injured civilians and extinguishing burned buildings in minimum time and forces in occurrences like these.

After the changes of the server and the rules of 2010, we improved the speed of opening roads by the agents in our Police Forces and the communication had some changes too, which are efficient. Also in maps with No Communication, spreading the data has improved significantly. In addition, we totally changed the algorithms of Fire Brigade zoning, so that we do not have to use apexes as much as the last team's code needed.

2. Communications

One of the factors that powerfully affect the decision-making process is Communication.

Agents have limited information of their own world and they have collected this information by moving around their world. Therefore, it is essential to have a better communication in order to decide correctly. According to this vital need, Poseidon09 used Impossibles radar System for having a suitable communication. In this system, agents receive the data in three steps and they should decide after updating the received data.

However, considering the changes that the server created and negative points for excessive use of "Tell" some limitations were determined for sending Information to agents.

In the new Server after the noise, which has been added, we implemented a new strategy. When we do not have any information to send in the radar system, we will write header and send a message with length one at least, so when the noise influences on the channel, the agent will notice, so they can change the channels.

Awareness of noise

There are two different conditions:

• 1- One of the output or input noise exists.
• 2- Both of them exist.
• In first one, if there is not any output or input noise, the sender or receiver can notice. If there is an output noise on sender, so receiver can tell this, to change channel or not to send anything.

In the other hand, if there is an input noise on sender, it can tell the receiver, because it means the receiver is not able to send anything and has to change its channel.

• In the other one, if we had both output and input noise, no one will notice. In this condition, the agent (Server) waits to hear something and if after more than 10-cycle, it does not hear, and it will change its own channel. If one of the channels is available, it means we have faced a no-communication map. If not, we will use the following strategy.

Choosing the channel

There is noise on the Centers channel:

In this condition, we think, its better that Center send nothing until the end of the limited time. In addition, its Agents set their channels on the other center (If that is able to hear and tell) and use its information.

It is important if it is Ambulance Agent, because they need center to have a task, in first priority the Ambulances tell their information to the new center.

There is noise on Agents channel:

Then we have their Center channel, which is able to hear and tell. Therefore, the Agents set their channels on it, so they hear the information. As you know, the sense of Police Forces is the most important. Therefore, if the noise affects Police Officers' channel, they tell their information to Fire Station.

The previous paragraphs was for at least 4 channels that there is one center channel and the agents can be divided into group n(in number of tells which center can hear) and tell to it.

For less number of channels we set channels according to following table:

Channel Configuration Based on Available Channels

2.1 No Communication

Over time, the importance of maps in which some possible exchange of information with no and therefore the importance of this part of the program is significant. Accordingly, the program for improving this section Poseidon years following parts:

• 1. Dividing ambulance (in related agent will be explained)
• 2. Receiving data from Center

Earlier the transition was that the city divided by the number of Police Forces that went to center of each zone to share the information which Ambulance and Fire Brigade of this zone went to the same center and received the information.

2.1.1 Fire Team Strategies

According to the problems, which existed after the omitted apexes from the given information (specially the Foligno map) we tried to be accurate in targeting fire and dividing the world into accurate zones for finding the most important target with significant accuracy in comparison to lots of easier algorithms. In other words using a new zoning algorithm, this does not need apexes as much as before.

2.1.2 Exchanging the Information

As you know, No-Communication scenario importance is high, because of the disconnection of the communication system in the real world, which happens after a disaster. For better performance, we have changed this point of Poseidon09's algorithm

There are two important parts presented

1. Which of the information must be sent:

As illustrated in Poseidon09's TDP the final idea of the team was dividing the city based on number of polices and spreading the information by them. That in specific cycle forces available in one place will approach the police and receive the data from them.

This idea was effective but it had problems such as waste of time by the action and limited gathering points. To solve the problem we use Center instead of Police Force, that is one centre assigns for main point and according to the situations assigned for forces, they will visit centers and transfer data. For example when polices face 3-4 new civilians if ambulance's first priority is total time of 40 cycles or they cannot save them or in 50 cycle, they will approach the centre. For Fire Brigades existing fire is important that the forces will detect it themselves and in search time the position of civilians are essential. Therefore, in beginning of search they shall go to centre. We should mention that we have predicted new detected civilians and the time ambulance did not approach center, and Team is looking for a more accurate estimation. In maps that no centre is presented we will act as our previous team and agents will transfer information with Police Forces in that zone.

2. How to send them:

As result, the facts divided to 3 parts: Forces (Civilians and agents), buildings and roads.

• 1. It is obvious that information of civilians and buridness forces is crucial. During the work, we found out that the Fire Brigades need each other's positions so we sent them too.
• 2. We will receive Fieriness and all information about building's fires in a short time. As result, there is no need to send them.
• 3. At first, we presumed the roads as open so the information about open road does not help much so we send information about the ways we certainly know are blocked.

3. Ambulance Team Agent

The main algorithm in our ambulance team is Ant Colony Optimization (ACO). Rescuing the civilians in a limited time is much like resource leveling problem that is used for saving time. ACO is one of the best solutions for this problem. In ACO we program agents in limited time cycles and run ants in parallel spaces, these ants find the best way to target, and they leave pheromones behind themselves that can evaporate. This omits undesirable ways. It helps us to find the best possible path.

The main function of Poseidon10's Ambulance is improving the previous year's team code and solving the bugs and computational problems of it.

We have solved these problems:

• 1. The effect of distance on agent's making decision was not enough, causing them to waste a lot of time.
• 2. In case of increase in the number of the agents, the run time process would increase a lot.
• 3. ACO had to ignore the civilians who were facing fire because they could not estimate the time needed for fire to reach the civilians.
• 4. ACO takes many risks, because the predicted time for the civilian's dead time and the time needed for transportation is not estimated accurately. Therefore, the agents acted conservatively and some times had to ignore the civilians who could be saved.

These are our recommended solutions to improve these mentioned problems:

In order to decrease the Process, we grouped the civilians based on their distance from each other and from refuges, so that near civilians will group in one. We scored each group according to the number of their members and their dead time. Then we gave ambulance agents to each group according to their scores and the number of the agents.

Now we can consider each group's civilians to run ACO for each ambulance instead of considering all civilians. In this order, the process will be reduced because of the reduction in the number of the civilians.

Each group will be updated every 20 cycle based on the renewed data and the ambulances will be assigned to the new groups.

In this way, we cannot only reduce the process but also can save the time duration of the ambulances on the way. We will also be able to upgrade the civilians' data faster.

Last year, the selected program for choosing the best ant, was the one that had been able to save the greatest number of civilians and the only criterion other than that was the health conditions of the civilians.

As our estimations will be more inaccurate when the time is further, we decided to score each saved civilian according to the time that it has been taken to refuge and his health condition. The score for each ant is the sum of each saved civilian's score that it has saved. Ultimately, the best program is chosen.

The score for each civilian is calculated as follows:

$2t =$ The arrival time of the civilian to the refuge

$t=$ current time

$$x = t^2 - t$$

We have estimated this to a third power function as follows:

Each civilian's score= $$y = -3E - 08x^3 + 2E - 05x^2 - 0.006x + 1.391$$

To estimate the dead time more accurately, we consider the bias of our previous estimation.

$T_n =$ the exact amount of the damage difference in the nth cycle

$P(1)^{n+} =$ the estimated damage difference for the (n+1) th cycle

$\alpha$ (Alpha), $0 \le \alpha \le 1$

$$T_{(n+1)} = \alpha \times T_n + (1-\alpha)P_n$$

The amount of $\alpha$ is determined according to the deviation of our estimation from its real amount ($P_n$) and from out previous estimate ($T_n$)

4. Police Force Agent

Police function is to facilitate other agents' operation. Police functions are as follows:

• 1. To unblock the agents stuck in the roadblocks
• 2. To make an access path to burning buildings
• 3. Searching for people who are missing
• 4. To unblock the minimum possible roads, so that all the strategic points have access to each other.
• 5. Patrolling the city roads to update citizens' status

To select the road or path that is required to be unblocked, the access of an agent to any given refuges analyzed:

Re-group agents who have access to each other AND/OR are near to one another

• 2. Develop the Minimal Spanning Tree of open or already- unblocked streets.
• 3. Identify the nearest agent to any given police.
• 4. Measure the distance in between the police and identified agent.
• 5. Add the distance (4) to the length of minimal spanning tree of the group, (Picture 1)
• 6. Add the result with the distance to the nearest refuge.
• 7. Save the result.

4.1 Urban Zoning for Disaster Prevention

At first, the whole world divided in to number of available police agents then Borders of the Zones will improve with the "Simulated Annealing" algorithm. So that in each stage, one of them will be chose and rated according to its critical situation and it begin to commix with neighbors zones (Each zone Rate depends on number of buildings, area and civilians of the zone) Then the surrounding zones will be combined and re-Rated, this process will be continued up to all the zones rate become equal.

We aim to attain similar conditions among police forces for best results. That is why we tried to have relatively equal rating parameters in all zones. Zoning scheme can be repeated several times during the simulation.

4.2 To open the way to reach the burned building

After the identification of each Police Zone, Searching for the civilians starts. Searching around the fired area has more priority. It is very beneficial for the Fire brigades, because during the Searching' paths around fired buildings will be unblocked automatically.

Obviously, other advantage of this strategy is that the civilians those are near the fire will be seen earlier so the rescue team will salvage them earlier because civilians around the fire die quickly.

4.3 Searching for the Civilians

After finishing unblocking, the ways each police travels logically between the civilians in its zone to report the new information to other polices and ambulance will use these data. If updates about a specific civilian are important for ambulance then police will visit that civilian more often. Another importance of this job is the civilians near fire will be identified sooner and will be shortly rescued by fire brigades. Saving the civilians around fire is vital because their health will rapidly decrease and as result will die soon.

Each police searches for civilians in his own zone. To increase speed of rescuing we use "Dominating Set" algorithm to find out minimum places those should be seen to find the civilians then we search for civilians groups. In each cycle one building will be searched, if there is no civilian in the house and within 10 meters next destination will be a building that is far from the previous, because we can guess there is a few civilians near that.

The possibility of other existing civilian is slight and while the whole purpose is rescuing the place, where the most civilians exist so when we found a house with a civilian trapped in it we move to the next one because the odds are high. By this strategy, all civilians will rapidly be under control.

Another important factor for discovering the distance until the next destination is the space from fire. As a result, if the fire was spotted the priority is the houses around and then the farther houses will be chosen as a goal.

When police agents do its function, it will move to other zones and shares their zones. Unblocking the least roads in a manner that all city spots will be corresponding. Because opening the roads is the main duty of police, it should find a way for disengaging the paths before starting to seek information about civilians.

As a result, we consider the city as a graph that its edges represent roads and vertices are like points of the city. If we want to match all the city spots there must be a connected graph or the least weight we use the Kruskal algorithm for finding the smallest spanning tree in weighted graph. After finding the parts of smallest spanning tree in the related zone of each police will unblock the paths on that way if blocked. This will help other agents to reach every spot of the time and will reduce the traffic.

5. Fire Brigade

The Fire Brigade (FB) agent is one of the most important agents in RCRSS because of its influence on fire spreading .Therefore we began to write a code that contains better and more efficient algorithms than our last code for RoboCup 2009. Based on the changes in the rules and simulators like the amount of centers and the wind, which has been added, The FB encountered many problems. For example, the way that fire spreads will depends on the side of the wind; thus, we added some new factors in our formulas based on these changes. We have to implement new strategies to control the fire spreading. We explain one of these strategies that we have implemented here:

When the map includes the wind, the FB agents understand that, it is better to try to extinguish buildings, which are on the side of the fire, which is equivalent with the side of the wind blowing. Because it can understand that, the wind will influence on fire spreading in that side.

In addition, it affects the speed of fire spreading in each side. For example, when the fire point is at the corner of the map, the FB agents try to extinguish buildings on side of the fire, which is closer than to the other parts of the city.

5.1 zoning

In the Poseidon10, we have implemented a new zoning algorithm for the Fire Brigade agent, which is based on the side of the wind resultant vector, zoning starts with finding the side of the wind blowing. Then it supposes some lineal on the wind resultant vector, one less than the amount of Fire Brigade agents. We have implemented this zoning to divide the difficulty of extinguishing a building among all fire brigade agents.

5.2 choosing buildings

The main responsibility of the FB agent is extinguishing the burning buildings but choosing the best building is the most important part here. It depends on the time an agent needs to extinguish building, the time to get there, the amount of civilians, which are in or around the building and the priority that we have assigned on burning buildings, based on some factors of buildings that we have calculated.

$$PN_{i} = T_{i}^{CV_{i}}$$

$$T = \left[\frac{M \cdot A \cdot F}{Tem \cdot FN}\right]^{-1} \cdot K$$

$$Priority = \left[T + \sum_{i=1}^{n} PN_{i}\right]^{CV}$$

Here, in the formulas PN is the priority of neighbors, T is the predicted time for extinguishing the building alone, CV is the amount of the civilians in the building. M is the material of the building, A is the area of the first floor of the building, F is the number of floors, Tem is the temperature and FN is the fieriness of the building. K is a static number, which we found by experience. The server does not give Tem and we have estimated that with another formula, which depends on fieriness and ...

6. Future works

Since Poseidon2006, we did not focus on Fire Brigade Positioning very accurately; future teams can design an appropriate positioning strategy. As we mentioned before, police force agents are as good as we decide not to spend lots of time to make it more optimally, in other words we aimed to improve the search to minimize the time we need to find all civilians.

Many older algorithms replaced with new and tested processes with higher effects and some of the elder algorithms were kept but debugged and optimized. However, the algorithms can improve and we will point out some of them in this part. Because it is the First year, the noise has been added to input and output messages the ideas in this part could be definitely improved.

We did not focus on Fire Brigade Positioning very accurately also finding the correct building to be extinguished can be more accurate too.

7. 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. Xiong, Y. & Kuang, Y.P. (2006) The CRIOCM 2006 International Symposium on "Advancement of 2. Construction Management and Real Estate": ANT COLONY OPTIMIZATION ALGORITHM FOR RESOURCE LEVELING PROBLEM OF CONSTRUCTION PROJECT. Beijing Jiaotong University.

2. Ingber, L.: Simulated annealing: Practice Versus Theory. Lester Ingber Research, 1993.

3. De Burg, M., Van Krefeld, M., Overmars, M., Schwarzkopf, O., Computational Geometry: Algorithms and Applications, Springer; 2nd edition 2000

4. Afzal ,A.Ariannezhad ,M.Shahhosseini, M.Mosadegh, Z.Vafadoost, M.:Poseidon Team Description, 2010