Poseidon Team Description Paper Robocup 2014, Joao Pessoa, Brazil

Ava Abderezaei, Mahshid Farzan, Kimia Ghaffari, Pooria Kaviani, Maral Khodaparast, Shiva Sadat Mahdavian, Fatemeh Nasehi, Rozhina Pourmoghaddam

Farzanegan High School, Robotics Reasearch Group, No. 56, Shahid Sarparast St., Taleghani Ave., Tehran, Iran; Tehran University, Enghelab Ave., Tehran, Iran; Sharif University of Technology, Department of Computer Science, Azadi Ave., Tehran, Iran

Abstract This manuscript describes the algorithms and contribution of Poseidon 2014 to acquire the optimum and efficient solutions for rescue agent simulation problems. New ideas in World-Modeling structure and agents' decision were implemented. Each section, explains new algorithms of this year's imp lant at io n in details. This version of Poseidon team is based on the sample code of the server with extensive changes in structure of agents and World-Model. In Poseidon 2014, computational geometry and artificial intelligence algorithms h a s b e e n u s e d for solving the problems of rescue agent simulation.

Introduction

The purpose of Rescue Simulation League is to decrease life and financial losses caused by natural disasters such as earthquakes, floods and etc. In order to achieve this goal, a large urban disaster is simulated and indicates agents' actions in this situation. This simulation matches real world limits and problems as accurately as possible. Rescue simulation agents include ambulance team agents, police force agents and fire brigade agents. The main task of the police force is to open the closed roads, the main duty of the ambulance team is to save lives and extinguishing the fire is the main duty of the fire brigade agents. In addition, all the agents are responsible to facilitate the other teams' tasks. The Poseidon team is trying to find solutions and improve available algorithms to solve agents' problems.

Our contributions include changing in World-modeling, and also police force agents' working system has been changed by implementation of "Task". Since the main duty of the ambulance team agent is to rescue the maximum number of civilians, selecting injured civilians is noteworthy. Thus we implemented a new idea to choose and rescue civilians and centralized it. In addition, a new algorithm for the fire brigade agents' "Fire zoning" and "Vision shapes".

World –Modeling and Communications

Considering the problems we faced last year, we declared there are some problems in core of the base-code. So we decided to implement a more practical and scientific algorithm for world-modeling.

The idea starts with separating the map into some shapes. Each shape is a polygon created with the borders of the areas. These shapes are generated by starting from a point in the city and followed the borders of the areas until having a closed shape [Fig 1]. This process will be continued until the whole city divides into closed shapes. As we can see, we have a lot of small shapes (inner shapes) and one big shape that includes whole city (outer shape, it exists because buildings in the out layer of the city have some borders that faces the out of the city. These borders together create the big shape). Then the big shape will be constricted with the amount of the agent's radius and small shapes will be expanded with this amount. Then the shapes will be differed from areas of the map. Now there are miniaturized areas in the map, and also each blockade will be expanded with the amount of the agent's radius, so agents can be considered as points. Finally the path between two points can be calculated by our old visibility graph method.

Although this is an accurate and reliable method, the amount of calculations required, will take a lot of time. So the first agent that connects to the server, calculates the necessary information and saves them to a file so that the next agents can access that data from the file. For the maps with that don't have pre-computation time, the last year methods will be used.

In the communications field, we figured out that although our algorithms were useful and effective, using them was hard for our new members because there were some complexities in the codes. Therefore, new system has been designed for the radar. This system included units named "Package". Each Package had a specific kind of message and provides certain facilities such as adding an area or a number to it. It could store as much data as we desired and could be simply sent. It's the same in the hearing process. It means we can gather information from it by using simple methods. Adding to the "easy-to-use" property that this new Packages provides, they come with more solidarity [Fig 3].

Also the part of information about the ways that had been worked with the index of the entrances haven't been send over the radar any more cause we found it useless comparing to amount of the volume it needs in radar capacity.

Ambulance Team Agent

The ambulance team agent is one of the most important agents. Their coherent plays an important role in maximizing the number of civilians they save. Therefore, it is necessary to centralize the ambulances and find the best algorithm for their synchronization. One of the advantages of this centralization is spreading the ambulance team agents efficiently.

In order to find the best form of distribution of the ambulances to rescue the civilians, the rescue operation of each ambulance team agent has been simulated repeatedly. A table is used to determine their distribution pattern and the time required for saving the civilians.

The first step is estimating the "Deadtime" which is the amount of time a civilian can stay alive. Based on our estimates, each one of the civilians is placed in a row. Then, an ambulance is chosen randomly to save each civilian. The time it takes for the ambulances to get the civilians to refuge is also calculated.

For the calculations of the table, the average distance the agent passes in each cycle is measured. Then, the number of cycles it takes for the agent to save the civilian is calculated according to it. Of course, based on the Deadtime, not all the civilians can get saved by only one ambulance team. Therefore, the number of agents required will be calculated using the calculations below and more ambulance teams will be included in the table.

Each of these random tables is called a "State". In each cycle of the game, the States are randomly made 1000 times for the civilians that don't have ambulances assigned to them. Each State has a value which is calculated according to the number of saved civilians and agents. As it might be expected, the worthiness of saving an agent is twice as much of a civilian's. The State which has the most value will be chosen and the ambulance center will assign it to ambulance teams in the format of Tasks. [Table 1].

Ambulance simulation

Feedbacks

After receiving the task, each ambulance evaluates whether it is possible to do the task or not in order to reduce the percentage of estimation errors because it is possible that the center's information wasn't updated. The feedback will be sent as two Booleans. The first one shows if the agent has any cleared way to that human. If this Boolean is false, the center will assign this task to another agent. The other Boolean reports to the center whether the task is practical or not. If the Deadtime is imminent or the number of free ambulances isn't enough, the task will not be practical. So, the civilian will be removed and also the task will not be given to any other ambulance team.

If the map is low-communication or no-communication and so the ambulance-team-agents don't receive any task from the center, it will choose the nearest civilian to it itself and start rescuing it.

Rescuing agents and civilians on the street

Sometimes, because of the aftershocks or the gas tanks, civilians and agents may have Buriedness in the roads, will be rescued with this new algorithm.

The ambulances move with more synchronization as a result of these new algorithms. They spend less time for useless moves. They start their next move right after finishing the current one and there is less waste of time.

Police Force Agent

The principle responsibility of the police force agent is cleaning the roads in a way that the other agents could perform their duties effectively and more efficiently.

Request

"Request" structure makes our targets (helping the other agents by clearing their path to their targets) sorted by their value in order to be done. This structure would help us to recognize agents' needs in detail comparing to previous years' code that we just do some regular cleanings. This helps us to cleaning important ways quicker.

Each Request has a start and an end. Start is the position of the Requester's (the agent who is sending a Request), and End is the area of the Requester's target.

At first if there is a stuck agent; it will send a Request that its end and start are both the agent's position.

There are two different types of requests:

If there is an agent who wants to reach its target and there is no cleared way and no reachable Police Force Agent; the agent will send a Request. For example the fire brigades that wants to reach the fire point or ambulance teams that wants to reach civilians.

All of the refuges and hydrants will be given to the police force by the structure of Request, both End and Start areas will be the position of the hydrant or the refuge.

Task

Requests will be divided into "Tasks", and Tasks will be assigned to police forces by the "Hungarian algorithm".

There are some ways for making tasks:

• When two requests have a way or a part of a way in common, that part will be one task and the rest will be transformed to one or more tasks [Fig 4].
• For some of the big Requests (Which there are some distance between end and start), they will be divided to more than one task according to their shape [Fig 5].

Different kinds of clearing

The main action that the police forces do, is clearing blockades. So we arranged different kinds of clear for different situations. Despite being able to clear blockades from further than our range of vision, we decided to clear them from close distance. It will let us use the maximum power of clearing and getting informed when the blockade is completely cleared.

BadBlockClear

This method will clean the way by cleaning the obstacle blockades and also cleaning the blockades of the entrances of the input area. So it's much faster than normal clearing.

FastClear

This method will only clear the blockades which prevent the agent from reaching to its target.

Fire brigade Agent

Fire Brigade Agent main duty is preventing the fire points from spreading.

Convex hull VS. Shape reconstruction

Due to this important duty, one of the fire brigades' important works is zoning the fired buildings. This can be implemented by gathering near fired buildings together in a zone. We call each of these zones a "FireZone". Then fire brigade agents will be assigned to zones.

For extinguishing each FireZone, we understood, Fire Brigade Agents must extinguish frontier buildings to prevent the spreading of fire.

In the previous years "Convex hull algorithm" had been used for finding frontier buildings of the zone but we realized this algorithm could not find all the frontier buildings in some zones. Therefore we used a more efficient algorithm. Its name is "Shape reconstruction algorithm". Considering that this algorithm can create a concave shape, it calculates the frontier buildings more effective than Convex hull algorithm [Fig 6].

Vision-Shape

We need to know that each building can be seen from where in the map because this shapes the main base of moving and extinguishing. In the previous years a set of points were found for each building which that building could not only be extinguished but also be seen from them. We decided to change the vision points to vision shapes. Because a list of points aren't exact and complete but shapes are more accessible and more reliable than points. The problem of vision shapes is like "Art Gallery problem".

First, there is a circle with the radius of distance view amount around each building that the building can be seen from it. Then the obstacles in the way should be considered to figure out the Vision shape. For solving that problem (figuring out the vision shape), the "Segment Weak Visibility" algorithm has been used. By this algorithm we can calculate that each segment of the building can be seen from where and then get the union of this shapes and create the whole vision shape of the building [Fig 7].

Search

It has been proved that a good search can affect the operation of a team in a positive way. And one of the most important factors in search is the zoning method. From our previous experiences , we recognized that an efficient zoning is the one that makes the agents move less, not the one that zones areas with less distance together [Fig 8].

To reach that purpose, we decided to use BFS algorithm for zoning, the same algorithm has been used for finding the ways in the team. This BFS starts from every building in the city. Next, it continues with the neighbors of the buildings and so on. Buildings will be in the same zone if only their BFSs reach each other sooner than reaching the other building's BFSs.

References

1. Abadi R., Behazin B., Eslami M., Ghasemi F., Moradi B., Pourmoghaddam R., Ramezanian M., Rezayat Z., Seyed Majidi N., Shirvani-Mahdavi N., Vartanian A., Kaviani P. : Poseidon Team Description Paper, 2011
2. Afzal A., Alipoor P., Alizade P., Arian nezhad M., Ghaffari K., Hasanpour Gh., Jahedi K., Kaviani P. , Omidvar G.: Poseidon Team Description Paper, 2013
3. O'Rourke J.: Art Gallery Theorems and algorithms, 1987
4. Akbari H., Ghodsi M.: Visibility Maintenance of a Moving Segment Observer inside Polygons with Holes