Networked Distributed POMDPs: A Synergy of Distributed Constraint Optimization and POMDPs

1 Introduction

In many real-world multiagent applications such as distributed sensor nets, a network of agents is formed based on each agent's limited interactions with a small number of neighbors. For instance, in distributed sensor nets, multiple sensor agents must coordinate with their neighboring agents in order to track individual targets moving through an area. In particular, we consider in this paper a problem motivated by the real-world challenge in [Lesser et al., 2003]. Here, each sensor node can scan in one of four directions - North, South, East or West (see Figure 1), and to track a target, two sensors with overlapping scanning areas must coordinate by scanning the same area simultaneously. We assume that there are two independent targets and that each target's movement is uncertain but unaffected by the actions of the sensor agents. Additionally, each sensor receives observations only from the area it is scanning and this observation can have both false positives and false negatives. Each agent pays a cost for scanning whether the target is present or not but no cost if turned off. Existing distributed POMDP algorithms [Montemerlo et al., 2004; Nair et al., 2003; Becker et al., 2004; Hansen et al., 2004] although rich enough to capture the uncertainties in this domain, are unlikely to work well for such a domain because they are not geared to take advantage of the locality of interaction. As a result they will have to consider all possible action choices of even non-interacting agents, in trying to solve the distributed POMDP. Distributed constraint satisfaction and distributed constraint optimization (DCOP) have been applied to sensor nets but these approaches cannot capture the uncertainty in the domain. Hence, we introduce the networked distributed POMDP (ND-POMDP) model, a hybrid of POMDP and DCOP, that can handle the uncertainties in the domain as well as take advantage of locality of interaction. Exploiting network structure enables us to present a novel algorithm for ND-POMDPs - a distributed policy generation algorithm that performs local search.

2 ND-POMDPs

We define an ND-POMDP for a group Ag of n agents as a tuple 〈S,A, P,Ω,O,R, b〉, where S = ×1≤i≤nSi × Su is the set of world states. Si refers to the set of local states of agent i and Su is the set of unaffectable states. Unaffectable state refers to that part of the world state that cannot be affected by the agents' actions, e.g. environmental factors like target locations that no agent can control. A = ×1≤i≤nAi is the set of joint actions, where Ai is the set of action for agent i.

We assume a transition independent distributed POMDP model, where the transition function is defined as P (s, a, s′ ) = Pu(su, s′u) · ∏1≤i≤n Pi(si, su, ai, s′i ), where a=〈a1, . . . , an〉 is the joint action performed in state s=〈s1, . . . , sn, su〉 and s′ =〈s′1 , . . . , s′n, s′u〉is the resulting state. Agent i's transition function is defined as Pi(si, su, ai, s′i ) = Pr(s′i |si, su, ai) and the unaffectable transition function is defined as Pu(su, s′u) = Pr(s′u|su). Becker et al. [2004] also relied on transition independence, and Goldman and Zilberstein [2004] introduced the possibility of uncontrollable state features. In both works, the authors assumed that the state is collectively observable, an assumption that does not hold for our domains of interest.

Ω = ×1≤i≤nΩi is the set of joint observations where Ωi is the set of observations for agents i. We make an assumption of observational independence, i.e., we define the joint observation function as O(s, a, ω) = ∏1≤i≤nOi(si, su, ai, ωi), where s = 〈s1, . . . , sn, su〉, a = 〈a1, . . . , an〉, ω = 〈ω1, . . . , ωn〉, and Oi(si, su, ai, ωi) = Pr(ωi|s1, su, ai).

The reward function, R, is defined as R(s, a) = ∑l Rl(sl1, . . . , slk, su, 〈al1, . . . , alk〉), where each l could refer to any sub-group of agents and k = |l|. In the sensor grid example, the reward function is expressed as the sum of rewards between sensor agents that have overlapping areas (k = 2) and the reward functions for an individual agent's cost for sensing (k = 1). Based on the reward function, we construct an interaction hypergraph where a hyper-link, l, exists between a subset of agents for all Rl that comprise R. Interaction hypergraph is defined as G = (Ag, E), where the agents, Ag, are the vertices and E = {l|l ⊆ Ag ∧ Rl is a component of R} are the edges. Neighborhood of i is defined as Ni = {j ∈ Ag|j ̸= i ∧ (∃l ∈ E, i ∈ l ∧ j ∈ l)}. SNi =×j∈NiSj refers to the states of i's neighborhood. Similarly we define ANi , ΩNi , PNi and ONi .

b, the distribution over the initial state, is defined as b(s) = bu(su) · ∏1≤i≤n bi(si) where bu and bi refer to the distributions over initial unaffectable state and over i's initial state, respectively. We define bNi = ∏j∈Ni bj(sj). We assume that b is available to all agents (although it is possible to refine our model to make available to agent i only bu, bi and bNi ). The goal in ND-POMDP is to compute joint policy π = 〈πi, . . . , πn〉 that maximizes the team's expected reward over a finite horizon T starting from b. πi refers to the individual policy of agent i and is a mapping from the set of observation histories of i to Ai. πNi and πl refer to the joint policies of the agents in Ni and hyper-link l respectively.

ND-POMDP can be thought of as an n-ary DCOP where the variable at each node is an individual agent's policy. The reward component Rl where |l| = 1 can be thought of as a local constraint while the reward component Rl where l > 1 corresponds to a non-local constraint in the constraint graph. In the next section, we push this analogy further by taking inspiration from the DBA algorithm [Yokoo and Hirayama, 1996], an algorithm for distributed constraint satisfaction, to develop an algorithm for solving ND-POMDPs.

We define Local neighborhood utility of agent i as the expected reward accruing due to the hyper-links that contain agent i:

While trying to find best policy for agent i given its neighbors' policies, we do not need to consider nonneighbors' policies. This is the property of locality of interaction that is used in the following section.

3 Locally optimal policy generation

The locally optimal policy generation algorithm called LID-JESP (Locally interacting distributed joint equilibrium search for policies) is based on the DBA algorithm [Yokoo and Hirayama, 1996] and JESP [Nair et al., 2003]. In this algorithm (see Algorithm 1), each agent tries to improve its policy with respect to its neighbors' policies in a distributed manner similar to DBA. Initially each agent i starts with a random policy and exchanges its policies with its neighbors. It then evaluates its contribution to the global value function, from its initial belief state b with respect to its current policy and its neighbors' policy (function Evaluate()). Agent i then tries to improve upon its current policy by calling function GetValue, which returns the value of agent i's best response to its neighbors' policies. Agent i then computes the gain that it can make to its local neighborhood utility, and exchanges its gain its neighbors. If i's gain is greater than that one any of its neighbors, i changes its policy and sends its new policy to all its neighbors. This process of trying to improve the local policy is continued until termination, which is based on maintaining and exchanging a counter that counts the number of cycles where gaini = 0. This is omitted from this article in order to simplify the presentation.

The algorithm for computing the best response is a dynamic-programming approach similar to that used in JESP. Here, we define an episode of agent i at time t as eti = 〈stu, sti , stNi , ⃗ωtNi 〉. Given that the neighbors' policies are fixed, treating episode as the state, results in a single agent POMDP, where the transition function and observation function can be defined as follows:

The function GetValue() returns the optimal policy for agent i given the above definitions of transition and observation functions and the policies of Ni. In this paper, GetValue() was implemented via value iteration but any other single agent POMDP algorithm could have been used.

4 Experimental Results

For our experiments, we ran the LID-JESP algorithm on the sensor domain (see Figure 1). The first benchmark

(JESP) is Nair et al.'s JESP algorithm [2003], which uses a centralized processor to find a locally optimal joint policy and does not consider the interaction graph. The second benchmark (LID-JESP-no-nw) is LID-JESP with a fully connected interaction graph. Figure 2(a) shows the run time in seconds on a logscale on the Y-axis for increasing finite horizon T on the X-axis, while Figure 2(b) shows the value of policy found on the Y-axis and increasing finite horizon T on the X-axis. All run times and values were obtained by averaging 5 runs, each with different randomly chosen starting policies . As seen in Figure 2(b), the values obtained for LID-JESP, JESP and LID-JESP-no-nw are quite similar, although LIDJESP and LID-JESP-no-nw often converged on a higher local optima than JESP. In comparing the run times, it should be noted that LID-JESP outperforms LID-JESPno-nw and JESP (which could not be run for T > 4 within 10000 secs).

5 Acknowledgments

This material is based upon work supported by the DARPA/IPTO COORDINATORs program and the Air Force Research Laboratoryunder Contract No. FA875005-C-0030.The views and conclusions contained in this document are those of the authors, and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the U.S. Government.