An Online Learning Approach towards Far-sighted Emergency Relief Planning under Intentional Attacks in Conflict Areas

1 Introduction

Humanitarian relief operations have become much more significant because of the increasing number of disasters around the world [Besiou and van Wassenhove, 2020; De Vries and Van Wassenhove, 2020]. For instance, 2011 Japan earthquake, 2017 Hurricane Maria, 2019 Australia Wildfires, as well as the ongoing virus epidemics, i.e., the COVID-19 across the world. These disasters have taken millions of lives and resulted in huge economic losses. Fueled by the need of mitigating the miserable effects of these disasters, humanitarian relief operations and disaster management received an increasing attention from researchers, and different aspects of the operations management have been studied in the literature [Huang and Song, 2018; Ekici and ¨Ozener, 2020].

∗Corresponding author

However, despite the uncertainty derived from the disaster itself, security issue and the derived uncertainty from malicious attackers are also vital factors affecting the actual humanitarian relief operations in conflict areas [Chaudhri et al., 2019]. There has been a rise in the number of attacks on humanitarian aid workers (including UN staff, NGO staff, etc.), reporting 226 attacks on aid workers in 2018 with 131 deaths, which is nearly four times the 2004 number of 63 incidents (with 56 deaths) [AWSD, 2018]. Attacks against aid workers have become a big challenge facing humanitarian organizations to provide security in fragile and conflict-affected areas [Hoelscher et al., 2017]. For example, the second largest DRC Congo Ebola outbreak in December 2019 has been a humanitarian crisis that originated in an active conflict area, which has severely affected the ability of relief efforts and vaccination [Schwartz, 2020]. The major epidemic area is the Eastern Congo including Nord-Kivu and Sud-Kivu province, in which more than 10 armed rebel groups exist [Usanov et al., 2013]. These armed groups actively operate in the regions of Ebola virus relief, controlling the routes in and out of the regions; levying taxes on households and transport; attacking healthcare and relief workers [Schwartz, 2020]. Hence, humanitarian relief planning practice in conflict-affected areas facing huge risk and uncertainty from hostile rebel groups.

To the best of our knowledge, few studies has focused on the multi-stage online emergency relief planning problem in conflict areas (MonERP) which takes the uncertainty from both adversary and environment into account. In this paper, we address this challenging problem, in which the humanitarian organization aims at transporting urgent resources (e.g., living and medical supplies) from the resource base to cities applying for the relief in real time, while the hostile armed group operates to hinder the relief operations by controlling some routes and levying taxes on transport. Different from general extensive-form games, data and parameters of the game (e.g., the amount of demands, the cost of transportation, the distribution of hostile rebel groups) come in an online fashion instead of being revealed at the outset. On receiving a relief request, the rescuer with limited resources needs to make an irrevocable decision whether to accept or reject the demand, with the overall objective of maximizing the demand satisfaction while considering the security risks of humanitarian operations. The attacker, on the other hand, has an opposite interest and can mobilize armed forces to control towns in their surrounding area.

In this work, we aim to develop the first salable and efficient online learning approach to MonERP, and the key contributions are: (1) We first model the omniscient version of MonERP as a multi-stage offline emergency relief planning problem (MoffERP), which is transformed as a binary integer linear programming with all data and parameters known in advance. The solution of MoffERP provides us with the upper bound of MonERP. (2) To meet the need of online and irrevocable decision making, MonERP is modeled as an online linear programming after integrating the result of Nash Equilibrium in each decision-making stage. (3) An online learning algorithm is proposed to solve MonERP, which achieves a O( 1 √n ) average regret when those online revealed parameters are generated i.i.d. from an unknown distribution; here, n is the number of decision-making stages. (4) Extensive experiments are conducted on a real anti-Ebola relief planning case based on the data of Ebola outbreak and armed attacks in DRC Congo. Evaluation results show the performance advantages of the far-sighted relief planning considering online features, and the proposed approach are applicable to large realistic-scale problems efficiently.

2 RelatedWorks

2.1 Humanitarian Relief Planning

Humanitarian relief operations require efforts on many fronts, such as facility location and network design, vehicle routing, inventory management, network flow, and combination of them, etc. Typical works of relief routing problems include models and methods for achieving objectives like minimizing delivery delay in various situations [Yuan and Wang, 2009; Sabouhi et al., 2019], maximizing the number of victims served [Ozdamar et al., 2018], minimizing life losses and human sufferings [Huang and Song, 2018], reducing cost and guaranteeing fairness [Zhu et al., 2019], etc. Some models focus on routing problems with determinate parameters, while problems with uncertainty attract more attention since they are closer to actual needs. For example, Allahviranloo et al. [2014] use robust optimization to address the demand uncertainty in vehicle routing problems. A robust optimization approach with a coaxial uncertainty set is developed by [Balcik and Yanıkoˇglu, 2020] for humanitarian needs assessment routing under travel time uncertainty. Unfortunately, the risk and uncertainty derived from malicious attacks are not considered in existing research.

2.2 Network Interdiction Game

Network interdiction problem is a kind of Stackelberg game, which has been widely applied to security decision-making scenarios relating to operations on networks, involving military operations, humanitarian relief, fare evasion, telecommunication, transportation and logistics, and cyber-security [Smith and Song, 2020; Sinha et al., 2018]. Besides of classic models [Fulkerson and Harding, 1977; Israeli and Wood, 2002], different variants of SPNI models with new features have received considerable attentions recently, including incomplete information [Borrero et al., 2019], goal recognition assistance [Xu et al., 2017], dynamic or adaptive interdiction [Correa et al., 2017; Xiao et al., 2018; Zhang et al., 2019] etc. However, few studies focus on the interdiction game with online data inputs.

2.3 Online Linear Programming

Sequential decision making has been an increasingly attractive research topic especially in scenarios with dynamic environment and long-term consideration. For instance, the scenario of online packing problem[Buchbinder and Naor, 2009], auction problem [Balseiro and Gur, 2019], and resource allocation[Balseiro et al., 2020]. These problems can be viewed as online linear programming (OLP), i.e., the problem of solving linear programs in a sequential setting. A simple and fast online algorithm for solving a general class of binary integer linear programs is proposed in [Li et al., 2020] achieving O(m√n) expected regret under the stochastic input online data, where n is the number of decision variables and m is the number of constraints. These studies provide a theoretically guaranteed algorithm for long-term revenue in sequential decision making, which is instructive for achieving far-sighted emergency relief planning.

3 Offline Multi-stage Relief Planning

In this section, we first model the offline version of MonERP as a sequence of stage-based games between the rescuer and attacker, after which it is integrated and transformed to a linear programming. Then, based on the mixed Nash equilibrium of stage-based games, the optimal offline relief planning is given by solving the linear programming.

3.1 The Simultaneous Relief Routing Game at Each Stage

In each stage of the MonERP, there is a simultaneous relief routing game between the rescuer and attacker. Both of them play the game on a road network G = (V, E) consisting a set of nodes V representing intersections (cities,towns, etc.) and a set of edges E representing roads. If the rescuer in stage t decides to meet the relief demand wt from the resource base city ot to the city of demand gt, she needs to plan a road path through the network so as to minimize the cost of transporting. The attacker, on the other hand, has several armed forces distributed in different nodes of the network and aims to mobilize them to interdict the rescuer thereby levying taxes or directly robbing under the constraint of mobility. We then model this stage-based confrontation between the rescuer and attacker as a simultaneous relief routing game as follows:

The attacker problem is implementing his armed forces distributed in the network to control some selected nodes so as to interdicting the relief routing of the rescuer. Denote by ht = (hjt)j∈V ∈ {0, 1}|V | the distribution vector of the armed forces, and hjt = 1 if there is an arm force stationed at node j. The strategy of the attacker is made up of |I| vectors, denoted by zit = (zijt)j∈V ∈ {0, 1}|V | , and zijt = 1 if the armed force i is decided to reach and control node j at stage t. Also, the actions of attacker are restricted by movement constraints, i.e., the movement cost of each armed force i ∈ I should not exceed the budget fit at stage t (vector form ft). Then, the set of all feasible strategies for the attacker can be denoted by

where 1 denotes the all 1 vectors, and the first constraint illustrates that one armed force can only be deployed once in each stage. Let L = (lj ′ j)j ′ ,j∈V ∈ R|V |×|V | + represent the cost of implementing the stationed force from node j to node j ′ , which can be estimated by the attacker using road transport information. Hence, the second constraint makes the deployment of armed forces not exceed the attacker's budget.

The rescuer problem is planning a routing path through the network from ot to gt which can be modeled as a shortestpath problem. Denote by yt = (ykt)k∈E ∈ {0, 1}|E| the decision variables of the rescuer representing a path in the network, and ykt = 1 if she selects the edge k to traverse. Let FS(i) and RS(i) represent the set of edges directed from/into node i. Then, the strategy space of the rescuer is determined by the following flow conversation constraints:

Then the set of all feasible strategies of the rescuer is

The utility for both players is the cost of emergency relief transporting. The rescuer aims to minimize it by selecting the path traversed, while the attacker interdicts the relief routing. The utility function is bi-linear and made up of their decision variables as follows:

where ck (vector form c) denotes the cost of traversing edge k, and dk (vector form d) represents the additional cost of passing through edge k which is controlled by the attacker with an armed force. Let z′kt be an intermediate decision variable, and z′kt = 1 if the edge k is under control of the attacker at stage t. Specifically, we suppose that all edges directing out of a force garrisoned node are under control, i.e.,

Denote by P = {attacker, rescuer} the set of players. Then, the simultaneous relief routing game at each stage can be expressed as a tuple Gt = (P,Zt, Yt, ut). The final cost of transporting at (vector form a) in this game is defined as the mixed Nash equilibrium of game Gt.

Additionally, if the rescuer selects an attacker-controlled edge to traverse at one stage, the transported relief resources wt will suffer a loss of being levied or robbed. The amount of loss at edge k depends on the levy rate q = (qk)k∈E ∈

(0, 1)|E| of armed forces the rescuer encountered. Denote by rt (vector form r) the left relief resources which can be successfully transported, we have

3.2 Multi-stage Offline Emergence Relief Planning

Based on results of game Gt at each stage, we construct a multi-stage offline emergence relief planning (MoffERP) by assuming that all data and parameters are known in advance. In this way, MoffERP is integrated as a linear programming.

Specifically, the rescuer has to make decisions about whether or not to meet the relief demand of a certain city at each stage. Denote by n the number of stages of MoffERP, and N = {1, 2 · · · , n} the set of stages. Let x = (xt)t∈N ∈ {0, 1}n represent the decision variables of the rescuer, and xt = 1 if she decides to meet the demand wt at stage t. To meet this demand, the rescuer has to pay a cost of at on transportation and can cover a certain amount of demand rt as a kind of revenue at this stage. Hence, as a long-term revenue seeker, the rescuer aims to maximize the total amount of demand satisfaction under the limitation on total amount of relief resources b1 and transportation budget b2.

Supposing that all online data rt and at are known in advance, we can formulate MoffERP to a binary integer linear programming as follows:

where x ∈ {0, 1}n , vectors r, w, a ∈ Rn+, and denote by b the vector [b1, b2]T . In this way, MoffERP can be solved using common binary integer linear programming techniques. Denote by ¯x∗ the optimal solution of P-MoffERP.

4 Online Multi-stage Relief Planning

In this section, we extend the MoffERP to a realistic online version (MonERP) where key parameters are revealed in an online manner. An online learning algorithm is then designed to solve it with theoretical analysis on average expected regret.

4.1 Online ProblemModeling

In the online version of problem, both players have to make irrevocable decisions without observing the future inputs. At each stage t, the parameter rt and at are revealed to the rescuer based on the Nash equilibrium results of the stage game Gt. Simultaneously, the rescuer needs to decide the value of xt in real time. Unlike the setting in MoffERP, rescuer only knows the history information Ht = {rj,wj, aj, xj}t-1 j=1 . Hence, the online decision strategy of rescuer can be presented as a function ϕ of the history and the observed parameters at the current stage t:

To design the function ϕ, we first analyze the distribution features of online parameters. It is assumed that the demand

(gt,wt, ft, ht) in game Gt are generated i.i.d. from an unknown distribution. As mentioned in Section 3, online parameters (rt, at) are generated in the process of each stagebased game Gt. Denote by N the Nash equilibrium mapping from the parameters (gt, wt, ft, ht) in game Gt to parameters rt and at, i.e.,

In Theorem 1, (rt, at) are proven to be i.i.d. sampled from unknown distribution P.

Theorem 1. The coefficient pair (rt, at) are generated i.i.d. from unknown distribution, if parameters (gt, wt, ft, ht) are generated i.i.d. from unknown distribution.

Proof. From the definition of i.i.d., we can prove that rt and at satisfy the independent condition first. As shown in Equation (7) and (10), the parameters gt, wt, ft, ht used to calculate rt are independent at different stages, so that rt satisfies the independent condition. Similarly, it can be proved that at is independent. Hence we have

As for proving (rt, at) are generated from identical distribution, both rt and at are computed in a fixed pattern at each stage and the parameters gt, wt, ft, ht are subject to identical distribution, which we could prove that (rt, at) are subject to identical distribution too. Hence we have

Therefore we conclude the proof.

4.2 Online Learning Approach

Before given the online learning algorithm to MonERP, we present the linear programming relaxation of P-MoffERP as follows:

Then, the dual problem of LP-MoffERP can be formulated as

where the dual decision variables are p ∈ Rn and s ∈ Rn . Denote by x∗ , p∗n , and s∗ the optimal solutions of problem LP-MoffERP and DP-MoffERP. From the complementary condition, we have

Algorithm 1 Online learning algorithm for MonERP

Input: n, online revealed coefficient pair (r,w, a)

Parameter: learning rate γt = 1 √n

Output: a sequence of online decisions x

• 1: Let e = bn
• 2: Initialize p1 = 0
• 3: for t = 1, 2, · · · , n do
• 4: Set
• 5: Compute

• 6: end for
• 7: return x = (xt)t∈N

and when rj = [wj aj] p∗n , the value of x∗j may be noninteger.

Note that parameters r, w and a are i.i.d. sampled from unknown distribution. Based on Equation (17), we can obtain an online algorithm using the theoretical results of online linear programming technique [Li et al., 2020] as shown in Algorithm 1. The step learning rate γt is set as 1 √n at each stage t.

To evaluate the performance of the online learning algorithm, we introduce the performance measure - regret- which is a common metric of online learning approach. Denote by R∗n = rTx∗ the optimal objective value of the online problem P-MonERP, and Rn = rTx the actual objective value under the online learning strategy x. The expected optimality gap between them is∆Pn = E[R∗n - Rn]. (18)

Denote by Ξ the family of distribution P, then the definition of regret is formally given as

Corollary 1. If the step learning rate γt = 1 √n for t ∈ N, then Algorithm 1 achieves O( 1 √n ) average regret of problem MonERP.

Proof. According to the state-of-the-art general theoretical results of online linear programming [Li et al., 2020], if the step learning rate is set as γt = 1 √n then the regret satisfies ∆Pn ≤ m(¯a + ¯ e)2√n. We then apply this result to MonERP, where m = 2 representing the rows number of [w a]. Hence, we have

where

It is clear that ¯a and ¯ e are both finite constants in each instance of problem MonERP. Therefore, Algorithm 1 achieves O( 1 √n ) average regret as required.

According to Corollary 1, when the number of stages n → ∞, we have the average regret ∆n n → 0, which theoretically illustrates the performance advantage of the proposed online learning algorithm.

5 Experimental Evaluation

In this section, we evaluate the proposed online learning approach for emergency relief planning under intentional attacks using a real case in the conflict area of DRC Congo. The convergence and near-optimality of the online learning algorithm are first analyzed under the real case scenario and data. Then, the influence of attacker's deployment budget on the humanitarian relief operations.

5.1 Test Case and Environment

A case study of MonERP is conducted on the base of statistical data of DRC Congo including road network data, Ebola outbreak data, and conflict statistics in Nord-Kivu and SudKivu province. The rescuer plans to pass through the conflict area in order to transport supplies to the city affected severely by the epidemic, while the rebel group as an attacker aims to gain payoff by controlling some routes.

The road network of Nord-Kivu and Sud-Kivu province is shown in Figure 1(a), which includes 810 vertices (i.e., cities and towns) and 2,188 arcs (i.e., major and other roads). The conflict data from 31 December 2018 to 5 January 2020 in the same area is shown in Figure 1(b), which is offered by the Armed Conflict Location & Event Data Project [ACLED, 2020]. The Ebola outbreak data in the same period reported by the World Health Organization is visualized as the map in Figure 1(c) [WHO, 2020]. Supposing that the emergency relief demand of a city is positively correlated with the number of Ebola cases outbreak in the city, we obtain the statistics on urban relief demand over time as shown in Figure 2. It is clear that the worst Ebola-affected areas such as Beni in Nord-Kivu have urgent and huge needs of humanitarian relief; however, the road network from non-infected areas such as Bukavu in Sud-Kivu province to these demand cities is in the control of rebel groups to a large extent.

Specifically, the traversing cost c is set as the length of the actual road between cities. The added cost of transporting d is assumed to be uniformly distributed on [1, ¯c], where ¯c denotes the average value of c. The movement cost ft is supposed to be uniformly distributed on [1, v¯c], where v represents the maximum cost coefficient. Denote by W = ∑nt=1 wt the total demand during this period, and C the total transporting cost of satisfying all demands over the period. In this case, the city Bukavu is set as the base of relief resources, and the demand cities include Beni, Butembo, Katwa, Kalunguta, Mabalako and Oicha.

The proposed models and algorithms are solved using the Gurobi 9.0.1 solvers, and tested on a Windows10 (64) computer with Intel Core-i7 CPU and 16.0GB RAM.

5.2 Results on Convergence and Optimality

The first experiment presents the performance of Algorithm 1 on convergence and optimality. We run 100 instances of MonERP on DRC Congo scenario with different d. Let the relief resources budget b1 = 0.5W, the transportation budget b2 = 0.4C, and the attacker's movement cost ft ∈ [1, 3¯c]. As shown in Figure 3, the results of average regret over stages illustrate that the expected optimality gap between the offline and online revenue converges to near zero as the number of stage n increase to +∞. These experimental results numerically validates Corollary 1.

In the second experiment (cf. Figure 4), we compare the time consumption T of obtaining the optimal offline and nearoptimal online solutions as the increase of stage number. Apparently, the proposed online learning algorithm is more timeefficient than the offline algorithm, which shows the advantage of this work tackling the far-sighted emergency relief planning under intentional attacks. Note that, the optimal offline results cannot be obtained by the rescuer since the data and parameters are revealed in an online manner.

5.3 Analysis of Impact Factors on Humanitarian Relief Planning

The third experiment focuses on the impact of relief resources and transportation budget on the amount of demand satisfaction as shown in Figure 5. We can observe a saturation critical boundary of their impacts. For instance, if we fix the ratio of relief resources budget at 50%, the increase of the transportation budget over 40% will not bring any growth on the amount of demand satisfaction.

The final experiment explores the impact of relief resources and transportation budget on the amount of robbed relief resources by the attacker as shown in Figure 6. It is clear that the increase of transportation budget has almost no impact on the amount of robbed relief resources by the attacker when the ratio of relief resources budget is below than 30%. However, when the relief resources budget is relatively sufficient (with a ratio more than 60% in this case), the increase of transportation budget first raises the amount of robbed relief resources to a peak value and then decreases it. This illustrates excessive rescue operations including inappropriate relief resources providing and transport capacity using in conflict areas may breed attackers.

6 Conclusion

To meet the realistic need of far-sighted emergency humanitarian relief planning in conflict areas where intentional attacks pose a serious risk on the security and efficiency of rescuing operations, we propose the problem of multi-stage online emergency relief planning and design a efficient online learning approach for the first time. Specifically, we first propose an offline multi-stage optimization problem of emergency relief planning under intentional attacks, in which all parameters in the game between the rescuer and attacker are supposed to be known or predictable. Then, an online version of this problem is introduced to meet the need of online and irrevocable decision making when those parameters are revealed in an online fashion. The modeling process is integrated with the stage-based zero-sum simultaneous game between the rescuer and attacker. To achieve a far-sighted emergency relief planning under attacks, we design an online learning approach which achieves a O( 1 √n ) average regret when those online revealed parameters are generated i.i.d. from an unknown distribution. Finally, extensive experiments on a real anti-Ebola relief planning case based on the data of Ebola outbreak and armed attacks in DRC Congo show the scalability and effectiveness of our approach. This work might inspire more efforts in the field of AI on realistic datadriven humanitarian operations research for the good of those citizens suffering from both disasters and conflicts.