Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations

1 Introduction

Planning under uncertainty for a team of agents has seen much progress thanks to the development of such models as multi-agent MDPs (MMDPs) [Boutilier, 1999] and decentralized MDPs [Bernstein et al., 2002]. Despite rapid progress, the practical application of these models remains limited due to their computational complexity. MMDPs are conceptually simple, but their complexity is exponential in the number of agents. For DEC-MDPs and POMDPs, optimal algorithms have been shown to be NEXP-Complete even for two agents [Bernstein et al., 2002].

To overcome this computational barrier, research has focussed on domains that exhibit certain structure, such as transition independence [Becker, 2006], structured interaction among agents and decomposable reward functions [Guestrin et al., 2001; Nair et al., 2005]. Sensor networks have emerged as a particularly relevant application domain where coordination among sensors is required to track or detect multiple stochastically moving targets over some finite horizon [Lesser et al., 2003]. Sensors often interact only through a joint reward function and they exhibit locality of interaction-each sensor interacts with a limited number of neigh-

Shlomo Zilberstein

Department of Computer Science University of Massachusetts, Amherst shlomo@cs.umass.edu

boring sensors. Significant scalability has been demonstrated for noisy sensors with partial observability using the NDPOMDP model [Nair et al., 2005; Kumar and Zilberstein, 2009], a restricted class of DEC-POMDPs.

Our proposed model, event-detecting multi-agent MDP (eMMDP), is a specialized framework for early outbreak detection of stochastically evolving events or targets in a distributed sensor network. A key feature of the model is that detection requires collaboration among agents, but even with perfect collaboration agents may fail to detect an event with certain probability. In addition, the network is resource constrained, not allowing all the events to be detected simultaneously. Agents receive a joint reward for successfully detecting an event and their goal is to maximize the accumulated reward over a finite horizon. Rewards for an event have a certain structure which is detailed below.

The eMMDP model is motivated by several real-world applications. One example is a sensor network application, Distributed Collaborative Adaptive Sensing (DCAS) [Pepyne et al., 2008], where a network of radars collaboratively sense the earth's atmosphere for weather phenomena, such as storms and tornadoes [Manfredi and Kurose, 2007]. Events in DCAS are the stochastically moving storms and detection implies extracting the storm's physical attributes such as velocity or moisture content. Coordination among radars is required for this task, and the overall goal is to find the policy (sector scan strategy) for radars such that storms are detected as early as possible, providing critical information about their attributes. A similar problem is that of containing virus propagation in a water distribution network [Ostfeld et al., 2006; Leskovec et al., 2007]. In such water sensor networks, the detection involves containing the spread of viruses as soon as possible to minimize the size of affected population. Several other physical phenomena share these early detection/containment characteristics such as the spread of fire in a building or in wilderness. The goal of early detection makes the reward structure inherently non-increasing. That is, the reward for detection does not increase with the horizon. We exploit this reward structure to design an efficient algorithm for eMMDPs with a guaranteed approximation bound.

A key contribution of our work lies in establishing connections between decision-theoretic planning for multi-agent systems, algorithmic concepts such as matroids and submodularity, and constraint optimization. The algorithm we present for solving eMMDPs, locally greedy submodular maximization (LGM), uses these key concepts: a matroid representation of the policy search space, submodularity of the policy value function, and constraint optimization to exploit the locality of interaction and avoid exponential complexity in the number of agents (which MMDPs suffer from). LGM is based on a generic approximation algorithm for submodular function maximization [Fisher et al., 1978]. Unlike other heuristics, it provides strong theoretical guarantee of a factor2 approximation, which is the worst case ratio between the optimal value and the value produced by the algorithm.

Using submodularity, we also provide a much tighter online bound for any eMMDP algorithm, and use it to show that policies produced by LGM are provably near-optimal on a number of sensor network configurations. Furthermore, matroids and submodularity are very general concepts not necessarily limited to eMMDPs. Thus, the ideas developed in this paper can become useful in other practical applications too.

2 Event-detectingMMDPs

An eMMDP is a tuple 〈A, L, T , S, P, A, {Rt i }, d〉, where

• A is a set of n stationary sensor agents (analogous to radars)
• L is a set of locations
• T is a set of k targets (storms) which move stochastically between the L locations
• S is a system state space: S = ×ki=1Si, where Si ⊆ L is the set of locations where target i can be. It must be noted that we use the term detection in a richer sense than merely modeling the location of targets, which statespace represents. In many applications, such as DCAS, state can be easily tracked using a specialized tracker application [Manfredi and Kurose, 2007].
• P is a state transition probability: if s = 〈s1, . . . , sk〉 is a joint state, P (s′ |s) = ∏ki=1 P (s′i |si), assuming transition independence of targets
• A is a joint action space: A = ×ni=1Ai, where Ai is the set of actions for agent i. An agent's action can be to scan a location (i.e. Ai ⊆ L) or to idle using the nop action
• {Rt i } = {{Rt1 }, . . . , {Rtk }} is a set of reward functions for k targets. Rt i is the reward for detecting target i at time step t. The reward is nonincreasing with time, that is ∀i : R1 i ≥ R2 i ≥ . . . ≥ RT i , indicating that targets should be detected as early as possible to maximize the reward.

We define the following interaction hypergraph, G = (V, E), to describe the interactions among the agents. There is a node for each agent i. There is a hyper-edge for each location l, which connects the nodes of all the agents that can scan l. Let A(l) = {i|l ∈ Ai} denote that set of agents for location l. To detect a target present in l, any subset of d agents from A(l) must scan it. A successful detection produces the associated reward, otherwise the reward is 0. While d can be arbitrary, we assume for simplicity that it is the same for all targets. Clearly, coordination among agents plays an important role in solving eMMDPs. The next section describes the policy structure and its value function.

2.1 Policy structure and value function

At each state st , the choice of targets to detect must come from the power set 2T . The joint policy π maps each state st ∈ S × T to a set τ ∈ 2T of targets to detect, i.e., π : S × T → 2T . Hiding the actual state-action mapping for agents under this representation helps provide insights about the problem and becomes useful in proving theoretical results later. In section 3.5, we describe how to extract the underlying policy (state-action mapping) and deal with the exponential size of the power set.

Since targets are independent, the policy and its value can be decomposed over the k targets: V (π) = ∑ki=1 V (πi), where πi : S × T → {0, 1}. If target i is detectable by the joint policy, i.e., i ∈ π(st ), then πi(st ) = 1, else 0. We define each V (πi) as follows. Let pti (πi) be the probability of detecting target i at time t according to πi. It is given by:

The probability P (st ) of being in state s at time t can be calculated easily using the given transition function and is conditioned on the initial state or belief. Further, if each detection is successful only with a certain probability, P (success), then each term of the above summation is multiplied by it. We use a shorthand of pti for pti (πi) and define V (πi) as follows:

Let qt i be the product ∏t-1 t′=1 (1 - pt′ i ) with q1 i = 1. This product denotes the probability that target i is not detected before time t. This notation further simplifies the value function:

The goal of solving an eMMDP is to find the joint policy π with the highest expected value V (π).

2.2 Hardness of eMMDPs

Theorem 1. Solving an eMMDP is NP-Hard.

Proof. We reduce the NP-Complete weighted k-Set Packing problem to eMMDP. Given a collection X1, . . . ,Xq of sets of cardinality at most k, with real weights for each set, the k-set packing problem is that of finding a collection of pairwise disjoint sets of maximum total weight. The reduction efficiently maps it to the tuple 〈L, A, T , A, {Ri}, d〉.

The set L include q locations, one for each Xi. Let X = ∪qi=1Xi. The set A includes one agent for each element x of X. The action set Ax for agent Ax includes actions to scan all locations lXi such that x ∈ Xi, i.e. Ax = {lXi : x ∈ Xi}. One target is present in each location lXi in the initial state, with associated reward equal to the weight of the set Xi. To detect the target in location lXi , |Xi| surrounding agents need to scan it. The time horizon for the problem is 1. Clearly, this reduction is polynomial time. The k in k-set packing signifies that for detecting a target, a fixed number of agents are required (parameter d in eMMDP). Finally we need to show that there exists a collection of disjoint sets with total weight W for the given k-set packing problem if and only if the corresponding eMMDP has a policy with value W.

(⇒) Let Xi1, . . . ,Xic be a disjoint collection with weight W. Corresponding to a target in location lXij , assign action lXij to each agent Ax : x ∈ Xij. Clearly, |Xij| agents scan location lXij , as required by eMMDP. This policy also prevents conflicts among agents in scanning assignment. That is, each agent scans at most one location. To prove this, suppose, Ax has to scan two locations lXij and lXij′ . By the construction of the action set for Ax, to scan locations lXij and lXij′ , both Xij and Xij ′ must contain x (i.e., Xij ∩Xij ′ ̸= φ). But, this is a contradiction because Xij, Xij ′ are disjoint. The value of the policy is W because the detected targets have the same rewards as the weights of their corresponding sets.

(⇐) Let the detected targets be in locations lXi1 , . . . , lXic , and the policy value be W. Then the sets in the packing problem are Xi1, . . . ,Xic. Their total weight is W and they are disjoint. Otherwise, for any shared element x ∈ Xij ∩Xij ′ , Ax has to scan both locations lXij and lXij′ to detect the respective targets, which is impossible.

3 Matroids and eMMDPs

Let E be a finite ground set and F be a non-empty collection of subsets of E. The systemM = (E,F) is a matroid if is satisfies the following two properties.

• The hereditary property: F1 ∈ F ∧ F2 ⊂ F1 ⇒ F2 ∈ F. In other words, all the subsets of F1 must be in F.
• The exchange property: ∀F1, F2 ∈ F: |F1| < |F2| ⇒ ∃x ∈ F2\F1 ; F1 ∪ {x} ∈ F.

The members of F are also called independent sets. Matroids are useful combinatorial structures, an example of which is the graphic matroid, where E is the set of all edges in a graph and F is the family of all acyclic subsets of edges.

A set F ∈ F is called maximal if there is no x ∈ E such that F ∪ {x} ∈ F. Many combinatorial optimization problems can be modeled as a matroid, with the optimal solution equivalent to finding the maximal, maximum weight independent set. A classical example on the graphic matroid is finding the maximum weight forest (equivalent to the minimum spanning tree when edge weights are subtracted from a large positive constant). Such set is maximal (i.e., adding an edge to a spanning tree creates a cycle) and maximum weight.

For a ground set partitioned as E = E1 ∪ E2 ∪ . . . ∪ Ek, the family of subsets F = {F ⊆ E : ∀i; |F ∩ Ei| ≤ 1} forms a matroid called a partition matroid. This family simply denotes that any independent set can include at most one element from each ground set partition. We show in the following sections that any eMMDP can be mapped to a partition matroid, where the collection F denotes the policy search space of the eMMDP. The set evaluation function z : 2E →ℜ for this matroid is similar to the eMMDP policy evaluation function. Finding an optimal policy for an eMMDP is equivalent to finding the maximal, maximum weight independent set under z.

3.1 eMMDP as a partition matroid

The policy for an eMMDP can be viewed as a collection of |S| ×T partitions. Each partition denotes a unique state-time pair st . The policy, π : S×T → 2T , constrains each partition to make sure that it is filled by exactly one element from the power set. Fig. 1 illustrates this with target set T = {1, 2, 3}. This notion is formalized below as a partitioned ground set.

Let E = ∪stEst , where Est = {(st , τ ) : τ ∈ 2T }, be a ground set. The subset system F = {F ⊆ E : ∀st ; |F ∩ Est | ≤ 1} forms a partition matroid. A member (st , τ ) ∈ E denotes that the policy in state st is to detect the targets in the set τ. The policy constraint is also modeled by the partition matroid. Clearly, the independent sets are the partial policies for eMMDP and the maximal independent set specifies the complete policy. The maximum weight, maximal set represents the optimal eMMDP policy. The weight criterion z, intuitively enough, is the evaluation function of the policy an independent set represents.

3.2 Set evaluation function

The evaluation function z : 2E → ℜ is defined for any subset of E. For the independent sets, z is the same as the evaluation function of the policy it represents. For partial policies, we assume no targets are detected in unspecified partitions.

Sets F which violate the matroid constraint, i.e., ∃Est : |F ∩Est | > 1, do not represent a valid policy as they include more than one element from a ground set partition. The function π then becomes a relation. For such invalid policies, the only change occurs in specifying the policy πi for each target i, with

The detection probability for each target and the final value can be calculated using this modified policy as in Section 2.1.

3.3 Monotonicity and submodularity

If the evaluation function z is linear in the weight of each element, then the greedy approach, which starts with an empty set and chooses the next best element, is optimal; this is exactly how Kruskal's algorithm for MST works. However, for eMMDPs, we show that z is submodular and monotone instead of linear. Surprisingly, a similar greedy approach gives factor-2 approximation [Fisher et al., 1978]. Goundan and Schulz [2007] provide a good overview of these concepts, which we summarize below. A set function z is said to be

• monotone, if z(F1) ≤ z(F2) whenever F1 ⊆ F2

• submodular, if z(F1∪{e})-z(F1) ≤ z(F2∪{e})-z(F2) for all F2 ⊆ F1 ⊆ E and e ∈ E \ F1

Submodularity is similar to the law of diminishing returns. As a set grows, the marginal gain of each subsequent element decreases. The marginal gain of an element e ∈ E \ F to F is ρe(F ) = z(F ∪ {e}) - z(F ). Equivalently, submodularity implies ρe(F1) ≤ ρe(F2), ∀F2 ⊆ F1.

For eMMDPs, this implies that extending a smaller partial policy leads to a higher increase in reward than extending its superset. Intuitively, in a smaller policy there are at least as many undetected targets as in its superset, possibly more. Therefore, the chance that a new target will be detected providing extra reward is higher when the smaller policy is extended.

Theorem2. The evaluation function for an eMMDP ismonotone and submodular.

Proof. For monotonicity, it suffices to show ρe(F1) ≥ 0. For eMMDPs, adding e = (st , τ ) can never decrease the probability of detecting any target, thus, ρe(F1) ≥ 0.

Consider the sets F1 ⊆ F2 ⊆ E, and an element e = (st+1 , τ ) ∈ E \ F2. Intuitively, we are extending the partial policy F2 by specifying targets to detect in state st+1 . Given, V (π) = ∑ki=1 V (πi), we will show that each V (πi) is submodular; submodularity of the joint policy follows by the property that a positive linear combination of submodular functions is also submodular.

With πF2 i we represent the underlying policy of set F2. V (πF2 i ) = ∑Tt=1 qt i · pti · Rt i . We can represent the above summation as a sum of values obtained from time step 1 to t (= vt1 ), the value at step t + 1, and the remaining value from step t + 2 to the end (vT t+2 ). Thus,

Consider the set F2 ∪ {e = (st+1 , τ )}. If target i /∈ τ, then ρe(F2) = 0, and proving submodularity is trivial as ρe(F1) ≥ 0 = ρe(F2) by monotonicity. Thus, we consider the nontrivial case when i ∈ τ. In Eq. (1), only the middle and the last termwill change by including e. Specifically, the probability of detecting target i at time t + 1 will increase by P (st+1 ), the probability of state s at time t +1, which can be calculated easily from the input parameters. Thus, we have

ρe(F2) is given by subtracting Eq. (1) from Eq. (2):

To show submodularity, we must prove ρe(F1) -ρe(F2) ≥ 0. Since, F1 is a subset of F2, the value of the sub-policy from time step t + 2 until T in πF2 i cannot be less than πF1 i , that is vT t+2 (πF2 i ) ≥ vT t+2 (πF1 i ). To get an upper bound on ρe(F2), we substitute vT t+2 (πF2 i ) = vT t+2 (πF1 i ). We get

Algorithm 1: Locally Greedy Submodular Maximization

Since, πF1 i is a subpolicy of πF2 i , the probability of not detecting target i is higher in πF1 i than πF2 i , i.e. qt+1 i (πF1 i ) ≥ qt+1 i (πF2 i ). Also, from the reward dependence on the time horizon we have vT t+2 ≤ Rt+2 i ≤ Rt+1 i . Thus, all the terms in Eq. (5) are ≥ 0. Hence, ρe(F1) - ρe(F2) ≥ 0, implying submodularity. Note that these results hold even when F2 represents a non-valid policy. The proof is similar, but omitted due to space constraints.

3.4 A submodular greedy algorithm

This section describes the 2-approximation greedy algorithm, LGM, for solving eMMDPs. It is based on an approach for maximizing submodular functions over a partition matroid. For details and proof of approximation quality guarantee we refer to Fisher et al. [1978] and a recent survey by Goundan and Schulz [2007]. The worst-case bound may seem loose, but using submodularity, we also provide a way to calculate much tighter online bounds, which we discuss later.

The surprisingly simple and efficient LGM technique, detailed in Algorithm 1 above, iteratively builds the policy AG. Starting with an empty set, the algorithm iterates over the policy partitions (as Fig. 1 depicts). In each iteration, it selects the element from the current partition which maximizes the marginal gain. The ordering of the partitions does not affect the quality guarantee, though a good ordering may provide a better solution.

It should be noted that LGM is not a myopic algorithm in the sense that it does take into account the sequential nature of the eMMDP policy. During the initial iterations, when AG is relatively sparsely filled, it has some myopic nature, but as the policy AG gets built progressively, the marginal gain step will take into account which targets already have high detection probability and focus the next iteration on targets with low current detection probability. This step combined with the submodularity of eMMDPs is the key to the strong quality guarantees provided by LGM. Other myopic heuristics-such as detecting targets that provide maximum immediate reward in each state using constraint optimization-cannot provide such quality guarantees.

Complexity

The complexity of LGM depends upon the number of partitions and the complexity of selecting the best element e⋆ from a partition. The number of partitions is |S| · T, linear in the state-space and horizon. However, maximizing the marginal gain requires iterating over 2|T | alternatives, which is exponential in the number of targets. To address this, we transform the problem below into a constraint optimization problem, which can be solved much faster in O(n · |Ai|m) time and space using the bucket elimination approach [Dechter, 1999]. Ai is the action set for an agent, n is the number of agents, and m is the induced width of the chosen depth-first search (DFS) ordering of the variables in the constraint formulation. The constraint graph we construct is similar to the agent interaction graph defined earlier-a hyper-edge can be simulated using an n-ary constraint involving all agents on the edge. Such formulation makes the complexity linear in the number of agents, a significant contribution that increases the scalability of the approach to large multi-agent systems. In looselycoupled systems, the induced width is low, making the constraint formulation particularly easy to solve. Setting up the constraint formulation requires calculating marginal gain of each target, which can be calculated in O(T ) time. Hence, the overall complexity of LGM is O(|S|T (|T |T + n|Ai|m))).

3.5 Maximizing the marginal gain

Before presenting the constraint formulation, we prove the following theorem. Intuitively, it states that the marginal gain for detecting a group of j targets in state st can be factored and represented as a sum of gains provided by each target.

Theorem 3. Let F ⊆ E and e = (st , τ ) is an element of E \ F, where τ = {i1, . . . , ij} represents the choice of j targets to detect in state st . Then, ρe(F ) = ∑jc=1 ρec (F ), where ec = (st , {ic}).

Proof. First note that ρe(F ) = z(F ∪ (st , τ )) - z(F ), which can be written as a telescoping series with τc = {i1, . . . , ic}

Each term on the RHS of Eq. (6) can be further decomposed with respect to the targets c′ ∈ T which do not occur in τc; for them the policy valuation remains unchanged, and the targets in τc; for which the valuation changes.

Subtracting the latter equation from the previous one gives

The theorem follows immediately by substituting this result with the right hand side of Eq. (6).

We conclude from Theorem 3 that if e = (st , {i1, . . . , ij}), then maximizing the marginal gain is equivalent to finding e⋆ ← argmaxe ∑jc=1 ρec (AG). Constraint optimization algorithms can efficiently solve this problem. Further, constraint optimization provides the actual policy (state-action mapping) for each agent in addition to maximizing marginal gain.

The constraint formulation

A constraint optimization problem (COP) is defined by a set of variables X = {X1, ...,Xn} and a set of constraint functions F = {f1, ..., fm}. Each variable Xi has a domain Di of possible values. Each constraint fj involves some subset of variables and specifies a reward for each value of the subset. The solution is the complete assignment X ∗ for the variables that maximizes the global reward.

Variables and domain: For each target i ∈ T , let li ∈ L be its location in state st . A(li) denotes the agents which can scan li. The constraint network includes a variable for each agent in the group A(li) (and for all targets i), but without any duplicates. The domain of each variable is the action set of the corresponding agent.

Constraints: To detect a target i and claim the reward, d agents from A(li) must scan li. To ensure this coordination, an n-ary constraint fi is created among all the variables, say X(li), corresponding to agents A(li) (and for all targets i). The valuation for the joint assignment x to X(li) is defined below. Xd denotes a group of d variables and xX is the projection of assignment x on variable X.

The above constraint valuation ensures that reward is only given when at least d agents fromA(li) scan location li. This formulation maximizes ∑ki=1 fi, where k is the number of targets. Clearly, the optimal solution includes detecting those targets which maximize this sum, which is also the maximum marginal gain. The group of detected targets can be extracted from solution X ∗ by examining each fi, and including target i in e⋆ for which fi ̸= 0 under X ∗ . Furthermore, the solution X ∗ denotes which action each agent must take, hence provides the actual policy for agents at state st . If an agent is not included in X ∗ , then it takes the nop action.

3.6 Online bounds

Theorem 4. Let AG be a policy returned by some arbitrary eMMDP algorithm, and A⋆ be the optimal policy. Then, z(A⋆ ) ≤ z(AG) + ∑Est ρ⋆Est (AG), where ρ⋆Est (AG) = maxe∈Est ρe(AG) is the maximum marginal gain any element of the partition Est can provide.

Proof. The proof is based on the following property of submodular functions. If S and T are any subsets of the ground set E, then z(T ) ≤ z(S) + ∑e∈T-S ρe(S). If we substitute T = A⋆ and S = AG, then we get

The optimal solution A⋆ is unknown, but we know it must respect the eMMDP partition matroid constraint, i.e., it must pick only 1 element from each partition. Thus, ∑e∈A⋆-AG ρe(AG) ≤ ∑Est ρ⋆Est (AG). From this, the theorem follows.

This property provides tight bounds for any eMMDP algorithm and, as the experiments show, is quite useful in practice.

4 Experiments

We performed experiments on multiple sensor network configurations using a 2.4GHz dual-core Mac, with 512MB allotted to JVM. We used a publicly available constraint solver for implementing the marginal gain maximization step of LGM [Petcu and Faltings, 2005].

Fig. 3 shows the first two configurations from [Nair et al., 2005]. Each sensor can scan in four directions. Every square shaped region between sensors represents a location where a target can be. To detect a target, two sensors must scan the location. For the 5P domain, we had three stochastically moving targets. A target can appear in any location with some probability (chosen randomly for each simulation), moves to the next location with probability 0.8 and remains at the current location with probability 0.2 (as in [Nair et al., 2005]). Clearly, not all targets can be detected at the same time: only one among the two targets in the same vertical column can be detected. For each simulation, rewards were selected from the range [50, 200]. We generated 100 random instance with horizon 5. Fig. 2(a) shows the quality of approximation for each instance. Clearly, the algorithm proves very effective in this case, producing near-optimal results for all input instances. The average quality achieved was 94.8 ± 0.3% of the optimal (the error term denotes 95% confidence interval). Average runtime was 53 ms.

Fig. 2(b) shows the approximation ratios for the larger 11Helix configuration with horizon 5. There were 6 targets, with a state-space of 729 and action-space of 411 . Again, the algorithm was able to produce near-optimal results for all the 100 random problem instances. Average quality was 92 ± 0.6% and average runtime was 426 ms. Despite an action-space of 411 , our results show that the constraint formulation made it possible to solve the problem efficiently by exploiting the locality of interactions among the agents, and LGM was able to produce near-optimal solutions by exploiting the submodularity of eMMDPs.

Fig. 2(c) shows how solution quality varies with the horizon. Each result is an average over 100 random instances, shown along with 95% confidence intervals. The graph clearly reflects the submodular nature of eMMDP policies. For the smaller horizons, the error term in the formulation of Theorem 4, ∑Est ρ⋆Est (AG), is higher as the policy size is small. The error decreases as the policy size increases with the horizon-exhibiting the property of diminishing returns. Nevertheless, we were able to achieve very high quality for each horizon. Table 1 shows the runtime for each horizon. The runtime clearly increases polynomially with the horizon, confirming the good scalability of our approach.

For the next set of experiments, we used a much larger configuration-a dodecahedron with 20 nodes and 30 edges (or locations for targets). There were 7 stochastically moving targets and two adjacent agents were required to detect a target. The configuration and sample trajectories are shown in Fig. 4(a). In this configuration, 4 targets can appear in the innermost pentagon with randomly chosen probability and 3 in the outermost. The edges adjacent to the top left innermost node (shown in green) are the possible initial locations of a target. Targets can move stochastically to an adjacent edge, or jump to an edge on the outer pentagon with randomly chosen probabilities. With 0.2 probability targets remain at a location connecting two regions. The rewards were chose randomly for each instance. Similar trajectories were defined for each of the 7 targets such that targets in the innermost pentagon stochastically move to an outer pentagon, and targets in outer pentagons move to an inner pentagon. This makes the problem combinatorially complicated, as it presents agents with many alternatives that they must evaluate. The size of the state-space is 78,125 and the actionsspace is 320 . Using reachability analysis, it was possible to reduce the state-space to an average of 16,000 per instance. Fig. 4(b) shows the approximation quality for each of the 100 instances. Again, LGM produced near-optimal results. The average quality was 95 ± 0.4%. The average runtime was

66 ± 1.7 sec. These results clearly demonstrate the scalability and approximation quality of our approach for large state and action spaces. Because the complexity is linear in the statespace, based on these experiments we could solve a problem with 1 million states in just over an hour, which is a major improvement over the state-of-the-art.

For comparison purposes, we implemented another heuristic approach. In this approach, the group of targets which maximize the immediate joint reward are selected for detection in each state, instead of the ones which maximize the marginal gain. Clearly, this is suboptimal as it completely disregards the sequential and stochastic nature of eMMDPs. For randomly generated instances, as expected, LGM always produces better value than this heuristic. The gain in solution quality provided by LGM varies due to the random nature of these experiments. On average, LGM provided 20-30% gain, and in many instances it nearly doubled the heuristic value on the 11-Helix domain.

5 Conclusion

Sensor networks often require coordination of several sensors to detect and identify target phenomena such as weather conditions. As the size of these networks grow, the complexity of coordinating the sensors and the sequential nature of the decision process makes it hard to achieve good performance. We present a formal framework, eMMDP, to study the general problem of outbreak detection and showed that it is NP-Hard. The main contributions of this work are: (1) showing that eMMDPs exhibit submodularity, and (2) establishing their connection with matroids to provide a simple, principled approximation algorithm for solving them. The approximation algorithm provides strong theoretical guarantee of factor-2 in the worst-case. Using submodularity we also provided much tighter online bound for any eMMDP algorithm and use it to show that LGM produces near-optimal policies.

To improve the scalability of the algorithm, a key step was reformulated as a constraint optimization problem. This made the complexity linear in the number of agents and exponential only in the induced tree-width of the interaction graph, which is often much smaller than the number of agents.

Matroids and submodularity are very general concepts that are likely to be useful in other contexts and help develop practical approximation algorithms. For example, any MDP and some classes of decentralized MDPs (such as transitionindependent DEC-MDPs) can be easily modeled as a partition matroid. Identifying domains that exhibit submodularity for these classes will allow a straightforward application of LGM and provide efficient approximation with similar strong theoretical guarantees.

Acknowledgments

This work was funded in part by the National Science Foundation under grant IIS-0812149 and by the Air Force Office of Scientific Research under grant FA9550-08-1-0181.