What Evacuation Can Maintain Social Distance! Proposed Algorithm For Deriving Social Distance-aware Evacuation Policies Using Deep Reinforcement Learning!
3 main points
✔️ The COVID-19 pandemic has pointed out the importance of placing social distance
✔️ Build a model to derive optimal guidelines for evacuation activities in emergencies, taking into account such social distance, using reinforcement learning.
✔️ Evaluation results show that the proposed model can derive efficient routing compared to the conventional algorithm - Sweep algorithm
Routing algorithms as tools for integrating social distancing with emergency evacuation
written by Yi-Lin Tsai, Chetanya Rastogi, Peter K. Kitanidis, Christopher B. Field
(Submitted on 5 Mar 2021 (v1), last revised 13 Oct 2021 (this version, v4))
Comments: Published on arxiv.
Subjects: Artificial Intelligence (cs.AI); Computers and Society (cs.CY); Human-Computer Interaction (cs.HC); Machine Learning (cs.LG)
code：
The images used in this article are from the paper, the introductory slides, or were created based on them.
background
Is it possible to derive the optimal evacuation route considering social distance?
In this study, we aim to derive the optimal evacuation policy considering social distance under the assumption of disasters such as a pandemic in COVID-19 - i.e., earthquakes and typhoons - by using deep reinforcement learning.
Maintaining social distance will continue to be essential against the still raging COVID-19; while disasters - i.g. floods, wildfires, earthquakes, landslides - may still occur during a pandemic. The possibility of social distance is assumed, and it is necessary to derive the best evacuation policy it has been reported that the increase in outbreaks of infectious diseases such as influenza, SARS-CoV-1, and SARS-CoV-2 are related to the climate change of several decades ago, Therefore, even after the convergence of COVID-19, it is necessary to prepare for the next pandemic. Therefore, it is necessary to clarify the evacuation policy considering social distance in preparation for and response to a complex disaster in anticipation of future pandemics.
This research aims to build an RL model that can improve evacuation operations in complex events, including both pandemics and foreseen disasters - i.g., earthquakes and tsunamis: specifically, we investigate the effect of the number of emergency vehicles required to extend evacuation time and evacuate We investigate the role of social distance in increasing social distance and develop an algorithm that improves evacuation efficiency compared to a non-DNN method - the Sweep algorithm - using optimized vehicle routing based on deep reinforcement learning. While the algorithm requires a priori operational rules for transporting evacuees, deep reinforcement learning can learn strategies based on action choices in the environment and agents, and search for optimal routing.
What is COVID-19?
First, we describe COVID-19, the subject of this study.
COVID-19 was discovered in Wuhan, China, in 2019 and subsequently spread worldwide, causing a pandemic. Symptoms develop about four or five days after a viral infection - as long as two weeks later. The main symptoms are fever; cough; breathlessness; lethargy; loss of smell and taste. Elderly people and those with underlying diseases such as heart disease and diabetes are more likely to develop severe pneumonia, and other generations have also reported respiratory symptoms, high fever, diarrhea, and taste disorder. Genetic sequencing analysis has reported that this virus is similar to the coronaviruses of bats and civets, suggesting that these may have undergone genetic modification. The number of cases is reported to be about 1,000 in Japan. It is spread from human to human via cough and droplets, mainly by airborne transmission. Currently, the development of a highly effective vaccine is underway to prevent the spread of the disease.
research purpose
In this study, we aim to construct an algorithm to derive an optimal evacuation policy considering the social distance, assuming a situation where COVID-19 is widespread.
Even in a pandemic situation, disasters such as earthquakes may occur, and it is necessary to derive an optimal evacuation policy while maintaining social distance. In this study, we propose a model that utilizes deep learning reinforcement learning to derive such a policy. Specifically, we formulate an evacuation route and derive an evacuation policy that maximizes an objective function under a set of constraints. The evaluation results show that the proposed algorithm can derive a more efficient evacuation policy compared to the conventional method - The sweep algorithm.
technique
In this section, we describe the outline and evaluation environment of the proposed method in this study.
case study
This study uses the evacuation policy in New Orleans as a case study as a simulation environment for disasters requiring social distance - New Orleans has an evacuation policy for a 72-hour hurricane evacuation, with 42 hours before reaching the coast. The plan is presented to pick up area residents from their homes and transport them to the Smoothie King Center, a citywide rescue center.
Problem formulation
In this research, one of the vehicle routing problems in pre-disaster evacuation -Vehicle Routing Problems (VRP)-, Capacitated Vehicle Routing Problem -CVRP The problem is based on a set of relief centers - depots - and nodes - customers - for pre-disaster evacuation, which can be formulated as follows
These equations imply above: an objective function that minimizes the total cost of the neighborhood - the total evacuation time; a constraint that each house is visited only once; a constraint that the emergency vehicle can depart from the rescue center only once for each route in K condition; a constraint that the number of emergency vehicles arriving and departing from each house/rescue center is the same; a constraint that ensures that the number of people picked up by an emergency vehicle on a single route does not exceed the vehicle capacity C; a constraint to avoid routes that are disconnected from the rescue center; a decision variable is 1 (visited) or 0 (unvisited) Constraints.
From the objective function and constraints thus formulated, each algorithm derives an evacuation policy.
Algorithm Design
In this section, we outline the models related to the conventional method - The sweep algorithm - and the proposed method utilized in this study.
The Sweep algorithm starts from the depot - the rescue center - with an arbitrary line; it sweeps this line counterclockwise, adding houses one by one when the line intersects a house, to determine the order of houses that the emergency vehicle should visit. The emergency vehicle must also return to the rescue center when it exceeds its passenger capacity.
The proposed model utilizes deep reinforcement learning, in particular, the attention model - this algorithm has been shown to perform well on path problems involving CVR. Attention models are based on attention-based transformers and CNNs-Convolutional Neural Networks masked by a self-attention layer, which are used to efficiently analyze graph-structured data, such as GAT -Graph Attention Networks-, whereas a type of Graph Attention Networks-, which integrates RL.
result
This section describes the results of the evaluation conducted in this study.
Trade-offs between geographic size and social distance
Here, the CVRP is simulated and analyzed for the trade-off between area size and social distance, where the process of emergency vehicles loading residents until they reach capacity is repeated - as the area size increases, the need to maintain social distance also It is assumed that this will increase. The locations of nodes - houses - and depots - rescue centers - in the standard CVRP dataset were used in this assessment. The demand for each node - household size and the number of people in each house in emergency vehicles - was generated using the average household size in New Orleans. The area sizes in the four datasets used were 20, 35, 52, and 68 homes. Here, social distance limits the number of people that can ride in one rescue vehicle - 64, 32, 16, 8, 4, and 2 people per vehicle, respectively. After the emergency vehicle finished loading the residents, the total time and number of routes were summed and output - see figure below.
Here, we assume that the plan is to begin loading residents 54 hours before the storm reaches the coast and collect the last residents by 30 hours before the storm reaches the coast - between 30 hours and 12 hours before the storm reaches the coast, the city can continue evacuation activities as needed. To evaluate the DNN-based and non-DNN models, we used a 42-hour and 24-hour threshold to determine if the emergency vehicles completed their evacuation mission within the expected timeline. The time performance was classified as Satisfactory - less than 24 hours, Borderline - 24-42 hours, and Not Allowed - 42 hours or more. The results were categorized into -.
Evaluation of Regional Scale
Here we present our assessment of changes at the regional scale.
The results of the assessment showed that the total time taken to evacuate increased with the size of the area, regardless of the number of people accommodated per rescue vehicle - social distance - - see figure below.
The total time for the proposed and conventional methods increased more with increasing social distance for all region sizes: for 32 occupants in an emergency vehicle, increasing the region size from 20 to 68 resulted in 1.89 h - proposed method - and 4.79 h-the conventional methods increased the total time; and for a more stringent social distance - 2 persons per vehicle - 23.37 h-the proposed method -and 22.18 h - the conventional method - the total time had increased.
In addition, the average total time for the six-vehicle capacities - 2, 4, 8, 16, 32, and 64 persons per vehicle - rose with region size and was linearly proportional - see figure below
For example, when the region size is increased from 20 to 68 with 16 persons per vehicle, the minimum - +0 hours/route - and maximum - +2 hours/route - cases with transit times of 2.37 and 2.97 times increase in the minimum - +0 hours/route- and maximum - +2 hours/route- cases. The relationship between region size and average total transit time approximated a linear proportional relationship when longer transit times were added compared to the case where no transit time was added to each route.
How to take a social distance
In this section, we discuss the relationship between social distance and evacuation time.
The evaluation results show that the total evacuation time increases with increasing social distance - see figure below.
In the most severe case, the evacuation time was less than 42 hours only when the transit time was zero. For 32 passengers per vehicle - a less restrictive social distance - the sensitivity of the evacuation time to the passenger limit was almost identical to the proposed and conventional method solutions.
Effectiveness of DNN-based and non-DNN solutions
In this section, we describe the comparison results between the effectiveness of the conventional method and the proposed model.
For each route scenario, the proposed method reduced the total evacuation time in 66.67% of cases compared to the conventional method - see figure below.
The proposed method required fewer pathways than in 8.33% of the scenarios. The proposed model also showed that, on average, the proposed model used more routes in less time. On the other hand, the advantage of the proposed method decreased as the transit time of each route increased. Also, except for the case of small region size and vehicle capacity - in the general vehicle example - the effectiveness of the proposed model was shown - the proposed model outperformed the conventional method by up to 40.18%, high capacity vehicles, mild social distance and maximum under large area conditions. The number of routes required was almost the same.
consideration
In this study, we developed an evacuation route model that can maintain appropriate social distance in the event of a pandemic such as COVID-19 using deep reinforcement learning. As a result of the evaluation, compared with the conventional routing algorithm -Sweep algorithm-, the evacuation policy derived by this model increases the efficiency of evacuation, while the case that the demand for social distance becomes strong is -i.g., larger region sizes-, reduced effectiveness- -while the use of deep reinforcement learning can improve efficiency, the time needed to add social distance to each evacuation route is not sufficient. The results of this study suggest that it is difficult to These findings are not only relevant to COVID-19, but also other disaster evacuations based on local registration information, and are expected to be adapted to such situations. It is also expected that, during the evacuation, the effectiveness of the model is reduced when the emergency vehicle size is small, while the method can be used effectively when the vehicle capacity is larger than each household: in these cases, multiple households are combined on the route, and an efficient routing strategy is It can be considered that it is difficult to derive heuristically - the RL model is likely to be effective for these tasks because it can self-learn without a correct answer, even in complex situations where it is difficult to set the correct answer.
One of the challenges in this study is learning and evaluation, considering the vehicle size. The proposed model tended to lose effectiveness especially when the emergency vehicle capacity was close to the size of one household - node. In general, the vehicle capacity is much larger than the demand of each node, so learning and evaluation must be performed for situations with low-capacity vehicles. In addition, when the social distance is long, the proposed model does not provide enough time for guidance, which is assumed to be insufficient for practical use. For this point, we can consider the use of other RL algorithms.
Categories related to this article
