RoboCup Rescue Simulation League Team Description <Kherad (IRAN)>
Saba Kiaei, Saina Ghadiany
Manzoumeh Kherad Institute IRAN
Abstract Kherad team was formed in spring 2013 while all members had ro botic programming competition experience before; especially in Demo league. Team was honored with the 1st place of "Using Modern Technology" prize in the aforementioned competition. Considering member's interest, Kherad decided to participate in Rescue Simulation league. To improve the level of the competitions, each year, codes are being released in Rescue Simulation league. Therefore, Kherad team decided to use S.O.S base code as its base.
1. Introduction
Each year, millions of people die because of natural disasters. With a practical disaster management this statistics can be decreased to the minimum. The purpose of the Rescue Simulation league is providing a platform in which rescue operation strategies can be tested and this platform is based on the reality. After the terrifying Kobe's earthquake in Japan, 1995, which killed 6000 people, Rescue Simulation project was initiated. This Project is a new practical domain of RoboCup. Its main purpose is to provide emergency decision support by integration of disaster information, prediction, planning, and human interface.
A generic urban disaster simulation environment is constructed on network computers. Heterogeneous intelligent agents such as Fire brigade, Ambulance team, and Police officer conduct search and rescue activities in this virtual disaster world. Real-world interfaces such as helicopter image synchronizes the virtuality and the reality by sensing data.
This problem involves advanced and interdisciplinary research themes. As AI/robotics research, for example, behavior strategy (e.g. multi-agent planning, realtime/any-time planning, heterogeneity of agents, robust planning, mixed-initiative planning) is a challenging problem. For disaster researchers, RoboCup Rescue works as a standard basis in order to develop practical comprehensive simulators adding necessary disaster modules. This paper explains Kherad's work which is based on artificial intelligence, sense, communication, different algorithms and etc.
2. Clustering
Clustering is a sufficient part in how agents will coordinate and do their tasks. By the virtue of this importance an assured clustering algorithm is needed. The algorithm that has been used in this code is K-means algorithm. This algorithm is used for each type of agents separately, meaning that for each type the number of clusters is equal to the number of agents – at any rate, it is used three times when the code is running.
After the clusters were specified, each agent will link to what of those clusters using the Hungarian algorithm.
3. Agents/Agent skills and action selection
3.1 Fire Brigade Agents
Fire Brigade's responsibility is preventing the spread of fire in order to decrease the measure of the damage and prepare a suitable condition for Ambulance agents to be able to make the best decision. Without a good strategy for fire agents, even if all agents perform flawless, the whole map is going to burn and all the civilians are going to die.
3.1.1 Cluster Assignment
Using K-means and Hungarian algorithm is to make sure all parts of the map are covered in order to not to miss any fire and to perform better.
3.1.2 Sates
Each fire agent goes through some states to execute its tasks. These tasks are put together hieratically. That means each agent should have the conditions of a state to execute the states' tasks. If not, agent checks the other states to find the right state for its own conditions.
3.1.2.1 States Explanations
States are based on possible situations for agents. Totally agents are in two positions: They're able to execute those tasks that are helpful to preventing fire like searching and extinguishing or they're not and they should do those tasks that make them recover. The main bases for dividing states are agent's water quantity and health percentage.
3.1.3 Fire Zone
Sometimes, fire spreads so fast and burns the buildings' neighbors before agents have the chance to reach the burning building and extinguish it. In this case, the best decision is controlling the fire and its spread and not extinguishing the burning house and its neighbors which all are on fire. Therefore extinguishing those burning neighbors that have neighbors that are not on fire and controlling their temperature is the best action to control the fire.
A fire zone is created when a building ignites and all the neighbors that have a higher than 20º temperature, get added to the fire zone. The important thing to know is that not all of a fire zones' buildings are on fire because the ignition temperature is 30º but all the buildings that have a temperature higher than 20º are added to the fire zone. This is meant to control the fire better and prevent the ignition of high temperature buildings.
3.1.4 Weight and Decision
At first, the agent should choose the most important fire zone and then it should choose the more important buildings among the fiery buildings (buildings that are in a fire zone) to extinguish. There are three factors for choosing the most important fire zone.
1. Center
A fire zone that is in the center of the map can effect more neighbors than the ones that are in the corner.
2. Area
Usually, not always, a larger fire zone is a more dangerous fire zone.
3. Estimating Fire Spread
To calculate the measure of fire spread, fire estimator was designed. Fire estimator calculates the number of the buildings that are going to ignite and the measure of damage in the case of worst fire control which is the maximum measure of fire spread. It calculates it based on the area and the number of the neighbors and the neighbor roads.
To find the most important building, each building in a fire zone has a weight. This weight is calculated depending on the following factors. Based on each factor, a coefficient –which is variable depending on each factor- is being multiplied to the weight number. These coefficients are found based on tests and experiences. Factors are:
4. Temperature
As the temperature increases, the building weighs more but this statement is true for the temperatures lower than 30º which is the ignition point. It means after 30º, the building weighs less.
5. Fieryness And Ignition
As it has been said before, all the buildings with a temperature higher than 20º are added to the fire zone and it means fire zone contains some buildings that aren't on fire but their temperature and the risk of ignition for them is high. These buildings are very important even more than the fiery buildings because they're not on fire but they are going to be very soon and with this fact that the goal is the least
damage, preventing them from getting ignited is the proper action; therefore, buildings with 0 fieriness (not ignited buildings) , weigh more than ignited buildings.
6. Area
Buildings with large areas, can speared the fire more than the small buildings; therefore, extinguishing them is in an advance priority. The weight of buildings with larger areas is more than buildings with smaller areas.
7. Number of neighbors
The number of the buildings' neighbor is very effective on the spread of fire. With more neighbors for a fiery building, more buildings are in danger; therefore, buildings with more neighbors, weigh more than the others.
8. Center
Being the center of a fire zone, makes a building a major threat for fire spread because fire spreads more from the center. To find the center buildings in a fire zone, the number of each building's neighbors is being calculated and the buildings with the most neighbors are considered as the center buildings.
9. Estimating Fire Spread
As it has been said before, the number of the buildings till the edge of the map or another fire zone or a long and wide road, is being counted for each building and the building with the most neighbors is considered as a very important building because it can spread the fire better
The fire brigade agents' decision is based on each buildings' weight. It chooses the building with the most weigh among the fiery buildings and extinguishes it. For example if a buildings' temperature is between 200 and 500, its weight is multiplied by 5 and if its area is between 20 and 50, its weight is multiplied by 2. Each factors' effect on the weight is condition based and the measure of effectivity is based on experience.
When there are enough agents, there are always at least two agents who don't extinguish the fire and just search. They extinguish only when the other agents go to the refuge to full their water tank, so the fire won't spread while they're gone. An example
3.1.5 Corner Finding
At first, the distance of each two points of the map is being calculated. The furthest two points of the map become selected. Then, a circle with the diagonal of their distance and the center of the map and then the tangent of the circle as the origin, are being drawn. Those two points are on the circle edges. After that the code draws a line between the origin point and all the points of the map. The line with the least angle with the origin is chosen and its end is counted as one of the points of the maps' edges. This point is now the origin for the algorithm and all stages are being repeated for this point. Because the first two points where the furthest points of the map, the algorithm is being executed from two sides and when those sides' points meet each other, the algorithm ends and the edges of the map are being found.
In the previous algorithm the edges were found but it is necessary to find the corners of the map because corners are the places that are less important and the pervious algorithm was a means to find the corners. A corner is found when the angle of a line changes rapidly.
3.1.6 Lead of the Corner Fire
When the number of the fire zones in a map is more than a specified number, the agents won't extinguish the corner fires. They just lead it to the end of the map with extinguishing some specified buildings in that fire zone. It's because corner fires zones can't spread the fire and they're less important than the other fires zones. Even a few agents can execute this action therefore other agents are going to be prepared and free for more important fires.
3.2. Ambulance Agents
The main responsibility of Ambulance Agents is to rescue damaged civilians. The most important part in Ambulance team function is to select the best civilian in order to be rescued. If the Ambulance Agents can decide properly, we can be sure that every important civilian in map, which the importance of each civilian is being calculated in each cycle according to its death time and buriedness, will be rescued till the end of the run.
3.2.1. Center-based decision
There are various situations possible in a rescue map. If the connection is in the high level, means that all agents can send message to others, there will be a center specified to makes decisions for other ambulance agents.
3.2.2. Cluster Assigning
As said before, if the communication is in the lowest level, means that agents' communication with each other bound to trying for sending messages, each agent must decide for itself. In this situation, there will be a cluster, specified by Kmeans and Hungarian algorithm, for each agent.
3.2.3. States
3.2.3.1. State Explanation
Our code is state-based; each agent in each cycle checks some specific states and if the conditions of that state are true, it does the task specified for that state.
3.2.3.2. Choosing civilian
The main strategy of choosing the best civilian is the same in selfagent-based decision or center-based decision. Nearly 10 cycles after the start of the run the decisions will be made -10 cycles so we can be sure that at least a few civilians are identified the best decision is going to be made. At first, each civilian will get a value according to its specifications as its buriedness, death time, number of ambulances it needs to be rescued, etc. Then, starts from the most important civilian, each civilian will get some ambulances, according to how many ambulance it needs to be completely rescued, for itself. By this strategy, we can assure the most important civilians will definitely be rescued.
Civilian value = 1/death time * burridness * hp
Death time is a somewhat measure according to the civilian's buriedness, health, hp etc. The death time calculates using the particle algorithm. A basic variant of the PSO algorithm works by having a population (called a swarm) of candidate solutions (called particles). These particles are moved around in the search-space according to a few simple formulae. The movements of the particles are guided by their own best known position in the search-space as well as the entire swarm's best known position. When improved positions are being discovered these will then come to guide the movements of the swarm. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered.
3.2.3.2.1. Center-based
In high-level communication, center has information about almost every civilians and ambulance agents; therefore, the best person to decide for every one is center. As said before, center will start assigning from the most valuable civilian. The most valuable civilian will get the best ambulance/s for itself. Each ambulance has a free time, according to its already task and when it is going to be available to rescue another civilian. Whenever an ambulance is being chosen for a civilian, that civilian rescue time will be added to that specific ambulance free time. Therefore, for the next civilian, that ambulance will have a new free time. For choosing the best ambulance for each civilian, the value of that ambulance will be calculated by its distance to that specific civilian and when that ambulance will rescue that civilian completely. A specific calculation will show which ambulance is better for that civilian. This decision is provident because it will be made by the number of civilians that will be rescued according to this specific decision.
At first of our programming for the rescue league, we were trying to calculate both best civilian for ambulances and best ambulances for civilian and then tie them in. But this algorithm was extremely complicated and it didn't worth the calculating time.
Ambulance value for each civilian = ambulance free time + distance to the civilian + buriedness + time to refuge (this formula will give the time in which the civilian will be rescued)
One important thing in high-level communication is the communication between ambulances and fire-bridge agents. Ambulances can inform fire-bridge agents by messaging them about fire bridges which might be dangerous for lots of civilians, or on the other hand, fire-bridge agents can inform ambulances about a filled-civilian place in the map. Center will decide if the ambulances should go to where they have been formed of or not.
3.2.3.2.2. Ambulance decision
In low-level communication, each ambulance will decide according to its cluster civilians. The strategy is the same, only civilians will be changed.
In no-level communication, ambulances only can inform others about their situation by talking to them from a near distance. When an ambulance enters the refuge, it talks to other ambulances if it needs any help. Therefore, each ambulance knows other civilians in addition to it self's cluster civilians.
If an ambulance finishes its cluster, means there are no more civilians in this specific cluster, it will move around the refuges to find out if any other ambulance needs help.
One of the risks in low-level communications is the same decision made by different ambulances. Ambulances will send a message about whom they had chosen to rescue in case that the message will be received. Otherwise, each ambulance knows the others decision making algorithm. Therefore, they won't choose the same low valuable civilian to rescue.
3.3. Police agents
The police agent's duty is to clear the paths and make the transportation between different points of the map available.
The police strategy is based on clustering, which had been explained at the top of the TDP. Each police will have its cluster and will clean the paths according to the weight that it gives to each of them.
3.3.1. Police agent's decision strategy
For giving each path a specified weight, there are varieties of presidencies that affect that weight. The police agents will clear the ways to the refuges in its cluster for the civilians that are healthy enough to walk by their own to the refuges. Whenever there is a fire in a police cluster, it will clear the way to that bridge so the fire agents will be able to reach that fiery building. Another important blockade needs to be clear is the blockade that might make an agent stuck in a place. If an agent gets stuck, it cannot do any of its tasks. Therefore, whenever a police agent finds a stuck agent, it will clear those blockades to free that agent. The other way to be cleared is the connection between clusters so that agents and civilians can move from them to other places. Each police agent will clear the connections between it cluster and near clusters.
After clearing the most important ways, according to their weights, the police agents will clear the subsidiary paths.
3.3.2. Choosing the best way
Police agents will choose the shortest path between points they want to have a connection to clear according to the Dijkstra algorithm. This will make the other agents movement easier and faster so each agent can do more tasks.
3.3.3. Communication
3.3.3.1. High-level communication
Whenever there is a fire that needs to be extinguished or there is a barred building that its civilians are in the priority for ambulance agents, police will receive a message from them and will clean the specified way for them.
3.3.3.2 Low-level and No-communication
In these situations, police agents are nearly aware of the other agents decisions, as by talking to them. According to their decision, the police agents will give a specified weight to each building and will clear the way of the buildings according to their weight and priority.
4. Search
An agent should search the map when it's free because most of the decisions are based on location of fires and civilians and the open roads.
Each agent starts the search from its own cluster. The search algorithm is like a circle maze that the agent starts the search from the center of it and eventually comes to the edges. The agent chooses the building that has the least cost of move for it to search.
Here's an example for fire search.
References
- "RoboCup Rescue Home". RoboCupRescue.org and RoboCupRescue.com. Retrieved 2009-06-26.
- "RoboCup Rescue". RoboCup 2009. RoboCup. 2009. Retrieved 2009-06-26.
- van Leeuwen, J. (ed.): Computer Science Today. Recent Trends and Developments. Lecture Notes in Computer Science, Vol. 1000. Springer-Verlag, Berlin Heidelberg New York (1995)
- Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. 3rd edn. Springer-Verlag, Berlin Heidelberg New York (1996)
- math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf
- www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/dijkstraAlgor.htm
- math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
- cs.uvm.edu/~xwu/kdd/Slides/Kmeans-ICDM06.pdf