Nonmyopic Adaptive Informative Path Planning for Multiple Robots

1 Introduction

Many robotic path planning applications involve uncertain environments with complex dynamics. For example, search and rescue in a disaster struck environment involves finding and rescuing the survivors with unknown locations using noisy sensors. With limited number of resource-constrained William J. Kaiser UCLA

(limited time or battery capacity) robots available for monitoring such environments, it is essential to perform path planning to visit a subset of locations that are most "informative".

Informative path planning - selecting the best locations to observe subject to given sensing constraints, in such uncertain environments necessitates a trade off between exploration (gathering information about the environment) and exploitation (using the current belief about the state of the environment most effectively). We distinguish two different classes of algorithms: Nonadaptive (offline) algorithms, that plan and commit to the paths before any observations are made, and adaptive (online) algorithms, that update and replan as new information is collected. Most of the previous work has either dealt with approximation algorithms for the nonadaptive setting (that also is a challenging, NP-hard optimization problem) [Singh et al., 2007; Meliou et al., 2007; Hollinger and Singh, 2008] or proposed (often myopic, i.e., limited look-ahead) heuristics for the adaptive setting that do not have any approximation guarantees [Stachniss et al., 2005]. Partially Observable Markov Decision Processes (POMDPs) have been used to perform adaptive path planning in complex environments [Roy et al., 2005]. However, such algorithms are only capable of near-optimally solving small instances of the problem.

In this paper we first propose a novel near-optimal algorithm for nonadaptive informative path planning which empirically outperforms existing nonadaptive algorithms. We then extend this nonadaptive algorithm to the adaptive setting. Our NAIVE- Nonmyopic, Adaptive, InformatiVE path planning algorithm, performs sequential model update and uses the nonadaptive algorithm as subroutine for replanning. We explicitly analyze the "adaptivity gap" (the potential performance gain of adaptive vs. nonadaptive algorithms), which allows us to give strong theoretical bounds on the suboptimality of our NAIVE algorithm. The previous state of the art in nonadaptive informative path planning is based on optimization of submodular set functions [Singh et al., 2007], which model a diminishing returns property that naturally arises in many information gathering tasks [Krause et al., 2006, 2008]. Our analysis is based on a novel extension of submodular set functions to adaptive sensing policies. For problems with a large adaptivity gap, we present an algorithm based on a multi-criterion utility function that seeks to simultaneously optimize exploitation (e.g., to rescue a large number of survivors) and exploration (e.g., to localize the survivors).

We also provide a generic sequential-allocation algorithm to extend any adaptive single robot path planning algorithm to multi robot optimization while (almost) preserving the approximation guarantee of single robot path planning algorithm. Specifically, the primary contributions of our work are:

• A new algorithm - PSPIELOR for near-optimal nonadaptive informative path planning for a single robot.
• A general algorithm - NAIVE- for single robot adaptive informative planning. By exploiting the fact that we can bound the "adaptivity gap" for interesting real world problems (demonstrated here for a search and rescue application and a scientific monitoring task), we can prove that the adaptive solutions obtained using NAIVE, using any near-optimal nonadaptive algorithm (such as PSPIELOR) as a subroutine, are provable competitive with the NP-hard optimal adaptive solution.
• A sequential-allocation algorithm for efficiently and near-optimally extending any algorithm for planning informative adaptive policies for a single robot (such as NAIVE or a POMDP solver) to the multi robot setting.
• The extensive evaluation of our proposed algorithms for two case studies, including a search and rescue problem and scientific monitoring using a real robotic system.

2 Problem statement

We are given a graph G = (V, E) with a discrete set (of locations) V connected by edges E, wherein the set V is simultaneously traversed by k mobile robots. To model the information gathering, we associate a random variable Xs with each location s ∈ V. The random vector XV = (X1, . . . , Xn) describes the (unobserved) state of the world. In our search and rescue example, XV models the distribution of survivors in a disaster struck environment. We assume that we have a prior joint distribution P(XV) that models the dependencies among the random variables across space. We discuss details about these models for both our search and rescue and scientific monitoring examples in Section 6.

When a robot i visits a location s ∈ V, it partially observes the state XV by making a noisy observation Ys = ys, according to some distribution P(Ys | XV). In the search and rescue example, the random variables Ys model possible false positives and negatives of the robots' noisy sensors (c.f., Section 6). In the adaptive setting, after making the observations, the robots then update the belief about the state of world, P(XV = xV | Ys = ys) and use the updated belief to choose the next observation location adjacent to s.

To quantify "informativeness" we define a function u(A, xV) that measures the utility of observing a set A ⊆ V of locations if the world is in state xV. The robots choose their movement to cooperatively maximize this utility. In the adaptive setting, the robots can select a different sequence π(xV) = (s1, . . . , sB) of locations for each possible belief about the state of the world. Note that, depending on the context, we use the notation π(xV) to refer both to the sequence (s1, . . . , sB) and the set {s1, . . . , sB} of locations visited. We call the location selection function π a policy. We only restrict policies to necessarily be sequential (i.e., a location st in a sequence (s1, . . . , sB) is chosen only based on observations yt′ where t′ < t), and respect the graph G (i.e., there must exist an edge between each st and st+1 in E).

For each possible policy π we compute its expected utility as U(π) = ∫ P(xV)u(π(xV), xV)dxV. In the search and rescue domain, U(π) denotes the expected number of survivors rescued when observations are made as per the policy π. Our goal, then, is to find a policy π that maximizes U(π). We call a policy nonadaptive if it selects the same sequence of locations independently of the state of the world.

For each sequence A of locations we also associate a cost C(A) that corresponds to the total number of time steps required to visit all locations in A. The total cost of a policy π is then given as C(π) = ∫ P(xV)C(π(xV))dxV. We also associate a (possibly different) starting (s(i) 1 ) and finishing location (s(i) B ) with each robot. We call Πi the set of all feasible policies starting at s(i) 1 and finishing at s(i) B , with C(π) upper bounded by some given budget B. Based on this notation, our goal is to solve the following optimization problem:

where π1∪. . .∪πk is the set of locations selected by all robots.

3 Structure in informative path planning

As shown by Krause et al. [2006], many problems of nonadaptively choosing locations satisfy the following intuitive diminishing returns property: Adding a new location s ∈ V helps more if we have selected only a few locations so far, than if we have already selected many locations. This intuition is formalized by the concept of submodular set functions: A function F : 2V → R is called submodular [Nemhauser et al., 1978] if whenever A ⊆ B ⊆ V and s ∈ V \B it holds that F(A∪{s})-F(A) ≥ F(B∪{s})-F(B).

In this paper, we generalize this notion to policies. For two policies π and π′ , we say π ⊆ π′ if π(xV) ⊆ π′ (xV) ∀xV, i.e., in any state of the world, π selects a subset of observation locations selected by π′ . We say |π| ≤ m if |π(xV)| ≤ m ∀xV ∈ XV. Similarly, we generalize other set operations π1 ∪ π2, π1 ∩ π2, π1 \ π2 etc. A function U that maps policies to real numbers is called submodular if for all policies π1, π2, π′ s.t. π1 ⊆ π2, it holds that U(π1 ∪ π′ ) -U(π1) ≥ U(π2 ∪ π′ ) -U(π2), i.e., adding π′ to π1 will lead to bigger improvement in expected utility than adding π′ to π2. Another intuitive property is that the utility function U is monotonic, i.e., as more locations are selected, the expected utility never decreases. Formally, a utility function over policies is called monotonic if U(π1) ≤ U(π2) whenever π1 ⊆ π2 ⊆ V.

In addition to submodularity and monotonicity, several spatial information gathering problems, including search and rescue and environmental monitoring, exhibit another important locality property: Observation locations which are very far apart are approximately independent. This implies that if we observe a subset of locations A1 in one region, and a set A2 in another region (far apart), then U(A1∪A2) ≈ U(A1)+ U(A2). This property can be abstracted by assuming that there are constants r > 0 and 0 < γ ≤ 1, such that for any sets A1 and A2 which are at least distance r apart, U(A1 ∪ A2) ≥ U(A1) + γU(A2). Such set functions U are called

(r, γ)-local [Krause et al., 2006]. In this paper, we generalize this notion to policies: We say U is (r, γ)-local if for any policies π1 and π2, s.t. the sets π1(xV) and π2(xV) are distance r apart in any state xV, then U(π1 ∪π2) ≥ U(π1)+γU(π2).

One way to construct (r, γ)-local, submodular, monotonic functions on policies is given by the following proposition:

Proposition 1. If u(A, xV) is (r, γ)-local, submodular and monotonic in A ∀ xV, then U(π) = ∫ P(xV)u(π(xV), xV) is (r, γ)-local, submodular and monotonic.

All proofs and additional experiments can be found in the longer version of this paper [Singh et al., 2009]. Below, we will only assume that the expected utility function U is (r, γ)-local, submodular and monotonic.

4 Single robot informative path planning

In this section, we develop NAIVE, a Nonmyopic Adaptive InformatiVE path planning algorithm for a single robot (k = 1). We extend the algorithm to multiple robots in Section 5. Our algorithm is based on the following approach. We start with a prior belief P(XV) about the state of the world. Based on this belief, we nonmyopically plan a nonadaptive path A maximizing the expected utility U(A) as per our current belief. The robot then moves to the first location s on the selected path, makes the observation Ys = ys, updates its belief P(XV | ys), and replans according to its posterior belief. In Section 4.1, we present the nonadaptive algorithm used as a subroutine for the adaptive procedure. In Section 4.2 we provide details on the adaptive procedure, and analyze its performance.

4.1 Nonadaptive informative path planning

We now present an algorithm for planning a nonadaptive policy πA where the sequence of observation locations A = (s1, . . . , sB) is selected by the policy πA independently of the state xV. It can be seen that if U is a (r, γ)-local submodular function on policies, then F(A) = U(πA) is a (r, γ)-local submodular set function. Hence, in the nonadaptive setting we need to find a set A∗ satisfying

where C(A) is the cost of the shortest path connecting the selected locations A, starting with s1 and finishing at sB.

This optimization problem, seeking to maximize a submodular utility function with an upper bound on the total cost, is called submodular orienteering problem (introduced by Chekuri and Pal [2005], who developed a theoretical, superpolynomial algorithm). In this paper, we propose a new, efficient algorithm, pSPIEL-Orienteering (PSPIELOR), for solving the submodular orienteering problem while exploiting the local-submodular property of the utility function. The complete algorithm is illustrated in Figure 1.

1. The algorithm takes as input a starting location (s1), a finishing location (sB), an upper bound on the path cost B and a local-submodular set function F, conditioned on previous observations. We, first, randomly partition the locations V \ {s1 ∪ sB} into small clusters of diameter αr (where α is a parameter). Subsequently,
2. nodes close to the "boundary" of their clusters are stripped away, such that the remaining clusters are "well-separated" (have distance ≥ r). (It was proved by Krause et al. [2006] that not too many nodes get stripped away). Due to the locality property of the utility function U, each cluster is approximately independent. This well-separated clustering is called padded decomposition [Gupta et al., 2003], and is illustrated in Figure 1a.
3. Within the locations Ci of each cluster i, we then use a greedy algorithm to get an ordering gi,1, gi,2, . . . gi,ni on the ni nodes (c.f., Figure 1b). Hereby, gi,ℓ+1 = argmaxv∈Ci\Gi,ℓ F({v} ∪ Gi,ℓ}), where Gi,ℓ = {s1, sB, gi,1, . . . , gi,ℓ}. These nodes are then connected to form a chain for the cluster using cost for the edge (gi,j, gi,j+1) to be the minimum cost required to reach the node j + 1 from the first j nodes already selected in the chain. This minimum cost is calculated by adding the cost of edges (as per E) in the shortest path traversed to reach the node j + 1 from the first j nodes. With each node gi,j, we associate an additive reward ri,j = F(Gi,j) - F(Gi,j-1). The submodularity of F ensures that the first k nodes in this chain are almost as informative as the best subset of k nodes in the cluster [Guestrin et al., 2005].
4. Next, we create a "modular approximation graph" G′ from G by taking all these chains, and creating a fully connected graph on s1, sB, g1,1, g2,1, . . . , gm,1, the starting and finishing nodes and all the first nodes of each chain. The edge costs are represented by the shortest path distances between the corresponding nodes and calculated by adding the cost of the edges (as per E) traversed in this shortest path (c.f., Figure 1c).
5. Constrained by budget B, we then use an existing modular orienteering algorithm [Chekuri et al., 2008] on G′ with s1 and sB as starting and finishing node respectively (c.f., Figure 1d). Note that modular orienteering is a special case of submodular orienteering where all observations are fully independent, i.e., utility function u(·, xV) is additive.
6. The selected path in G′ is then expanded in terms of the corresponding shortest path in G (c.f., Figure 1e). Since each edge in G′ may represent multiple edges spanning through locations in G, the corresponding expanded path in G will now (possibly) have additional nodes from G that were absent in G′ .
7. Finally, tour-opt heuristics by Lin [1965] are applied to smooth out and shorten the path over the selected locations (c.f., Figure 1f).

The PSPIELOR algorithm and its analysis is based on the PSPIEL algorithm, originally proposed for the purpose of communication-efficient informative sensor placement, by Krause et al. [2006]. However, it implements necessary modifications for path planning such as handling a starting (s1) and finishing (sB) location and applying the modular orienteering algorithm followed by path expansion and smoothening in steps 4-6. We prove the following result about PSPIELOR:

Proposition 2. PSPIELOR finds a path A with cost O(r dim(V,E)) × B and expected F(A) ≥ Ω(γ) × F(A∗).

where A∗ is the optimal set chosen for this problem and dim(V,E) is the doubling dimension, which is constant for many graphs and is O(logn) for arbitrary graphs [Gupta et al., 2003]. Running time of PSPIELOR is polynomial in number of observation locations. In Section 6, we empirically show that PSPIELOR outperforms state of the art algorithms for submodular orienteering for the search and rescue problem.

4.2 Adaptive informative path planning

We now describe NAIVE- our Nonmyopic Adaptive InformatiVE path planning algorithm, based on an iterative Bayesian updating and replanning approach. The algorithm is initialized with specified starting (s1) and ending locations (sB) and an upper bound of B timesteps on the path cost. In first timestep, NAIVE applies a nonadaptive algorithm, such as PSPIELOR, using the utility function F(A | ys) = ∫ P(xV | ys)u(A, xV)dxV representing the "conditional utility" conditioned on observation Ys = ys made at s1. The algorithm then moves the robot to the next location on the selected nonadaptive path and iteratively use PSPIELOR with updated starting location s1 and budget B - 1, while keeping the finishing location fixed at sB, in the subsequent timesteps. Algorithm 1 outlines this non-myopic, adaptive algorithm.

Let πNAIVE be the location selection policy induced by the NAIVE algorithm. It can be seen that πNAIV E performs at least as well as the nonadaptive path πA that PSPIELOR returns, i.e., U(πNAIVE) ≥ U(πA). Moreover, we have the following result that compares the performance of NAIVE to the performance of an optimal adaptive policy.

where π∗ is an optimal sequential policy of length Ω(B/(r dim(V,E))).

Algorithm:NAIVE-PSPIELOR Input: s1, sB, u, B Output: Sequence of selected locations π(xV) begin s ← s1; π[1] = s; Bpp ← B; obs ← {}; for 1 ≤ t ≤ B do ys ← observe(s); obs ← obs ∪ {Ys = ys}; 1 Pt ← pSPIELOR(s, sB,Bpp, F(· | obs)); s ← Pt[2]; π[t + 1] ← s; Bpp ← Bpp - 1; return π; end

Hereby, Γ is a (computable) upper bound to the adaptivity gap, a fundamental quantity in active learning, defined as the ratio

i.e., the ratio of the performance of the optimal policy divided by the performance of the best nonadaptive path. We explicitly bound Γ for the two case studies of search and rescue and hotspot sampling in Section 6.

Theorem 3, along with the fact that we can bound the adaptivity gap for interesting real-world applications (Propositions 5 and 6) implies that the adaptive solutions obtained by the NAIVE algorithm, using any near-optimal nonadaptive algorithm (such as PSPIELOR or EMIP) as a subroutine, are provably competitive with the NP-hard optimal adaptive solution.

4.3 Trading off exploration and exploitation

If the adaptivity gap Γ is small, Theorem 3 proves nearoptimal performance of the NAIVE algorithm. In the case of large adaptivity gap, we choose the following algorithm to select paths that simultaneously exploit the current belief about the state of the world as well as decrease the bound on the adaptivity gap as much as possible. We define two utility functions, U1 and U2. The second utility, U2(π) = ∫ P(xV)u(π(xV), xV)dxV, seeks to exploit our current belief of the world. The first utility U1 seeks to make observations that are likely to reduce the adaptivity gap, i.e., it is chosen such that U1 → 0 implies Γ → 0. Both objective functions are application specific, and we will explain our choices in Section 6. We then use scalarization [Boyd and Vandenberghe, 2004] by setting

where 0 ≤ λ ≤ 1 and π(xV) ∈ V. λ is a knob we can turn: if λ = 0, we exploit our current belief about the survivor locations, by seeking to observe the locations where survivors are most likely located. If λ = 1, we explore in order to reduce the uncertainty about the survivor locations. Values 0 < λ < 1 encourage a tradeoff of exploration and exploitation. A similar analysis was used for Gaussian Processes by Krause and Guestrin [2007] (who did not consider path planning).

5 Multi robot informative path planning

One approach for extending any single robot planning algorithm to plan simultaneous paths with multiple robots is to form a new graph where each node represents the vector of locations of all k robots, and then apply the single robot algorithm to this product graph. Unfortunately, the size of this product graph grows exponentially in k, which is infeasible for large teams of robots. We now present an algorithm for multiple robot adaptive path planning that scales linearly in the number k of robots, while providing almost the same performance as applying the single robot algorithm to the product graph. The algorithm, sequential allocation, extends any single robot algorithm for adaptive informative path planning, such as NAIVE-PSPIELOR, or a POMDP solver, to the multi robot setting. Sequential allocation is a greedy algorithm, that optimizes the policy πi for robot i conditioned on all policies π1, . . . , πi-1 that have already been selected, by optimizing πi = argmaxπ Uπ(1:i-1)(π), where Uπ(π′ ) = U(π ∪ π′ ) -U(π) and π(1:i-1) = π1 ∪ · · · ∪ πi-1. This algorithm is similar to the algorithm proposed by Singh et al. [2007] for the nonadaptive setting, and generalizes it to the framework involving policies. We prove:

Theorem 4. Suppose we have an approximation algorithm that, given policies πj ∈ Πj and π(1:i) = π1 ∪ · · · ∪ πi, finds a solution πG such that Uπ(1:i)(πG) ≥ 1 η maxπ∈Πi+1 Uπ(1:i)(π). Then sequential allocation using this algorithm guarantees a solution (π′i )i such that

When using NAIVE-PSPIELOR, η = O(Γ/γ). The approximation guarantee provided by sequential-allocation algorithm holds even when the planning is done sequentially at each timestep, i.e., the information about the observation locations selected so far, for each robot, is known to all the planners while they select their next observation location. Further, this information may be communicated to all the planners for distributed path planning or the paths may be centrally planned by a single planner.

6 Experiments

We now present empirical results on two case studies.

6.1 Case Study I: Search and rescue

We perform our first set of experiments on a realistic simulation environment for a search and rescue domain.

Experimental setup: This case study is based on the Sensor Planning Research Challenge (SPRC), originally announced for the International Conference on Machine Learning, 2007, and extended by slight modifications. The SPRC problem considers an earthquake in a large urban environment with survivors spread across heavily populated areas of interest, accessible only using rescue helicopters (c.f., SPRC 2007 for details on the problem specification). Each helicopter is equipped with two capabilities - a long range, noisy sensor to detect the survivors; and the ability of rescuing the survivors using a short range sensor. Field of view of these helicopters is assumed to be occluded by the buildings and only the unobstructed survivors are assumed to be detected or rescued.

With unknown survivor locations and noisy observations, we therefore need to tradeoff the detection (exploration) using the long range sensor and rescuing survivors at known locations (exploitation). For path planning, we discretized the search space into 1000 locations distributed uniformly at random. We assume a total of 500 survivors distributed according to a mixture of Gaussians with (unknown) 4 (resp. 9) centers. The prior joint distribution P(XV) for survivor locations is assumed to be uniform. Figure 2a illustrates a snapshot of one timestep during the path planning.

Model: For each helicopter location s, we associate the corresponding fields of view for each sensor, W1,s ⊆ V and W2,s ⊆ V, that provides a subset of unobstructed locations in the corresponding range (with W2,s ⊆ W1,s). For each s′ ∈Wi,s, Xs′ is revealed with certain false positive/negative probability pi. We assume that the short range sensor provides exact localization and hence p2 = 0, while we associate a non-zero noise p1 with the long range sensor. The observation Ys therefore is the noisy measurement of the random vector XW1,s and the noise-free observation of XW2,s . Using the observations ys, we then perform Bayesian inference to compute the probability density of survivor locations, P(Xs | ys), which involves multi-person tracking and data association (details in the longer version of this paper [Singh et al., 2009]).

The exploration utility function is the expected value of u1(A, xV), the number of people detected at locations A in state xV . The exploitation utility function is defined as the expectation over u2(A, xV), i.e., the number of people rescued at locations A in state xV . We can show the following result:

Proposition 5. The adaptivity gap is bounded as Γ ≤ EyV maxs P(Xs | yV)/P(Xs).

Hence the adaptivity gap is bounded by the maximum "amplification" in the occupancy probability P(Xs) that can occur by knowing all observations. Note that the above bound on Γ can be approximately computed with arbitrarily small additive error by sampling possible observation vectors yV .

(g) Comparison of computation effort for 50 timesteps

(h) Multi robot using NAIVE-PSPIELOR

(i) Paths for multi robot using NAIVE-PSPIELOR

Figure 2: Search and rescue experiments comparing the performance of NAIVE-GREEDY, NAIVE-HEUR and NAIVE-PSPIELOR.

Experimental results: We empirically compare the performance of NAIVE-PSPIELOR with two other algorithms - (a) NAIVE-GREEDY with a greedy algorithm as subroutine in Line 1 of Algorithm 1; and (b) NAIVE-HEUR with a path planning heuristic proposed by Chao et al. [1996] (empirically shown to provide efficient results in the nonadaptive setting by Singh et al. [2007]) as subroutine. For sake of brevity, we refer to the nonadaptive greedy algorithm as greedy and the nonadaptive heuristic algorithm as heuristicOP .

For both NAIVE-HEUR and NAIVE-PSPIELOR, we fixed the starting and finishing location as the current location. We fixed budget B to 50 timesteps and explorationexploitation parameter λ to 0.5. Each experiment was run multiple times to compute the expected utility. To reduce the computation effort for the nonadaptive path planning algorithm, we fixed the lookahead to 8 timesteps. Lookahead budget was empirically found to have insignificant influence on the performance of the corresponding adaptive algorithm.

Figures 2b and 2c compare the expected utility (expected number of survivors rescued) for NAIVE-GREEDY, NAIVE-HEUR and NAIVE-PSPIELOR with survivors scattered in 4 and 9 clusters respectively. In the case of fewer clusters, the expected utility gap widens between nonmyopic planning using NAIVE-PSPIELOR and myopic NAIVE-GREEDY and NAIVE-HEUR. Figure 2c compares the performance of all the three algorithms with their corresponding nonadaptive versions. We also compared with the performance of an efficient nonadaptive path planning algorithm (with provable approximation guarantees) proposed by Singh et al. [2007], referred to in the figure as EMIP. As expected, the adaptive algorithms provide better expected utility compared to the nonadaptive algorithms.

Figure 2d compares the expected utility while performing path planning using NAIVE-PSPIELOR for different values of exploration-exploitation parameter, λ. For the given problem setting, the utility function favors exploitation of the current knowledge about survivor locations (XV) in larger expected utility for smaller λ. Exploration benefit (to achieve higher expected utility) between λ = 0.1 and λ = 0 also diminishes with time. Figure 2e and Figure 2f illustrate paths for NAIVE-PSPIELOR and NAIVE-GREEDY for λ = 0.1 respectively. Nonmyopic planning using NAIVEPSPIELOR results in seeking out more survivor clusters (even when they are at a large distance from the current location) more quickly than myopic NAIVE-GREEDY.

Figure 2g compares the computation effort (on a standard dual core desktop) between NAIVE-PSPIELOR and NAIVE-HEUR for an experiment running over 50 timesteps with varying budget inputs. With its polynomial running time guarantee, and corresponding empirical validation of low computation effort, as shown in Figure 2g, and significant increase in expected number of survivors rescued (c.f., Figure 2c), NAIVE-PSPIELOR can be used for efficient path planning in search and rescue domain.

Figure 2h illustrates the performance of sequentialallocation when using NAIVE-PSPIELOR and PSPIELOR as the single robot path planning algorithms. When using NAIVE-PSPIELOR, each robot exchanges the the collected observation information with other robots before performing path planning to decide the next observation location. Since each of the multiple robots can now (possibly) explore different regions of the environment, increasing the number of robots from two to three when using NAIVE-PSPIELOR results in higher performance gain than when using PSPIELOR (nonadaptive path planning). Figure 2i illustrates typical paths taken by each robot when a total of 3 robots were available for path planning using sequential-allocation.

6.2 Case Study II: Hotspot sampling

Our second case study applies informative path planning to the scientific application of monitoring photosynthetically active regions in a forest understory. Tropical forests, in particular the small plants growing in the below-canopy environments, play a significant role in global climate change [Houghton, 2005]. Spatial and temporal variation of light intensity in such environments is not well known and its measurement is technically challenging.

Experimental setup: We collected a series of 10 images, each separated by ≈ 20 minutes, from 8:30 - 11:30 AM, using a down-looking camera to capture light intensity distribution under a tree canopy at San Jacinto mountains reserve (Southern California). A camera can only capture the reflected light intensity. However, the incident light intensity is of importance for the photosynthesis process. Accurate light measurements require a physical sensing system and cannot be captured using a camera. We only used these images to model the complex dynamics of such environments. We projected these images onto a planar surface to be sampled using a light sensor attached with Planar Networked Info Mechanical System (NIMS-PL, Borgstrom et al. [2008], c.f., Figure 3a). We discretized the image into a uniform grid of 15 × 15 locations for path planning.

Model: We modeled the observed light intensity as a multivariate normal distribution over the grid locations XV:

In consultation with the biologists, we applied a suitable transformation to the collected intensity data to identify the set of locations critical for photosynthesis (for the specific plant species growing in the observed region). The goal of this monitoring problem is observe as many critical regions as possible. Hence, we define the exploitation utility function, U2, as expectation over u(A, xV), the number of critical locations in A given true intensity xV . The exploration utility function U1 quantifies the expected reduction in uncertainty for the multivariate gaussian (trΣV - trΣV|A). In this case, Σ represents the prior joint distribution P(XV), learned empirically from the remaining projected images other than the one used for performing path planning (leave-one-out cross-validation). After observing each location Ys, we perform Bayesian inference, updating our belief about the joint light distribution, conditioned on the observations, i.e., we compute posterior mean μV|Ys and covariance ΣV|Ys . We can prove an analogous statement to Proposition 5:

Proposition 6. The adaptivity gap is bounded as Γ ≤ EyV maxs P([Xs ∈ R] | yV)/P(Xs ∈ R) where R represents the "interesting range" of light intensity.

Hence the adaptivity gap is bounded by the maximum increase in the expected number of "photosynthetically interesting" observation locations that can occur by knowing all observations. Red dots in Figure 3b represent all the photosynthetically interesting locations in the corresponding image.

Experimental results: We fixed λ to 0.5, and path planning budget (Bpp) for nonadaptive path planning algorithm to 10 timesteps (to reduce the computation effort) and budget (B) to 40. Figure 3c compares the expected percentage of critical observation locations observed in each of the projected images using NAIVE-PSPIELOR and PSPIELOR. The X-axis represent the number of timesteps. As the time progresses, the average utility gap between an online and an offline algorithm increases. This result demonstrates that adaptive path planning can successfully take into account observations to predict relevant regions for further monitoring.

7 Conclusions

In this paper we presented a nonmyopic algorithm for informative path planning using multiple robots. Our adaptive algorithm - NAIVE- works by applying a novel nonadaptive path planning algorithm - PSPIELOR- as a subroutine at each timestep with the updated belief about the state of the environment to decide the next observation location. We analyze the performance of NAIVE using the concept of submodular functions, which we generalize to sequential policies. We bound the algorithm's suboptimality by analyzing the adaptivity gap that quantifies the benefit of the optimal adaptive over the optimal nonadaptive policy.

For the case of a small adaptivity gap, our algorithm exhibits provably near-optimal performance guarantees for efficiently monitoring the complex uncertain environments, outperforming state of the art nonadaptive algorithms. To handle large adaptivity gaps, we use a multicriterion utility function that seeks to simultaneously optimize exploitation of the current belief about the state of the environment and exploration to decrease the uncertainty about state of the environment.

We also provide a generic sequential-allocation algorithm for extending any single robot path planning algorithm in this setting, such as NAIVE-PSPIELOR, for multi robot optimization while (almost) preserving the approximation guarantee of the single robot path planning algorithm. We extensively evaluate our approach on the search and rescue domain and on an actual robotic system for the critical application of monitoring light intensity in the forest understory. We believe that our results can benefit the development and analysis of new adaptive algorithms and their application to complex scientific and societal problems.

Acknowledgements This work was supported by NSF Grant Nos. ECCS-0725441 and CNS-0331481. We would also like to thank Zainul Charbiwala for his comments to improve the paper presentation. Amarjeet Singh was partially supported by UCLA Dissertation Year Fellowship. Andreas Krause was partially supported by a Microsoft Research Graduate Fellowship.