Coordinating Human-UAV Teams in Disaster Response

1 Introduction

First Responders (FRs) face major challenges in planning search and rescue missions in the aftermath of major disasters. In such domains, FRs have to perform rescue tasks (e.g., extinguishing a fire or providing first aid) to minimize loss of life and costs (e.g., time or fuel costs). Thus, they have to plan their path to the tasks (as these may be distributed in space) and complete them, taking into account the status of the current tasks (e.g., health of victims or building fire) and the environment (e.g., if a fire or radioactive cloud is spreading). Uncertainty in the environment (e.g., fires spreading or riots erupting) or in the responders' abilities to complete tasks (e.g., some may be tired or get hurt) means that plans are likely to change continually to reflect the prevailing assessment of the situation. However, information about the tasks and the environment is often very limited [Fiedrich and Burghardt, 2007; Wu and Jennings, 2014]. Hence, it is crucial for the FRs to collect as much information as possible while performing their tasks.

To support the work of FRs, Unmanned Aerial Vehicles (UAVs) have been widely deployed for information gathering in disaster response [Adams and Friedland, 2011]. They are fast and can collect information with onboard sensors (e.g., photos with cameras). Crucially, they can be deployed in hazardous environments (e.g., due to fire or radioactive cloud) and thus help gather information without putting people in harm's way. To date, UAVs have not been well integrated with planning systems that explicitly model the uncertainty in the environment and suggests courses of actions both for FRs and UAVs [Adams and Friedland, 2011]. This is challenging because, on one hand, FRs need up-to-date information from UAVs about the disaster site in order to better plan their actions, while on the other hand, UAVs must predict where FRs may move to next so they can concentrate on these locations for information gathering. Otherwise, UAVs may fail to collect information critically required by FRs. It is therefore essential to develop novel solutions that coordinate humanUAV teams in disaster response.

Against this background, we develop a novel approach for such human-agent collectives [Jennings et al., 2014] in disaster response where a planner agent gathers information with the assistance of UAVs and plans actions on behalf of FRs. In more detail, we consider a scenario involving rescue tasks distributed in a physical space over which a radioactive cloud is spreading. Tasks need to be completed by the FRs before the area is completely covered by the cloud. As FRs will die from radiation exposure, they need to know the radioactivity levels at the task sites and along the paths to the tasks. Crucially, such information should be collected by UAVs before FRs decide their next actions. We model this problem as a Partially Observable Markov Decision Process (POMDP) given that the environment is uncertain and only partial information about the radioactive cloud is observable to the UAVs. Although a POMDP provides a nice and coherent mathematical model that optimizes both actions for the UAVs and the FR in a single framework, solving large POMDPs is usually computationally demanding. As a result, our problem is intractable for most existing methods. Therefore, we propose a novel algorithm that combines planning and sensing based on Monte-Carlo simulation and value of information to compute policies both for FRs and UAVs. By so doing, we closely couple online planning (for FRs) with active sensing (for UAVs) to achieve more effective rescue missions. Furthermore, our algorithm is anytime and scalable for large domains. We empirically evaluated our algorithm using a benchmark simulator for disaster response and show that our algorithm outperforms the leading POMDP solver (i.e., POMCP) in the benchmark domain with faster runtime and better solution quality.

2 RelatedWork

Previous approaches for planning in disaster response typically assume the current state is fully observable to the planner agent [Musliner et al., 2006; Wu et al., 2015a; Ramchurn et al., 2015c; 2015a]. However, this assumption is usually unrealistic for real-world applications. In early work for disaster response, POMDPs have been used to make token coordination decisions for a team of agents [Xu et al., 2005] but not for task planning and information gathering. Most recently, [Wu et al., 2015b] proposed to boost the performance for RoboCup Rescue simulation using POMDPs but this approach requires predefined macro-actions. There are related work using POMDPs for UAV based applications such as target search / detection / tracking [Geyer, 2008; Chanel et al., 2013; Ramchurn et al., 2015b; Bernardini et al., 2015], collision avoidance [Bai et al., 2012b] and path planning [Ragi and Chong, 2012]. In disaster response, POMDPs were considered as a useful model for search and rescue operations using UAVs [Waharte and Trigoni, 2010]. However, none of them integrate information gathering with task planning to guide both FRs and UAVs in disaster response.

In the past decades, many approaches have been proposed to solve POMDPs. Our work relates to the online planning literature where agents interleave planning with execution in each decision step [Silver and Veness, 2010; Wu et al., 2010; Somani et al., 2013] . Similar to our method, problem structures are often exploited to efficiently solve large POMDPs [Ong et al., 2010; Bai et al., 2012a]. However, it is worth noting that our goal in this paper is not to propose a better method for general POMDPs. Instead, we aim to introduce a subclass of POMDPs useful for common disaster response scenarios and propose a novel algorithm that is faster than the state-of-the-art to solve such problems. In what follows, we will present our scenario and model and discuss why this model is nontrivial and cannot be easily tackled by existing solvers.

3 Disaster Scenario

We draw upon previous work for the disaster scenario in which a satellite leaks radioactive particles after having crashed in a sub-urban area, causing damage to infrastructure and injuring civilians as a result [Ramchurn et al., 2015c]. These particles are gradually spreading over the area, threatening to contaminate food reserves and people. Hence, emergency services are deployed to evacuate the casualties and key assets before they are engulfed by the radioactive cloud.

Let G denote a grid overlaid on top of the disaster space, and assume the satellite debris, casualties, assets, and actors are located at various coordinates (x↪y) 2 G in this grid. The radioactive cloud induces a radioactivity level l 2 [0↪ lmax] at every point that it covers. Since an FR in the disaster space may receive radiation doses that may, at worst, be lifethreatening, we assign her a health level h 2 [0↪hmax] that decreases based on the radiation dose that she received from the space. Given the invisibility of radiation, the information about the radiation levels has to be collected by sensors placed in the disaster space. As the radioactive cloud are also likely to shift across the disaster space due to wind direction and speed, UAVs are deployed, equipped with geiger counters and other sensors in order to loiter and monitor the state of the cloud. Note that the information collected by UAVs is uncertain due to the poor positioning of the sensors and the variations in wind speed and direction.

In our settings, rescue tasks are performed by an FR working in the disaster space, guided by a planner agent. While FRs execute tasks, the agent collects information about the environment using UAVs, generates plans and communicates its instructions directly to the FR. To capture the uncertainty (e.g., the spread of the radioactive cloud) and partial observability (UAVs can only collect the information near their current location) of the domain, we model this problem as a POMDP which we present in the following section.

4 The POMDPModel

We model the aforementioned disaster response problem 1 using Partially Observable Markov Decision Process (POMDP) defined as tuple M = hS↪A↪P↪R↪W↪O↪Ti, where:

• ÷ S = SFR⇥SRC ⇥SUAV is the state space where: SFR := ¶(x↪y)↪h♣(x↪y) 2 G↪h 2 [0↪hmax]♦ are the variables for the FR with her coordinates (x↪y) in the grid G and her health level h; SRC := ¶lx↪y♣lx↪y 2 [0↪ lmax]↪ (x↪ y) 2 G♦ are the variables for the radioactive cloud with the radioactive level lx↪y for every cell (x↪y) in G; and SUAV := ¶(x↪ y)i♣(x↪ y)i 2 G↪ i 2 1▷▷n♦ are the variables for n UAVs with the (x↪y)i coordinate for UAV i.
• ÷ A = AFR ⇥AUAV is the action space where: AFR and AUAV are the action variables for the FR and the UAVs respectively to move in the grid G.
• ÷ P(s0 ♣s↪a) = P(s0f r ♣s f r↪src↪af r)P(s0rc♣src)P(s0uav♣suav↪auav) is the state transition function where: P(s0f r ♣s f r↪ src↪ a f r) is the transition function for the FR as her next state s0f r 2 SFR depends on her current state s f r 2 SFR, the current state of the radioactive cloud src 2 SRC, and the action taken by her af r 2 AFR; P(s0rc♣src) is the transition function for the radioactive cloud as the next state s0rc 2 SRC only depends on the current state src 2 SRC, not the actions of the FR and the UAVs; and P(s0uav♣suav↪auav) is the transition function for the UAVs as their next state s0uav 2 SUAV depends on their current state suav 2 SUAV and their actions auav 2 AUAV .
• ÷ R(s↪a) = R(s f r↪af r)+R(suav↪auav) is the reward function where: R(s f r↪a f r) is the reward function for the FR and R(suav↪auav) is the reward function for the UAVs.
• ÷ W := ¶li♣li 2 [0↪ lmax]↪ i 2 1▷▷n♦ is the observation space where li is the sensor reading of the radioactive level recorded by UAV i at its current location.
• ÷ O(o♣a↪s0 ) = O(o♣s0uav↪s0rc) is the observation function modeling the probability of the UAVs observing o 2 W (i.e., the sensor reading) given that the UAVs' next state is s0uav and the next state of radioactive cloud is s0rc.

1 Our model generalizes to other disaster scenarios with the radioactive cloud being replaced by other uncertain event (e.g., fire).

• ÷ T is the horizon, i.e., the deadline of the tasks.

We assume that the FR and UAVs know their current locations using GPS and the FR can directly report her health level when doing the tasks. Hence the states of the FR and UAVs s f r↪suav are fully observable 2 to the planner agent. However, the state of the radioactive cloud src is hidden to the agent and therefore UAVs are deployed to collect information about it. In our setting, each UAV can record the reading of the radioactive level at its current location and hence the state of the radioactive cloud is partially observable to the planner agent.

At each time step, as shown in Figure 1, the planner agent first selects an action a f r for the FR and an action auav for the UAVs. As received from the agent, the actions are executed by the FR and the UAVs. This results a state transition in the world and an observation o about the state of the radioactive cloud src is received by the UAVs. After that, the UAVs send back their current state and observation suav↪o to the agent and the FR also reports her current state s f r. Then, the agent proceeds to the next time step and the process repeats until the horizon T is reached. Thus, the goal is to find actions that ensure that UAVs gather as much information as possible to maximize the number of tasks that the FR is able to complete without being harmed by the cloud.

Given the POMDP, we must solve it and compute a policy that maps belief states (i.e., distributions over states) to actions, i.e., p : D(S)!A. In POMDPs, the quality of a policy p is evaluated based on the value function V p (·). The objective of solving a POMDP is to find the optimal policy p ⇤ in the policy space that maximizes the expected value given the initial belief state b 0 : p ⇤ = argmaxp2PV p (b 0 ).

Although many techniques exist for solving POMDPs, there are several challenges inherent in our problem that make it nontrivial to be solved by them:

1. The state space of our problem is very large. Suppose that the size of grid G is ♣G♣, the number of health levels is Nh and the number of radioactive levels is Nl . The size of the overall state space is O(♣G♣Nh · ♣G♣n ·N♣G♣ l ). Due to the huge state space of our problem, it is computationally intractable for most existing POMDP solvers. This is also known as "the curse of dimensionality".
2. The action and observation spaces of our problem are also very large. Both grow exponentially with the number of UAVs. This makes existing approximate POMDP algorithms inefficient because the policy space becomes huge given large number of actions and observations. This is also known as "the curse of history" in the POMDP literature [Kaelbling et al., 1998].

2 Information about the FR and UAVs is not the focus of the sensing tasks in this paper but will be considered in future work.

1. The transition function cannot be represented explicitly with probability values. Notice that the spreading of the radioactive cloud involves a very complex physical process. Therefore, given the current state of the radioactive cloud src and a next state s0rc, it is very difficult to compute the transition probability P(s0rc♣src) especially when the state space of the radioactive cloud is huge. Fortunately, we can stochastically generate a next state s0rc given src based on some physical rules. Thus, approaches that require the use of transition probabilities cannot be applied to our problem.

In the next section, we present our planning algorithm for our POMDP formulation of the disaster response problem.

5 Online Planning Algorithm

To address the aforementioned challenges, we adopt an online planning approach so that we only need to compute the best action for the current belief state at each time step, instead of the entire belief space. The key observation we make is that the information gathering and task execution are two processes in our problem, where the former one is performed by the UAVs and the later one is accomplished by the FR. Based on this, we divide the whole algorithm into two procedures, one for task planning and the other for information gathering. However, these two procedures cannot be executed completely separately because the FR needs the information about the radioactive cloud in order to effectively plan her action, while the UAVs must know which tasks will be taken by the FR to actively collect information about those tasks.

To this end, we propose the OPAS algorithm - Online Planning with Active Sensing. As shown in Figure 2, in each time step, the FR computes a policy and specifics her action and the UAVs use this policy to update their sensing action. Notice that the UAVs' actions are dependent on what policy is chosen for the FR. In turn, for the FR, she can update and enhance the policy she computes based on information reported by UAVs as they fly over the areas chosen. Here, the key procedures are: 1) How to compute the FR's policy; 2) How to choose the best sensing action for the UAVs; 3) How to update the belief state of the radioactive cloud given the observation from the UAVs. In the following sections, we will describe these procedures in detail.

5.1 Simulation-Based Task Planning

To compute the policy for the FR, we first get her current state, which is fully observable by the agent. Starting from

Algorithm 1: Simulation-Based Task Planning

Input: The belief state of radioactive cloud brc(·) 1 s⇤f r the current state of the FR, t the current time step 2 repeat 3 b t rc brc↪s f r s⇤f r 4 for t t to T do 5 foreach a f r 2 AFR do 6 # Compute the Q value 7 Q(s f r↪b t rc↪af r) R(s f r↪af r)+ 8 Âs0f r Pr(s0f r ♣s f r ↪ b t rc↪ a f r )V (s0f r ↪ b t+1 rc ) 9 a best f r argmaxa f r Q(s f r ↪ b t rc↪ a f r ) 10 # Update the value function 11 V(s f r↪b t rc) Q(s f r↪b t rc↪a best f r ) 12 if s f r: tasks are completed or FR is dead then 13 Terminate the simulation 14 b t+1 rc update the belief state based on b t rc 15 s f r ⇠ P(·♣s f r ↪ src↪ a best f r ) 16 until it is timeout. 17 # Choose the best action for the FR 18 return a⇤f r argmaxaf r Q(s⇤f r ↪brc↪af r)

the FR's current state, several simulations are run for her during planning. Specifically, for each possible action of the FR, we compute the Q-values. After that, the best action for the FR is selected and the value function is updated. This process advances to the next time step with the new states drawing from the transition model until the planning horizon is reached or the process is terminated. We repeat the simulation multiple times until it runs out of time for planning. Finally, the best action for the FR is computed based on the Q-values. The main process is outlined in Algorithm 1. Indeed, this algorithm is analogy to RTDP-Bel [Geffner and Bonet, 1998] for POMDPs, which converges to the optimal policy given sufficient number of simulations. Note that the state of the radioactive cloud is independent of the actions of the FR and the UAVs. Hence the belief state is updated based on a Markov chain for the spreading process. By so doing, the FR makes her decision based on the knowledge about the radioactive cloud that is current available.

One remaining question is how to efficiently compute the Q-values in the algorithm. Typically, this is done using the Bellman equation as:

However, this equation requires to enumerate all possible states of the FR and the radioactive cloud. Given that our state space is very large, the computation of the exact Q-values will be intractable. To address this, we approximate the Q-values with Monte-Carlo simulations. The basic idea is to repeatedly draw K state samples based on the transition model given the current states and the action. Then, the expected value is es-

Input: The belief state brc(·), the value function V(s f r↪ ·) 1 s f r↪suav the current states of the FR and the UAVs 2 foreach auav do 3 Q(brc↪suav↪auav) 0 4 for k = 1 to K do 5 # Simulate the action execution 6 src ⇠ brc(·)↪ s0rc ⇠ P(·♣src) 7 s0uav ⇠ P(·♣suav↪ auav)↪ o ⇠ O(·♣s0uav↪ s0rc) 8 b0rc update the belief state brc with o 9 # Compute the value of information 10 Vin f o kV(s f r↪b0rc)-V(s f r↪brc)k 11 Q(brc↪suav↪auav) Q(brc↪suav↪auav)+Vin f o 12 Q(brc↪suav↪auav) R(suav↪auav)+Q(brc↪suav↪auav)◁K 13 # Choose the best action for the UAVs 14 return a⇤uav argmaxauav Q(brc↪suav↪auav)

timated by the mean value of the samples as:

where s k f r ↪s k rc are the k-th sample drawn from the transition function: (s k f r ↪ s k rc) ⇠ P(·↪ ·♣s f r ↪ src↪ a f r) where src ⇠ brc(·).

5.2 Information-Based Active Sensing

We choose the sensing action for the UAVs based on the Value of Information (VoI) [Howard, 1966] - a well-known concept for information theory. Specifically, given that the FR's state is s f r, we define the VoI as the difference in value for the belief states before and after some sensing action:

where brc is the current belief state about the radioactive cloud and b0rc is the belief state after the UAVs taking some sensing action. Intuitively, if the likelihood of some states of the radioactive cloud changes significantly and the expected values of the FR regrading of these states are large, the sensing action of the UAVs is considerably informative. If the sensing action makes no difference to the FR's expected value, then this action is not informative because the information collected by the UAVs is not useful for the FR's decision.

Given an action for the UAVs, there will be many possible observations obtained by them and each observation corresponds to a new belief state. Therefore, the VoI of the UAVs taking action auav in state suav is computed as:

where b o rc is the new belief state given brc↪auav↪o and

Proposition 1. Given the optimal value function for the FR, the sensing action that maximizes the VoI is the optimal action for the UAVs in the POMDP.

Algorithm 3: Alternative Maximization for Sensing

1 a⇤uav a random action in AUAV , Q⇤uav -· 2 repeat 3 e 0, q sample a set of waypoints based on Q 4 foreach UAV i 2 1▷▷n in a random order do 5 auav a⇤uav # The current best action 6 foreach (x↪ y) 2 q and (x↪ y) is reachable by UAV i do 7 auav[i] set the target of UAV i as (x↪y) 8 Quav compute the expected value of auav 9 if Quav >Q⇤uav then 10 e e +(Quav-Q⇤uav) # Residual 11 a⇤uav auav↪Q⇤uav Quav 12 until e is sufficiently small or it is timeout. 13 return a⇤uav # The best action for the UAVs

The proof is omitted due to limit of space but can be done by showing that the sensing action that maximizes the VoI is also the action that maximizes the Bellman equation. Thus, it is the optimal action for the UAVs in the POMDP. Intuitively, the most informative action is also the optimal one for the UAVs because the their only task is to sense the environment and gather the information that is most useful for the FR.

In order to compute the VoI of each sensing action and select the most informative one, we propose an active sensing algorithm shown in Algorithm 2. Firstly, we read the current state of the FR and the UAVs. Then, we estimate the VoI for each sensing action. As aforementioned, the state space about the radioactive cloud is very large. Therefore, we estimate the expected value using simulations. Specifically, we draw a sample of the state from the current belief state and run the simulation with the sensing action chosen. After the simulation, an observation given the states and the sensing action is obtained. Then, we use the observation to update the belief state and compute the new one. Given the two belief states, the VoI is computed using Equation 3. We average the VoI over several simulation samples and add it with the immediate reward of the sensing action:

where b o k rc is the k-th belief state given o k drawn from the probabilities: o k ⇠ Pr(·♣brc↪suav↪auav). At this point, we obtain an approximate value of the sensing action and accordingly the sensing action with the maximum value is selected.

However, it is costly to consider the value of every sensing action because the action space for the UAVs is very large. To address this, we propose a local search algorithm to find the best sensing action using alternative maximization. The main procedure is outlined in Algorithm 3. Starting with a random sensing action, we sample a set of waypoints along the possible path of the FR as shown in Figure 3. Then, for each UAV in a random order, we generate a sensing action by assigning its location to each waypoint. After that, we compute the expected value of this sensing action and choose it as the best action if it has larger expected value than the previous one. To sample a set of waypoints, we simulate the movement of the FR by selecting the best action based on the Q-value computed by Algorithm 1 and collect the waypoints of the FR in the simulation. We use the same method to compute the expected value for each sensing action as in Algorithm 2. We next consider how to represent the beliefs of the planner.

5.3 Particle-Based Belief Updating

Now, a typical method to represent the belief state is to define a probability distribution over all possible states and update it according to the Bayesian rule. Unfortunately, the state space of the radioactive cloud is very large. Therefore, we use a set of weighted state particles to represent the belief state: brc ⇡ {(s 1 rc↪w 1 )↪ · · · ↪(s n rc↪w n ) s.t. Â n k=1 w k = 1 where the weights sum to one. Notice that the particle-based belief representation has been widely used in many state-ofthe-art POMDP solvers to tackle problems with large state space [Thrun, 1999; Silver and Veness, 2010]. When sampling a state from the belief state, it selects a state particle from the particle set with the probability of its weight.

To update the belief state given an sensing action and an observation from the UAVs, we first draw a state of the radioactive cloud from the current belief state. Next, we simulate the process and obtain the next state of the radioactive cloud and the UAVs. Then, we add the new state of the radioactive cloud to the new particle set representing the new belief state with the weight based on the observation function conditioning on the observation. When a sufficient number of new particles have been collected, we normalize the weights of the new particles and return the set as the new belief state.

6 Empirical Evaluation

To evaluate our algorithm, we extended an existing benchmark simulator used to develop prototypes for real-world studies [Ramchurn et al., 2015c]. Specifically, the disaster space is overlaid by a 55⇥50 grid with obstacles (e.g., buildings, walls, water pools, etc.) and the radioactive clouds. We consider a single FR and a group of UAVs for the response tasks, where the FR must move to the task locations and complete the tasks before the resources are engulfed by the radioactive cloud. Here, a system state consists of: the FR's (x↪y)-coordinate in the grid and her health level, the radioactive level for each cell of the grid, and the UAVs' coordinates. For the actions, the FR can move either one of the 8 neighboring cells (unless the cell is occupied by an obstacle) or just stay in her current cell and each UAV can move to any cell in the 10⇥10 sub-grid centered with its current location. For the transition function and the reward function, we adopt the same settings as in [Ramchurn et al., 2015c]. An observation is defined as a set of sensory readings from the UAVs about the radioactive levels at their current coordinates. To simulate the noisy sensors, random Gaussian noises are added to the sensory readings.

Due to the large state and action space, there are few existing algorithms that can solve our problem. Among them, POMCP [Silver and Veness, 2010] is currently the leading solver for large POMDPs. Particularly, POMCP only requires a black-box simulator, which fits our domains. Therefore, we compared our approach with POMCP and used the same problem instances generated by the simulator. To simplify the tests, we fixed the locations of the radioactive sources but randomized the start location of the FR and the task locations to generate different problem instances. We used the same random seeds so the problem instances for each algorithm were identical. Due to the stochastic nature of our problem, we ran each algorithm 1000 times until the results are statistically meaningful and recorded the mean and standard deviation of the runtime per step and the accumulated rewards obtained from the tests. A machine with a 3.50GHz Intel Core i7 CPU and 8GB RAM was used to produce the results.

Figure 4 summarizes our experimental results. As aforementioned, both OPAS and POMCP are online planning algorithms. Therefore, they must be able to complete the planning process and compute the action with limited amount of time in each decision step to vary the number of simulations allowed. In Figure 4(a), we show the performance of OPAS and POMCP given different time per decision step (x-axis). These results were obtained by varying the number of simulations allowed in each algorithm. The performance is evaluated based on the mean of the values (y-axis) in multiple runs. As we can see from the figure, OPAS converged much faster than POMCP. Moreover, it achieved much larger value than POMCP given the same amount of time per step. In our tests, we observed that POMCP got stuck in a local optima with the value of about 50. Note that the runtime of both OPAS and POMCP grows linearly with the number of simulations.

For reasons of presentation, the standard deviations for POMCP are omitted in Figure 4(a) because they are large. This is not surprising because the FR guided by POMCP was killed by the radioactive cloud in the runs of some challenging problem instances. In such cases, the runs terminated with a penalty of -100. In contrast, the performance of OPAS was very stable (with the standard deviation about 6) even for those challenging problem instances. Note that we tested both methods with the same set of problem instances. We observed that the FR guided by OPAS kept alive across all runs in the experiments, which is crucial for disaster response tasks. As in Algorithm 1, we use a conservative strategy where the FR's policy is computed with the information currently available.

Figures 4(b) and 4(c) illustrate the performance of OPAS and POMCP in runtime and value respectively with different numbers of UAVs. As shown in Figure 4(b), the runtime of both algorithms grows linearly with the number of UAVs and OPAS ran faster than POMCP with the same number of UAVs. This confirms the scalability of OPAS for problems with many UAVs. It is interesting to see from Figure 4(c) that the values of both algorithms decreased with more UAVs. This indicates that there may be redundancy in the information collected by the UAVs. With more UAVs, there are more costs to run them but the benefit in the sense of information value is limited. Generally, the best number of UAVs depends on the specific problem at hand. In the problem instances we chose, 2 UAVs seem sufficient for collecting the information about the radioactive cloud. It is worth noting that, with different numbers of UAVs, OPAS produced better values than POMCP though they shared similar trend. With more UAVs, the standard deviation of OPAS grows because there is more diversity over the runs in the choice of the UAVs' actions with larger action space. Again, the standard deviations of POMCP were omitted for reasons of presentation.

7 Conclusion

In this paper, we proposed a novel approach that integrated online planning with action sensing for guiding an FR, assisted by UAVs in disaster response. In more detail, we modeled the problem as a POMDP and proposed a novel algorithm to efficiently solve this model. In particular, we presented a novel model based on POMDPs for planning and sensing in disaster response capturing both uncertainty and partial observability of that domain. To solve the model, we proposed an online planning algorithm that is anytime and scales well based on Monte-Carlo simulation and the concept of value of information. Results from our experiments confirmed the scalability and advantage of our algorithm in the benchmark domain comparing to the leading POMDP solver (i.e., POMCP). Future work will look at conducting fieldtrials of our approach using human FRs and physical UAVs.

Acknowledgments

We thank all the anonymous reviewers for their constructive comments. This work is supported in part by the Fundamental Research Funds for the Central Universities (No. WK0110000045) and the Youth Innovation Promotion Association, CAS (No. CX0110000012).