Efficient sensor network planning based on approximate potential games

Abstract

This article addresses information-based sensing point selection from a set of possible sensing locations. A potential game approach has been applied to addressing distributed decision making for cooperative sensor planning. For a large sensor network, the local utility function for an agent is difficult to compute, because the utility function depends on the other agents’ decisions, while each sensing agent is inherently faced with limitations in both its communication and computational capabilities. Accordingly, we propose an approximation method for a local utility function to accommodate limitations in information gathering and processing, using only a part of the decisions of other agents. The error induced by the approximation is also analyzed, and to keep the error small, we propose a selection algorithm that chooses the neighbor set for each agent in a greedy way. The selection algorithm is based on the correlation between one agent’s and the other agents’ measurement selection. Furthermore, we show that a game with an approximate utility function has an $ϵ -$ equilibrium and the set of the equilibria include the Nash equilibrium of the original potential game. We demonstrate the validity of our approximation method through two numerical examples on simplified weather forecasting and multi-target tracking.

Keywords

Sensor networks distributed sensor planning mutual information potential game approximate utility

Introduction

The goal of cooperative sensor network planning problems is to select the sensing locations for a sensor network so that the measurement variables taken at those locations give the maximum information about the variables of interest. This problem can be formulated as an optimization problem with the global objective function of mutual information between the measurement variables and the variables of interest.^1–9 For the distributed/decentralized implementation of the optimization problem, there are two main research directions. The two directions can be differentiated by the number of steps required to solve a local optimization problem for each agent until a solution is obtained. One direction can be described as a single-run algorithm, which includes local greedy and sequential greedy decisions.^4,7 While these greedy algorithms are simple to implement, and especially a sequential greedy algorithm guarantees the worst-case performance when the objective function satisfies submodularity. However, they are subject to some limitations. Since each agent selects the sensing locations by solving only one problem, these single-run algorithms do not fully take advantage of possible information flows, and thus the decisions can be arbitrarily suboptimal. The other direction is an iterative algorithm, which generates a sequence of solutions to converge to an approximate optimal solution.^1,3,10 An iterative method solves the optimization problem approximately at first and then more accurately with an updated set of information as the iterations progress.¹¹ A game-theoretic method is one of the iterative algorithms, which finds a solution through a decision-making process called a repeated game, that is, the same set of games being played until converging to a solution. Especially, a potential game approach provides a systematic framework for designing distributed implementation of multi-agent systems and many learning algorithms that guarantees convergence to an optimal solution.^12–16

In Choi and Lee,¹ we adopted a potential game approach to a sensor network planning. Potential games have been applied to many multi-agent systems for distributed implementation due to their desirable static properties (e.g. existence of a pure strategy Nash equilibrium) and dynamic properties (e.g. convergence to a Nash equilibrium with simple learning algorithms).^12,17 The formulation of a multi-agent problem as a potential game consists of two steps: (1) game design in which the agents as selfish entities and their possible actions are defined and (2) learning design which involves specifying a distributed learning algorithm that leads to a desirable collective behavior of the system.² For game design, we proposed the conditional mutual information of the measurement variables conditioned on the other agents’ decisions as a local utility function for each agent. This conditional mutual information is shown to be aligned with the global objective function for a sensor network, which is mutual information between the whole sensor selection and the variables of interest. For a learning algorithm, joint strategy fictitious play (JSFP) is adopted. With these two design steps, we showed that the potential game approach for distributed cooperative sensing provides better performance than other distributed/decentralized decision-making algorithms, such as the local greedy and the sequential greedy algorithms.

However, this conditional mutual information–based local utility function may incur significant computational burden, in particular when the random entities of interest take non-Gaussian distributions and/or the size of sensor network is large, since the conditional distribution of local measurement variables conditioned on all other agents’ decisions are needed to be quantified. The dependency of the local utility on all other agents’ decisions may also lead to substantial communication overload over the network. Therefore, it is desirable to use an approximate local utility function that can capture the key dependency structure in the mutual information without losing the computational tractability.

One way of approximation is to introduce some notion of neighbors, only the decisions of which are considered in the calculation of an agent’s local utility function; this work particularly focuses on presenting approximation schemes of this fashion and verifying the effectiveness of them. We first propose a simple neighbor selection algorithm based on network topology, whose preliminary concept was suggested in our previous work.¹⁸ Building upon this naive selection method, we propose a greedy selection method that considers the correlation structure of the information space in which the cooperative sensing decision is made. Then, theoretical properties of this type of approximation schemes in terms of closeness to a Nash equilibrium are analyzed and discussed. Two numerical examples on multi-target tracking in the joint multi-target probability density (JMPD) framework and on an idealized weather sensor targeting are presented to demonstrate the feasibility and validity of our approximation algorithms. While the preliminary version of the proposed methodology was reported in Lee and Choi,¹⁹ this article includes theoretical analysis of the proposed approximation schemes and also an additional numerical case study.

The rest of the article is organized as follows. In the “Sensor network planning problems” section, we give an overview of the sensor network planning problem. In the “Sensor network planning as a potential game” section, we present a background for a game-theoretic approach and the problem formulation using a potential game. We describe our approximation algorithm to address computational and communication issues of the approach in the “Approximate local utility design” section. Simulated examples are presented in the “Numerical examples” section.

Sensor network planning problems

This section describes a sensor network planning problem. A sensor network model is defined and provides a formulation as an optimization problem with a global objective function using mutual information.

Sensor network model

The primary task of a sensor network is to collect information from a physical environment in order to estimate the variables of interest, called target states. The target states $x_{t}$ are the set of variables of interest we want to know through the measurements. They are a part of the state variables representing the physical environment (see Figure 1). In a problem of our concern, the physical environment is represented with a finite set of measurable states, $x_{S} = [x_{s_{1}}, x_{s_{2}}, \dots, x_{s_{M}}]$ and the target states $x_{t}$ in spatial-temporal space. The subscript $S = {s_{1}, s_{2}, \dots, s_{M}}$ denotes a set of possible sensing locations for a sensor network and is referred to as a search space, and each element $x_{s}$ represents the state variable at the sensing location $s \in S$ .

Figure 1.

A graphical model for representing probabilistic relationships between states and measurement variables.

We consider a sensor network consisting of $N$ sensing agents deployed in the search space. A sensing agent can be a vehicle carrying sensors on it, such as an unmanned aerial vehicle (UAV). In the case of sensor nodes installed at fixed locations, a sensing agent can be considered as a virtual agent that selects a set of sensor nodes to turn on. Due to the dynamic constraints on the sensing agents, the search space for each sensing agent is a subset of the whole search space $S_{i} \subset S$ . For a mobile sensor network, the search space for each sensing agent can be obtained by discretizing the search space which is available at the next time step.

The sensor measurements for the ith agent at the sensing point $s_{i} \in S_{i}$ are a function of the state variable at the point and the variables of interest

z_{s} = h (x_{s}, x_{t}) + w_{s}, w_{s} ~ N (0, R_{s})

(1)

where $w_{s}$ is white noise uncorrelated with any other random variables. The observation function $h (\cdot)$ could be a nonlinear or linear mapping of the states and the target states. In a target tracking problem, the variables of interest are the location of the target, and if sensors observe the bearing or range to the target, then the observation function $h (\cdot)$ is expressed as a function of relative geometry of s and the target location $x_{t}$ . In a weather forecasting problem, $h (\cdot)$ depends only on the state variable itself at the sensing location $s$ , such as temperature and pressure, then the observation model becomes $z_{s} = x_{s} + w_{s}$ .

Since the target states $x_{t}$ are correlated with the states in the search space and the sensors make observations of the states in the search space corrupted with some noise, sensor measurements are correlated with the target states and have information about the target. The correlation between the target states and the other states in a search space can be expressed as a joint probability distribution $p (x_{t}, x_{S})$ of two sets of random variables, $x_{t}$ and $x_{S}$ . Accordingly, the correlation between the target states and the measurements can be represented by the joint probability distribution $p (x_{t}, z_{S})$ . To obtain the probability distribution of whole states, the states are represented with a probabilistic model, and moreover if the states evolve with time, we also should establish a dynamic model of the states. With the models related to the states, a measurement model will give an expression for the joint probability distribution of the target states and the measurement.

Sensor planning problem for maximum information

The goal of sensor network planning problems is to find out the optimal sensing locations that maximize the information reward about the target states. Here, the information reward can be thought of as a reduction in the uncertainty of the variable of interest due to the information included in the measurement variables. This uncertainty reduction is quantified with mutual information, which is the difference between the prior and posterior entropy of $x_{t}$ conditioned on $z_{s}$ ²⁰

I (x_{t}; z_{s}) = H (x_{t}) - H (x_{t} | z_{s})

(2)

where

H (x_{t}) = - \int p (x_{t}) \log p (x_{t}) d x_{t}

(3)

H (x_{t} | z_{s}) = - \int p (x_{t}, z_{s}) \log p (x_{t} | z_{s}) d x_{t} d z_{s}

(4)

$H (x_{t})$ is the entropy of the target states distribution, $H (x_{t} | z_{s})$ is the conditional entropy of the distribution when conditioning on the measurements, and $I (x_{t}; z_{s})$ is the mutual information between the target states and the measurements. The entropy of a random variable is a metric of its uncertainty. As shown in the above definition, the entropy is not dependent on the value of the random variable itself but rather depends on the shape of the distribution. In the case of a Gaussian distribution, the entropy is computed by the determinant of the covariance matrix $P (x_{t})$ , not using its mean value

H (x_{t}) = \frac{n_{t}}{2} \log (2 π e) + \frac{1}{2} \log (| P (x_{t}) |)

(5)

where $n_{t}$ is the dimension of the random vector $x_{t}$ . When the states are jointly Gaussian and the measurement model is linear and the observation noise is Gaussian, then the mutual information can be expressed with the prior and posterior covariance matrices

I (x_{t}; z_{s}) = \frac{1}{2} \log (| P (x_{t}) |) - \frac{1}{2} \log (| P (x_{t} | z_{s}) |)

(6)

Since a sensor network has limited resources, the system should select the set of sensing points that give the maximum information about the target states to reduce the number of observations. Therefore, a sensor network planning problem can be stated as selecting the most informative set of sensing points $s_{1 : N} = {s_{1}, s_{2}, \dots, s_{N}}$ over the search space $S$

s_{1 : N}^{*} = \arg \max_{s_{1 : N} : s_{i} \in S_{i}} I (x_{t}; z_{s_{1 : N}})

(7)

Note that ith sensing location $s_{i}$ is selected from its designated region $S_{i}$ . $z_{s_{1 : N}} = [z_{s_{1}}, \dots, z_{s_{N}}]$ is a random vector that represents the measurement variables taken at the locations $s_{1 : N} \subset S$ . In a centralized approach, the problem is a combinatorial optimization: it computes the mutual information for every combination of sensing points and then chooses the set giving the maximum mutual information. Thus, the computational burden increases exponentially with the number of sensing agents and the size of the search space. To address this combinatorial computational complexity, we proposed a potential game-based approach and showed the validity of the proposed method through numerical examples. In the following section, we will review a game-theoretic framework for cooperative sensor planning and analyze the complexity of this formulation.

Sensor network planning as a potential game

Potential games are applied to many engineering optimization problems (such as cooperative control²¹ and resource allocation²²) due to their static (existence of Nash equilibrium) and dynamic properties (simple learning algorithm).¹⁷ This section provides the required game-theoretic background used to develop the results in this article and describes a potential game formulation of a sensor network planning problem. Finally, we present limitations in applying the approach to a large sensor network.

Game-theoretic architecture

Consider a finite game in strategic form consisting of three components:²³

A finite set of players (agents): $N = {1, 2, \dots, N}$ .

Strategy spaces: a finite set of actions (strategies) $S_{i}$ , for each player $i \in N$ .

Utility functions: a utility (payoff) function $U_{i} : S \to R$ , for each player $i \in N$ .

Accordingly, a finite strategic-form game instance is represented by the tuple $〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N} 〉$ . In this setting, each player has an action set that the player can select and has a preference structure over the actions according to its utility function $U_{i}$ . A joint strategy space of a game is denoted by $S = \underset{i \in N}{Π} S_{i}$ , which represents a set of all possible combinations of actions for all players to choose at a time. $s = (s_{1}, s_{2}, \dots, s_{N}) \in S$ is the collection of strategies of all players, called a strategy profile, where $s_{i} \in S_{i}$ denotes the strategy chosen by player $i \in N$ . For notational convenience, $s_{- i} = (s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{N})$ denotes the collection of actions of players other than player $i$ . With this notation, a strategy profile is expressed as $s = (s_{i}, s_{- i})$ .

A utility function $U_{i} (s_{i}, s_{- i})$ for player $i$ reflects the preference of player $i$ over its possible actions $S_{i}$ . Given other players’ actions, each player would prefer an action that gives the maximum payoff. If every player selects the action with the maximum payoff given other players’ actions and the chosen action is consistent with the beliefs that other players assumed about the player’s action, and it is also true for all the players, then no player would change his action in this strategy profile. This follows a solution concept in a non-cooperative game, a Nash equilibrium. Formally, a strategy profile $s^{*} \in S$ is a pure Nash equilibrium if

U_{i} (s_{i}, s_{- i}^{*}) - U_{i} (s_{i}^{*}, s_{- i}^{*}) \leq 0

(8)

for every $s_{i} \in S_{i}$ and every player $i \in N$ . A Nash equilibrium is a strategy profile in which no player can improve its payoff by deviating unilaterally from its profile.

A potential game is a non-cooperative game in which the incentive of the players changing their actions can be expressed by a single function, called the potential function. That is, that the player tries to maximize its utility is equivalent to maximizing the global objective for a set of all the players.²⁴

Definition 1

A finite non-cooperative game $G = 〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N} 〉$ is a potential game if there exists a scalar function $ϕ : S \to R$ such that

U_{i} ({s'}_{i}, s_{- i}) - U_{i} ({s ″}_{i}, s_{- i}) = ϕ ({s'}_{i}, s_{- i}) - ϕ ({s ″}_{i}, s_{- i})

(9)

for every $i \in N$ , ${s'}_{i}, {s ″}_{i} \in S_{i}$ , and $s_{- i} \in S_{- i}$ . The function $ϕ$ is referred to as a potential function of the game $G$ .

The property of a potential game in equation (9) is called a perfect alignment between the potential function and the player’s local utility functions. In other words, if a player changes its action unilaterally, the amount of change in its utility is equal to the change in the potential function.

Potential games have two important properties.¹⁷ The first one is that the existence of pure strategy Nash equilibrium is guaranteed. Since in a potential game the joint strategy space is finite, there always exists at least one maximum value of the potential function. This strategy profile maximizing the potential function locally or globally is a pure Nash equilibrium. Hence, every potential game possesses at least one pure Nash equilibrium. The second important property is the presence of well-established learning algorithms to find a Nash equilibrium by repeating a game. Many learning algorithms for potential games are proven to have guaranteed asymptotic convergence to a Nash equilibrium.²¹

In this article, our main focus is to approximate utility functions of a potential game. To address strategy profiles in a near potential game with approximate local utility functions, a near Nash equilibrium is introduced. A strategy profile $s^{ϵ}$ is an $ϵ - equilibrium$ if

U_{i} (s_{i}, s_{- i}^{ϵ}) - U_{i} (s_{i}^{ϵ}, s_{- i}^{ϵ}) \leq ϵ

(10)

for every $s_{i} \in S_{i}$ and every player $i \in N$ . In a Nash equilibrium, every player chooses the action that gives the payoff equal to or greater than the payoffs for choosing other actions. In a near Nash equilibrium, there can be an action which gives a better payoff by no more than \epsilon. When \epsilon is equal to zero, an $ϵ - equilibrium$ is a Nash equilibrium.

Cooperative sensing as a potential game

From a game-theoretic perspective, each sensing agent is considered a player in a game who tries to maximize its own local utility function, $U_{i} (s_{i}, s_{- i})$ , where $s_{i}$ is the set of sensing locations for sensor $i$ , and $s_{- i}$ represents the set of sensing locations other than sensor i’s selections. In our previous work,¹ we showed that the conditional mutual information of sensor i’s measurements conditioned on the other agents’ sensing decisions leads to a potential game with a global objective function

ϕ (s_{i}, s_{- i}) = I (x_{t}; z_{s_{i}}, z_{s_{- i}}) = I (x_{t}; z_{s_{1 : N}})

(11)

The local utility function can be represented by

U_{i} (s_{i}, s_{- i}) = I (x_{t}; z_{s_{i}} | z_{s_{- i}})

(12)

With this local utility function, the designed potential game is solved by repeating the game for $t \in {0, 1, 2, \dots}$ . At each time step $t$ , each agent $i \in N$ chooses an action according to a specific learning rule (such as fictitious play, better/best response, and log-linear learning²⁵), which is generally represented as a probability distribution $p_{i} (t)$ over i’s action set $S_{i}$ . $p_{i} (t)$ is obtained from the utility values of agent $i$ based on the other agents’ decisions up to the previous stages. The general structure of learning algorithms is summarized in Algorithm 1.

Algorithm 1:

Learning Algorithm $(U_{i}, F_{i})$

Choose an initial action with some specific rule.
while Convergence criteria not satisfied do
for

i \in {1, \dots, N}

do
Update the strategy according to the learning rule,

p_{i} (t) = F_{i} (s (0), \dots, s (t - 1); U_{i})

Choose an action according to

p_{i} (t)

end for
end while

The learning algorithms are varied according to a specific update rule $F_{i}$ . To solve a sensor network planning problem, we adopted JSFP¹² as the learning rule. In JSFP, each agent assumes that other agents play randomly according to the joint empirical frequencies, $f_{- i} (s_{- i}; t)$ , which represents the frequency with which all players but $i$ have selected a joint action profile $s_{- i}$ up to stage $t - 1$ . In a strategy update step at each stage $t$ , a player computes the expected local utility for action $s_{i} \in S_{i}$ based on the empirical frequency distribution of its opponents as

U_{i} (s_{i}; t) = E_{f_{- i} (t)} [U_{i} (s_{i}, s_{- i})]

In Marden et al.,¹² it is shown that the expected utilities $U_{i} (s_{i}; t)$ for each $s_{i} \in S_{i}$ can be expressed with a simple recursion rule

\begin{matrix} U_{i} (s_{i}; t) = \frac{1}{t} \sum_{τ = 0}^{t - 1} U_{i} (s_{i}, s_{- i} (τ)) \\ = \frac{t - 1}{t} U_{i} (s_{i}; t - 1) + \frac{1}{t} U_{i} (s_{i}, s_{- i} (t - 1)) \end{matrix}

(13)

Having computed $U_{i} (s_{i}; t)$ for all $s_{i} \in S_{i}$ , agent $i$ selects the best action that gives the maximum expected utility. Although JSFP does not guarantee convergence to a pure Nash equilibrium even for a potential game, a JSFP with inertia was proven to reach a Nash equilibrium. In our previous work,¹ we showed that the JSFP for a sensor network planning problem can be converged to a Nash equilibrium by using¹² (Theorem 2.1) and specifying the termination condition of the algorithm.

Computational complexity analysis

As described in Choi and How,⁶ the potential game-based approach to cooperative sensor planning enables one to find out the informative set of sensing locations with much less computation than an exhaustive search. However, a conditional mutual information conditioned on the other agents’ sensing locations has limitations when applied to a large sensor network, because every agent needs information about the decisions made by the other agents in the previous stage. If the communication network is strongly connected, one agent’s decision can be forwarded to all the other agents, and then the next stage can be initiated after this information exchange has happened. This decision sharing among all the agents incurs substantial communication cost/traffic. In addition to this communicational burden on a network, the conditional mutual information itself increases computation load on each agent’s processing unit for obtaining utility values. In this section, we will analyze the computational complexity for JSFP algorithm applied to sensor network planning in more detail.

As shown in Algorithm 1, the distributed solution of a potential game is obtained by repeating a one-shot game until it converges to equilibrium. In JSFP, at each stage $t$ , agent $i \in N$ updates its expected utility values $U_{i} (s_{i}; t)$ over the possible actions $s_{i} \in S_{i}$ , and then chooses the best action that gives the maximum expected utility. To obtain $U_{i} (s_{i}; t)$ , an agent should first compute the utility values $U_{i} (s_{i}, s_{- i} (t - 1))$ based on the previous decisions of the other agents as shown in equation (13) and then update the expected utility with the weighted sum of the previous average utility $U_{i} (s_{i}; t - 1)$ and the utility $U_{i} (s_{i}, s_{- i} (t - 1))$ obtained from a one-step look-back scheme. The resulting computation time for agent $i$ to reach a solution is then

{\hat{T}}_{i} = L N_{S_{i}} N_{p_{i}} T_{U_{i}}

(14)

where $L$ is the number of repeating a game until convergence, $N_{S_{i}}$ is the size of an action set $S_{i}$ , and $N_{p_{i}}$ is the number of computations of the local utility for each play of a game. $T_{U_{i}}$ corresponds to the time taken to calculate the local utility function for a given strategy profile. Here, $N_{p_{i}}$ is constant for the specific learning algorithm and $L$ is related to the convergence rates of the learning algorithms for a potential game. Although its relation to the game size has not been fully established for a general potential game, it has been shown that many of the learning rules converge to a solution within reasonable time for specific potential game structures²⁶ and especially JSFP applied to a sensor network planning problem has shown to converge to a close-to-optimal solution with computation cost less than greedy strategies.¹ Thus, we focus on the term $T_{U_{i}}$ to analyze the computation time for a potential game approach.

The main reason for the computation load of $T_{U_{i}}$ is due to conditioning the decisions from all of the agents. For example, in case of a multivariate normal distribution, a local utility function (equation (12)) can be rewritten using the backward scheme in Choi and How⁶ and the mutual information for Gaussian variables (equation (6)) with additive white Gaussian measurement noise

\begin{matrix} U_{i} (s_{i}, s_{- i}) \\ = I (x_{t}; z_{s_{i}} | z_{s_{- i}}) = H (z_{s_{i}} | z_{s_{- i}}) - H (z_{s_{i}} | x_{t}, z_{s_{- i}}) \\ = \frac{1}{2} \log | P (z_{s_{i}} | z_{s_{- i}}) | - \frac{1}{2} \log | P (z_{s_{i}} | x_{t}, z_{s_{- i}}) | \\ = \frac{1}{2} \log | P (z_{s_{i}}) - P (x_{s_{i}}, x_{s_{- i}}) P {(z_{s_{- i}})}^{- 1} P (x_{s_{- i}}, x_{s_{i}}) | \\ - \frac{1}{2} \log | P (z_{s_{i}} | x_{t}) - P (x_{s_{i}}, x_{s_{- i}} | x_{t}) P {(z_{s_{- i}} | x_{t})}^{- 1} P (x_{s_{- i}}, x_{s_{i}} | x_{t}) | \end{matrix}

(15)

where $P (z_{s}) = P (x_{s}) + R_{s}$ and $P (z_{s} | x_{t}) = P (x_{s} | x_{t}) + R_{s}$ denote the covariance matrices of measurement variables at sensing selections $s$ , and $R_{s}$ denotes the measurement noise covariance. As shown above, the computation of the inverse of matrices relating to the other agents’ decisions is needed to obtain a local utility function. Inversion of $n \times n$ symmetric positive matrix requires approximately $(2 / 3) n^{3}$ floating-point operations,²⁷ and thus computation time for the conditional mutual information increases proportional to the cubic of the number of sensing agents $(O (N^{3}))$ . For a large sensor network, the computation of a utility function for an agent becomes intractable. Therefore, to keep the game approach scalable as the number of sensors increases, we need to approximate the local utility function.

Approximate local utility design

In this section, an approximation method is proposed to reduce the computational and communicational burden of computing the local utility function. The method modifies the form of a local utility function itself by removing some of the conditioning variables, which represent the decisions of other agents.

Approximate utility function

The proposed approximation method for computing the local utility function is to reduce a number of the conditioning variables using the correlation structure of the information space, making the local utility function depend on the part of the decisions

{\tilde{U}}_{i} (s_{i}, s_{N_{i}}) = I (x_{t}; z_{s_{i}} | z_{s_{N_{i}}})

(16)

where $s_{N_{i}}$ is the set of the measurement selections correlated with sensing agent i’s decision, referred to as a neighbor set of sensing agent $i$ , and $z_{s_{N_{i}}}$ denotes the corresponding measurement variables. The neighbor set $s_{N_{i}}$ is a subset of $s_{- i}$ . To reduce the computation, the neighbor set should be a strict subset of $s_{- i}$ . In some applications, this allows for less memory requirement for each agent (as, for example, an agent only needs to carry covariance matrix for the random vector associated with its own and neighboring agents’ sensing regions). The following lemma shows the quantification of the error incurred by the approximation.

Lemma 1

Let $Δ_{U_{i}}$ denote the difference between the approximate local utility for sensor $i$ and the true value of equation (12), then

Δ_{U_{i}} = c_{1} (s_{- i}) - I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}})

(17a)

= c_{2} (s_{- i}) + I (z_{s_{i} \cup s_{N_{i}}}; z_{s_{- N_{i}}}) - I (z_{s_{i} \cup s_{N_{i}}}; z_{s_{- N_{i}}} | x_{t})

(17b)

where $s_{- N_{i}} \overset{Δ}{=} s_{1 : N} \ {s_{i} \cup s_{N_{i}}}$ is the set of the chosen sensing locations of the sensors other than sensor $i$ and its neighbors. $c_{1} (s_{- i})$ and $c_{2} (s_{- i})$ encompass the terms that are constant with respect to the ith sensing agent’s selection; thus, they do not affect the preference structure of sensor $i$ .

Proof

The conditional mutual information of equations (12) and (16) can be expanded using chain rule²⁰

\begin{matrix} Δ_{U_{i}} = I (x_{t}; z_{s_{i}} | z_{s_{N_{i}}}) - I (x_{t}; z_{s_{i}} | z_{s_{- i}}) \\ = [I (x_{t}; z_{s_{1 : N}}) - I (x_{t}; z_{s_{N_{i}}}) - I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}})] \\ - [I (x_{t}; z_{s_{1 : N}}) - I (x_{t}; z_{s_{- i}})] \end{matrix}

(18)

Canceling out common terms results in the first equation (17a). To obtain the second equation (17b), a preliminary result is given for exchanging of conditioning variables in mutual information³

I (x_{a}; x_{b} | x_{c}) = I (x_{a}; x_{b}) - I (x_{a}; x_{c}) + I (x_{a}; x_{c} | x_{b})

Equation (17b) follows by rewriting the third term of equation (18) using the above property

\begin{matrix} Δ_{U_{i}} = I (x_{t}; z_{s_{- i}}) - I (x_{t}; z_{s_{N_{i}}}) - I (x_{t}; z_{s_{- N_{i}}}) \\ + I (z_{s_{i} \cup s_{N_{i}}}; z_{s_{- N_{i}}}) - I (z_{s_{i} \cup s_{N_{i}}}; z_{s_{- N_{i}}} | x_{t}) \\ = c_{2} (s_{- i}) + I (z_{s_{i}}, z_{s_{N_{i}}}; z_{s_{- N_{i}}}) - I (z_{s_{i}}, z_{s_{N_{i}}}; z_{s_{- N_{i}}} | x_{t}) \end{matrix}

Remark 1

In a target tracking example, the difference (equation (17b)) between the approximate local utility and the true local utility can be simplified as

Δ_{U_{i}} = c (s_{- i}) + I (z_{s_{i} \cup s_{N_{i}}}; z_{s_{- N_{i}}})

Applying the assumption that the measurements are conditionally independent given the target states, the last term in equation (17b) becomes zero, then the error can be represented with mutual information between the sensing selections related with sensing agent $i$ and the others. In this case, the sensing locations that are correlated with sensing agent $i$ ’s search space are selected as a neighbor set of sensing agent $i$ regardless of the variables of interest.

Remark 2

In cooperative games, the common terms $c_{1} (s_{- i})$ and $c_{2} (s_{- i})$ for all the strategies of agent $i$ in equation (17) do not affect its preference structure, because the payoff difference $[U_{i} (s'_{i}, s_{- i}) - U_{i} ({s ″}_{i}, s_{- i})]$ quantifies by how much agent $i$ prefers strategy $s'_{i}$ over strategy ${s ″}_{i}$ given that the other agents choose the actions $s_{- i}$ .¹⁷ Note that a Nash equilibrium is defined in terms of payoff differences, suggesting that games with identical preference structure share the same equilibrium sets. Thus, if the sum of the last two terms in equation (17) is zero, a game with approximate local utility functions will have the same equilibrium sets as a game with a true value of equation (12).

To keep the error incurred by the approximation small, we propose two neighbor selection algorithms: geometry-based and correlation-based. These methods differ in the definition of the distance between sensing points. In geometry-based selection, the distance between two sensing points is the spatial distance as the name suggests. It can be obtained simply by calculating the Euclidean distance between the sensing locations. On the other hand, the correlation-based method uses the correlation between measurement variables taken at the sensing points as a measure of closeness. In most cases, the geometric closeness of the sensing points can be translated into correlation between the measurements taken at those locations. That is, the more closely located sensors are, the more correlated their measurements. Therefore, the geometry-based approach is sufficient for neighbor selection in many applications. However, when the target states exhibit highly nonlinear spatiotemporal dynamics, the closeness in sensing locations has nothing to do with the correlation between the corresponding measurements. Thus, we propose the correlation-based selection algorithm to address this nonlinearity issue.

Geometry-based neighbor selection algorithm

Intuitively, the simplest way to determine the neighbor set for each agent is by defining the neighborhood by closeness in geometric distance. In many cases, such as monitoring spatial phenomena as in Krause et al.,⁴ geometric closeness of two sensing locations can be translated into correlation between corresponding measurement variables taken at those locations. In this section, we propose a selection algorithm in which neighbors are selected as agents located within some range from each agent. We refer to this selection method a geometry-based neighbor selection.

One technical assumption made in this section is that the communication network can be represented as a connected undirected graph, $G = (N, E)$ . In this graph, the closeness is defined by the number of hops if multi-hop schemes are used in inter-agent communication. Then, the neighbors of agent $i$ can be represented as $N_{i} \overset{Δ}{=} {j : (i, j) \in E}$ . It is beneficial to limit the neighbors in this way, because the geometry-based selection can obtain both computational and communicational efficiency at the same time. To find out how the solution property of the game is changed, we will first investigate whether or not the localized utility function in equation (16) is aligned with the global potential $ϕ (s_{i}, s_{- i})$ in equation (11). Using the expression for $Δ_{U_{i}}$ in equation (17), then difference in the utility between two admissible sensing actions $s_{i'}$ and $s_{i ″}$ can be expressed as

\begin{matrix} {\tilde{U}}_{i} ({s'}_{i}, s_{- i}) - {\tilde{U}}_{i} ({s ″}_{i}, s_{- i}) = [ϕ ({s'}_{i}, s_{- i}) - ϕ ({s ″}_{i}, s_{- i})] \\ - \underset{Difference in potentiality}{\underset{︸}{[I (x_{t}; z_{s_{- N_{i}}} | z_{{s'}_{i} \cup s_{N_{i}}}) - I (x_{t}; z_{s_{- N_{i}}} | z_{{s ″}_{i} \cup s_{N_{i}}})]}} \end{matrix}

(19)

From equation (19), a game defined by the local utility in equation (16) is not necessarily a potential game with potential function in equation (11), because the last bracket termed difference in potentiality does not vanish in general. (This statement does not exclude possibility of a potential game with the same local utility function for a different potential function.) Instead, further analysis can be done to identify the condition under which this localized version of the game constitutes a potential game aligned with the objective function of the cooperative sensing.

The last term in equation (19) can also be represented as

I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}}) = \underset{Effect of x_{t} on conditional dependency of i and - N_{i}}{\underset{︸}{I (z_{s_{i}}; z_{s_{- N_{i}}} | z_{s_{N_{i}}}) - I (z_{s_{i}}; z_{s_{- N_{i}}} | x_{t}, z_{s_{N_{i}}})}} + c_{3} (s_{- i})

(20)

by using equation (16). Noting that the last term in equation (20) does not depend on agent i’s action, the difference in potentiality represents how significantly the verification variable $x_{t}$ changes the conditional dependency between an agent (i.e. $z_{s_{i}}$ ) and further agents (i.e. $z_{s_{- N_{i}}}$ ) conditioned on the nearby agents (i.e. $z_{s_{N_{i}}}$ ). One meaningful case is when $I (z_{s_{i}}; z_{s_{- N_{i}}} | z_{s_{N_{i}}}) = I (z_{s_{i}}; z_{s_{- N_{i}}} | x_{t}, z_{s_{N_{i}}}) = 0$ .

Proposition 1

If $z_{s_{i}}$ and $z_{s_{- N_{i}}}$ are conditionally independent of each other conditioned on $z_{s_{N_{i}}}$ , for all $s_{i} \in S_{i}$ for all $i$

I (z_{s_{i}}; z_{s_{- N_{i}}} | z_{s_{N_{i}}}, y) = 0

for any $y$ . Therefore, the localized utility in equation (19) constitutes a potential game with the global potential $ϕ$ in equation (11).

Proof

Proof is straightforward by noting that $I (a; b | c) = 0,$ if $a$ and $b$ are conditionally independent of each other conditioned on $c$ .

In other words, if $z_{s_{i}}$ is conditionally independent of $z_{s_{- N_{i}}}$ , then once $z_{s_{N_{i}}}$ is known there is no information that can be additionally obtained from $z_{s_{- N_{i}}}$ to have better idea about $z_{s_{i}}$ . Furthermore, the statement in Proposition 1 can be further extended as follows.

Proposition 2

If there exists $K$ such that $z_{s_{i}}$ are conditionally independent of outside of its Kth order neighbors when conditioned on the up to Kth order neighbors, $U_{k = 1}^{K} z_{s_{N_{i}^{k}}}$ , where $N_{k}^{i}$ is kth order neighbor, then the localized utility function

{\tilde{U}}_{i}^{K} = I (x_{t}; z_{s_{i}} | z_{s_{N_{i}^{1}}}, \dots z_{s_{N_{i}^{K}}})

(21)

constitutes a potential game with global potential (equation (11)).

There are some contexts that the conditional independence condition is at least approximately satisfied. Many physical phenomena are associated with some notion of time and length scale. If the correlation length scale of the motion of interest is order of inter-agent distance, there will be no too significant dependency between agents far from each other; then, the conditional independence assumption in the previous propositions can be satisfied. This statement certainly is domain and problem dependent; it is not appropriate to make some general statement of satisfaction of the conditional independence assumption.

Correlation-based neighbor selection algorithm

As shown in equation (17), the error incurred by the approximation of the local utility function can be considered in two ways. In the first equation, the error is the mutual information between the target states and the measurement variables which is not in the neighbor set of agent $i$ . If after conditioning on the measurement selections of sensing agent $i$ and its neighbors, the measurement variables at $s_{- N_{i}}$ have little information about the target variables, and the error becomes small enough to approximate the local utility function with sufficient accuracy. That is, the measurement variables at $s_{- N_{i}}$ have information about the target states which is already included in the measurements at $s_{i}$ and $s_{N_{i}}$ .

For the second way, the error can be considered as the difference between the prior mutual information and the posterior mutual information conditioning on the target states. This amounts to the mutual information of the variables at $s_{i} \cup s_{N_{i}}$ and $s_{- N_{i}}$ projected onto the subspace generated by the target states.²⁸

To make the error sufficiently small, the method to select the neighbor set for each agent should be determined. In most cases, measurement variables taken at close locations are correlated with each other, and measurements taken at distant locations from sensing agent i’s search space have little correlation with agent i’s selection. Thus, each sensing agent can approximate its utility function by considering the neighbor set consisting of sensing agents close to each agent. However, for example, in sensor planning for weather forecasting, the assumption that closeness in Euclidean distance means correlation between variables is broken. Weather dynamics is highly nonlinear, and thus, the neighbor set should be chosen in different ways from usual cases. For nonlinear target dynamics, such as a weather forecast example, a sequential greedy scheme is proposed. Every sensing agent conducts the greedy scheme to determine its neighbor set. The algorithm simply adds sensing agents in sequence, choosing the next sensor which has maximum mutual information about the target states conditioned on the measurement variables of a sensing agent’s search space and its pre-selected neighbors. Using the first error bound in equation (17), the algorithm greedily selects the next sensing agent $j$ that maximizes

I (z_{s_{j}}; x_{t} | z_{s_{i} \cup s_{N_{i}}}) = H (z_{s_{j}} | z_{s_{i} \cup s_{N_{i}}}) - H (z_{s_{j}} | z_{s_{i} \cup s_{N_{i}}}, x_{t})

(22)

Algorithm 2 shows the greedy neighbor selection algorithm.

Algorithm 2:

Neighbor Selection Algorithm for Weather Forecast Example $(i, P_{0} = P (z_{S_{- i}}), P_{t} = P (z_{S_{- i}} | x_{t}))$

s_{N_{i}} : = \emptyset

s_{- N_{i}} : = S_{1 : N} \ S_{i}

3: for

j \in {1, \dots, n}

do
4: for

y \in s_{- N_{i}}

do
5:

e_{y} = \log (\frac{P_{0} (z_{y})}{P_{t} (z_{y})})

6: end for
7:

y^{*} = \arg \max_{y \in s_{- N_{i}}} e_{y}

s_{N_{i}} : = s_{N_{i}} \cup y^{*}

s_{- N_{i}} : = s_{- N_{i}} \ y^{*}

10:

P_{0} = P_{0} (z_{s_{- N_{i}}}) - P_{0} (z_{s_{- N_{i}}}, z_{y^{*}}) P_{0} (z_{y^{*}}, z_{s_{- N_{i}}}) / P_{0} (z_{y^{*}})

11:

P_{t} = P_{t} (z_{s_{- N_{i}}}) - P_{t} (z_{s_{- N_{i}}}, z_{y^{*}}) P_{t} (z_{y^{*}}, z_{s_{- N_{i}}}) / P_{t} (z_{y^{*}})

12: end for

If we leave out measurement variables that have little correlation with the selection of sensor $i$ , we can approximate the local utility function with a small error. This approximation reduces the burden of computation significantly, making the potential game approach to the sensor network planning problem feasible. However, it cannot be guaranteed that the approximate local utility function satisfies the alignment with the global objective; thus, a game with an approximate local utility function may not be a potential game. Fortunately, the bound to the Nash equilibrium of the potential game can be obtained from the difference in local utility functions.

Analysis of approximate potential game

The approximate utility functions cause a change in the preference structure of the players and break the alignment condition for a potential game. It follows that the game cannot guarantee the existence of a pure Nash equilibrium which exists in the potential game with the true utility function. However, if the approximation error in a utility function stays small, we can expect that a game with the approximate utility functions has similar properties to that of the potential game.²⁹ Before presenting the theorem for the equilibria of two games that are close in terms of payoffs, we first introduce the following lemma from Candogan et al.¹⁷

Lemma 2

Consider two games $G = 〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N} 〉$ and $\tilde{G} = 〈 N, {S_{i}}_{i \in N}, {{\tilde{U}}_{i}}_{i \in N} 〉$ , which differ only in their utility functions. If $| U_{i} (s) - {\tilde{U}}_{i} (s) | \leq Δ_{u}$ for every $i \in N$ and $s \in S$ , then every $\tilde{ϵ} - equilibrium$ of $\tilde{G}$ is an $ϵ - equilibrium$ of $G$ for some $ϵ \leq 2 Δ_{u} + \tilde{ϵ}$ (and vice versa).

The difference between $ϵ$ and $\tilde{ϵ}$ is always less than twice the maximum difference of utility functions. This upper bound can be expressed by another measure of the closeness of games: maximum pairwise difference (MPD).²⁹

Definition 2

The MPD between two games $G = 〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N} 〉$ and $\tilde{G} = 〈 N, {S_{i}}_{i \in N}, {{\tilde{U}}_{i}}_{i \in N} 〉$ is defined as

δ_{u} \overset{Δ}{=} \max_{i \in N, s_{i}, s_{i'} \in S_{i}, s_{- i} \in S_{- i}} | (U_{i} (s_{i}, s_{- i}) - U_{i} (s_{i'}, s_{- i})) - ({\tilde{U}}_{i} (s_{i}, s_{- i}) - {\tilde{U}}_{i} (s_{i'}, s_{- i})) |

(23)

The MPD represents the distance between two games in terms of the difference of unilateral utility changes rather than the difference of their utility values. This notion of distance between games identifies a strategic equivalence between them.²⁹ This is because, as mentioned in Remark 2, the preference structure is determined by the amount of the utility improvement due to unilateral deviations of each agent $| U_{i} (s_{i}, s_{- i}) - U_{i} (s_{i'}, s_{- i}) |$ and not by the utility value $U_{i} (s_{i}, s_{- i})$ itself. Then, the inequality of Lemma 2 is expressed as

ϵ \leq δ_{u} + \tilde{ϵ}

(24)

This result comes from the proof of Lemma 3. Let $s^{*}$ be an $\tilde{ϵ} - equilibrium$ of $\tilde{G}$ . Then

\begin{matrix} U_{i} (s_{i}, s_{- i}^{*}) - U_{i} (s_{i}^{*}, s_{- i}^{*}) \leq U_{i} (s_{i}, s_{- i}^{*}) - U_{i} (s_{i}^{*}, s_{- i}^{*}) - ({\tilde{U}}_{i} (s_{i}, s_{- i}^{*}) - {\tilde{U}}_{i} (s_{i}^{*}, s_{- i}^{*})) + \tilde{ϵ} \leq δ_{u} + \tilde{ϵ} \end{matrix}

In case $G$ is a potential game, we refer to $\tilde{G}$ as the approximate potential game of $G$ . Two games that are close to each other in their utilities have similar equilibrium. The lemma shows the extent of how close the $ϵ - equilibria$ of two games are. Specifically, if $G$ has a Nash equilibrium, then the other game has an $ϵ - equilibrium$ , such that $ϵ \leq 2 Δ_{u}$ or $ϵ \leq δ_{u}$ from equation (24). Therefore, if we make a game sufficiently close to the existing game with a Nash equilibrium, then an equilibrium property of an approximate game can be identified. The following theorem shows that the equilibria of two games can be related in terms of the difference in utilities.

Theorem 1

Consider a potential game $G = 〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N} 〉$ and its approximate game $\tilde{G}$ with approximate utility functions ${{\tilde{U}}_{i}}_{i \in N}$ , that is, $\tilde{G} = 〈 N, {S_{i}}_{i \in N}, {{\tilde{U}}_{i}}_{i \in N} 〉$ . Assume that $| U_{i} (s_{i}, s_{- i}) - {\tilde{U}}_{i} (s_{i}, s_{- i}) | \leq Δ_{u}$ for every $i \in N$ and $(s_{i}, s_{- i}) \in S$ . Then every Nash equilibrium of $G$ is an $ϵ - equilibrium$ of $\tilde{G}$ for some $ϵ \leq δ_{u}$ .

Proof

Since a Nash equilibrium is an $ϵ - equilibrium$ with $ϵ = 0$ , the result follows from Lemma 2 and equation (24).

This result implies that the Nash equilibria of a potential game with the true utility function are included in the approximate equilibria of the game with approximate utility functions. That is, if we let the set of $ϵ - equilibrium$ of the game $\tilde{G}$ be ${\tilde{X}}_{ϵ}$ and the set of Nash equilibria of the potential game $G$ be $X_{0}$ , then $X_{0} \subset {\tilde{X}}_{ϵ}$ . Since the potential game has at least one Nash equilibrium, there exists at least one $ϵ - equilibrium$ in the approximate game $\tilde{G}$ . In a special case, Nash equilibria of the potential game can be maintained in its close potential game with approximate utility functions. If the differences in utility for each player between playing its best response and playing the second-best response at a Nash equilibrium are greater than $δ_{u}$ , then Nash equilibria of the potential game can be included in the set of Nash equilibria of the game. More specifically, if for every $s^{*} \in X_{0}$

U_{i} (s_{i}^{*}, s_{- i}^{*}) - U_{i} (s_{i}, s_{- i}^{*}) \geq δ_{u}

(25)

for every $i \in N$ and for every $s_{i} \in S_{i}$ , $s_{i} \neq s_{i}^{*}$ , then every Nash equilibrium of $G$ is a Nash equilibrium of $\tilde{G}$ . In this case, we can guarantee the existence of a Nash equilibrium in the game with approximate utility functions. That is, ${\tilde{X}}_{0} \neq \emptyset$ and $X_{0} \subset {\tilde{X}}_{0}$ , where ${\tilde{X}}_{0}$ is a set of Nash equilibria of $\tilde{G}$ .

Corollary 1

Consider a potential game $G = 〈 N, {S_{i}}_{i \in N}, {U_{i}}_{i \in N}, ϕ 〉$ with global objective function defined in equation (12) and local utility function defined in equation (13) for cooperative sensor network planning and its approximate potential game $\tilde{G} = 〈 N, {S_{i}}_{i \in N}, {{\tilde{U}}_{i}}_{i \in N} 〉$ . Suppose $Δ_{u} = max_{i \in N, s_{i} \in S_{i}} I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}})$ . If for every $s^{*} \in X_{0}$

H (z_{s_{i}} | x_{t}, z_{s_{- i}^{*}}) - H (z_{{s_{i}}^{*}} | x_{t}, z_{s_{- i}^{*}}) \geq 2 Δ_{u}

for every $i \in N$ and for every $s_{i} \in S_{i}$ , $s_{i} \neq s_{i}^{*}$ , then there exists at least one Nash equilibrium in $\tilde{G}$ and $X_{0} \subset {\tilde{X}}_{0}$ .

Proof

$Δ_{u} = \max_{i \in N, s_{i} \in S_{i}} I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}})$ means that the approximation changes the preference structure of $G$ with the error less than $2 Δ_{u}$ by Lemma 1 and Lemma 2. That is, $δ_{u} = 2 Δ_{u}$ . Since

\begin{matrix} U_{i} (s_{i}^{*}, s_{- i}^{*}) - U_{i} (s_{i}, s_{- i}^{*}) = I (z_{s_{i}^{*}}; x_{t} | z_{s_{- i}^{*}}) - I (z_{s_{i}}; x_{t} | z_{s_{- i}^{*}}) \\ = H (z_{s_{i}} | x_{t}, z_{s_{- i}^{*}}) - H (z_{s_{i}^{*}} | x_{t}, z_{s_{- i}^{*}}) \end{matrix}

there exists at least one Nash equilibrium in $\tilde{G}$ and $X_{0} \subset {\tilde{X}}_{0}$ by the above discussion about the set of Nash equilibrium points.

$δ_{u}$ is the maximum difference in utility values except the common terms. After selecting the neighbor set for every agent by conducting Algorithm 2, $Δ_{u}$ is computed by finding out the maximum value $I (x_{t}; z_{s_{- N_{i}}} | z_{s_{i} \cup s_{N_{i}}})$ over the whole sensing agents. When the upper bound for $ϵ$ is not sufficiently small, we can add more neighbors for the agent that gives the maximum value.

We have demonstrated the existence of equilibrium points in the games with approximate utility functions, but there remains an issue about efficiency of the resulting equilibrium points. Candogan et al.²⁹ provided a learning dynamics for a near potential game and showed that convergence to a small neighborhood of the equilibria from the original game can be established. However, we still have an efficiency issue of the equilibria. For a potential game, log-linear learning is shown that it guarantees on the percentage of time that the strategy profile will be at a potential maximizer.³⁰ However, it is not known how quickly this learning dynamics converges to the best solution. In Choi and Lee,¹ we demonstrated the validity and efficiency of the JSFP method through numerical examples. Likewise, we will show the efficiency of the resulting equilibrium with numerical simulations.

Numerical examples

The proposed approximation method is demonstrated on two numerical examples with nonlinear models: sensor management for multi-target tracking and sensing point targeting for weather forecast. In the first example, we apply the localized utility function to a sensor selection problem for multi-target tracking. In target tracking, the sensors gain information about the kinematic state of a group of target and the measurement model is generally nonlinear, such as the range to the target or bearing only measuring Infrared (IR) sensors. A particle filter has been successfully applied to estimating the target states with better performance than Kalman filters. However, computation of mutual information for a particle filter grows exponentially with the number of sensing points; thus, it is impossible to calculate entropy with full information. The first example shows that the approximation method enables a potential game approach to be applied to a sensor planning problem with a large sensor network. Also it demonstrates the efficiency of the geometry-based neighbor selection algorithm, because the geometric distance between sensing points is related with the amount of information about the target states. The other example is sensor targeting in the context of numerical weather forecast. While the first example shows the performance of the approximation local utility itself and the simple neighbor selection method is sufficient to limit the conditioning variables, the weather forecast example allows comparison of two neighbor selection algorithms: a geometry-based method and a correlation-based method. Since the weather dynamics is highly nonlinear, the closeness in sensing locations has nothing to do with the correlation between the corresponding measurements.

Multi-target tracking

To demonstrate performance of the proposed game-theoretic approach under a nonlinear and non-Gaussian sensor model, a multi-target tracking example is investigated. A similar example using the JMPD technique introduced in Kreucher et al.³¹ has been referred.

JMPD is a specialized particle filter method which helps estimate the number of multi-targets and state of each target effectively. JMPD approximates the multi-target state with $N$ particles of $[x_{p}^{i}, w_{i}]$ , which is expressed as follows

x_{p}^{i} = [x_{p, 1}, x_{p, 2}, \dots, x_{p, n_{i}}]

where $x_{p}^{i}$ is estimating multi-target states, $w_{i}$ is a likelihood weight of the particle, $n_{i}$ is the estimated number of targets, and $x_{p, k}$ is a state of the kth target. To realistically design a simulation, each agent is assumed to carry its own particles. Using the JMPD framework, the probability distribution of the multi-target state (which is equivalent to the verification variable) can be approximated as shown below

p (x_{t}) \approx \sum_{i = 1}^{N} w_{i} δ (x_{t} - x_{p}^{i})

In this example, a fixed sensor network tries to estimate the number and states of multi-targets moving within a 2400 m × 2400 m region with nearly constant speed. In this space, image sensors are uniformly arranged to detect targets. Each sensor gives detection (1) or non-detection (0) as a measurement value according to the range-based detection rate as follows

P_{d} (r) = P_{d, 0} e^{- r / R_{0}}

where $r$ is the distance between the nearest target and the sensor, and $P_{d, 0}$ and $R_{0}$ are sensor parameters.

The objective of this sensor problem for the multi-target tracking is finding a set of sensing points maximizing the mutual information about the multi-target states at a given situation. Similarly, as in the next weather forecasting example, each agent needs to evaluate the local utility to obtain a cooperative solution. The local utility and its approximate version can be evaluated by using equations (12) and (16), respectively. Mutual information under a particle filter framework can be computed using the Monte Carlo integration technique below (see Hoffmann and Tomlin³ for more detailed derivation). Here, the computation of the integral is equivalent to a finite sum since the possible measurement is only 0 or 1

H (z_{s}) \approx - \int_{Z} [\sum_{i = 1}^{N} (w_{i} p (z_{s} = z | x_{t} = x_{p}^{i}))] \log [\sum_{i = 1}^{N} (w_{i} p (z_{s} = z | x_{t} = x_{p}^{i}))] d z

(26)

H (z_{s} | x_{t}) \approx - \int_{Z} (\sum_{i = 1}^{N} w_{i} p (z_{s} = z | x_{t} = x_{p}^{i}) \log p (z_{s} = z | x_{t} = x_{p}^{i})) d z

(27)

Note the variables in the equation; local utility each agent evaluates cannot coincide with each other if each agent does not share the same particles. Especially in a situation when agents have poor information about the multi-target, it is highly probable that each agent will have different particle sets. Then each agent will estimate different values of the utility even with the same observation result, interrupting cooperation among sensor networks. However, this problem can be solved easily by assuming that agents have the same random generator and share the same random seed so that they can generate exactly the same pseudorandom numbers.

The proposed game-theoretic method has been tested for two different sensing topologies: six sensors in a 3 × 2 grid and six sensors in a 6 × 1 grid, where each grid corresponds to a 400 m × 400 m region over a 2400 m × 2400 m space, as described in Table 1. Each sensor is located in the center of its grid. A sensor can select maximum $n_{i}$ sensing points, and each sensor can also choose the same sensing points multiple times. None of sensing regions overlap for any two sensors

S_{i} \cap S_{j} = \emptyset, \forall i \neq j

(28)

Table 1.

Topology of multi-target tracking example cases (a × b: a grids in horizontal, b grids in vertical).

Case	$N$	$n_{i}$	$S_{1 : N}$	$S_{i}$
1	6	2	3 × 2	2 × 3
2	6	2	6 × 1	1 × 6

As a simulation scenario, a two-target scenario after one observation with each JMPD step is considered. A detailed situation is described in Figure 2. As shown in the figure, sensors estimate the multi-target states under high uncertainty; thus, proper choice of sensing points becomes important to obtain a large amount of information using the same sensor resources.

Figure 2.

Scenario and sensing points determined by the correlation-based approximate JSFP in each case. Red stars: true positions of multi-targets. Green dots: particles estimating the state of multi-target.

The proposed method is compared with greedy strategies and the JSFP algorithm with full information. The global optimum solution is not evaluated since it is hardly obtained in tractable time under the particle filter framework. Instead, full information JSFP algorithm has been assumed to give a near optimal solution. The compared approaches are (1) greedy strategies in which each agent makes a locally optimal decision using partial information, (2) JSFP learning algorithms in which a local utility is obtained using full information about the other agents’ decisions, and (3) JSFP learning rule in which a local utility function is approximated by limiting conditioning variables to the neighbor’s decisions. Neighbors are defined in two different ways. One is determined in terms of multi-hop in communication and the other defines neighborhood with correlation in search space. These distributed methods are presented in detail as follows:

Local greedy: Local greedy strategy maximizes the mutual information of its own selection as shown below

\max I (z_{s_{i}}; x_{t})

Sequential greedy: Each agent selects the sensing location, which gives the maximum mutual information conditioned on the preceding agents’ decisions

\max I (z_{s_{i}}; x_{t} | z_{s_{1 : i - 1}})

JSFP with inertia: Implementation of Algorithm 1 with inertia, that is, an agent is reluctant to change its action to a better one with some probability (in this example, with probability $α = 0.3$ , an agent chooses a better action).

JSFP without inertia: Implementation of Algorithm 1 without inertia.

Approximate JSFP with two-hop neighborhood with inertia: Iterative process with local utility functions defined in equation (16). In this strategy, the neighbors are determined in terms of multi-hop in inter-agent communication—that is, by the geometry-based selection algorithm.

Approximate JSFP with correlation-based neighborhood with inertia: Iterative process with local utility functions defined in equation (16). The neighbors are determined by Algorithm 2 using the correlation structure of the search space.

The resulting objective values for six different strategies are given in Table 2, and the histories of objective values in the iterative procedure are shown in Figure 3.

Table 2.

Objective values for six different strategies.

	Case 1	Case 2
Local greedy	0.6299	0.7370
Sequential greedy	0.6386	0.7524
JSFP—full without inertia	0.6415	0.7558
JSFP—full with inertia	0.6415	0.7543
JSFP—approximate two hops with inertia	0.6415	0.7543
JSFP—approximate correlation with inertia	0.6415	0.7543

JSFP: joint strategy fictitious play.

Figure 3.

Histories of objective values with stage count for two cases.

Primarily, the JSFP with full information gives the best solution compared to other strategies as expected. In addition, the approximate JSFP gives a better solution than greedy strategies. As seen in case 1, approximate JSFP gives the same solution as JSFP with full information. However, unlike in the weather forecasting example, the correlation-based approximate JSFP does not always show better performance than the geometry-based approximate JSFP. The first reason is that there is no complex correlation between the sensors, and the correlation is highly related to the Euclidian distance. Second, approximate JSFP algorithms sometimes exhibit an interesting feature in that it may meet the optimal solution during its iteration but does not adopt it, as shown in the correlation-based approximate JSFP of the second example. This is because local utility approximation breaks the potentiality, and agreement among sensors no longer guarantees cooperation. Most importantly, the approximate JSFP algorithm can reduce the computational burden of the JSFP algorithm efficiently while still obtaining a good cooperative solution. Note that calculating the local utility through equations (26) and (27) incurs proportional costs to $2^{| s_{i} \cup s_{i} |}$ . In other words, computational cost can be reduced exponentially by the number of considering measurement variables $z_{s_{i} \cup s_{N_{i}}}$ decreased by neighboring approximation. Hence, approximate JSFP can be efficiently used in a particle filter framework with a high order of sensing points which needs increased computation time to evaluate the local utility of JSFP or sequential greedy strategies.

Sensor targeting for weather forecast

The proposed game-theoretic method is demonstrated on a sensor targeting example for weather forecast using Lorenz-95 model. The Lorenz-95 model³² is an idealized chaos model that is implemented for the initial verification of numerical weather prediction. In this article, we consider a sensor targeting scenario as Choi and How⁶ in which a two-dimensional (2D) extension of the original one-dimensional (1D) Lorenz-95 model was developed and adopted. The 2D model represents the global weather dynamics of the mid-latitude region of the northern hemisphere as follows¹

\begin{matrix} {\overset{\cdot}{y}}_{i j} = (y_{i + 1, j} - y_{i - 2, j}) y_{i - 1, j} + \frac{2}{3} (y_{i, j + 1} - y_{i, j - 2}) y_{i, j - 1} - y_{i j} + \bar{y}, \\ (i = 1, \dots, L_{o n}, j = 1, \dots, L_{a t}) \end{matrix}

where $y_{ij}$ denotes a scalar meteorological quantity, such as vorticity or temperature, at the ith longitudinal and jth latitudinal grid point, each of which corresponds to the state variable at the point. The size of the whole region is $L_{on} = 36$ longitudinal and $L_{at} = 9$ latitudinal grid points, which are equivalent to 694 km × 694 km.

The sensor targeting problem for the weather forecast can be rephrased as selecting the optimal sensing locations in the search region at $t_{s} = 0.05$ (equivalent to 6 h in wall clock) to reduce the uncertainty in the verification variables. The verification variables correspond to $y$ in the verification region at the verification time $t_{v} = 0.55$ (equivalent to 66 h). While unattended ground sensors of size 93 are already installed and take measurements every 6 h, the decision should be made to choose additional sensing locations for mobile sensing agents, such as UAVs at $t_{s}$ . Using the ensemble square root filter³³ with the above weather dynamics, the joint probability distribution of the measurement variables $z_{S}$ at $t_{s}$ and the verification variables at $t_{v}$ can be approximated by a multivariate Gaussian distribution obtained from the samples of the filter (see Choi and How⁶ for additional details of the problem). With the covariance matrix of the measurement variables and the verification variables $P (z_{S_{1 : N}} \cup x_{t})$ , the problem can be treated as a static sensor selection problem. To reduce the computational burden for this sensor selection problem (equation (7)), a backward scheme⁶ is utilized to calculate the mutual information for the global objective function

\begin{matrix} I (x_{t}; z_{s}) = I (z_{s}; x_{t}) \\ = H (z_{s}) - H (z_{s} | x_{t}) \\ = \frac{1}{2} \log (| P (z_{s}) |) - \frac{1}{2} \log (| P (z_{s} | x_{t}) |) \\ = \frac{1}{2} \log (| P (x_{s}) + R_{s} |) - \frac{1}{2} \log (| P (x_{s} | x_{t}) + R_{s} |) \end{matrix}

(29)

where the measurement equation is given by $z_{s} = x_{s} + v_{s}$ with $v_{s} ~ N (0, R_{s})$ for all $s \in S_{1 : N}$ . For the given covariance matrix $P (x_{S_{1 : N}} \cup x_{t})$ obtained from the ensemble square root filter, the two covariance matrices $P (x_{S_{1 : N}} | x_{t})$ and $P (x_{S_{1 : N}})$ are computed prior to the selection process. The unconditioned covariance matrix for the measurement variables $P (x_{S_{1 : N}})$ is formed by simply removing the rows and columns corresponding to the verification variables from $P (x_{S_{1 : N}} \cup x_{t})$ . The conditional covariance matrix $P (x_{S_{1 : N}} | x_{t})$ is computed by conditioning $P (x_{S_{1 : N}})$ on the verification variables $x_{t}$ . Once these two covariance matrices are obtained, then the selection process for each sensing agent is equivalent to the selection of the corresponding principal submatrix and calculation of determinants.

In a potential game, each agent computes the local utility function defined by the conditional mutual information between the measurement selection and the verification variables conditioned on the other agents’ action. We obtain the local utility using the backward scheme as the mutual information of the global objective as in equation (15). We should calculate the two matrices $P (z_{S_{i}} | z_{s_{- i}})$ and $P (z_{S_{i}} | x_{t}, z_{s_{- i}})$ over the search space of agent $i$ before comparing the preference of the agent. For the obtained covariance matrices $P (x_{S_{1 : N}} | x_{t})$ and $P (x_{S_{1 : N}})$ from the backward scheme, the two conditional covariance matrices $P (z_{S_{i}} | z_{s_{- i}})$ and $P (z_{S_{i}} | x_{t}, z_{s_{- i}})$ are computed by conditioning on the other agents’ sensing selections, respectively. If the number of sensing points each agent selects is one, then the covariance matrix for one sensing point becomes a scalar, which is a corresponding diagonal elements in the matrix.

The approximate local utility is computed in the same way as computing the local utility (equation (15)) with the exception of the conditioning variables. The conditioning variables are replaced with the neighboring agents instead of all the other agents’ selections

\begin{matrix} {\tilde{U}}_{i} (s_{i}, s_{N_{i}}) = I (z_{s_{i}}; x_{t} | z_{s_{N_{i}}}) \\ = H (z_{s_{i}} | z_{s_{N_{i}}}) - H (z_{s_{i}} | x_{t}, z_{s_{N_{i}}}) \\ = \frac{1}{2} \log (| P (z_{s_{i}} | z_{s_{N_{i}}}) |) - \frac{1}{2} \log (| P (z_{s_{i}} | x_{t}, z_{s_{N_{i}}}) |) \end{matrix}

(30)

The proposed game-theoretic method using an approximation of the local utility has been tested for three different sensing topologies; 9 sensors in a 3 × 2 format in two different search spaces and 15 sensors in a 2 × 3 format in a larger region than the first and second cases, as described in Table 3. An oceanic region of size 12 × 9 (in longitude × latitude) is considered as a potential search region, among which the whole search space $S_{1 : N}$ is chosen and each agent is assigned its own sensing region $S_{i}$ separated from the other agents as shown in equation (28) of the multi-target tracking example. The number of sensing locations for each agent is set to be one for all the cases, as in Choi and Lee,¹ because the global optimal solution cannot be obtained in tractable time. Several approaches, both centralized and distributed, are compared with the proposed method. The centralized approach is an exact method that searches the entire candidate space $S$ , by which we can obtain the global optimal solution. As in the multi-target tracking example, the distributed approaches are greedy strategies and JSFP algorithm with full information.

Table 3.

Topology of example cases (a × b: a grids in longitude, b grids in latitude).

Case	$N$	$n_{i}$	$S_{1 : N}$	$S_{i}$
1	9	1	9 × 6	3 × 2
2	9	1	9 × 6	3 × 2
3	15	1	10 × 9	2 × 3

The resulting objective values for the seven different strategies are given in Table 4, and the histories of objective values in the iterative procedure are shown in Figure 4. The results for iterative algorithms with inertia are obtained from Monte Carlo simulation and represent average objective values. Case 3 is different from the other two cases in that a larger sensor network is considered, and the global optimal solution cannot be obtained in tractable time. However, from the examples of small sensor networks, we consider that the optimal solution of the third case may be close to the JSFP with full information. Thus, we can consider the objective value for the JSFP with full information as an upper bound for the sensor networks with a large number of sensors.

Table 4.

Objective values for seven different strategies.

Strategy	Case 1	Case 2	Case 3
Global optimal	1.6222	1.7563	N/A
Local greedy	1.3941	1.6668	2.8238
Sequential greedy	1.4301	1.6959	3.0218
JSFP—full without inertia	1.6222	1.7427	3.2319
JSFP—full with inertia	1.6162	1.7479	3.2236
JSFP—approximate two hops with inertia	1.4393	1.7026	2.9476
JSFP—approximate correlation with inertia	1.5928	1.7519	3.1662

JSFP: joint strategy fictitious play.

Figure 4.

Histories of objective values with stage count for three cases.

First, note that the JSFP with full information of other agents’ actions gives a better solution than the sequential greedy algorithm, and the solution is the same as or close to the optimal solution in Choi and Lee.¹ The sequential greedy strategy can be considered as a baseline for comparing the performance of different strategies, since it guarantees the worst-case performance in polynomial time, even though the guarantee is applied to problems in which the objective functions satisfy some conditions. The JSFP with approximate local utility functions also presents a better performance than the sequential greedy strategy except for approximate JSFP with two-hop neighborhood of the third example. The approximate local utility function based on the correlation always gives a better solution than ones depending on the actions of the neighbors selected by geometry-based method. In cases 1 and 2, the objective value for the approximate JSFP with a correlation-based neighborhood is close to the JSFP with full information. The important thing to note here is that the number of conditioning variables used for computing the utility functions is half of the JSFP with full information. As mentioned in the “Computational complexity analysis” section, the computation time for the conditional mutual information increases proportional to the cubic of the conditioning variables. Therefore, the computation time for the approximate local utility function is reduced by a factor of approximately 8.

Conclusion

An approximation method for computing the local utility function has been presented when a sensor network planning problem is formulated as a potential game. A local utility function of each agent that depends on the neighboring agents’ decisions is presented, and a neighbor selection algorithm is proposed to keep the error induced by the approximation small. Two sensor targeting examples for weather forecasting and multi-target tracking demonstrated that potential game formulation with the approximation local utility function gives good performance close to a potential game with full information.

Footnotes

Handling Editor: Konstantinos Kalpakis

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by Agency for Defense Development under contract #UD140053JD and in part by Air Force Office of Scientific Research (AFOSR) grant (FA2386-16-1-4064) via Asian Office of Aerospace Research and Development (AOARD).

ORCID iD

Han-Lim Choi

References

Choi

Lee

SJ.

A potential-game approach for information-maximizing cooperative planning of sensor networks. IEEE T Contr Syst T 2015; 23(6): 2326–2335.

Gopalakrishnan

Marden

Wierman

An architectural view of game theoretic control. ACM SIGMETRICS Perf Eval Rev 2011; 38(3): 31–36.

Hoffmann

Tomlin

CJ.

Mobile sensor network control using mutual information methods and particle filters. IEEE T Automat Contr 2010; 55(1): 32–47.

Krause

Singh

Guestrin

Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 2008; 9(2): 235–284.

Choi

How

Coordinated targeting of mobile sensor networks for ensemble forecast improvement. IEEE Sens J 2011; 11(3): 621–633.

Choi

How

JP.

Efficient targeting of sensor networks for large-scale systems. IEEE T Contr Syst T 2011; 19(6): 1569–1677.

Nguyen

Kodagoda

Ranasinghe

et al . Information-driven adaptive sampling strategy for mobile robotic wireless sensor network. IEEE T Contr Syst T 2016; 24(1): 372–379.

Williams

Fisher

Willsky

AS.

Approximate dynamic programming for communication-constrained sensor network management. IEEE T Signal Proces 2007; 55(8): 4300–4311.

Schwager

Dames

Rus

et al . A multi-robot control policy for information gathering in the presence of unknown hazards. In: Robotics research. Cham, London: Springer, 2017, pp.455–472.

10.

Grocholsky

Information-theoretic control of multiple sensor platforms. PhD Thesis, University of Sydney, Sydney, NSW, Australia, 2002.

11.

Boyd

Parikh

Chu

et al . Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Machine Learn 2011; 3(1): 1–122.

12.

Marden

Arslan

Shamma

JS.

Joint strategy fictitious play with inertia for potential games. IEEE T Automat Contr 2009; 54(2): 208–220.

13.

Marden

Arslan

Shamma

JS.

Regret based dynamics: convergence in weakly acyclic games. In: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, Honolulu, HI, 14–18 May 2007, p.42. New York: ACM.

14.

Mohsenian-Rad

Huang

et al . Demand side management for wind power integration in microgrid using dynamic potential game theory. In: Proceedings of the 2011 IEEE GLOBECOM workshops, Houston, TX, 5–9 December 2011, pp.1199–1204. New York: IEEE.

15.

Dai

Huang

Yang

Game theoretic max-logit learning approaches for joint base station selection and resource allocation in heterogeneous networks. IEEE J Sel Area Comm 2015; 33(6): 1068–1081.

16.

Dai

Huang

Zhao

et al . Resource optimization for device-to-device and small cell uplink communications underlaying cellular networks. IEEE T Veh Technol 2018; 67(2): 1187–1201.

17.

Candogan

Menache

Ozdaglar

et al . Flows and decompositions of games: harmonic and potential games. Math Oper Res 2011; 36(3): 474–503.

18.

Choi

. A potential game approach for distributed cooperative sensing for maximum mutual information. In: Proceedings of the American control conference, Washington DC, 17–19 June 2013. New York: IEEE.

19.

Lee

Choi

. Approximate potential game approach for cooperative sensor network planning. In: Proceedings of the InfoSymbiotics/DDDAS conference, Hartford, CT, 10 August 2016.

20.

Cover

Thomas

. Elements of information theory. Hoboken, NJ: John Wiley & Sons, 2012.

21.

Marden

Arslan

Shamma

JS.

Cooperative control and potential games. IEEE T Syst Man Cy B 2009; 39(6): 1393–1407.

22.

Choi

Kim

Johnson

et al . Potential game-theoretic analysis of a market-based decentralized task allocation algorithm. In: Distributed autonomous robotic systems. Tokyo: Springer, 2016, pp.207–220.

23.

Fudenberg

Tirole

Game theory. Cambridge, MA: The MIT Press, 1991.

24.

Monderer

Shapley

Potential games. Games Econ Behav 1996; 14(1): 124–143.

25.

Fudenberg

Levine

DK.

The theory of learning in games. Cambridge, MA: The MIT Press, 1998.

26.

Borowski

Marden

Frew

EW.

Fast convergence in semi-anonymous potential games. In: Proceedings of the 52nd IEEE conference on decision and control, Florence, 10–13 December 2013, pp.2418–2423. New York: IEEE.

27.

Andersen

Gunnels

Gustavson

et al . A recursive formulation of the inversion of symmetric positive definite matrices in packed storage data format. Lect Notes Comput Sc 2002; 2367: 287–296.

28.

Pinsker

Information and information stability of random variables and processes. Oxford: Holden-Day, 1964.

29.

Candogan

Ozdaglar

Parrilo

PA.

Near-potential games: geometry and dynamics. ACM T Econ Computation 2013; 1(2): 11.

30.

Marden

Shamma

JS.

Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation. Game Econ Behav 2012; 75(2): 788–808.

31.

Kreucher

Hero

Kastella

et al . Efficient methods of non-myopic sensor management for multitarget tracking. In: Proceedings of the 43rd IEEE conference on decision and control, Nassau, Bahamas, 14–17 December 2004, vol. 1, pp.722–727. New York: IEEE.

32.

Lorenz

Emanuel

Optimal sites for supplementary weather observations: simulation with a small model. J Atmos Sci 1998; 55(3): 399–414.

33.

Whitaker

Hamill

Ensemble data assimilation without perturbed observations. Mon Weather Rev 2002; 130(7): 1913–1924.