RoboCup Rescue 2019 TDP Agent Simulation Ri-one (Japan)

Yamato Higashi, Joichiro Amada, Takahiro Ijichi, Soichiro Komura, Koki Sakaue, Akinori Kanechika, Hiroaki Nozaki, Kaito Nakano, Keita Fukui, Haruki Nakamura, Ryota Fuji, Takafumi Nishida

Ritsumeikan University, Japan

http://rione.org/hp/

Abstract We implemented new methods in modules: we implemented a new path planning for agents to pass intersections; Gaussian mixture model was implemented for clustering instead of K-means algorithm. We implemented new strategies: efficient assignment of ambulance teams (AT) for victims according to a dynamic changing condition of AT and time was implemented; fire brigades (FB) was implemented to extinguish the fire near the gas station in priority; a method of beforehand extinguishing the buildings that were not burning and adjacent to the burning building was implemented for FB; a method of removing blockades on roads near a refuge in priority was implemented for police forces (PF); To evaluate the method an experiment was performed.

1 Introduction

The RoboCup Rescue Simulation(RCRS) is a multi-agent simulation of disaster relief activities. The RCRS server simulates various environments imitating a city after a disaster. An aim of RCRS is to make use of virtual agents to rescue buried victims from blockades and extinguish fires that make buildings go up in flames.

Last year, we implemented some strategies: matching algorithm was improved for AT; an allocation method to dynamic clusters of fires was implemented for FB; a method of searching for fire under all situations was implemented for FB; an algorithm to supply water efficiently was implemented for FB; a method of clearing blockades was improved for PF; an algorithm which could choose roads prioritized depending on several conditions was implemented for PF; Kmeans++ algorithm was implemented for clustering instead of K-means algorithm; a new path planning algorithm was implemented [1].

In this year, we implemented new methods in modules and strategies. Each of the chapters described the following contents which were implemented. Chapter 2.1 described an accuracy improvement of Gaussian mixture model. Chapter 2.2 described a new route search method. Chapter 3.1 described an improvement of matching algorithm for AT. Chapter 3.2 described two new methods for FB. Chapter 3.3 described a method of determining a target on roads near the refuge in priority for PF. Chapter 4 described the result of an experiment. Chapter 5 described the conclusion of this development.

2 Modules

(This section contains subsections listed below)

2.1 Clustering

In our conventional clustering, K-means algorithm was used to divide a whole map into clusters so that agents could do rescue activities efficiently. Last year, K-means++ algorithm, it was modified K-means algorithm, was used to deal with a problem that the improper solutions were likely to be chosen in our team. However, there was a problem that faced a lack of agent in an area dense with buildings because K-means algorithm didn't consider the density of points. Therefore Gaussian mixture model (GMM) was implemented for clustering instead of K-means algorithm.

In GMM, a mixture of k Gaussian distributions represented points to divide them into k clusters. The probability Pi(x) which point x was an element of cluster i was represented:

$$P_i(x) = \pi_i N(x|\mu_i, \Sigma_i) / \sum_{k=1}^K \pi_k N(x|\mu_k, \Sigma_k)$$

where πⁱ represents the mixing coefficient; µⁱ represents the mean of points of cluster i; Σⁱ represents the dispersion of points of cluster i. The parameters were defined by the below steps.

• 1. The parameters are initialized by placing a suitable value.
• 2. Calculate the tentative probability Pⁱ ∗ (x) of each point x, each cluster i.
• 3. Update parameters by below formula.

$$\mu_k = \frac{1}{N_k} \sum_{n=1}^{N} P_k^*(x_n) x_n$$

$$\Sigma_k = \frac{1}{N_k} \sum_{n=1}^{N} P_k^*(x_n) (x_n - \mu_k) (x_n - \mu_k)^T$$

$$\mu_k = \frac{N_k}{\sum_{i=1}^{K} N_i}$$

$$(N_k = \sum_{n=1}^{N} P_k^*(x_n))$$

4. Repeat those steps until the probability no longer changes.

In RCRS, road and building were applied as points. As a result, a suitable clustering was enabled in a map with the bias of the density of points.

2.2 Path Planning

The path planning algorithm is used to get the shortest path between two positions on the map so that agents can move efficiently. Until last year, our algorithm was based on A* algorithm and looking at the list of neighboring Areas (hereinafter referred to as "neighbors") which start from the starting point of the agent one by one. However, this method was inefficient because roads and buildings were not distinguished in the list of neighbors and the destination was searched regardless of whether it was a road or a building. For solving this problem, this algorithm divided the path that the agent passed by each intersection and added it to the list. Using this method, the obtained list consists of a road only. Using this obtained list as an edge and an intersection as a node, we used the A* algorithm.

It was possible to obtain the path to the destination by the search result of the path planning, and even if the destination was a building, that obtained path was a path to the neighbors which adjoin the building. Furthermore, in the previous method, both the original list of neighbors and the list of only the roads needed to be made, however, this new method need only one list. This brought about reduction in the calculation. In addition, because the list obtained by this method divided each at intersections, it is possible to narrow the choice of the way when agents pass through the same intersection.

3 Strategies

(This section contains subsections listed below)

3.1 Police Force

The main role of PF is to clear blockades which are caused by a disaster. In particular, to ensure roads for other agents such as AT and FB are PF's top priority. Hereinafter, an entrance is defined as a road adjacent to a building.

3.1.1 Refuge

In order to perform disaster relief activities smoothly, it is important to clear blockades on a refuge at first. Because, when an entrance to a refuge was blocked with blockades, not only civilians can't take refuge but also damaged agents can't recover. Especially, FB needs to supply water at refuges. Therefore, it was necessary for PF to clear blockades on roads near refuge in priority. As the method for that, PF was set to add to a list only roads which were near the refuge and obstructed with blockades, and to clear blockades on these roads in priority. Using this method, when even one entrance to the refuge was blocked with blockades, PF cleared blockades on these roads even if other agents that suffered from blockades.

3.1.2 Solve Congestion

PF should ensure roads for many other agents and civilians to pass along. Because one road was obstructed with blockades, many agents and civilians couldn't reach their destinations. Therefore, it was important for PF to preferentially clear blockades on roads which many agents and civilians frequently passed. As the method for that, PF was set to count the number of agents and civilians near each road, to add to a list only roads which many agents and civilians were near and obstructed with blockades, and to clear blockades on these roads in priority. Using this method, when several agents and civilians gather in one road with blockades, PF cleared blockades on the road in priority.

3.1.3 result

The program with these new strategies and without these was executed at maps of Kobe and Sakae three times. Every score of the results were averaged. Table 1 shows a result of the execution. The score generally improved.

A result of the execution of new PF strategies and last year's

3.2 Ambulance Team

A purpose of ambulance team agent(AT) is rescuing injured people (hereinafter referred to as "victim") and carry them into refuges. Deciding which people AT need to save is important task. There were two improved points in the detector section.

Firstly, the process of rescue was changed a way that an agent rescued a victim to another way that many agents rescued a victim last year. However, the standard to make a group of AT was not considered. In this year, this standard came to be used for rescue in a group. Specifically, the more simulation cycle past and fire spread, the more AT called farther range.

Secondly, the standards to select victims that should be picked at top priority became very complex. Then, all elements affecting the value were examined carefully. The score increased because AT could pick up many victims. The elements considered were time to transit and save victims, and estimated the damage. The damage was calculated simulator to estimate.

3.3 Fire Brigade

A purpose of fire brigade agent(FB) is extinguishing a fire occurred in a disaster. It was important not to spread damages caused by the fire. There were three improved points in detector section.

3.3.1 Target

In order to prevent the expansion of fire damage even just a little, it is important to check the spread of the fire to a gas station in priority. Because, when gas station catches fire, it explodes and causes a very widespread fire. Furthermore, when agents and civilians are caught up in the explosion, they not only are damaged but also became to be unable to move. Therefore, it was necessary that FB to extinguish the fire near the gas station in priority was implemented. As the method for that, FB was set to choose only buildings near gas station from all buildings and added these buildings to a list, and to do fire fighting activities on buildings added to the list in priority. Using this method, when even one building near a gas station was on fire, FB extinguished the fire on these building.

3.3.2 beforehand Extinguish

Preventing fire spreading to buildings during FB fire extinguishing activities leads to narrow a range in which FB move and more efficient fire extinguishment. Therefore, it needs to beforehand extinguish the " heating buildings "which aren't on fire and are adjacent to the burning building for efficient fire fighting activities. By beforehand extinguish, it lowered the temperature of heating buildings, and it was possible to prevent the spreading fire to heating buildings. As a method for that, when there are more than three FBs performing fire extinguishing, the FB that is the farthest from a burning building moves close to the heating building that has the highest temperature and extinguishes the heating building.

3.3.3 Hydrant

Last year, hydrants were used positively to supply water. However, supplying water at a hydrant was not efficiently. Each FB needed calculation to search hydrant. In addition, when several FBs used the same hydrant, they need a lot of time to complete supplying water. Therefore, FB should use refuge to supply water. FB doesn't have to think about which is more efficient, hydrant or refuge. It can reduce calculation when FB need to supply water.

3.3.4 result

The program with these new strategies and without these was executed at maps of Kobe and Sakae three times. Every score of the results were averaged. Table 2 shows a result of the execution. The score generally improved.

A result of the execution of new FB strategies and last year's

4 Preliminary Results

This year 's program and last year's were executed at maps of VC, Kobe, and Istanbul three times. Every score of the results was averaged. Table 3 shows a result of the execution.

A result of the execution of this year 's and last year's

5 Conclusions

Following is the conclusionof this paper.

• – ATs were decided the rule of making group and could increase the score.
• – FBs were improved efficiently by using the only refuge to supply water, beforehand extinguishing and prioritizing buildings near the gas station.
• – PFs were increased priority of the clearing blockades on roads near the refuge.

References

1. Takafumi Nishida, Kosuke Okajima, Haruna Iuchi, Eisei Mashiro, Masataka Suzuki, Takumi Oibayashi, Risa Morimoto, Terumi Oguri, Akinori Kanechika, Hiroaki Nozaki, Keita Fukui, Soichiro Komura, Kaito Masuda, Yamato Higashi, Takahiro Ijichi, Joichiro Amada, Haruki Nakamura, RoboCupRescue 2018-Rescue Simulation League. Team Description. Ri-one (Japan), 2018.