RoboCup Rescue 2019 TDP Agent Simulation CSU_Yunlu (China)

Fu Jiang, Wuqian Lv, Jiaxin Zhang, Jun Peng, Yongjian Fu, Yuanyang Lou, Xiaoyong Zhang

Central South University, China

Abstract This paper describes CSU_Yunlu's main strategies of RoboCup Rescue Agent Simulation. An estimation function based on K-means algorithm is leveraged to divide the city into different areas. Then another function based on Ant Colony Optimization enables the agent entities to choose the optimal path. The partition-based communication method improves the efficiency of information sharing. The strategies for three agents (Police Force, Ambulance Team and Fire Brigade) improve the efficiency of the rescue operation.

1 Introduction

Team CSU_Yunlu has been participating in the RoboCup rescue simulation competition since 2006. Moreover we have achieved good results in both RoboCup 2016 and 2017. We hope to optimize our strategy and improve the performance of our team based on the strategies we have in previous years.

The main contents of this article are listed as follows (Figure1): clustering, path planning, communication and specific strategies for the three agents (Police Force, Ambulance Team and Fire Brigade).

2 Modules

2.1 Clustering

Purpose

In the rescue environment in RoboCup Rescue Agent Simulation, every map consists of thousands of nodes. In order to help the agents enhance the efficiency of searching the whole map, we need a clustering module to divide the whole map into clusters. Each cluster can be seen as a smaller map, and the complexity of getting the information of each cluster is reduced greatly.

Related Works

Nowadays, many clustering algorithms have been proposed, which can be roughly divided into four categories: partition-based clustering. Level-based, density-based, grid-based. In particular, Wang Zhenyu proposed the clustering algorithm based on Markov. But it needs a great number of data. K-Means is the typical partition-based algorithm, CURE is the hierarchical algorithm, DB-SCAN is the density-based algorithm, and CLIQUE is the grid-based algorithm. Among them, K-means has the advantages of low complexity and fast computing speed, and is often used as the choice of many team clustering algorithms. SEU just used the original K-means algorithm, the cluster numbers are determined by the number of three kinds of agents. Ri-one use the K-means++ algorithm. However, the algorithm has the shortcoming of random selection of the initial cluster center and clustering number depends on subjective experience.

Proposed Approach

Our team determines to use canopy algorithm to improve the K-means algorithm in combination with the actual simulation environment. Specific steps are as follows:

1. Input the cluster object $X = {x_1, x_2, x_3, ..., x_n}$, determine two values: tight threshold $D^1$, loose threshold $D^2$.
   • ($D^1 = D + \Delta d$, $D^2 = D - \Delta d$, $D^1 > D^2$, $D$: the average distance between the building nodes which are in the X on the environment map.)
2. $S$ is a collection of all nodes in the graph. Choose a node $P$ as a Canopy cluster randomly or Sequentially from $S$ and calculate the distance d between other nodes and $P$ respectively.
3. If d $\geq D^1$, then the node will be in a new Canopy cluster; if d $< D^1$, the node will be added in the cluster $P$.
4. If d $< D^2$, at this point, it is considered that this node is already close enough to the cluster $P$ and it is impossible to be added in a new Canopy cluster. So it will be removed from $S$.
5. Repeat the process of 2-4 until $S$ is empty. At this point, there will be m Canopy cluster where every node may doesn't belong to just one cluster.
6. Compare m to the number of different agents n. The value of k will be min{m, n}
7. Carry out the K-means algorithm.

Pros and Cons

Our proposed approach makes the selection of the initial cluster center and clustering number more reasonably to some extent. It will improve the accuracy and efficiency of the algorithm even in some extreme cases. However, the selection of two thresholds affects the execution efficiency of the algorithm and classification accuracy directly. The selection of thresholds depends mainly on subjective experience or trial. In order to get a better result, we must adjust two thresholds constantly.

2.2 Path Planning

Purpose

The pathfinding strategy is to help the agent and the citizen find the optimal path. The purpose is to make their movements more efficient and enable them to reach their destination faster. The efficiency of mobility is the most important foundation for rescue operations. Improving the efficiency of mobility means increasing the efficiency of all rescue operations.

Related Works

In recent years, the application of this algorithm in network routing has attracted more and more attention. Some new ant colony-based routing algorithms have been proposed. Compared with the traditional routing algorithms. Ant Colony-based algorithm has the advantages of information distribution, dynamic, randomness and asynchronous in network routing, and these features can meet the needs of network routing.

MIC team from Iran adopted the ant colony algorithm in 2018. They set different heuristic values for different agents. Ambulance Team and Fire Brigade need to reach their destination as quickly as possible, so you need to choose a path with a high probability. Police Force needs to clear the barrier, so you need to choose a path with a small probability to detect if there is any obstacle.

Proposed Approach

Compared with other optimization algorithms, Ant Colony-based algorithm has the following characteristics:

a) The positive feedback mechanism is used to make the search process converge continuously and finally approximate to the optimal solution. b) Each individual can change the surrounding environment by releasing pheromones, and each individual can perceive real-time changes in the surrounding environment, and indirectly communicate with each other through the environment. c) The search process adopts distributed computing mode, and multiple individuals simultaneously perform parallel computing, which greatly improves the computing power and operating efficiency of the algorithm. d) The heuristic probabilistic search method will not stuck in the local optimum, and can find the global optimal solution.

Specific methods:

Step 1. Use the game map to obtain the node model of the path. Determine the starting node and the target task point node. Initialize the relevant parameters; Step 2. Release some ants at the starting point. Start a path searching;

Step 3. The ant calculates the state transition probability according to the pheromone concentration of each path and the heuristic function, determines the next path node by using Roulette Wheel Selection rule, and does not select the node that has passed;

Step 4. After all ants reaching the target node, select the shortest arrival path of the total distance in the search cycle, and save the shortest path in the list. Update the pheromone concentration on all paths (all pheromones naturally decay, the path pheromone concentration of ants passing through increases, the shorter the path, the more the pheromone concentration increases).

Step 5. Determine whether the search time is reached. If not, go to step 2 to start the next search cycle, otherwise output the shortest path stored in the list.

We can simulate a situation: path 1 is the shortest path but cannot be passed because of blocks. According to the ant colony algorithm, another path is slightly longer but passable, e.g. path 2. When the blocks of path 1 is cleaned by the police agent, some ants will pass path 1 because of the heuristic function. Therefore, the pheromone concentration of path 1 increases rapidly. The pheromone concentration of path 2 decreases continuously. Finally path 1 is selected. The group algorithm fits with the real situation of the rescue mission. This method is highly efficient.

Pros and Cons

Advantages:

a) It is a distributed solution. b) It can be combined with heuristic algorithms to further improve the efficiency.

Disadvantages:

a) It is difficult to set optimal parameters. b) The computation complexity is high.

2.3 Communication

Purpose

Communication is an important factor for disaster relief. The information that an agent can obtain is limited. Sharing the information with other agents can improve the efficiency of rescue task. The key to communication lies in how to properly deal with the communication within partitions and the communication among partitions.

Related Works

For the communication method, there are not many descriptions in the previous Team Description Paper (TDP). In fact, there are many implementation methods at present. The difficulty lies in how to ensure the transmission efficiency while transmitting information to as many agents as possible. In some studies, information is identified by the importance levels. Then the agent chooses to filter part of the information for reception based on the importance levels, which improves the efficiency of delivery.

Proposed Approach

The communication strategy is generally divided into communication within partitions and communication among partitions.

Communication Within Partitions: Agent will judge whether the message is related to itself or not when receiving a message. If it is related, the agent will give priority to the task in this message. If it is not relevant, this message will be broadcast to the nearby agents. Other agents also reacted after making similar judgments.

Communication Among Partitions: We set up a message sender's task to the Police Force agent. Different partitions' agents meet with the message senders at the meeting point after a fixed period to receive the message. The reason for choosing the Police Force Agent is that it can reach anywhere and can clear the obstacles along the way. They are highly efficient to act as message senders.

Pros and Cons

Advantages:

a) Ensuring that the message is delivered in place.

Disadvantages:

a) A small number of message senders will restrict the message delivery efficiency. b) Too many message senders will use a lot of Police Force resources.

3 Strategies

3.1 Police Force

Purpose

Police's clean behavior plays an important role. In order to help the other agent to carry out the work in time and promote the efficient operation of the whole simulation system, we must ensure that the police agent behavior of high efficiency. Its efficiency is shown as the following three aspects: correctness, effectiveness, smooth.

Related Works

ZJU Base team divides the police mission into three levels. The advanced tasks include self-rescue (avoiding harm to reduce damage), access to shelters (no obstacles around the shelter, ensuring that the agent can enter), and an urgent task is to help the stuck agent, intermediate and low-level tasks include various search tasks (search for fire points, roads and citizens, etc.)

SEU-Jolly team uses the grid division method to disperse the police in the early stage of police intelligence. At the same time, the distributed algorithm was used for task assignment and personnel scheduling.

MRL team uses distributed decision-making algorithms to greatly reduce the impact of communication restrictions. At the same time, the partitioning method is adopted to allocate the police to the equal-sized partitions, and completely cover the entire map in the case of a reduced search space. Therefore this method can reduce redundant work. A linear weighting model is used for the path selection. The clearing priority order is determined according to the value of each path.

Disadvantages: The distribution of police agents is not reasonable. And many teams' strategies for police intelligent body clearing actions have not been highly efficient, resulting in the incompatibility of existing clearing actions and the bad effectiveness of clearing obstacles.

Proposed Approach

Firstly, for task allocation, we divide task assignment into two categories: distributed task assignment in the absence of central agent and centralized task assignment based on central agent. According to these two categories, we propose a task assignment strategy based on task priority and an another one based on the Hungarian algorithm. Finally, for the clearing module, we use the Guideline model, which allows the police agent to move along the guideline and makes the walking trajectory as simple as possible.

Guideline Model

Determine the starting point of the bootstrap

agentEdgeLine, agentAreaLine and areaEdgeLine;

Step1: obtain the road area where the agent is located, denoted as sourceArea; Step2: get the connection boundary of the next region adjacent to the SourceArea and path, denoted as edgeTo.Get the middle of the boundary, call it middle; Step3: make three straight lines: the connection line from the location of the agent to the boundary center point, the connection line from the location of the agent to the center of the road area where the agent is located, and the connection line from the road center to the boundary center, respectively denoted as

Step4: calculate the included Angle between agentAreaLine and areaEdgeLine, agentAreaLine and agentEdgeLine, respectively denoted as $\theta$ and $\alpha$; Step5: compare the size of $\theta$ and $\alpha$, if $\alpha < 80$ and $\theta > 80$, the intelligent body position is the starting point of the guideline; Otherwise, the starting point is still the center of the road area where the agent is located.

The points, lines, angles and areas used in the above steps are shown in the figure below:

Plan the intermediate connection process of the path guideline

Step1: traverse from the first road area to the penultimate area of the entire path;

Step2: determine the starting point of the current region and the midpoint of the adjacent boundary between the current region and the next region;

Step3: establish the regional guidance line from the starting point to the middle point of the boundary, and add it to the list of path guidance lines;

Step4: take the middle point of the current boundary as the starting point of the next regional guideline; Step5: repeat steps Step2 through Step5.

A schematic diagram of the above process is shown below:

Determine the endpoint of the path guideline

All the intermediate and indirect processes of the path guidance line above start from the midpoints of two adjacent boundaries until the last area, that is, the road area where the target point is located.The path to be cleared by the police is planned to the target point, but not the area where the target point is located. At this point, the target point is used as the end point of the last area guideline and the area guideline is added to the list of path guidelines. Schematic diagram is shown as follows:

Experimental result

The figure below shows a comparison of the model with and without the guideline

Pros and Cons

Advantages:

a) The agent is adaptive to the dynamic rescue environment. b) The trajectory of the police agent can be optimized.

Disadvantages:

a) The quality of the communication mechanism seriously affects the results of task assignment. b) The Guideline model requires a more rational design when dealing with intersections and map edges.

3.2 Ambulance Team

Purpose

The task of the ambulance team is to rescue, treat the trapped wounded and transport them to the refuge quickly and effectively. Based on the strategies in previous years, we plan to improve the efficiency of rescue.

Related Works

Team RoboAKUT rescues according to the state of trapped people. If he is buried, the agent needs to rescue the buried person from the ruins. If he is injured, the agent needs to be similar to the building according to the distance between the agent and him. The center of the object detector is assigned.

Tehran uses the 'death time' algorithm, which estimates the period that can lead to civilian death. According to the estimated death, it can determine the burial point and health point of the parent.

University of Tabriz uses Artificial Neural Network and Particle Filtering to find a reasonable and efficient solution.

Proposed Approach

The combination of AIS and agent technology can form an immune agent model. In the case that the task is unknown and diverse, the immune agent model can achieve the autonomous cooperation and rescue tasks between multiple heterogeneous agents. Taking the rescue agent as an example, the rescue system of the rescue agent can be mapped to the artificial immune system. In the design of the algorithm, the antigen corresponds to the action of the rescue agent to choose which citizen to rescue, and the antibody corresponds to each citizen or injured person. According to the evaluation function of the artificial immune network, the whole rescue action will be realized.

Pros and Cons

Advantages:

a) It uses weights to make decisions and ensure the rationality of decisions

Disadvantages:

a) AIS can't always obtain good performances especially when the population is unevenly distributed.

3.3 Fire Brigade

Purpose

The purpose of setting this strategy is to better control the fire and reduce casualties. Determine the edge building by constructing a convex hull of the point set, and then extinguish the fire from the outside to the inside to prevent the fire from spreading.

Related Works

The Concave Hull is also a tool that can be used to compute the envelope of a set of points in the plane, by generating convex or non-convex polygons that represent the area occupied by the given points.We also plan to incorporate this method to improve the accuracy and the fire suppression efficiency.

There are many teams that choose to prioritize extinguishing by weighting the building elements. Although this can quickly save a damaged building, it will cause the fire to spread too quickly and damage more buildings.

Proposed Approach

The method of weighting the priority fire extinguishing according to the various indicators of the building cannot control the spread of the fire. Therefore, our strategy is to prioritize the firefighting of buildings outside the perimeter to prevent the spread of fire and keep the fire within a certain range.

Convex hull creation: Each building can be treated as a point. Then we build a convex hull of this point set. The surrounding buildings are then determined. We use Graham algorithm to build convex hulls. The first step is sorting points set. The second step is stack scan. At the end of each simulation cycle, the program updates the fire information and updates the convex hull.

When choosing a priority building in the edge, we also consider the following strategies:

a) When the fire can be controlled around at the refuge, give priority to fire at the refuge. b) Giving priority to extinguish the fire may be extinguished gasoline station. c) After the fire out of the petrol station to check whether it is possible to burn again.

Pros and Cons

Advantages:

a) The fire is easy to control and the area affected is small.

Disadvantages:

a) The internal building has a high probability of overburning.

4 Preliminary Results

Preliminary Results ( means we have modified the map.)*

5 Conclusions

Different agents have different responsibilities and behaviors, so the priorities of tasks are different. We should design different strategies for different agents for an efficient solution. At the same time, we can't ignore the cooperation between agents. Effective cooperation strategies can generate greater benefits. Communication is the foundation of cooperation, so we try to use a reasonable communication strategy to improve the score.

In the coming period, we plan to absorb the advantages of other team agents, and then improve our strategies.

References

1. Kandeh, A., Absalan, A.: Rescue Agent Simulation Aura. RoboCup 2018 (2018)
2. Levent, H.: Rescue Agent Simulation RoboAKUT. RoboCup 2018 (2018)
3. Nejad, R.V., Zare, A., Iranbakhsh, R.: Rescue Agent Simulation M.I.C. RoboCup 2018 (2018)
4. Nishida, T., Okajima, K., Iuchi, H., Mashiro, E., Suzuki, M., Oibayashi, T., Morimoto, R., Komura, S., Kanechika, A., Nozaki, H., Fukui, K., Ijichi, T., Oguri, T., Masuda, K., Higashi, Y., Amada, J., Nakamura, H.: Rescue Simulation League Team Description Rione (Japan). RoboCup 2018 (2018)
5. Niu, W., Wu, J.: Rescue Simulation League SEU_Jolly Team Description (2015)
6. Qian, C.: Rescue Simulation League Team Description SEUUniRobot (P.R.China). RoboCup 2017 (2017)
7. Sharbafi, M.A., Ghiasvand, O.A., Ramandi, S.A.: Rescue Simulation League MRL Team Description (2014)
8. Sun, H., Guo, L., Xie, P., Wang, X.: Research on artificial immune algorithm in robot path planning[J](in Chinese) (2018)
9. Tang, L., Li, J., Wang, Y.: Rescue Simulation League Team Description<ZJUBase(China)>[OL] (2014)
10. Wu, J.: The police division strategy based on K-means algorithm in RoboCup rescue simulation [A](in Chinese) (2015)
11. Zhang, P., Kang, T., Jiang, F., Peng, J., Zhang, X.: Rescue Simulation League Team Description CSU_Yunlu(China). RoboCup 2017 (2017)
12. Zhang, W.: Research and application of MapReduce clustering method [D](in Chinese) (2018)