RoboCupRescue 2010 – Rescue Simulation League Team Description Paper – SEU_REDSUN (P.R.China)
Guan Daqi, Chen Ning, Jiang Yinhao
School of Mechanical Engineering, Southeast University
http://me.seu.edu.cn/sfzx/rescue
Abstract After RoboCup 2009 Graz, Austria, a lot of work has been done in our code. In this paper, a forecasting extinguish method based on particle filter will be introduced. Meanwhile, a method based on minimum spanning tree for police force agent will be covered. As the appearance of Score Vector, some close and relative research work has been done in the decision method of ambulance team agent. We also do some research work in non-communication situation. Although certain features still need fully test, SEU_REDSUN has gained 3rd place in RoboCup China Open 2009 based on these new features.
1. Introduction
RoboCup Rescue Simulation System (RCRSS) is a large-scale Multi-Agent System (MAS) of urban disasters. In such a dynamic, partially observable environment, the action decision making is always the primary problems which need to be effectively solved. Our code structure is shown in the graph below.
The effectiveness of decision making needs a complete and accurate world modeling. So, we established different channel based communication models in diversified dis asters for information sharing: the typical communication model and communication model under no center conditions. The latter model has some profitable characteristics such as adaptability, minimum time delay and virtually equally distributed channels. These characteristics especially enable us to build a more realistic world model under certain sharp conditions. As for decision making, both centralized and distributed approaches are adopted. A simplified decision process is shown in Fig.2. Basic low level action of moving is addressed to fulfill different needs of our agents in such a dynamic and uncertain system.
Decision making of fire brigade is both distributed and centralized. We use particle filter method to predict the building temperature and then the center decide how many fire brigades needed to extinguish the fire of a fire site or a fire zone. As inspired from the real forest fire fighting, a fire zone based approach is used to slow fire spreading. The fire brigade receives tasks from the center and executes them. If it has completed the tasks and hasn't received new tasks, it makes decision itself.
This paper also analyses the practical tactics of police force traffic clearing and city search in extensive urban disaster with graph theory. Using minimum spanning tree algorithm and shortest path algorithm to build mathematical model of city traffic can assist police force in executing relieving missions, which brings up a new approach to disaster rescue.
Ambulances adopt totally centralized decision making approach which is treated as a dynamic assignment procedure: how to assign limited civilians to given number of ambulances in this dynamic environment. It can be very easy to understand that the total time for ambulances performing each successful rescue task is spent on two aspects: the time on road and the time on rescuing civilians. Besides, if we could estimate when civilians will be dead (Death Time), we will know the maximum ambulance needs for each civilians. Thus the assignment would be achieved. In order to estimate civilian death time, a particle swarm optimization (PSO) method is then illustrated. In the new scoring rule (Score Vector), the factor affect the result of rescue work has been divided into 6 different score vectors. We should integrate these factors to get an overall best solution.
2. World Model and Communication
Based on the disaster environment, the world model is mainly divided into three parts: simulation constants, base world objects and specific status object collections. Simulation constants would keep unchanged during a simulation. The base world objects would hold memory of objects which represent the object relationship of disaster environment. Most important of all, the specific status object collections are generally lists or sets of objects with similar attributions. For instance, a specific object collection named 'buried agents' is a humanoid list that contains humanoid objects whose buriedness is greater than zero. Every cycle, the second and third parts are updated differently in that the former is updated with cognition information; while the latter is a reconstruction of world objects.
After simulation starts, agents communicate with each other to get more information of the disaster space, upon which decisions can be made properly and correctly. World model is the core memory of the disaster space for agents to predict, to reason and to make decisions. Each cycle, agents update their world model with sensed and received information. A self-adaptive, effective communication model is established to share self-sensed information as soon as possible and build a more complete and accurate world model.
Currently, the communication of rescue simulation system is channel based with both channel numbers and channel capabilities are limited. For typical information sharing between agents, simplified model is shown in Fig. 3.
When all communication centers collapsed, we use the first agents (Sequenced by their IDs) to replace center agent to establish the communication model. These agents are called virtual centers. The simplified model is shown in fig 4.
There are still some situations, one center collapsed or two collapsed. When two centers collapsed, we can integrate mentioned models to solve the problem. The communication model is shown as fig 5 (Only the fire station is in use).
When only one center collapsed, we can use remaining centers to construct the communication model. This model can lead to message delay, but sometimes we can't find the best solution. The communication model is shown as fig 6.
3. Agent Skills and Action Selection
[Introductory section for agent skills]
3.1 Fire Brigade Agent
Prediction of fire spreading is crucial for fire brigade agents controlling fires. By the estimation of buildings temperature, we can get a more reasonable task allocation plan.
The building temperature update process building temperature include update of building fuel, update of building energy, update of building water quantity and radiation process. The specific process is as follows:
- Update of building fuel
$$CF(i) = IF \times f(i) \times Rnd$$
CF(i) is the cost of fuel in time step i, IF is the initial fuel of the building, f(i) is the cost coefficient, it is not less than 0.005. Rnd is a random float number between 0.8 and 1.2. f(i) is calculated as follows:
$$f(i) = \frac{T(i)}{1000} \times \frac{F(i)}{IF} \times 0.2$$
T(i) is the temperature of building in time step i, F(i) is the fuel of building in time step i. If f(i) < 0.005, f(i) = 0.005.
The initial fuel is calculated by:
$$IF = \rho_f \times V \times Rnd$$
- update of building energy
Energy update process of building includes the decrement of building's fuel and the increment of building's energy. The update process is as follows:
$$E(i) = E(i) + CF(i)$$
E(i) is the energy of building in time step i, like equation 8, the fuel of building decreases by:
$$F(i) = F(i) - CF(i)$$
If CF(i) is bigger than F(i), then CF(i) equals F(i).
- update of building's water quantity
The effect of water is related to the energy owned by the building. If the effect of water effect i( ) is smaller than the energy difference of building E i() , the water will evaporate; When effect i( ) is bigger than E i() , the real effect of water and energy consumption should multiple a coefficient pc i() .
$$\Delta E(i) = [T(i) - T_i] \times \Gamma$$
Ti is the initial temperature of the world and equals 20 C . is the heat capacity of the building.
$$pc(i) = 1 - (effect(i) - \Delta E) / effect(i)$$
If effect i( ) is smaller than E i() , The water quantity of building is zero. The energy of building is calculated by:
$$E(i) = E(i) - effect(i)$$
If effect i( ) is bigger than E i() , the energy of building is zero. The water quantity is calculated by:
$$WQ_B(i) = WQ_B(i) \times (effect(i) - \Delta E) / effect(i)$$
WQ i(*)B is the water quantity of building in time step i.
- radiation process
The radiation energy of building can be calculated by Stefan-Boltzmann law:
$$T_{rad} = \sigma \times (T(i) + 273)^4 \times S$$
is Stefan-Boltzmann constant, S is the area of buildings' wall.
Particle Filter (PF) base on Monte Carlo method. We can use the frequency of an event instead of the probability of the event. Here is the state equation:
$$x(t) = f(x(t-1), u(t), w(t))$$
$$y(t) = h(x(t), e(t))$$
Equation 11 is state transfer equation and equation 12 is the observation equation. x(t) is the state of time t. u(t) is control value. w(t) and e(t) are model noise and observation noise. y(t) is the observation value of time t. Goal of Particle Filter is from observation value y(t), state x(t-1) of time *t-*1 and control value u(t) to filter out the true state x(t).
First of all, we should generate a large number of sampling based on the state x(t-1) of time *t-1 and its probability distribution. The sampling is called particles. These particles distribute on state space with the probability distribution of x(t-1). We evaluate all the particles with conditional probability ( | ( ) )i P y x t . It means the probability of getting observation value y when you choose particle i in true state x(t). The conditional probability is the weight of particle i. We filter particles with low weight with re-sampling method. Particles left will be the true state x(t).
3.2 Ambulance Team Agent
The performance of ambulances could greatly affect the final scores. We treat the process of rescuing civilians as a dynamic assignment problem: given m ambulances and k civilians. We use Particle Swarm Optimization(PSO) to complete the allocation. The whole algorithm description is in our team's team description 2009. The new scoring method (Score Vector) adds a lot of factors into decision process. From the table 1 behind, we can see score vectors and their influence on ambulance teams' decision factor. The positive sign means this kind score vector is
Through table 2, we can see that civilians' lives have been divided into 4 levels. Two positive levels and two negative levels are divided by 4000 HP(Health Position).
So the decision objective is not only the most civilians, we but also need to rescue more healthy civilians. We find that civilian whose HP is lower than 4000 in the situation using score vector is just as the civilian whose HP just over 0 in the old situation not using score vector. We using the same algorithm as 2009, but introducing the Relative HP into this algorithm. The Relative HP is defined as this:
$$HP_{r} = \begin{cases} HP - 4000, & (HP \ge 4000) \ HP - 1000, & (HP < 4000) \end{cases}$$
Table 1 Score Vectors and Their Influence
| Factor | Influence on the score | Factor | Influence on the score |
|---|---|---|---|
| Dead Civilians(DC) | - | Ration in Refuge(RIR) | + |
| Critical Civilians(CC) | - | Ration of Rescued(ROR) | + |
| Average Civilians(AC) | + | Ratio of Destroyed(ROD) | - |
| Healthy Civilians(HC) | + | Ratio of Extinguished(ROE) | + |
| Travelling Time(TT) | - | Average Time of Rescue(ATOR) | - |
| Number of Message(NOM) | - | Average Time of Extinguished(ATOE) | - |
Table 2. Civilians' Lives and Their HP
| Factor | HP | Influence on The Score |
|---|---|---|
| Healthy Humanoid | $7001 \le HP \le 10000$ | + |
| Humanoid with average health | $4001 \le HP \le 7000$ | + |
| Humanoid with critical health | $1001 \le HP \le 4000$ | - |
| Dead humanoid | $HP \le 1000$ | - |
3.3 Police Force Agent
After emulation construction of the city map, a discrete structure model of the city traffic has to be set up based on this map. The model aims at: Quickly connect the whole disaster-stricken city, to set up the most efficient communication line for other rescuer staff, to search the whole city in order to identify the distribution of the residents. To put it simply, police agents should be able to find out all the fire brigade, ambulance crew, citizen and buildings on fire, connect them with the refuges. On this basis, the shorter the route for fire brigade and ambulance crew to reach their perspective objectives.
The key lies in the routes, the route from the refuges to the buildings where injured citizens are located, from refuges to the buildings which are on fire and the routes for police to search out all the buildings in the whole disaster environment. So, what are directly relevant to police's rescuing work are buildings. That is to say, what should be more concerned are which buildings to search out than which roads to clear up.
From the relation among buildings, nodes and roads, we know that exit nodes of buildings connect the roads and buildings, which are respectively the executive target and strategy target of the police intelligent agent. Based on it, we can set up emulated discrete model (also called as graph theory model)-- undirected connected graph G= (V, E). V is the Vertex set including all the exit nodes of the building; E is the Edge set including edges between exit nodes of the building which are directly connected with roads without passing through other exit nodes, and set the actual length of the road as the weight of the edge; mark total number of the Vertex as n, the total number of the edges as e. Figure 7 and 8 are part of the undirected connected graph take Kobe Japan as an example.
In disaster rescue operation, we need to form up the latest path from where the wounded citizens are to the refuge, even there are many refuges in the map, and we only need the latest path to the nearest refuge. So, we have to deal with a problem of shortest path of a single-source (finite source) without negative weight.
References
- RoboCup-Rescue Simulation Manual, RoboCup Rescue Technical Committee (2000).
- Meng Qingfa, Guan Daqi. SEU_RedSun 2009 Team Description.
- Guan Daqi, Xu Yingqiu, Tan Yingzi. Particle Filter Based Study of Fire Forecasting in RCRSS.
- Jiang Yinhao, Xu Yingqiu, Tan Yingzi. MST & SP Based Traffic Clearing and City Search in RCRSS.
- Chen Ning, Xu Yingqiu, Tan Yingzi. Ambulance Team Algorithm Based on Multi-Evaluation Index in RoboCupResce.