RoboCup Rescue 2022 TDP Agent Simulation CSU_Yunlu (China)

Fu Jiang, Tingyu Yuan, Haibo Chen, Zijin Wang, Ming Chen, Yibin Wang, Jiayu Chang, Lepeng Wang

Central South University, China

Abstract We will explain themain strategies and algorithms of CSU_Yunlu in this year's RoboCup Rescue Agent Simulation in this paper.Taking advantages of k-means algorithm and optimized k means++ algorithm , the buildings are divided into different clusters . We use A* routing algorithm to enable the agents to select the optimal path. The partition-based communication method improves the efficiency of conveying message. The strategies for several agents improve the efficiency of the rescue operation.

1 Introduction

Team CSU_Yunlu [1] has been participating in the RoboCup rescue simulation competition since 2006. In addition, we have achieved good results in RoboCup 2016, 2017, 2019 and 2020. We hope to optimize our strategy and improve the performance of our team based onthe strategies we have in previous years.

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

2 Modules

(No introductory text for this section)

2.1 Clustering

(Content organized in subsections below)

Purpose

In the rescue environment in RoboCup Rescue Agent Simulation, every map consists of thousands of nodes. In order to improve the efficiency of searching the whole map for agents, we can divide the whole map into clusters through a clustering module. Each cluster can be seen as a smaller map, which greatly reduces the complexity of obtaining the information of each cluster. It is conducive to better allocation of each agent to each building set, so the overlap between agents can be reduced and working efficiency can be improved.

Related Works

Kmeans algorithm is a widely used clustering algorithm. The algorithm can not only classify a small amount of data. It can also be iterated and updated. With the deepening of iteration, it can be further optimized. However, if the amount of data is large and the initial k-center point is not set well, more energy will be consumed in thesubsequent iterative optimization.

For the optimization of this problem, K-means + + algorithm can be used.Incidentally, similar to the probability of roulette [2], the initial k center points can be better determined. It can improve the optimization efficiency of the algorithm and reduce the running time of the algorithm.

Proposed Approach

K-means++ algorithm is used by our team to solve the problems of the clustering generation.

The specific algorithm steps are in the following approaches::

• (1) A point is randomly selected as the first cluster center from the input data point set.
• (2) For each point X in the dataset, calculate the distance D (x) between it and the nearest cluster center (which refers to the selected cluster center)
• (3) Select a new data point as the new cluster center, the principle : the point with larger D (x) is more likely to be selected as the cluster center. Then, we will calculate the sum of D(x) of all unselected points, and randomly give a number between 0 and sum, then calculate the sum of D(x) from the first unselected node. Until the sum is greater than the random number, this is one of the centralpoints we want.
• (4)Repeat the steps of 2 and 3 until K cluster centers are selected.(5)Using these k initial cluster centers to run standard k-means algorithms.

Pros and Cons

• (1) It can better solve the problem of center selection in K clustering.(2) For large data or K value, D (x) calculation and subsequent iterative optimization still need a lot of time.Because the initialization node is not fixed every time, and it is not guaranteed that the initialization node is good enough every time the code runs.

2.2 Path Planning

(Content organized in subsections below)

Purpose

The pathfinding strategy is designed to help agents and citizens find the optimal path. 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

By calculating the sum of the consumption value and the predicted value of the current path, the possible priority of each path can be determined. In many cases, A * is the best solution. In addition, in some cases, other algorithms based on A *, such as D * [4] and Ara [5], have even better performance than A *.

MRL team [6] from Iran adopted the A* algorithm in 2019. With respect to the existence of the blockades, if the navigation doesn't work properly, it can cause a huge time waste. They implemented new graph based on area passable edges and available blockades. Their A* algorithm considers these passable and blocked nodes to finding shortest reachable route.

Proposed Approach

The main steps of the A* algorithm used by our team are as follows:

• (1)Add the starting road to openlist.(2)Take out the first node in openlist and add it to Closelist.

Then,judge all the edges that can be passed. If they are not in openlist and Closelist, add them to openlist.Otherwise, compare and update the consumption value with the source node.

• (3)According to F = G(current consumption value)+H(predicted value), all the nodes in openlist are sorted from small to large.
  • (4)When the openlist is not empty, continue to operate 2 and 3.
• (5)Judge whether there is a path.If yes, the path will be obtained and output.

Pros and Cons

• (1) A* algorithm is the fastest algorithm to calculate the shortest path so far. But it is only a better algorithm in most cases, thatis, it can only find the better solution, but often not the optimal solution. However, due to its high efficiency, it has a wide range of applications.
• (2) However, the key of A* algorithm is how to select the evaluation function. The closer to the correct valuation function, the faster the correct solution can be obtained,but the completely correct valuation function is generally not available. Therefore, the A* algorithm can not guarantee the correct solution every time. An unsatisfactory evaluation function may even make itinefficient, and it will give the wrong answer. So we must choose different schemes according to the reality.

2.3 Communication

(Content organized in subsections below)

Purpose

Communication is an important factor for disaster relief. The information that an agent can obtain is limited.Sharing information between agents can improve rescue efficiency. The key to communication lies in how to properly handle the communication within and between the various partitions .

Related Works

For the communication method, The difficulty lies in how to transmit information to as many agents as possible while ensuring transmission efficiency. 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 communicationwithin 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 not, this message will be broadcast to the nearby agents. Other agents will respond similarly.

Communication Among Partitions: Different agents have totally different tasks. However, the messages they catch from environment are helpful for all kinds of agents. For example, the Police Force agent may find buried humans. So, once they get this information, they need to immediately alertother agents in order to better help humans.

Pros and Cons

Advantages:

• (1) Ensuring that the message is delivered in place.
• (2) Ensuring that the message is spread rapidly.

Disadvantages:

(1) A large number of message senders will reduce the message processing efficiency.

3 Strategies

(No introductory text for this section)

3.1 Police Force

(Content organized in subsections below)

Purpose

Police's clean behavior plays an important role. In order to help other agents to clear the roadblocks as quickly aspossible and promote the efficiency of the whole simulation system, we must ensure that the police agent behavior be of high efficiency. Its efficiency is shown in the following three aspects: correctness, effectiveness, smooth.

Related Works

Team ZJU Base team [7] divides the police mission intothree levels. The advanced tasks include self-rescue (avoiding harm to reduce damage), accessing to shelters (no obstacles around the shelter, ensuring that the agent can enter), and the urgent task is to help the stuck agent, intermediate and low-level tasks include various search tasks such as searching for fire points, roads and citizens, etc.

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

Team MRL [9] used a guideline to help police force agents clear a road smother and prevent to create jagged blockades in a long straight path. What's more, it will greatly improve the efficiency of road cleaning in early stage of rescue simulation.

Proposed Approach

Firstly, for task allocation, we divide the task assignment into two categories: distributed task assignment in the absence of central agent and centralized task assignment based on the centralagent. According to these two categories, we propose a task assignment strategy based on task priority and Hungarian algorithm.

Guideline Model

Determine the starting point ofthe bootstrap

• (1) Obtain the road area where the agent is located, denoted as source Area.
• (2) Get the connection boundary of the next region adjacentto the Source and path, denoted as edge. Get the middle of the boundary, call it middle.
• (3) Make three straight lines: the connection line from the location of the agent to the boundary center point, the connection linefrom 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 agentEdgeLine, agentAreaLine and areaEdgeLine;
• (4) Compare the size ofθ and α, if α < 80 and θ > 80, the intelligent body position is the starting point ofthe 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:

Pros and Cons

Advantages:

• (1) The agent is adaptive to the dynamic rescue environment.
• (2) The trajectory of the police agent can be optimized.

(3) The clear action save plenty of time which brings convenience of other agents' rescue action.

Disadvantages:

• (1) The quality of the communication mechanism seriously affects the results of task assignment.
• (2) The Guideline model requires a more rationaldesign when dealing with intersections and map edges.

3.2 Ambulance Team

(Content organized in subsections below)

Purpose

The task of the ambulance team is to rescue the injured residents from the fire brigade and deliver them to the appropriate shelter quickly and effectively.

Related Works

Doctors will focus on transporting injured residents to suitable shelters. Ambulance team is to send the injured residents and to assist the Fire Brigade.

Proposed Approach

In order to make doctors treat as many patients as possible and find more victims, we optimized the doctor's decision-making and cooperation with peers:

• (1) Classify the rescue objects,then set the priority and select the rescue objects according to the priority.
• (2) After the target is established, the rationality of the target is judged according to the information obtained.
• (3) Strengthen the cooperation ability of agents: through communi cation and cooperation, a doctor nearest to the injured residents will be selected to rescue.
• (4) When no injured person is waiting for rescue, the doctor will search the building according to certain strategies, and inform the police to clear the road block if it is found.
• (5) When doctors search for shelter after loading humans, they judge the time to arrive at the shelter and the sum of waiting timeto ensure that the injured can get the fastest rescue.
• (6) In calculating the rescue time, the correction time will be increased according to the calculation time. For example, when the subject is next, the correction time is zero. Through which can we ensure that all subjects use the same treatment method.

Pros and Cons

Advantages:

• (1) It uses weights to make decisions and ensure the rationality of decisions.
• (2) The communication part of agent is optimized to enhance the ability of cooperation between agents.

Disadvantages:

(1) Strategies depends on the accuracy and timeliness of communication, and the ability of independent strategies is not strong. In specific cases, it will affect the rescue effect.

3.3 Fire Brigade

(Content organized in subsections below)

Purpose

In the past, the firefighters' major task is putting out fires. But the fire rarely happens in the actual earthquake disaster. For this reason, the map will no longer be on fire in the latest version and the duty of firefighters also changed to rescue buried citizens.

Related Works

Follow the doctors' example, the firefighters' behavior are divided into two parts. One is to move to a known location of the injured citizens and rescue them, and the other one is to search for an injured citizen. In the actual running scene, many people will die due to it takes a long time to rescue a citizen. Therefore, we must ensure that most of the time is to rescue a citizen rather than to search for an injured one in every firefighters.

Proposed Approach

We first rank the injured by distance, then abandon those who have died or cannot be saved. Finally, target the nearest citizen. If the firefighters can't find anyone buried, they go into the building and found who in need of help.

Pros and Cons

Advantages:

(1) Choosing target according to distance can improve the efficiency of agent. In addition, giving priority to rescuing injured citizens can substantially decrease the number of injured citizens.

Disadvantages:

(1) There will be some firefighters to save a target which waste a lot of time to move to the target location.

4 Preliminary Results

We have compared us with last year's champion AIT on last year's final map.

Comparison with AIT-Rescue team on final maps

5 Conclusions

Different agents have different responsibilities and behaviors, so the priorities of tasks are different. Path Planning and Clustering are the most basic and important modules, so finding a better way to achieve them is a constant topic. We should design different strategies for different agents to achieve an efficient solution. At the same time, we can't ignore the coopera tion 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. Also, we will try to introduce more advanced methods and we will improve the behavior of some agents in the future, too.

References

1. Jiang, F.,Lv,W.,Cai,G.,Chen,R.,Yue,B.,Gao,Y.,Ge,Y., Chen, X., Xiong, J., Lv, W.: Rescue Simulation League Team Description CSU_Yunlu(China). RoboCup 2020(2020)
2. David Arthur and Sergei Vassilvitskii: k-means++: The Advantages of Careful Seeding(2007)
3. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4(2), 100–107 (1968)
4. Likhachev, M., Ferguson, D.I., Gordon, G.J., Stentz, A., Thrun, S.: Anytime dynamic a*: An anytime, replanning algorithm. In: ICAPS. vol. 5, pp. 262–271 (2005)
5. Likhachev, M., Gordon, G.J., Thrun, S.: Ara*: Anytime a* with provable bounds on sub-optimality. In: Advances in neural information processing systems. pp. 767–774 (2004)
6. Zarei, S., Chatri, M., Mirfattahi, S.: Rescue Agent Simulation MRL. RoboCup 2019 (2019)
7. Tang, L., Li, J., Wang, Y.: Rescue Simulation League Team Description<ZJUBase(China)>[OL] (2014)
8. Niu, W., Wu, J.: Rescue Simulation League SEU_Jolly Team Description (2015)
9. Ardestan, P., Taherian, M., MohammadAliZadeh, P., JazebNikoo, E.: Rescue Simulation League MRL Team Description (2017)