RoboCup 2016–Rescue Simulation League Team Description
Fu Jiang, Xiaoyong Zhang, Jun Peng, Xianguan Hu, Tiancheng Wang, Yupeng Sun, Yun Lei, Yujao Cui, Deyu Yu, Chuchu Zhong
School of Information Science and Engineering, Central South University Yuelu District, Changsha, China
Abstract CSU_Yunlu Rescue Simulation Team has got the sixth place in the world 2015 [1]. To get better performance, we fix found bugs and make some significant changes on agents' strategies introduced in the following part of the paper. Moreover, we improve the partitioning and searching algorithm to be more effective. Separate maps and scenarios are designed to test the codes for each part, making sure the effort really pay off.
Keywords: RoboCup Rescue Simulation, partition, search, agents' strategies, tool
1 Introduction
Our CSU_Yunlu team has began to participate in RoboCup Rescue Simulation competition since 2006 [2]. We develop our project by learning from other teams and proposing some original methods. We do make great progress, which consequently pushes us forward towards the study of agent and multi-agent.
We improve the partitioning and searching algorithm and make some changes on agents' strategies. The selection of water suppliers and target extinguishing buildings of fire brigade, the task allocation and the setting of blockades' priorities of police force and the implementations of one-to-one rescue and the calculation of rescue time of ambulance team will be explained in details. We also need a more efficient tool to test for evaluating the agents' behavior.
2 Partitioning and Searching Algorithm
In the first beginning, the whole map will be divided into clusters using K-means plus plus algorithm, the cluster numbers are equal to the number of the three kinds of agents respectively. Then each agent will has its exclusive partition to do searching work. Owing to the static feature of police force's and ambulance team's task, such partitioning is enough. However, for fire fighters, the fire changes all the time, and will spread in uncertain directions, so the partitioning strategy is surely more important to them, which definitely decides whether the fire can be found soon or not.
In our old strategy, the fire fighters only search their own partitions for fire, because of their belonging fire fighters being buried or far away, which will result in their being late for timely discovery. And consequently the fire gets bigger and uncontrollable just as what we suffered in previous competitions. Nowadays, we are working to solve that large problem.
A practicable method may be described as follows:
Initially, set the cluster number of fire brigade to be $$\frac{\text{SizeOfFireBrigade}}{2}$$
so that at least two fire fighters will belong to a same cluster, and it will ensure all clusters have movable fire fighters to more degree, decreasing the possibility that some clusters will not be searched in time. It must be noticed that all fire fighters will do searching work before anyone finds fire.
And then, we change the cluster number according to current fire conditions to achieve more efficient searching, extinguishing and world model updating work. Meanwhile, we will adjust the number of fire fighters doing searching work.
Once fire gets extremely big, all fire fighters will be distributed to carry out extinguishing work to decrease the damage as far as possible.
3 Fire Brigade
The main task for a fire brigade is to extinguish all fire as soon as possible to decrease the damage to buildings and citizens. It concerns with many problems, like the water resource, the buildings' priorities and the extinguishing strategy. To finish the work perfectly, efficient strategies should always be put forward.
3.1 The Utility of Hydrants
Under many circumstances, there are only several refuges but hundreds of hydrants. It becomes more important to make the best use of hydrants to supply water for fire brigades, especially in the condition that fire spreads widely or the traffic is not good. When making choices between refuges and hydrants, we follow the rules below:
Firstly, give hydrants no consideration if the refilling rate is too slow.
Secondly, give up hydrants that are nearer to other fire fighters, because such hydrants are more likely occupied with or to become target supplier of others. We do this to avoid two or more fire fighters go for the same hydrant, and crashing the channels resulting from too many messages sent.
Thirdly, maintain an exclusive hydrant list for each fire fighter. In the beginning, it includes all the hydrants, and then we delete the hydrant given up any time. And finally, every fire fighter will get their own corresponding water suppliers.The drawback is that it can't be updated dynamically, therefore, the optimal hydrant may be ignored after the burning area changes.
Finally, take both time to refill and distance between the fire fighter and target supplier into account.
3.2 Target Building Selecting
Learned from other teams, we set the priority of burning and unburnt buildings separately. The building material and size, the reachability and fieryness of the building, the lasting time of the fire since ignited and the surrounding situations like gas stations' existence and the fire's spreading features contribute differently to the priority. Meanwhile, we adapt pre-water strategy for unburnt buildings, especially for those near gas stations and newly ignited big buildings, which could obviously slower the spreading of fire.
3.3 Strategy for Extinguishing
Fire brigades might miss the best chance to extinguish the fire that is invisible. So we implement an original method. Fire brigades will do a clockwise extinguishment standing just on the position where they extinguished a fire, which making the fire extinguished completely.
Besides, in the fire spreading, the speed of air transfer is much lower than transfer among adjacent buildings, so the road slowers the spreading of fire to some degree. But once the fire goes across the road, it will bring larger and faster fire ingition. That is why we need to extinguish the fire before it extends to another road side. As a result, fire brigade will focus their water resources to avoid the fire going across the neighboring roads..
3.4 Get Outer Burning Buildings
It is much reasonable to give up the buildings in the middle of the entire burning area, and gather fire brigades together outsides the area so as to control the fire sooner. Therefore, we give higher priority for outer burning buildings.
If the burning building is on the outer, then the maximum included angle between the line segments formed from this building to its nearby burning buildings shall be within 180 degree range. In other words, all burning buildings are on the same side of a straight line passing through this building, while the direction of this line has no influence on the result.
3.5 Machine Learning to Get Adaptive Parameters
Caused by that there are many parameters not easy to set manually, we plan to adapt some machine learning algorithm such like supporting vector machine(SVM) [3] with linear kernel or other, decided by the actual effect. That can be achieved by calling matlab codes in java and adjust the parameters adaptively ( We recommend matlab for its strong scientic computational function especially quick calculation speed.) or just getting constant parameters computed using past examples, and we could also use the machine learning library in java directly.
We must train the SVM at first. We input the variables and related labels and then get the parameters which form the SVM structure. Here, the variables will be some combination of the building's attributes just mentioned above. And the labels will be the priority of each building being considered to be the next extinguishing target. As a kind of supervised learning method, we set labels for the training examples using our experiences. The parameters here will be the weights of different factors. Once we get the model, we could use it to get the priority for new examples.
4 Police Force
The main task for a police force agent is to clear the blockades. The performance of police force agents will affect the rescue efficiency. Therefore, we add some modules such as work partition, task allocation, priority of the clean targets, etc. At the same time, we optimized some modules such as clear method.
4.1 Get Rational Allocation of Tasks
In order to get more rational allocation of tasks,all the police force agents are distributed in their own work area. We use K-means++ algorithm to take the partition. In K-means++ algorithm, a cluster is a group of buildings which are closest to the cluster center. This algorithm cost very short time to divide the map so that we are able to perform more computations during preprocessing.
4.2 Clearing Strategy
For the blockades, we have two strategies. One is clearing the blockades with different priorities, where those stuck agents (fire brigade and ambulance team) have the highest priority. The other one is just clearing all blockades around the current police force agent. It's worth mentioning that we have two blockade-clearing methods, direction clear method and scale clear method. For direction clear, we select a specific point (usually, we choose the center point of the neighbor area's edge.). Then, clear the blockades between the agent's coordination and the specific point's coordination. For scale clear, the police force agents will clear a wide range of blockades around them. But briefly, it takes much more time. So, recently, we update the clear strategies. Because the scale clear waste too much time, we cut down its usage. It will just be used when the agents are stuck or clear some entrances of buildings.
4.3 Help Fire Brigade and Ambulance Team
Besides, to make fire bridges and ambulance teams get to the places they should be as soon as possible, we plan that the police force agents first clear the main road to make the main road available for other agents or citizens. If the current area has an entrance to a neighbor building and the distance from the entrance to the agent's location is in a certain range, then they will clear the entrance. Also, if the agents find the neighbor buildings in fire, they will broadcast to the fire bridge (if channels are available in the maps).
5 Ambulance Team
The main task for an ambulance team is to rescue the citizens in the building as much as possible and send them to the refuge. Therefore, the task distribution is extremely important and it needs an accurate and efficient decision. In recent years, we optimized some modules such as work partition, task update, task allocation, rescued object management, etc. And recently, we made some following changes based on the original behavior. 1) Make sure one ambulance agent rescue one citizen buried. When selecting a rescue target and moving to him, the ambulance agent will mark this target and then talk to the other ambulance agent, which would not select this citizen buried as rescue target.
- An ambulance agent select a rescue target based on the distance between them, the rescue time, the health point of the target, the time of sending the target to the refuge.
- Take measures to prevent ambulance team from getting stuck by roadblock, especially not completely removed roadblock, and doing nothing.
- Avoid an ambulance agent's searching for buried people into the fire place.
- The number of buried humans in a cluster will be reset and recalculated in each cycle to guarantee the dynamic reflection of the present refuges' distribution.
- When an agent is dying, it should stay at the refuge. And when a gas station explodes, all the agents around will get badly hurt, so they should stay away from it and set the priority of the citizens buried.
- When calculating the rescue time, we will add correction time on the basis of rough calculated time. And there should be a relationship between the correction time and the rough calculated time, in general it is a proportionality relationship. For instance, when the subject is beside, the correction time is zero. By this way it can make sure that all the subjects use the same handling method.
- When rescuing the target and firing the location, the ambulance agent will determine whether to evaluate based on the health point, the leaving time, the rescue time and many more.
6. Visualization Tool to Make Evaluations
Our viewer part was designed for test. We learnt from the server code and added display of clusters, convex hulls, boundaries, fire conditions marking , entity IDs and so on. Because of these, we can trace certain agent to evaluate its behavior and help to find problems and make improvements on the strategy making.
However, it is not convenient and time-consuming to debug one by one. We will spend some time on it to improve our design. And it is worthwhile to mention that separate maps and scenarios should be designed to test the codes for each part.
Acknowledgment
This project has been developed with the help of many individuals and support from School of Information Science and Engineering, Central South University. And we have learnt a lot from other teams and some relevant websites. Thanks to them all.
References
[1] RoboCup Rescue website. http:/roborescue.sourceforge.net/ [2] Fu Jiang, Xiaoyong Zhang, Tao Cao, Xin Xu, Yong Meng, Xiaoyu He, Mingzhu Shi, Huan Tian, Hongbing Luo, Lu Tang, Jun Peng: RoboCup 2015-Rescue Simulation Team Description CSU_Yunlu(China), 2015. [3] ALEX J. SMOLA, BERNHARD S.: A tutorial on support vector regression, Statistics and Computing 14: 199–222, 2004.