# Optimizing Consensus-based Multi-target Tracking
with Multiagent Rollout Control Policies

Tianqi Li1, Lucas W. Krakow2 and Swaminathan Gopalswamy1 1Tianqi Li and
Swaminathan Gopalswamy are with the Department of Mechanical Engineering,
Texas A&M University, College Station, TX 77840, USA {xmcx731,
<EMAIL_ADDRESS>Lucas W. Krakow is with the Bush Combat Development
Complex (Texas A&M) Bryan, TX 77807, USA<EMAIL_ADDRESS>work has been
submitted to the IEEE for possible publication. Copyright may be transferred
without notice, after which this version may no longer be accessible.

###### Abstract

This paper considers a multiagent, connected, robotic fleet where the primary
functionality of the agents is sensing. A distributed multi-sensor control
strategy maximizes the value of the collective sensing capability of the
fleet, using an information-driven approach. Each agent individually performs
sensor processing (Kalman Filtering and Joint Probabilistic Data Association)
to identify trajectories (and associated distributions). Using communications
with its neighbors the agents enhance the prediction of the trajectories using
a Consensus of Information approach that iteratively calculates the Kullback-
Leibler average of trajectory distributions, enabling the calculation of the
value of the collective information for the fleet. The dynamics of the agents,
the evolution of the identified trajectories for each agent, and the dynamics
of individual observed objects are captured as a Partially Observable Markov
Decision Process (POMDP). Using this POMDP and applying rollout with receding
horizon control, an optimized non-myopic control policy that maximizes the
collective fleet information value is synthesized. Simulations are performed
for a scenario with three heterogeneous UAVs performing coordinated target
tracking that illustrate the proposed methodology and compare the centralized
approach with a contemporary sequential multiagent distributed decision
technique.

###### Index Terms:

multiagent rollout, target tracking, multi-sensor system, information-driven,
POMDP

##  I Introduction

In the paradigm of autonomous systems, sensing is regarded as the primitive
which transforms information of the physical world into the system as input
for example action selection or planning. Interactions between sensing and
other primitives support the tasks which employing sensor information in world
modeling, stimulus of controller and knowledge representation. Research on
control strategies with considerations centered around information and
sensors, including but not limited to target tracking, searching, world
mapping, is a new and fast-growing focus. Information-driven [1, 2], or
sensor-driven control [3], studies the problem of optimizing a system’s
configuration and resource allocations to optimize or improve sensing
performance.

There are two main schemes in data processing of multiagent systems,
_centralized_ and _distributed_. In a centralized architecture, every agent
must send its information (observation, processed message, control information
etc.) to a central control node either directly or by some multi-hop relay.
This configuration can instigate challenges with respect to the growth of the
system’s number of agents and this is compounded when the agents are mobile:
the central node has bandwidth linear to the number of agents; the topological
change in the communication graph caused by moving agents makes it hard for
the message be passed by all nodes in the network [4]. The distributed
approach means there is no fixed information aggregation component central to
the operation of the system, and the communication is peer to peer [5]. In
applications like sensor fusion, distributed processing may negatively impact
the system’s overall performance when compared to a centralized method, its
advantages are realized in sensor resource management and the robustness of
the system, e.g., communications. Decentralized sensor fusion can be more
adaptable in applications like sensor deployment for maximal coverage [6],
where sensors that require local decisions already possess the needed local
information such as target tracking estimates. For the aspect of
communication, constraint in bandwidth makes the centralized sensor fusion
infeasible to be for large system implementation [7].

The trend of applying decentralized algorithms is arising in the information-
driven tasks, leveraging the aforementioned advantages. [8] establishes the
link of distributed target tracking and information-driven mobility, as a
byproduct the behavior of flocking is observed in single target tracking by a
mobile multisensor network. [9] presents the coordinated intermittent
searching of robot team in a restricted area with max-consensus algorithm on
the information to picture the occupancy map, in which mobile sensor
formations are propelled by average consensus on decisions.

However, an optimal solution for such coordinated heterogeneous multiagent
planning poses a computational challenge. [10] introduces the sensor planning
based on the estimation of a single target with the range-bearing sensor model
and motion constraints, and studies such a strategy in single and
(heterogeneous) multisensor scenarios. With motion constraints on the robots
(maximum speed and minimum distance to the target), such non-convex
constrained optimization problems are NP-hard in general. The work in [11]
strives to maximize the FoV of the sensing team by topological reconfiguration
of the robot network under sensor deterioration. The solution to the proposed
reconfiguration problem equates to a circle packing problem in 2-dimension
space, which is shown to be NP-complete [12]. It is clear that optimality is
difficult to achieve, thus, efficient suboptimal solutions are of great value
for implementations. Recently a multiagent version of rollout policy was
published [13], which takes augments the traditional rollout approach through
sequential optimization. In a multiagent system containing $n$ agents with
$\mathbb{R}^{s}$ as the action domain of each agent, the joint optimization
requires the computation of order $O(s^{n})$. However, when performing
_sequential_ optimization with respect to the agents, rollout reduces the
computation load to the order of $O(sn)$.

This paper focuses the coordination of mobile multi-sensor system in the task
of target tracking. Different from work in [10], scenario of tracking multiple
targets is studied for a more generic version of distributed target tracking.
For the simplicity of the problem, agents are considered as UAVs for freedom
of movement and alleviate sensor-to-target and sensor-to-sensor distance
constraints. Since future targets positions are stochastic, a non-myopic
behavior is of great interest in the planning. This is achieved through the
application of a receding horizon when computing rollout policies. We
formulate a POMDP framework and apply a sequential rollout method in a
consensus-based distributed target tracking task to solve an information-
driven coordinated planning with a heterogeneous multiagent system. With
simulation designed in target tracking, the performance of tracking in rollout
algorithm shows

  1. 1.

The non-myopic behavior extracted from the multiagent rollout benefits the
tracking performance for the fleet of mobile sensors

  2. 2.

The computation advantages of the sequential optimization in multiagent
rollout policy can be realized with minimal target tracking degradation.

This paper is organized in the following manner. Section II describes
fundamental setup of distributed target tracking and the objective of the
proposed problem. Section III details the proposed non-myopic multisensor
planning in a framework of POMDP. Section IV presents the simulation results
which demonstrates the coordination of sensors in target tracking task.
Insights of this study are recapped and future work is proposed in Section V.

##  II Problem Statement

We consider a heterogeneous mobile multi-sensor system in a task of target
tracking for our specific control problem. Each _agent_ is equipped with
sensors, actuators and a communication device for the three main functions:
sensing, mobility and communicating with peer agents. This multi-sensor system
has total $n$ agents and each agent has a unique label $i\in[n]$. Define the
state of the single agent $i$ as $s^{i}\in\mathcal{S}^{i}$, where $s^{i}$
contains the pose and velocity of the agent in horizontal plane
$s^{i}\in\mathcal{S}^{i},s^{i}=(x,y,\theta,v_{x},v_{y})$. We assume a
holonomic model for the dynamics of each agent where the control inputs
directly alter agent’s velocity; the control domain $\mathcal{U}^{i}$ is the
velocity of the agent, such that $u^{i}\in\mathcal{U}^{i},u^{i}=(v_{x},v_{y})$
and the azimuth in pose is consistent with velocity, i.e.
$\theta=arctan(v_{y}/v_{x})$. An agent $i$ has the following attributes:

  * •

Mobility: For agent $i$, in discrete time space, we have state
$s_{k}^{i}\in\mathcal{S}^{i}$ and control $u_{k}^{i}\in\mathcal{U}^{i}$, the
sensor state transition function is $s^{i}_{k+1}=f_{i}(s^{i}_{k},u_{k}^{i})$ .

  * •

Sensing: Each sensor has a limited field of view (FoV) and an associated
_sensing quality_ . For a quad-copter UAV agent, we define the FoV of agent
$i$ by variable $\phi_{k}^{i}(s_{k}^{i})$ parameterized by agent state. For
sensing quality, a scalar $\alpha_{i}$ is defined in the measurement
uncertainty matrix $R$, detailed in (3).

  * •

Communication: An agent communicates to other within its neighborhood defined
by the distance of $d_{c}$. For simplicity, we assume this threshold is
universal across agents.

The multisensor network is comprised of $n$ agents described above. The
network can then be represented as an undirected proximity graph
$\mathcal{G}=(V(\mathcal{G}),E(\mathcal{G}))$, let vertex $v\in
V(\mathcal{G})$ represents an agent in graph and every edge $e\in
E(\mathcal{G})$ represents communication link between two agents, i.e.
$\forall\\{i,j\\}\in V(\mathcal{G}),||s^{i},s^{j}||\leq d_{c}$. Define the
_neighbor_ of agent $i\in V(\mathcal{G})$ as the set of graph vertices
$N_{\mathcal{G}}(i)\in V(\mathcal{G}),\text{s.t. }\forall j\in
N_{\mathcal{G}}(i),\\{i,j\\}\in E(\mathcal{G})$, and we denote the degree of
agent $d(i)=|N_{\mathcal{G}}(i)|$.

###  II-A Distributed Target Tracking

In the multi-target tracking (MTT) problem, at each time step $k$, an agent
$i$ generates a set of measurements deemed as an observation,
$Z_{k}^{i}=\\{z_{k,1}^{i},z_{k,2}^{i}...,z_{k,m^{i}_{k}}^{i}\\}$ with
cardinality $|Z_{k}^{i}|=m^{i}_{k}$. Given a target state $\mathbf{x}\in\chi$
which contains position and velocity variables in a 2-dimensional Cartesian
coordinate system, and a measurement, $z\in\mathcal{O}$, generated from a
target is taken to be the target’s position.

A linear assumption of the dynamic of target is

$\textbf{x}_{k+1}=F_{k}\textbf{x}_{k}+w_{k},\leavevmode\nobreak\
w_{k}\sim\mathcal{N}(0,Q_{k})$ (1)

with $w_{k}$ represents the motion disturbance in a normal distribution,
$F_{k}$ is the nearly constant velocity motion model, and observation law is

$z_{k}=H_{k}\textbf{x}_{k}+v_{k},\leavevmode\nobreak\
v_{k}\sim\mathcal{N}(0,R_{k})$ (2)

with $v_{k}$ represents the measurement noise. The common range-bearing sensor
model is considered in our paper, which is widely studied and applied [14].
Specifically, for agent $i$ with state $s^{i}_{k}$, let $r_{k}$ and $\rho_{k}$
denote the estimated range and bearing of a mobile target,
$r_{k}=max(||s^{i,pos}_{k}-\textbf{x}^{t,pos}_{k}||,r_{0})$, $\rho_{k}$ is the
angular measurement between the sensor and target, the observation covariance
matrix $R_{k}^{i}(s^{i}_{k},\textbf{x}^{t}_{k})$ for target $t$ is

$R_{k}^{i}(s^{i}_{k},\textbf{x}^{t}_{k})=\alpha_{i}G(\rho_{k})\begin{bmatrix}0.1\times
r_{k}&0\\\ 0&0.1\pi\times r_{k}\end{bmatrix}G(\rho_{k})^{T}$ (3)

where $G(\rho)$ is the rotation matrix of angle $\rho$, and sensing quality
factor $\alpha_{i}$ is a scalar in this uncertainty matrix. This imposes the
spatially varying measurement error [15]. To avert computational issues inside
the Kalman filter updates, we apply $r_{0}$ as the minimal effective range
threshold.

Based on the principle of distributed target tracking in [16], the systematic
estimation is twofold: i) single agent local estimation and prediction; ii)
track fusion over agents. For a single agent, the estimation includes the
measurement-to-track assignment and estimation update given measurement. One
method of this measurement-to-track assignment is the joint probabilistic data
association filter (JPDAF) [17]. JPDA algorithm handles the assignments based
on conditional probabilities calculated with respect to predicted target
locations and the received measurements. Since the target may be outside of
sensor FoV or simply undetected, we also employ M-out-of-N track maintenance
logic for both track confirmation and deletion. A track is confirmed/deleted
if there are more than M detections (or missed detections, respectively) in
the latest N consecutive observations.

Once the local tracking step (JPDAF) is complete, messages containing tracking
information from an agent’s neighbors are received and processed to update
local track in the consensus period. As is common in distributed sensor
fusion, we follow the average consensus scheme for this step. However, instead
of sending the measurements, we perform consensus of information (CI) which
directly processes the tracking information. For example, [18] utilizes the
information filter to make average consensus of track information, and the
result is proven to be the Kullback–Leibler average (KLA) of the initial local
distributions [19]. Denote $\Theta^{i}_{k}$ as the set of local tracks of
agent $i$. In a Kalman filter, a pair consisting of the mean vector and
covariance matrix ($\textbf{x}^{t}_{i,k|k},\textbf{P}^{t}_{i,k|k}$) is the
standard representation of a track $t\in\Theta^{i}_{k}$. The same track can be
represented in information filter by the pair comprised of an information
matrix $\mathbf{\Omega}^{t}_{i,k|k}={\textbf{P}^{t}_{i,k|k}}^{-1}$ and an
information vector
$\textbf{q}^{t}_{i,k|k}=\mathbf{\Omega}^{t}_{i,k|k}\textbf{x}^{t}_{i,k|k}$.

As with any consensus algorithm, multiple updates must be done for the
information to converge across the network. We denote the total number of
consensus update steps as $L$, which take place in order to accurately
proliferate the JPDA tracking information to all agents of the network. These
$L$ updates are taken over each discrete epoch, e.g., from $k$ to $k+1$. At
each consensus update $l=1,2,\ldots,L$ the average consensus step for agent
$i$ is

$\displaystyle\mathbf{\Omega}^{t}_{i,k|k}(l+1)=$
$\displaystyle\frac{1}{1+d(i)}\sum_{j\in
N_{G}(i)\cup\\{i\\}}\mathbf{\Omega}^{t}_{j,k|k}(l)$ (4a)
$\displaystyle\mathbf{q}^{t}_{i,k|k}(l+1)=$
$\displaystyle\frac{1}{1+d(i)}\sum_{j\in
N_{G}(i)\cup\\{i\\}}\mathbf{q}^{t}_{j,k|k}(l)$ (4b)

Given the fixed number of consensus steps, the output of CI is
$(\mathbf{\Omega}^{t}_{i,k|k}(L),\mathbf{x}^{t}_{i,k|k}(L))$.

###  II-B Information-driven multiagent Coordination Control

The multisensor system described above is information-driven, i.e. the control
of mobile sensors is to obtain over all more information of targets by
observation and distributed target tracking. Firstly a good choice of
information utility is essential to picture the objective of the system in a
mathematical formation. The existing choices includes entropy [1] , Fisher
Information matrix [8], the covariance matrix in Gaussian [10, 11, 15] and
other sensor model-based heuristics [20]. In our problem, the trace of
covariance matrix of targets is chosen for its perceptual intuition and ease
of computation in the Gaussian based data association. To further simplify the
computation, since the information matrix $\mathbf{\Omega}^{t}_{i,k|k}$ is the
inverse of covariance matrix $\textbf{P}^{t}_{i,k|k}$, the trace of
information matrix is applied as the utility of information. In our
distributed multisensor system, the utility of information of agent $i$ in
time $k$ is defined as

$\Phi^{i}(k)=\sum_{t\in\Theta^{i}_{k}}tr(\mathbf{\Omega}^{t}_{i,k|k}(L))$ (5)

Notice that this utility contains the process of distributed MTT in Section
II-A, term $\mathbf{\Omega}^{t}_{i,k|k}(L)$ is defined as the output of
consensus step of certain track $t$ by (4a).

###  II-C Semantic Map

The study of sensing is dependent on the environment, and in our mobile
multisensor system the physical environment has impact on sensibility of
agents. The semantic meaning of areas and objects helps in understanding the
environment and provides guidance on robot decision making. Following [21],
define the world $W=(T,X,Y)$ with a topological graph $T$ to represent
components of physical object set $X$ and semantic element set $Y$. In our
problem, geological factor affects the quality of detection like tree shadows
and ground reflection, by utilizing the semantic map, the movement of targets
into occlusion area will be predicted based on Kalman filter. Such semantic
information helps picturing the future observations based on current target
belief. Given a set of observation $Z$, semantic map functions as $W(Z)$ which
returns the observation outside the occlusion area.

##  III Method

###  III-A A POMDP Model

A Partial Observable Markov Decision Process (POMDP) model is formulated in
[15], which describes a non-myopic sensory centralized multi agent motion
planning with the task of target tracking. This POMDP model is extended to the
multi agent scenario with distributed planning in this paper. Define a POMDP
model as a tuple of $\mathcal{P}=(\mathcal{X,U,T,R,O})$.

State $\mathcal{X}$: The state of POMDP contains the state of agents
$\mathcal{S}$, state of targets $\chi$ and state of filter $\mathcal{F}$. The
state of all $n$ agents is defined as
$\mathcal{S}=\mathcal{S}^{1}\times\mathcal{S}^{2}...\times\mathcal{S}^{n}$.
Together with agents states $s_{k}\in\mathcal{S}$, the overall FoV of these
agents is
$\phi_{k}(s_{k})=\phi^{1}_{k}(s_{k}^{1})\times\phi^{2}_{k}(s_{k}^{2})...\times\phi^{n}_{k}(s_{k}^{n})$,
which is regarded as a variable parameterized by agents state. Targets state
$\chi$ contains all position and velocities of current targets. The filter
state
$\mathcal{F}_{k}=\\{(\textbf{x}_{i,k|k}^{t},\textbf{P}_{i,k|k}^{t})|\forall
i\in[n],\forall t\in\Theta^{i}_{k}\\}$, which are all agents maintained tracks
represented by Gaussian distributions with posterior means
$\textbf{x}_{i,k|k}^{t}$ and posterior covariance matrices
$\textbf{P}_{i,k|k}^{t}$. The POMDP state is summarized as
$x_{k}=(s_{k},\chi_{k},\mathcal{F}_{k})$.

Action $\mathcal{U}$: The action domain is the overall action to the
multisensor system, with the control domain of each sensor defined by the 2-d
velocity in Section II. Such control domain has constraint from both the
physical world and the agents’ kinematic constraints. Assume the maximum
velocity is set as $v_{m}ax$ for all agents $i\in[n]$. Thus at time $k$, the
control domain $\mathcal{U}^{i}_{k}$ of a single agent $i$ is implicit with
its state $s_{k}^{i}$. The joint action domain is then defined as
$\mathcal{U}_{k}=\mathcal{U}_{k}^{1}\times...\times\mathcal{U}_{k}^{n}$.

Observation and Observation Law $\mathcal{O}$: Observation is generated by
sensors equipped on agents through perception algorithm, here we assume that
an ideal perceptual component outputs observations with no false alarms in
areas without occlusion in $W$. Under Gaussian noise assumptions, the
observation law of a target is presented by (2) with the dynamic sensor model
defined as (3). From a system perspective, the joint observation domain of all
sensors is defined as $\mathcal{O}$,
$Z_{k}\in\mathcal{O},Z_{k}=\\{Z_{k}^{i}|i\in[n]\\}$. For agent $i$, its
observation $Z_{k}^{i}$ is constrained by the semantic map $W$ and its FoV
$\phi^{i}_{k}$.

State Transition $\mathcal{T}$: State transition law is defined as the mapping
$\mathcal{T}:\mathcal{X}\times\mathcal{U}\xrightarrow[]{}\mathcal{X}$. In the
state
$x_{k}\in\mathcal{X}_{k},x_{k}=(s_{k},\chi_{k},\mathcal{F}_{k}),u_{k}\in\mathcal{U}_{k}$,
the state transition is decomposed into the following: i) the agents’
transitions are completely determined by
$s^{i}_{k+1}=f_{i}(s^{i}_{k},u_{k}^{i})$; ii) target states
$\textbf{x}_{k}^{t}\in\chi_{k}$ are a stochastic process (1) with Gaussian
additive noise, independent of sensor state $s_{k}$ and control variable
$u_{k}$. iii) the filter state $\mathcal{F}_{k}$ is dependent on both agent
state $s_{k}$, FoV of sensors $\phi_{k}$ and target state $\chi_{k}$ and
evolves according to the chosen tracking filter equations, JPDA with average
consensus.

Reward $\mathcal{R}$: The reward function for single agent is a mapping
$\mathcal{X}\times\mathcal{U}\xrightarrow[]{}\mathbb{R}$, with the objective
of maximizing the tracking information.For agent $i$, its tracking set
$\Theta^{i}_{k}$ can be regarded as the subset of all targets in the system
$\Theta^{i}_{k}\subseteq\chi_{k}$. The standard objective in MTT is to
minimize the tracking error over the system. By design, the information
utility function defined in (5) directly reflects our purpose by maximizing
the trace of the inverse of uncertainty matrix over all tracks. In [19] it is
shown that under the assumption of strongly connectivity in the sensor
network, the estimation error of CI is asymptotically bounded in mean square
error. Let $\tilde{\Phi}(\cdot)$ denote the _converged estimate_. We assume
given $L>L_{0},\forall i\in[n],|\Phi^{i}(k)-\tilde{\Phi}(k)|<\epsilon$, with
$\epsilon$ sufficiently small this error can be ignored. This implies that the
track information of each agent is close enough after sufficient steps of
consensus that each agent may take its local estimate to _be_ the converged
estimate of the system, i.e., $\Phi^{i}(k)\approx\tilde{\Phi}(k)$. Then the
one-step reward for the system is

$\mathcal{R}(x_{k},u_{k})=E_{v_{k},w_{k}}[\tilde{\Phi}(k+1)|x_{k},u_{k}]$ (6)

This POMDP contains two challenging points for an optimal solution: first the
action domain expands exponentially with number of agents which leads the
computational challenge; second the state transition $\mathcal{T}$ is a
continuous stochastic process.

###  III-B Belief-State MDP

Different from POMDP, the Markov Decision Process (MDP) is fully observable in
the state as well as state transition model, which makes it possible to
calculate optimal policy given a state and Q-function. To solve the POMDP, it
can be transferred to an MDP problem with belief state, $b_{k}$: in state
$x_{k}=(s_{k},\chi_{k},\mathcal{F}_{k})$ definition, the unobservable part is
the target state $\chi_{k}$ which is represented by the posterior distribution
conditioned on the history of actions and observations, i.e.
$b_{k}(x)=P_{\chi_{k}}(x|Z_{0},...,Z_{k};u_{0},...,u_{k-1})\in
B(\mathcal{X})$, here $B(\mathcal{X})$ represents the domain of belief state.
Then the one-step belief-state reward is defined as

$\tilde{\mathcal{R}}(b_{k},u_{k})=\int\mathcal{R}(x,u_{k})b_{k}(x)dx$ (7)

replacing (6). Under the assumption of perfect data association and a linear
Gaussian system, a target’s belief state can be represented by a Gaussian
distribution such that for target $\chi^{i}\in\chi_{k},$
$b_{k}^{\chi^{i}}\sim(\textbf{x}_{i,k|k}^{\chi^{i}},\textbf{P}_{i,k|k}^{\chi^{i}})$.
Based on this we take the mean and covariance derived from the JPDAF as a
sufficient representation of the belief state for the belief-state MDP reward
calculations. The belief state update is then captured using the defined state
transition for the fully observable portions, i.e., agent state and the target
belief-state update is
$f_{b}:B(\mathcal{X})\times\mathcal{U}\xrightarrow[]{}B(\mathcal{X})$,
approximated by the filter state update. With belief state $b_{0}$, the
cumulative belief reward over $N$ decision stages (horizon) is

$V_{N}(b_{0})=E\\{\sum_{k=0}^{N}\tilde{\mathcal{R}}(b_{k},u_{k})|b_{0}\\}$ (8)

The _policy_ in belief-state MDP is a mapping
$\mu:B(\mathcal{X})\xrightarrow[]{}\mathcal{U}$ which provides the action
given belief state. In a belief-state MDP, an optimal policy generates the
action to maximize the cumulative reward in (8). Following Bellman’s
principle, the optimal objective function is interpreted as
$V_{N}^{*}(b_{0})=\max_{u}\tilde{\mathcal{R}}(b_{0},u)+E[V^{*}_{N-1}(b_{1})|b_{0},u]$.
Thus, we define a Q-value function in the fixed horizon as
$Q_{N}:B(\mathcal{X})\times\mathcal{U}\xrightarrow[]{}\mathbb{R}$,
specifically

$Q_{N}(b_{0},u)=\tilde{R}(b_{0},u)+E[V^{*}_{N-1}(b_{1})|b_{0},u]$ (9)

If N is fixed as constant, this problem becomes receding horizon control and
the optimal policy $\pi^{*}$ is defined

$\displaystyle Q_{N}(b,u)$
$\displaystyle=\tilde{R}(b,u)+E[V^{*}_{N-1}(b^{\prime})|b,u]$ (10a)
$\displaystyle\pi^{*}(b)$
$\displaystyle=\operatorname*{arg\,max}_{u\in\mathcal{U}}Q_{N}(b,u)$ (10b)

where state $b^{\prime}$ in (10a) is the random belief state obtained from
state $b$ after taking action $u$.

###  III-C Multiagent Rollout Policy

The rollout algorithm is a suboptimal solution in decision making which
implements a sequential optimization method over a finite time horizon [22].
Given a simple base policy (typically an easy to compute heuristic), the
rollout policy is guaranteed to improve upon the base policy. A multiagent
version of rollout is introduced recently by Bertsekas in [13] which maintains
a policy improvement property under a sequential decision making with respect
to agents. In standard one-step lookahead rollout algorithm, from initial
state $x_{0}\in\mathcal{X}$ a trajectory is generated
$\\{x_{0},\tilde{u}_{0},x_{1},...,x_{N-1},\tilde{u}_{N-1},x_{N}\\}$ with one-
step reward function $g_{k}(x_{k},u_{k})$ and reward-to-go function
$J_{k,\pi}(x_{k})$, and a sequence of actions called policy
$\pi=\\{\tilde{u}_{0},...,\tilde{u}_{N-1}\\}$ is determined by one-step
lookahead maximization

$\tilde{u}_{k}=\operatorname*{arg\,max}_{u_{k}}E\\{g_{k}(x_{k},u_{k})+J_{k+1,\pi}(x_{k+1})\\}$
(11)

Similarly, the belief-state MDP starts with initial belief $b_{0}$ and solves
such one-step lookahead minimization as (11). Propagating the the belief into
the future is computationally expensive and the accuracy of the estimates
decreases with length of the time. Thus one-step rollout that we implement
here focuses on solving the immediate action $\pi^{*}(b_{0})$, which is based
on an approximate expected reward-to-go (ERTG) of
$E[V^{*}_{N-1}(b^{\prime})|b,u]$ in (10a), and the policy of future beliefs is
base policy.

####  III-C1 Base Policy

The base policy of our multi-sensor system is decomposed into individual
sensors. Denote the base policy of the described system as
$\bar{\mu}=\\{\bar{\mu}^{1},...,\bar{\mu}^{n}\\}$, with each sensor’s base
policy in a proximal tracking: the sensor will move towards to the track of
largest uncertainty within distance $d_{0}$, i.e. the track $t^{*}$ with

$\displaystyle
t^{*}=\operatorname*{arg\,min}_{t\in\Theta^{i}_{k}}tr(\mathbf{\Omega}^{t}_{i,k|k})$
(12a) $\displaystyle|s_{k}^{i,pos}-\textbf{x}^{t^{*},pos}_{k}|\leq d_{0}^{i}$
(12b)

For agent $i$, its base policy is

$\bar{\mu}^{i}(s_{k}^{i})=v_{0}\frac{s_{k}^{i,pos}-\textbf{x}^{t^{*},pos}_{k}}{|s_{k}^{i,pos}-\textbf{x}^{t^{*},pos}_{k}|}$
(13)

The consideration of proximity in base policy enables the sensor to maintain
the target tracking with the simple heuristic of the distance between sensor
and its worst local tracking estimate. This base policy is specifically
motivated by our sensor model with spatially varying measurement error from
(3). By moving towards track $t^{*}$ defined in (12), an efficient but myopic
single-agent base policy is built.

####  III-C2 Rollout Policy

The base policy is designed in a distributed single agent’s way without
coordination among agents. The lookahead approach applied by the rollout
policy implicitly optimizes the agents maneuvers across the system inducing
coordinated movements. The one-step maximization objective function including
ERTG term $\tilde{V}_{N-1}(b)=E[V_{N-1}(b)|b,\bar{\mu}]$ is

$\displaystyle Q_{N}(b,u)$
$\displaystyle=\tilde{R}(b_{0},u)+\tilde{V}_{N-1}(b_{0})$ (14a)
$\displaystyle\pi^{*}(b_{0})$
$\displaystyle=\operatorname*{arg\,max}_{u\in\mathcal{U}}Q_{N}(b_{0},u)$ (14b)

The optimal solution $\pi^{*}(b_{0})=\\{u^{1},u^{2},...,u^{n}\\}$ in (14b) is
in a high dimension space $\mathcal{U}$ that brings computational issue in the
approach. In multiagent rollout algorithm, there are two approaches in solving
the one-step lookahead optimization: 1) all-agents-at-once solves (14b) in one
optimization equation, i.e. returns solution in domain $\mathcal{U}$, which is
typically challenged in computation with the growth of dimensionality; 2)
agent-by-agent initializes the policy $\pi(b_{0})$ with all base policy
$\bar{\mu}$ on each agent, doing optimization in $n$ times with $i$th time
optimizing the action of agent $i$, solves the joint action policy in a
specified sequence of agents. The algorithm of agent-by-agent is described as
Algorithm 1. Such agent-by-agent optimization reduces the computation by the
trade-off with suboptimality, a brief description of such sequential
optimization is in Algorithm 1.

Algorithm 1 Multi-Sensor Agent-by-agent Rollout Target Tracking

0: At time $t=k$, Sensor network graph $\mathcal{G}=(V,E)$, agent state
$s_{k}=(s^{1}_{k},...,s^{n}_{k})\in\mathcal{S}$, observation set
$Z_{k}=\\{Z^{i}_{k},...,Z^{n}_{k}\\}$.

1\. Local sensor update, obtain local tracking set $\Theta^{i}_{k}$ for sensor
$i$;

2\. Consensus update with neighbor sensor nodes by (4), all agent obtains
state in POMDP $b_{k}\in B(\mathcal{X})$;

3\. Initialize control $u_{k}$ with base policy
$\bar{\mu}(b_{k})=\\{\bar{\mu}^{1},...,\bar{\mu}^{n}\\}$ by (13) such that
$u_{k}=\\{u_{k}^{i}|\forall i\in[n],u_{k}^{i}=\bar{\mu}^{i}\\}$;

4\. Rollout policy solving one-step optimization

for $i\in[n]$ do

$u_{k}^{i}=\operatorname*{arg\,max}_{u_{k}^{i}\in\mathcal{U}^{i}_{k}}Q_{N}(b_{0},u_{k})$

update $u_{k}$

end for

return $u_{k}$;

##  IV Simulation Result

To validate the aforementioned distributed target tracking rollout policy, a
simulation of the multisensor system is constructed described by the following
scenario: 3 UAVs carrying camera sensors are deployed within a parking lot
perimeter. The task of UAVs is to monitor the people walking in this parking
lot, as we assume the perception algorithm provides the observation data
$Z_{k}^{i}$ in the frequency of 5 Hz. To have a close simulation of human’s
trajectory, step lengths of trajectories obey a Levy walk with the speed
interval of [1.0, 3.0] m/s. For this multiagent system, UAVs are set at
different altitudes which makes the FoVs $\phi^{i}_{k}(\cdot)$ and sensing
qualities $\alpha_{i}$ heterogeneous. Specifically, UAV 1 has a $20\times 20$
m square FoV with $\alpha_{1}=0.1$; UAV 2 has $25\%$ larger side length of FoV
and $\alpha_{2}=1.5\alpha_{1}$; UAV 3 has $10\%$ larger side length of FoV and
$\alpha_{3}=1.2\alpha_{1}$. As the control variable defined in Section II,
UAVs move on the horizontal planes with fixed altitude by commanding the
velocity, with $v_{0}=5$ m/s defined in base policy (13), and $d_{0}^{i}$
equal to the diagonal of FoV to classify proximal tracks of a certain agent.
We assume that when the sensors move, the FoV maintains orientation consistent
with the coordinate system and the same angle through a stabilizing.

Figure 1: Scenario of 3 UAVs monitoring in a parking lot. The UAV FoV’s,
denoted as squares, define initial positions. The vegetation areas, solid
green blocks, occlude camera detection. The target trajectories are the grey
gradient lines from dark (start) to light (end).  Figure 2: An example
tracking result from agent-by-agent rollout, sensors trajectories are dotted
lines with corresponding FoVs.

The parking lot map is shown in Fig. 1, here the areas of occlusion (tree
cover) provides semantic meanings to the system in observation laws defined in
POMDP. Utilizing such semantic information enables the system to plan based on
environment and increases the agent coordination.

The control frequency for the system is 1 Hz, which runs rollout policy for
all agents. For a sufficient Q-value approximation in (14), belief states of
target position are represented by Monte Carlo sampling [23]. In each control
iteration, 50 samples are drawn in the Gaussian belief of targets to formulate
the possible trajectories in N sec rollout horizon. Solving of the one-step
lookahead optimization of systemwise decision in (14b) as well as per agent in
Algorithm 1 is accomplished through numerical optimization, specifically
Differential Evolution.

Figure 3: Target tracking performance in OSPA metric, a comparison between the
agent-by-agent (distributed) and all-agents-at-once (centralized) rollout
policies. Total 50 trials are run in the simulation of 40 decision epochs,
with mean and 95% confidence interval are plotted of the OSPA metric.
Parameter of OSPA is with $c=40.0,p=2$ following terminology in [24]. This
encapsulates both tracking error and target cardinality estimates with respect
to ground truth.

A typical control result of agent-by-agent rollout is represented in Fig. 2.
The cooperative behavior is observed between the UAV 1 and 2 when Target 1
moves through the bottom green occlusion (between $t=5$ and $t=15$): UAV 1
moves to bottom left to continue tracking Target 2 while UAV 2 starts tracking
Target 1. A similar behavior happens again between UAV 2 and 3 when Target 1
moves through the top occlusion area (between $t=20$ and $t=30$). UAV 2
maintains Target 3 and Target 4 but UAV 3, which initially kept track of
Target 4, leaves Target 4 to be tracked by UAV 2 and transitions focus to the
track of Target 1.

The performance of the target tracking task is measured by the Optimal
Subpattern Assignment (OSPA) [24] metrics in Fig. 3. These results are all
generated based on the scenario depicted in Fig. 1. Specifically, three
algorithms are investigated, an agent-by-agent greedy algorithm ($N=1$) which
explicitly optimizes the one-step belief-state reward (7) and the two rollout
policies, namely all-agents-at-once and agent-by-agent. Two major conclusions
can be drawn from Fig. 3. First the reader can observe from $t=15$ to $t=35$
the performance of the greedy algorithm suffers. This anomaly arises from the
myopic policies lack of consideration for future impacts from current action
choices and is especially apparent when UAVs need to perform target hand-offs,
changing focus from one set of targets to another. Both of the rollout
algorithms with extended horizons, $N=5$, account for the future trajectory
shifts of the targets and the future movements of the cooperative fleet. The
second realization is the minimal performance differentiation between the two
rollout algorithms. This result shows that the sequential distributed control
decision paradigm is a viable replacement for the centralized control. More
specifically this demonstrates that the advantages of the control space
dimension reduction from exponential to linear with respect to number of
agents [13] can be employed in the model with partially observable states,
e.g., the task of target tracking. In the context of implementation, this also
yields the advantage of allowing each agent to compute it’s own optimized
control, distributing the computational load across all agents evenly.

##  V Conclusion

A multiagent (multi-sensor) target tracking problem is formulated as a POMDP.
The control policy optimization, based on receding horizon rollout was
implemented on an agent-by-agent basis. This sequential decision making
augmentation, multiagent rollout introduced in [13], is compared to a
standard, all-agents-at-once, rollout policy generation. The sequential
implementation showed similar performance when implemented in a distributed
tracking system where information maintained on a per agent basis and
assimilated across the system through consensus-based JPDA.

With these initial results in hand further investigations will include
applications considering limited communication range and/or bandwidth and
extending the heterogeneity level of the agents. Beyond viable scenario
extensions for real-world considerations, the simulations herein have shown a
lackluster in computational efficiency which leads to further extension of
this sequential methodology either through similar avenues of reinforcement
learning alluded to in [13] or though approximate dynamic programming
techniques which follow the vein of rollout and receding horizon control.

## References

  * [1] F. Zhao, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration,” IEEE Signal processing magazine, vol. 19, no. 2, pp. 61–72, 2002.
  * [2] A. C. Bellini, W. Lu, R. Naldi, and S. Ferrari, “Information driven path planning and control for collaborative aerial robotic sensors using artificial potential functions,” in 2014 American Control Conference, pp. 590–597, IEEE, 2014.
  * [3] L. Paull, S. Saeedi, M. Seto, and H. Li, “Sensor-driven online coverage planning for autonomous underwater vehicles,” IEEE/ASME Transactions on Mechatronics, vol. 18, no. 6, pp. 1827–1838, 2012.
  * [4] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor fusion based on average consensus,” in IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005., pp. 63–70, IEEE, 2005.
  * [5] B. Siciliano and O. Khatib, Springer handbook of robotics.  Springer, 2016.
  * [6] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on robotics and Automation, vol. 20, no. 2, pp. 243–255, 2004.
  * [7] Z.-Q. Luo, “Universal decentralized estimation in a bandwidth constrained sensor network,” IEEE Transactions on information theory, vol. 51, no. 6, pp. 2210–2219, 2005.
  * [8] R. Olfati-Saber, “Distributed tracking for mobile sensor networks with information-driven mobility,” in 2007 American Control Conference, pp. 4606–4612, IEEE, 2007.
  * [9] B. Ristic and A. Skvortsov, “Intermittent information-driven multi-agent area-restricted search,” Entropy, vol. 22, no. 6, p. 635, 2020.
  * [10] K. Zhou and S. I. Roumeliotis, “Multirobot active target tracking with combinations of relative observations,” IEEE Transactions on Robotics, vol. 27, no. 4, pp. 678–695, 2011.
  * [11] R. K. Ramachandran, N. Fronda, and G. S. Sukhatme, “Resilience in multi-robot target tracking through reconfiguration,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 4551–4557, IEEE, 2020.
  * [12] E. D. Demaine, S. P. Fekete, and R. J. Lang, “Circle packing for origami design is hard,” arXiv preprint arXiv:1008.1224, 2010.
  * [13] D. Bertsekas, “Multiagent rollout algorithms and reinforcement learning,” arXiv preprint arXiv:1910.00120, 2019.
  * [14] B. D. Anderson and J. B. Moore, Optimal filtering.  Courier Corporation, 2012.
  * [15] L. W. Krakow, C. M. Eaton, and E. K. Chong, “Simultaneous non-myopic optimization of uav guidance and camera gimbal control for target tracking,” in 2018 IEEE Conference on Control Technology and Applications (CCTA), pp. 349–354, IEEE, 2018.
  * [16] N. F. Sandell and R. Olfati-Saber, “Distributed data association for multi-target tracking in sensor networks,” in 2008 47th IEEE Conference on Decision and Control, pp. 1085–1090, IEEE, 2008.
  * [17] T. Fortmann, Y. Bar-Shalom, and M. Scheffe, “Sonar tracking of multiple targets using joint probabilistic data association,” IEEE journal of Oceanic Engineering, vol. 8, no. 3, pp. 173–184, 1983.
  * [18] G. Battistelli, L. Chisci, G. Mugnai, A. Farina, and A. Graziano, “Consensus-based linear and nonlinear filtering,” IEEE Transactions on Automatic Control, vol. 60, no. 5, pp. 1410–1415, 2014.
  * [19] G. Battistelli and L. Chisci, “Kullback–leibler average, consensus on probability densities, and distributed state estimation with guaranteed stability,” Automatica, vol. 50, no. 3, pp. 707–718, 2014.
  * [20] M. Chu, H. Haussecker, and F. Zhao, “Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks,” The International Journal of High Performance Computing Applications, vol. 16, no. 3, pp. 293–313, 2002.
  * [21] K. Zheng and A. Pronobis, “From pixels to buildings: End-to-end probabilistic deep networks for large-scale semantic mapping,” arXiv preprint arXiv:1812.11866, 2018.
  * [22] D. Bertsekas, “Rollout algorithms for discrete optimization: A survey,” Handbook of Combinatorial Optimization, D. Zu and P. Pardalos, Eds. Springer, 2010.
  * [23] Y. He and E. K. Chong, “Sensor scheduling for target tracking: A monte carlo sampling approach,” Digital Signal Processing, vol. 16, no. 5, pp. 533–545, 2006.
  * [24] D. Schuhmacher, B.-T. Vo, and B.-N. Vo, “A consistent metric for performance evaluation of multi-object filters,” IEEE transactions on signal processing, vol. 56, no. 8, pp. 3447–3457, 2008.