1
Sensor Assignment Algorithms to Improve
Observability while Tracking Targets
Lifeng Zhou, Student Member, IEEE, and Pratap Tokekar, Member, IEEE
Abstract—We study two sensor assignment problems for multi-
target tracking with the goal of improving the observability of
the underlying estimator. We consider various measures of the
observability matrix as the assignment value function. We first
study the general version where the sensors must form teams to
track individual targets. If the value function is monotonically
increasing and submodular then a greedy algorithm yields a
1/2–approximation. We then study a restricted version where
exactly two sensors must be assigned to each target. We present
a 1/3–approximation algorithm for this problem which holds for
arbitrary value functions (not necessarily submodular or mono-
tone). In addition to approximation algorithms, we also present
various properties of observability measures. We show that the
inverse of the condition number of the observability matrix is
neither monotone nor submodular, but present other measures
which are. Specifically, we show that the trace and rank of the
symmetric observability matrix are monotone and submodular
and the log determinant of the symmetric observability matrix
is monotone and submodular when the matrix is non-singular.
If the target’s motion model is not known, the inverse cannot be
computed exactly. Instead, we present a lower bound for distance
sensors. In addition to theoretical results, we evaluate our results
empirically through simulations.
I. INTRODUCTION
Assigning sensors to better track targets is a well-studied
problem [1]–[13]. The typical setup is to formulate a one-to-
one assignment problem which can be solved using bipartite
graph matching algorithms [14]. Unlike these works, we focus
on scenarios where multiple sensors can be assigned to each
target. Furthermore, the utility of assigning multiple sensors
may not even be a simple addition of individual utilities, and
can have diminishing returns. We study two versions of these
many-to-one assignment problems and give constant-factor
approximation algorithms for each.
We study these assignment problems in settings where
assigning the right set of sensors can improve the observability
in tracking potentially mobile targets using noisy sensors. The
performance of the target state estimators can be improved
by exploiting the observability of the underlying system [15]–
[18]. Our formulation is motivated by scenarios where sensing
multiple targets by the same sensor can be time-consuming as
is the case in the following applications. For example, Tokekar
et al. [19] presented a system to track radio-tagged fish in
which each radio tag is assigned a unique frequency. In order
to get a measurement for one frequency, the sensor spends two
seconds listening to the periodic emissions. Therefore, tracking
multiple targets by the same sensor can be time-consuming.
Motivated by these scenarios, we seek to assign sensors to
track targets with the constraint that each sensor is assigned at
most one target. However, multiple sensors can be assigned to
track the same target. In fact, more sensors can often improve
the tracking performance.
We first study a general assignment problem where there
is no restriction on the number of sensors assigned to a
target. We let the algorithm decide the optimal configuration
of sensor teams assigned to each target. If the value function
is submodular and monotone,1 a greedy algorithm gives a
1/2–approximation [20]. In general, this bound is tighter,
i.e., 1 −1/e by using the randomized continuous greedy
algorithm [21]. However, for a deterministic algorithm, 1/2–
approximation is the best-known result [21]. We show that
observability measures such as the trace and rank of the
symmetric observability matrix are submodular and monotone
and the log determinant is submodular and monotone when the
symmetric observability matrix is non-singular. However, the
inverse of the condition number, a commonly-used measure,
is neither monotone nor submodular, which is shown by a
counterexample.
We then study a restricted version of the problem where
the value function can be arbitrary (not necessarily monotone
and submodular) but exactly two sensors must be assigned
to a target. In fact, we show in
Corollaries 1 and 2 that
at least two range sensors must be assigned for the inverse
condition number to be greater than zero. Even for the case
of bearing sensors, it is known that two sensors are necessary;
there exists work on assignment and placement of pairs of
bearing sensors for improving target tracking [5], [7]. We study
the analogous problem for range sensors. We prove that the
greedy algorithm achieves a 1/3–approximation of the optimal
solution for assigning pairs of range sensors.
Observability is a basic concept in control theory and has
been widely applied in robotics. Observability for range-only
beacon sensors, in particular, has been closely studied for
underwater navigation. Gadre and Stilwell [15] analyzed the
local and global observability [22] for the localization of
an autonomous underwater vehicle by an acoustic beacon.
The problems of single vehicle localization and multi-vehicle
relative localization are studied in [17] using an observability
criterion introduced in [23]. In these works, it is the sensors
that are moving. Consequently, the sensors know their control
vectors and can thus, compute the observability matrix and its
measures. When tracking a target, however, the control inputs
for the targets may be unknown. In recent work, Williams
and Sukhatme [18] studied a multi-sensor localization and
target tracking problem where they showed how to leverage
graph rigidity to improve the observability for sensor team
1We use “monotone” and “monotone increasing” interchangeably.
arXiv:1709.06428v3  [cs.RO]  23 Oct 2018
2
localization and robust target tracking.
Unlike these works, we consider scenarios where the control
inputs for the targets are not known to the sensors. Conse-
quently, we cannot compute the observability matrix exactly.
Instead, we present a novel lower bound on the observability
for the case of unknown target motion tracked by range-
only sensors. Specifically, we show how to lower bound the
condition number [23] of the partially known observability
matrix using only the known part (Section III). The result
is specific to the problem at hand where the inputs appear,
linearly, on a single line of the observability matrix.
In addition to theoretical results, we conduct simulations to
evaluate the empirical performance of the algorithms. We find
that sensors are assigned to targets almost uniformly using
the greedy algorithm for the first problem (Section V-A). The
greedy algorithm for the second problem performs much better
than 1/3 in practice (Section V-B).
II. OVERVIEW OF THE PROBLEM AND RESULTS
In this section, we first formally define the problems that
are studied and then summarize the main contributions of this
work.
A. Problem Formulation
We consider a scenario where there are N sensors and L
targets in the environment. We use σ(tl) to represent the set of
sensors assigned to target tl. σ−1(si) gives the set of targets
assigned to sensor si. We use σi(tl) to give the ith sensor as-
signed to target tl. We order the assigned sensors by using their
IDs such that σ1(tl) < σ2(tl) < σ3(tl) < . . .. Let ω(si, sj, tl),
and ω(Si, tl) be some measure of the observability of tracking
tl with si and sj, and with a set of sensor(s) Si, respectively.
We calculate the observability measure by taking account of
the relative positions of sensors and targets (which will appear
in the observability matrix) at every time step.
We start with the problem of assigning a set of sensors
to each target. The sensors form teams of varying sizes to
track individual targets. Sensors within a team can share
measurements so as to better track the targets. We constrain
each sensor to be assigned to only one target. This is motivated
by scenarios where sensing multiple targets can be time
consuming (as is the case with radio sensors [19], [24] or
communicating multiple measurements with the team can be
time and energy consuming.
Problem 1 (General Assignment) Given a set of sensors,
S := {s0, . . . , sN} and a set of targets, T := {t0, . . . , tL},
find an assignment of sets of sensors to targets to
maximize
L
X
l=1
ω(σ(tl), tl)
(1)
with the added constraint that each sensor is assigned to at
most one target.
Problem 1 is the general assignment problem which is
difficult to solve for arbitrary ω(·). In order to solve the
assignment problem for arbitrary value functions, we consider
a restricted case where each target is tracked by exactly two
sensors.
Problem 2 (Non-overlapping Pair Assignment) Given
a
set of sensors, S := {s0, . . . , sN} and a set of targets,
T
:= {t0, . . . , tL}, find an assignment of non-overlapping
pairs of sensors to targets:
maximize
L
X
l=1
ω(σ1(tl), σ2(tl), tl)
(2)
with the added constraint each sensor is assigned to at most
one target. That is, for all i = 1, . . . , N we have |σ−1(si)| ≤
1, assuming N ≥2L.
B. Contributions
The main contributions of this paper are summarized as
follows.
1) We derive a lower bound on the inverse of the condition
number of the observability matrix which is useful when
the control input for the target is not known.
2) We show that the condition number of the observability
matrix is neither submodular nor monotone increasing.
We show that the trace and the rank of the symmetric
observability matrix are submodular and monotone in-
creasing. We also show the log determinant of the sym-
metric observability matrix is submodular and monotone
when the symmetric observability matrix is non-singular.
3) We
present
a
greedy
assignment
algorithm
that
yields a 1/2–approximation for Problem 1 and 1/3–
approximation for Problem 2.
4) We verify the performance of our proposed greedy
algorithm with various observability measures (that not
necessary submodular) through extensive simulations.
We start by showing how to bound the inverse of condition
number (Section III) and then present the assignment algo-
rithms (Section IV)
III. BOUNDING THE OBSERVABILITY
Consider a mobile target tl whose position is denoted by
ptl. Suppose there are N stationary sensors that can measure
the distance2 to the target. We have:
 ˙ptl = utl,
zsi = hi(ptl) = 1
2∥psi −ptl∥2
2, i = 1, ..., N
(3)
where ptl := [xtl, ytl]T gives the 2D position of the target, and
utl := [ulx, uly] defines its control input, which is unknown to
the sensor. Let utl,max ≜max ∥utl∥2. zsi defines the range-
only measurement from each sensor si whose position is given
by psi = [xsi, ysi]T . For simplicity, we also assume that the
target does not collide with any sensor, i.e., ∥psi −ptl∥2 ̸= 0
and no two sensors are deployed at the same position.
We analyze the weak local observability matrix, O(ptl, utl),
of this multi-sensor target tracking system. We show how
to lower bound the inverse of the condition number of
2We use the square of the distance/range for mathematical convenience.
3
O(ptl, utl), given by C−1(O(ptl, utl)), independent of utl. We
also show that the lower bound, C−1(O(ptl, utl)), is tight.
We compute the local nonlinear observability matrix by
using Lie derivatives [18], [22] for this system (Equation 3)
as,
O(ptl, utl) =


∇Lh1
0
∇Lh1
1
...
∇Lh2
0
∇Lh2
1
...
...
∇LhN
0
∇LhN
1...


=


xtl −xs1, ytl −ys1
ulx, uly
0, 0
...
xtl −xs2, ytl −ys2
ulx, uly
0, 0
...
...
xtl −xsN , ytl −ysN
ulx, uly
0, 0
...


.
(4)
This equation can be rewritten as,
O(ptl, utl)
=


xtl −xs1, ytl −ys1
xtl −xs2, ytl −ys2
...
xtl −xsN , ytl −ysN
ulx, uly


(N+1)×2
.
(5)
The state of the target tl is weakly locally observable if the
local nonlinear observability matrix has full column rank [22].
However, the rank test for the observability of the system
does not tell the degree of the observability or how good the
observability is. The condition number [23], defined as the
ratio of the largest singular value to the smallest, can be used
to measure this degree of unobservability. We use the inverse
of condition number given as,
C−1(O(ptl, utl)) = σmin(O(ptl, utl))
σmax(O(ptl, utl)).
(6)
Note that, C−1 ∈[0, 1]. C−1 = 0 means O(ptl, utl) is singular
and C−1 = 1 means O(ptl, utl) is well conditioned. A larger
C−1 means better observability (see more details in [17]).
In the local nonlinear observability matrix O(ptl, utl), utl
is unknown and not controllable by the sensor. On the other
hand, ptl −psi, depends on the relative state between each
sensor si and target tl and is known to the sensor (assuming
an estimate of the target’s position is known). Thus, we first
partition O(ptl, utl) into the known and unknown parts as,
O(ptl, utl) =
O(ptl)
O(utl)

,
(7)
where
O(ptl) :=


xtl −xs1, ytl −ys1
xtl −xs2, ytl −ys2
...
xtl −xsN , ytl −ysN

,
(8)
and
O(utl) :=
ulx, uly

,
(9)
indicate the contributions from the sensor-target relative state
and target’s control input, respectively. Since O(utl) is un-
known, we cannot compute C−1(O(ptl, utl)) exactly. Instead,
we compute its lower bound as below.
Theorem 1 For the multi-sensor-target system (Equation 3)
with the number of sensors, N ≥2, the inverse of the condition
number is lower bounded by
σmin(O(ptl))
q
σ2max(O(ptl)) + u2
tl,max
.
We present the full proof for this and other results in the
appendix.
We wish to improve the worst case, i.e., the lower bound
of C−1(O(ptl, utl)), by optimizing the sensor-target relative
state by assigning a different subset of sensors to the target.
In the following, we will show that at least two sensors are
required to improve the lower bound.
Corollary 1 The lower bound of the observability metric in
one-sensor-target system, C−1(Oi(ptl, utl)),
is identically
zero. It does not depend on the position of the sensor and
therefore cannot be controlled by the sensors.
When the number of sensors, N ≥2, we have a positive
result that shows that the sensors can improve the lower bound
on the inverse of the condition number of optimizing their
positions, even though the contribution to the observability
matrix from the target’s input, O(utl), is unknown and cannot
be controlled.
Corollary 2 Suppose that the number of sensors assigned
to tl, N
≥2. If the sensors increase C−1(O(ptl)) and
σmin(O(ptl)) (the inverse of condition number and the small-
est singular number of the relative state contribution O(ptl)),
then the lower bound of C−1(O(ptl, utl)) also increases.
Remark 1 The lower bound C−1(O(ptl, utl)) is tight when
the target is known to be stationary. If uo ∈{0}, O(ptl, utl) =
O(ptl) by Equation 5 and Equation 8. Thus, from Equa-
tion 6 and Theorem 1, the lower bound C−1(O(ptl, utl)) =
C−1(O(ptl, utl)), which implies that the lower bound is tight.
Next, we use these results for assigning sensors to targets.
IV. ASSIGNMENT ALGORITHMS
So far, we have assumed that we know the true position,
ptl(k), of the target at time k. In practice, we only have
an estimate, ˆptl(k), for tl along with its covariance Σtl(k).
The estimate is obtained by fusing measurements using, for
example, an Extended Kalman Filter (EKF). We use the
estimated position of the target for the assignment algorithms
in the simulation (Section V).
A. General assignment as Submodular Welfare Optimization
We first study the General Assignment (Problem 1) where
each target tl is tracked by a subset of sensors σ(tl) ⊂S, l ∈
{1, 2, ..., L} whose cardinality is not necessarily two. This is
known as submodular welfare problem in the literature [21]
4
where the objective is to maximize Pn
i=1 wi(Si) for indepen-
dent sets {Si|Si ⊆S, i = {1, 2, ...n}} by using monotone
and submodular utility functions wi. A greedy algorithm [20]
yields a 1/2–approximation for this problem. We first show
that the lower bound of the inverse of the condition number
is neither monotone nor submodular. This is not surprising
since it has been shown that similar measures for analogous
versions of the controllability matrix are also not submodular
or monotone increasing [25].
Theorem 2 The lower bound of the inverse of condition
number function ω(·) is neither monotone increasing nor
submodular.
Proof: We prove the claim by giving two counter-
examples.
Case 1: Given the sensors s1(0, 0), s2(2
√
3, −9), s3(
√
3, 3)
and target t1(
√
3, 1) with ut1,max
=
1 in 2-D plane,
ω({s1, s3}) = 0.5345 > ω({s1, s2, s3}) = 0.1823, which
shows ω(·) is not monotone increasing.
Case 2: Given the sensors s1(0, 0), s2(2
√
3, 0), s3(
√
3, 0.1),
s4(
√
3, 3) and target t1(
√
3, 1) with ut1,max = 1 in 2-D plane,
ω({s1, s2, s3})−ω({s1, s2}) = 0.3310−0.5345 = −0.2035 <
ω({s1, s2, s4, s3}) −ω({s1, s2, s4}) = 0.8765 −0.9258 =
−0.0493, which shows ω(·) is not submodular.
Therefore, we focus on other measures of observability and
summarize the results in Theorem 3.
Theorem 3 The trace and rank of the symmetric observability
matrix, O(ptl, utl) := OT (ptl, utl)O(ptl, utl), and of the
sensor-target relative state contribution matrix, O(ptl) :=
OT (ptl)O(ptl), are submodular (modular) and monotone in-
creasing. The log determinant of the two matrices is submod-
ular and monotone increasing if the corresponding matrix is
non-singular.
The reason that we also study the measures of the symmetric
observability matrix by sensor-target relative state contribution
is that the control input of the target is unknown, and thus
the symmetric observability matrix is not available. The proof
provided in the appendix is similar to proving that the trace of
the Gramian, the log determinant, and the rank of the Gramian
are monotone submodular [25]. Note that, if O(ptl) is singular,
its log determinant is −∞. In our sensor assignment case,
if a single sensor is assigned to target tl, O(ptl) is always
singular, i.e., det(O(ptl)) = 0 (see the proof of Corollary 1).
If no sensors are assigned to a target, then the matrix is not
defined. Thus, at least two sensors need to be assigned to a
target to ensure non-singularity of O(ptl).
B. A 1/3–approximation algorithm for Problem 2
Next, we study a more specific assignment (Problem 2)
where each target tl is tracked by a pair of sensors but
allow the value function to be arbitrary. We propose a greedy
algorithm to solve this problem. In each round, we calculate
the observability metric, ω(σ1(tl), σ2(tl), tl) for all triples
(σ1(tl), σ2(tl), tl), σ1(tl), σ2(tl) ∈S, tl ∈T , and select
the triple which has the maximum ω(σ1(tl), σ2(tl), tl), then
remove {σ1(tl), σ2(tl)} from sensor set S and remove tl from
target set T , respectively. We present the greedy approach in
Algorithm 1 where ω(GREEDY) denotes total value obtained
by the greedy approach. In this case, we can use the inverse
of the condition number as ω(·).
Algorithm 1: Greedy Non-overlapping Pair Assignment
k ←0, ω(GREEDY) ←0
while true do
Compute all possible ω(σ1(tl), σ2(tl), tl).
Pick the triple (σ1(tl), σ2(tl), tl) with maximum
ω(σ1(tl), σ2(tl), tl) defined as ωmax.
ω(GREEDY) ←ω(GREEDY) + ωmax.
Remove {si, sj} from the sensor set S and remove tl
from the target set T .
k ←k + 1
end
Theorem 4 ω(GREEDY) ≥
1
3ω(OPT) where OPT is the
optimal algorithm for Problem 2. The running time for Al-
gorithm 1 is O(N 2L2).
Proof: We first give the proof for the approximation ratio
of Algorithm 1. Recall that ω(GREEDY) and ω(OPT) will
be the sum of ω(·) terms of triples consisting of one target
and the two assigned sensors. As a shorthand, we will denote
ωg(l) and ω∗(l) to be the values of the triple assigned to tl
by GREEDY and OPT, respectively.
We show that there exists a many-to-one mapping M :
[1, · · · , L] →[1, · · · , L] such that:
1) ω∗(k) ≤ω(M(k)); and
2) |M−1(y)| ≤3 for all y ∈Y where Y ⊆[1, ..., L] is the
range of M.
That is, each triple in OPT is mapped to some triple in
GREEDY whose value is at least as high and no triple in
GREEDY has more than three terms in OPT mapped to it.
We first show that if such a mapping exists, then the main
result holds. Then, we prove the existence of such a mapping
by constructing a specific M.
If such a mapping M exists, we prove ω(GREEDY) ≥
1
3ω(OPT) as below.
ω(OPT) =
L
X
k=1
ω∗(k)
≤
L
X
k=1
ωg(M(k))
=
X
y∈Y
ωg(y)|M−1(y)|
≤3
X
y∈Y
ωg(y)
≤3
L
X
l=1
ωg(l)
= 3ω(GREEDY).
(10)
The first inequality is due to ω∗(k) ≤ωg(M(k)). The second
equality is because M maps each item in [1, ..., L] to the set
5
Y. The second inequality is due to |M−1(·)| ≤3. The third
inequality is because Y ⊆[1, ..., L].
Next, we show that such a mapping always exists by
constructing one. We will define M in the order in which the
triples are picked by GREEDY. Suppose GREEDY picks the
triple (si, sj, tl) in some round. Then ωg(l) = ω(si, sj, tl).
We will map at most three triples in OPT to this triple in
GREEDY. There are three cases.
(a) Case 1
(b) Case 2
(c) Case 3
Fig. 1. The optimal solution in three cases. In all cases, the GREEDY chooses
the triple (si, sj, tl). Case 1: The OPT charges ω(si, sj, tl) to the same triple
(si, sj, tl) chosen by the GREEDY. Case 2: The OPT charges ω(si, sj, tl)
to at most two triples — (si, sj, tm) and (sp, sq, tl). Case 3: The OPT
charges ω(si, sj, tl) to at most three triples — (si, sp, tm), (sj, sq, tn) and
(su, sv, tl). Here, i ̸= j ̸= p ̸= q ̸= u ̸= v and l ̸= m ̸= n.
1) (si, sj, tl) is also chosen by OPT (Figure 1-(a)). If
M(l) has not been defined in previous rounds, we
define M(l) = l. Note that, here ωg(l) = ω∗(l) and
|M−1(l)| = 1. Therefore, the two conditions for a valid
mapping are satisfied.
2) Exactly two of (si, sj, tl) appear in a triple chosen
by OPT (Figure 1-(b)). Consider the case where OPT
chooses (si, sj, tm) and (sp, sq, tl) where m ̸= l. All
other cases are symmetric. If M(m) has not been
defined in a previous round, we define M(m) = l. Note
that, if M(m) was not defined in a previous round, then
ω∗(m) ≤ωg(l). Otherwise, GREEDY would pick the
triple (si, sj, sm) in this round. Similarly, if M(l) is not
defined in a previous round, we define M(l) = l. By a
similar argument, if M(l) was not defined in a previous
round, ω∗(l) ≤ωg(l). Furthermore, |M−1(l)| = 2.
Therefore, the two conditions for a valid mapping are
satisfied.
3) No two of (si, sj, tl) appear in the same triple chosen
by OPT. Suppose instead they appear in three distinct
triples, (su, sv, tl), (si, sp, tm), and (sj, sq, tn) as shown
in Figure 1-(c). We can use a similar argument as
in the previous case. If any of l, m and n were not
mapped in a previous round, then we will map them to l.
Furthermore, since they were not mapped in a previous
round, their value in OPT cannot be greater than ωg(l).
Finally, |M−1(l)| ≤3. Therefore, the two conditions
for a valid mapping are satisfied.
Therefore,
given
such
a
mapping
M,
it
follows
that
ω(GREEDY) ≥1
3ω(OPT).
We next prove the running time for Algorithm 1. The
“while” loop runs for L rounds since all the targets must be
tracked eventually. Inside the “while” loop, we compute all
possible triples and find the best one. This requires O(N 2L)
time. Overall, Algorithm 1 runs in O(N 2L2) time.
It is possible to generalize this result to the case where
exactly n sensors are to be assigned to a target with n ≥2. We
can obtain a generalized bound, ω(GREEDY) ≥
1
n+1ω(OPT)
by using a proof similar to that of Theorem 4.
V. SIMULATIONS
We illustrate the performance of the assignment strategies
for sensor selection using observability measure as the perfor-
mance criterion. A video showing the algorithm in action is
submitted as supplementary material.
A. Greedy General Assignment
We first simulate the greedy assignment [20] for Problem 1
by using the trace of the symmetric observability matrix
by sensor-target relative state contribution, trace(O(ptl)) as
observability measure which is monotone and submodular
(modular) as shown in Theorem 3. Notably, for maximizing
a modular function, the greedy algorithm yields an optimal
solution. We start with the greedy assignment with 8 stationary
sensors and 3 targets moving in a circle and utl,max = 1, l ∈
{1, 2, 3} within 100 time steps in a 10 × 10 environment. At
each timestep, we use the greedy approach [20] to assign a
set of sensors to each target, and use the measurements of the
set of sensors to update the estimate of the target by EKF as
shown in Figure 2.
In order to further evaluate the greedy approach for general
assignment, we set the number of targets as L = 5 and number
of sensors, N, from 20 to 50. For each N ∈{20, 21, ..., 50},
the positions of sensors and targets are randomly generated
within [0, 100] × [0, 100] ∈R2 for 30 trials. We compare the
number of sensors assigned to one specific target, i.e., tl, l ∈
{1, 2, ...L} with the N/L as shown in Figure 3. It shows that
the sensors are assigned to each target almost evenly.
B. Greedy Non-overlapping Pair Assignment
We then simulate the greedy non-overlapping pair assign-
ment (Algorithm 1) for solving Problem 2. With the same
environment setting, we start with simulating Algorithm 1
with trace(O(ptl)) as the observability measure (Figure 4).
We know that the observability measure for greedy non-
overlapping pair assignment does not have to be monotone
submodular. Therefore, we use the log determinant of the
symmetric observability matrix by sensor-target relative state
contribution, log det(O(ptl)), and the lower bound on the
inverse of the condition number of the observability matrix,
C−1(O(ptl, utl)), for the assignment. The assignments for a
specific scenario are shown in Figures 5 and 6. Note that, even
6
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(a) k = 1 (initial time)
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(b) k = 60
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(c) k = 100
Fig. 2.
Greedy General Assignment [20] in action for tracking three targets with circular motion by using trace(O(ptl)). The three colors red, blue and
magenta specify three targets, respectively. The pentagram, filled square, solid ellipse (sometimes, it looks like a solid circle) and dotted circle indicates the
true position, estimate mean position, variance and trajectory for the target, respectively. The black diamond indicates the sensor. The solid line joining the
target and sensor indicates that the sensor is assigned to the target.
15
20
25
30
35
40
45
50
55
Number of sensors
2
4
6
8
10
12
14
Number of sensors assigned to one target
Number of sensors assigned to one specific target
Number of sensors / Number of targets
Fig. 3.
Number of sensors assigned to each target.
though a pair of sensors is assigned to target tl, O(ptl) is not
always non-singular.
For each target tl, the estimate generated by EKF includes
its mean position ˆptl and variance Σtl, l ∈{1, 2, 3}. To
evaluate the tracking performance, denote the mean error as
errtl = ∥ˆptl −ptl∥2.
(11)
and the trace of covariance as tr(Σtl). Figure 7 shows errtl
and tr(Σtl) for each target tl with the greedy algorithms to
the two assignment problem and with trace(O(ptl)) as the
measure. We can observe that the greedy general assignment
performs better for some target (e.g., t2), but performs worse
for target t1 as compared to the non-overlapping pair as-
signment (Figure 7-(b)). Both algorithms maximize the sum
of the observability measures for the three targets. In the
non-overlapping pair assignment, a pair of sensors is always
assigned to each target whereas in the general assignment,
there are situations where no sensors are assigned to a target.
This can be due to the fact that it is profitable to assign more
than two sensors to some target in order to maximize the sum.
We can observe the happening in Figure 2 where there exist
some time steps (e.g., k = 100) when less than two sensors
are assigned to a target (red), which leads to a bad tracking
performance for individual targets in the general assignment
case (Corollary 1). However, in all cases, the greedy general
assignment [20] ensures that the sum of individual measures
is within a factor of 2 of the optimal sum.
Figure 8 shows the tracking performance with the inverse
condition number and log det is comparable. The performance
with trace is worse as compared to the other two. However,
we can only use the trace for the greedy general assignment,
since it is submodular and monotone. This exactly reflects
the importance of our greedy non-overlapping pair assignment
that better observability measures, i.e., log det and inverse
condition number, which are not necessarily submodular and
monotone are also allowed.
C. Baseline Comparisons
The Non-overlapping Pair Assignment (Problem 2) is NP-
Complete. Therefore, finding ω(OPT) is infeasible in poly-
nomial time. In order to empirically evaluate the Greedy
Non-overlapping Pair Assignment (Algorithm 1), we use two
baselines. When the number of sensors and targets is small,
we compute the optimal solution using brute-force. When the
number of sensors and targets is large, we compute an upper
bound on the optimal solution value by solving a relaxed
version of Problem 2. In this relaxed version, one sensor is
allowed to be assigned to multiple targets (unlike Problem 2).
However, we still require a pair of sensors to be assigned to
at most one specific target.
We formulate the new assignment as Relaxed Pair As-
signment (Problem 3). It is clear that solving Relaxed Pair
Assignment problem optimally gives us an upper bound of
7
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(a) k = 1 (initial time)
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(b) k = 60
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(c) k = 100
Fig. 4.
Greedy Non-overlapping Pair Assignment (Algorithm 1) in action for tracking three targets with circular motion by using trace(O(ptl)). The three
colors red, blue and magenta specify three targets, respectively. The pentagram, filled square, solid ellipse (sometimes, it looks like a solid circle) and dotted
circle indicates the true position, estimate mean position, variance and trajectory for the target, respectively. The black diamond indicates the sensor. The solid
line joining the target and sensor indicates that the sensor is assigned to the target.
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(a) k = 1 (initial time)
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(b) k = 60
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(c) k = 100
Fig. 5.
Greedy Non-overlapping Pair Assignment (Algorithm 1) in action for tracking three targets with circular motion by using log det(O(ptl)). The
three colors red, blue and magenta specify three targets, respectively. The pentagram, filled square, solid ellipse (sometimes, it looks like a solid circle) and
dotted circle indicates the true position, estimate mean position, variance and trajectory for the target, respectively. The black diamond indicates the sensor.
The solid line joining the target and sensor indicates that the sensor is assigned to the target.
the optimality for Non-overlapping Pair Assignment problem.
We can use this upper bound for the comparison of the greedy
approach in Non-overlapping Pair Assignment.
Problem 3 (Relaxed Pair Assignment) Given a set of sen-
sors, S
:=
{s0, . . . , sN} and a set of targets, T
:=
{t0, . . . , tL}, find an assignment of non-repetition pairs of
sensors to targets:
maximize
L
X
l=1
ω(σ1(tl), σ2(tl), tl)
(12)
with the added constraint that all pairs are non-repetition,
that is, ∀k, l = 1, . . . , L, k ̸= l, σ1(tk) ̸= σ1(tl) or σ2(tk) ̸=
σ2(tl).
The Relaxed Pair Assignment can be solved optimally
by using maximum weight perfect bipartite matching (MW-
PBM) [26]. Note that a sensor can be matched in multiple
distinct pairs and assigned to multiple targets. This violates the
constraint in Problem 2 where each sensor can be matched to
at most one pair and assigned at most once. The MWPBM can
be solved using the Hungarian algorithm [14] in polynomial
time.
While the Relaxed Pair Assignment computes an upper
bound for ω(OPT), we can compute ω(OPT) exactly using
brute-force when N and L are small by enumerating all the
possibilities. There are QL−1
l=0
N−2l
2


possible cases. Thus, the
brute-force algorithm has an exponential running time.
Figure 9 shows the total value of the greedy algorithm,
ω(GREEDY), the brute-force algorithm, ω(OPT), and the
MWPBM, ω(MWPBM) for log det and inverse condition
number. We simulate the following environment: N = 2L,
the positions of sensors and targets are generated randomly
within [0, 100] × [0, 100] ∈R2 for 30 trials for each L, and
the target’s maximum control input is uo,max = 1.
We run the comparison code on a MacBook Pro with 2.6
GHz Intel Core i5 and 8 GB Memory. When L = 7 and
8
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(a) k = 1 (initial time)
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(b) k = 60
-4
-3
-2
-1
0
1
2
3
4
5
6
x
-2
-1
0
1
2
3
4
5
6
7
8
y
(c) k = 100
Fig. 6.
Greedy Non-overlapping Pair Assignment (Algorithm 1) in action for tracking three targets with circular motion by using C−1(O(ptl, utl)). The
three colors red, blue and magenta specify three targets, respectively. The pentagram, filled square, solid ellipse (sometimes, it looks like a solid circle) and
dotted circle indicates the true position, estimate mean position, variance and trajectory for the target, respectively. The black diamond indicates the sensor.
The solid line joining the target and sensor indicates that the sensor is assigned to the target.
N = 14, MATLAB runs out-of-memory when running the
brute-force algorithm (there are 681080400 possible cases for
each trial). When L = 6 and N = 12, brute-force could not
finish after running for 25 hours. Thus, we only consider the
case when L is varied from 1 to 5.
From Figure 9, we observe that ω(MWPBM) is the highest
because the MWPBM gives the upper bound of ω(OPT). More
importantly, ω(GREEDY) is close to ω(OPT) and much higher
than the theoretical bound of 1
3ω(OPT).
Next, we compare ω(GREEDY) and ω(MWPBM), without
brute-force, for larger values of L and N. We vary L from
1 to 20 and set N = 2L. For both observability measures,
Figure 10 shows that ω(GREEDY) is close to ω(MWPBM)
and much higher than 1
3ω(MWPBM). Thus, even though we
give a theoretical 1/3–approximation for the greedy algorithm,
it performs much better in practice.
VI. CONCLUSION
In this paper, we solved sensor assignment problems to
improve the observability for target tracking. We derived the
lower bound on the inverse of the condition number of the
observability matrix for a system with a mobile target and N
stationary sensors. The lower bound considers only the known
part of the observability matrix — the sensor-target relative
position and an upper bound on the target’s speed. We showed
how this lower bound can be employed for sensor selection.
We considered two sensor assignment problems for which we
presented constant-factor approximation algorithms. While we
presented the two algorithms as alternatives to each other, they
can also be combined to give better results. We proved the log
det, log det(O(ptl)) is submodular and monotone only when
O(ptl) is non-singular and performs better in terms of tracking
than the trace (which is submodular and monotone). We can
combine the greedy general assignment with the greedy non-
overlapping pair assignment to use log det as the observability
measure. First, we use the non-overlapping assignment to
assign a pair of sensors to each target to make sure that O(ptl)
is non-singular. Then, we can improve the assignment strategy
by using the greedy general assignment strategy to assign more
sensors to each target.
Our immediate work is focused on assigning sensors to
cover an area instead of tracking a group of targets. Another
avenue is designing an efficient set covering strategy based on
observability measures which are submodular and monotone.
In many scenarios, the sensors are actually robots that are
mobile [3], [27]–[33]. in such cases, in addition to solving
the assignment problem, we can also optimize the trajectories
of the sensors. An immediate future work is to devise joint
assignment and planning algorithms for better observability.
Many of the results presented can be easily extended to
3D tracking. We conjecture that at least three sensors will be
required for ensuring non-trivial lower bounds of the inverse
condition number in 3D. The non-overlapping pair assignment
can be extended to assigning non-overlapping triplets. We
conjecture that this algorithm will yield a 1/4-approximation.
APPENDIX
PROOF FOR THEOREM 1
Proof: The singular values of O(ptl, utl) can be found
as the square-root of the eigenvalues of the symmetric observ-
ability matrix, O(ptl, utl), given as [34],
O(ptl, utl)
=
OT (ptl, utl)O(ptl, utl)
=
OT (ptl)O(ptl) + OT (utl)O(utl). (13)
 p
λmin(O(ptl, utl)) = σmin(O(ptl, utl)),
p
λmax(O(ptl, utl)) = σmax(O(ptl, utl)).
(14)
We can use Weyl and dual Weyl inequalities to bound the
singular values. For Hermitian matrices X and Y with r
eigenvalues written in increasing order λ1(X) ≤λ2(X) ≤
. . . ≤λr(X) and λ1(Y ) ≤λ2(Y ) ≤. . . ≤λr(Y ),
respectively, the Weyl inequalities [35] is given by,
λi+j−1(X + Y ) ≥λi(X) + λj(Y )
(15)
9
0
10
20
30
40
50
60
70
80
90
100
0
1
2
3
errt1
0
10
20
30
40
50
60
70
80
90
100
0
1
2
3
errt2
Greedy Non-overlapping Pair with trace
Greedy General with trace
0
10
20
30
40
50
60
70
80
90
100
k
0
0.5
1
1.5
errt3
(a)
0
10
20
30
40
50
60
70
80
90
100
0
5
10
15
tr(Σt1)
0
10
20
30
40
50
60
70
80
90
100
0
0.5
1
tr(Σt2)
Greedy Non-overlapping Pair with trace
Greedy General with trace
0
10
20
30
40
50
60
70
80
90
100
k
0
0.5
1
1.5
tr(Σt3)
(b)
Fig. 7.
Comparison of mean error (a) and trace of covariance (b) for three-
target tracking within 100 time steps by Greedy General Assignment [20] with
trace(O(ptl)) and Greedy Non-overlapping Pair Assignment (Algorithm 1)
with trace(O(ptl)).
where i, j ≥1 and i + j −1 ≤r. Similarly, the dual Weyl
inequalities is given by
λi+j−r(X + Y ) ≤λi(X) + λj(Y )
(16)
where i, j ≥1 and i + j −r ≤r.
Since O(ptl, utl)
∈
R2×2, OT (ptl)O(ptl)
∈
R2×2
and
OT (utl)O(utl)
∈
R2×2
are
symmetric
matrices,
they
are
Hermitian
with
the
eigenvalues
(in
ascending order) as λ1(O(ptl, utl))
≤
λ2(O(ptl, utl)),
λ1(OT (ptl)O(ptl))
≤
λ2(OT (ptl)O(ptl))
and
λ1(OT (utl)O(utl))
≤
λ2(OT (utl)O(utl)).
Following
0
10
20
30
40
50
60
70
80
90
100
0
0.5
1
1.5
errt1
0
10
20
30
40
50
60
70
80
90
100
0
0.5
1
1.5
2
2.5
errt2
Greedy Non-overlapping Pair with inv(cond)
Greedy Non-overlapping Pair with log(det)
Greedy Non-overlapping Pair with trace
0
10
20
30
40
50
60
70
80
90
100
k
0
0.5
1
errt3
(a)
0
10
20
30
40
50
60
70
80
90
100
0
0.5
1
tr(Σt1)
0
10
20
30
40
50
60
70
80
90
100
0
0.5
1
tr(Σt2)
Greedy Non-overlapping Pair with inv(cond)
Greedy Non-overlapping Pair with log(det)
Greedy Non-overlapping Pair with trace
0
10
20
30
40
50
60
70
80
90
100
k
0
0.5
1
tr(Σt3)
(b)
Fig. 8.
Comparison of mean error (a) and trace of covariance (b) for
three-target tracking within 100 time steps by Greedy Non-overlapping
Pair Assignment (Algorithm 1) with C−1(O(ptl)), log det(O(ptl)) and
trace(O(ptl)).
the Weyl and dual Weyl inequalities, we get
λ1(O(ptl, utl)) ≥λ1(OT (ptl)O(ptl)) + λ1(OT (utl)O(utl)),
λ2(O(ptl, utl)) ≤λ2(OT (ptl)O(ptl)) + λ2(OT (utl)O(utl)).
(17)
Thus,
λ1(O(ptl, utl))
λ2(O(ptl, utl)) ≥
λ1(OT (ptl)O(ptl)) + λ1(OT (utl)O(utl))
λ2(OT (ptl)O(ptl)) + λ2(OT (utl)O(utl)).
(18)
Then, from Equation 14 and Equation 18, the inverse of the
10
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
Number of targets
0
10
20
30
40
50
60
70
80
90
ω(MWPBM)
ω(OPT)
ω(GREEDY)
1
3ω(OPT)
(a)
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
Number of targets
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
ω(MWPBM)
ω(OPT)
ω(GREEDY)
1
3ω(OPT)
(b)
Fig. 9.
Comparison of the total value charged by greedy approach (Al-
gorithm 1) with the brute-force algorithm and the maximum perfect pair
matching by using log det log(det(O(ptl))) (a) and inverse condition number
C−1(O(ptl, utl)) (b), respectively.
condition number of the local nonlinear observability matrix,
C−1(O(ptl, utl)) =
s
λ1(O(ptl, utl))
λ2(O(ptl, utl))
≥
s
λ1(OT (ptl)O(ptl)) + λ1(OT (utl)O(utl))
λ2(OT (ptl)O(ptl)) + λ2(OT (utl)O(utl)).
(19)
Thus, we have the lower of the inverse of the condition
number,
s
λ1(OT (ptl)O(ptl)) + λ1(OT (utl)O(utl))
λ2(OT (ptl)O(ptl)) + λ2(OT (utl)O(utl)).
(20)
By calculating the eigenvalues of symmetric matrix of target’s
control contribution,
OT (utl)O(utl) =
 u2
lx
ulxuly
ulyulx
u2
ly

,
0
2
4
6
8
10
12
14
16
18
20
22
Number of targets
0
50
100
150
200
250
300
350
400
ω(MWPBM)
ω(GREEDY)
1
3ω(MWPBM)
(a)
0
2
4
6
8
10
12
14
16
18
20
22
Number of targets
-2
0
2
4
6
8
10
12
14
16
18
20
ω(MWPBM)
ω(GREEDY)
1
3ω(MWPBM)
(b)
Fig. 10.
Comparison of the total value charged by greedy approach
(Algorithm 1) with the maximum perfect pair matching by using log det
log(det(O(ptl))) (a) and inverse condition number C−1(O(ptl, utl)) (b),
respectively.
we have,
λ1(OT (utl)O(utl)) = 0
λ2(OT (utl)O(utl)) = u2
lx + u2
ly = u2
tl.
(21)
Then the lower bound of C−1(O(o, uo)) (Equation 20) is
calculated as
C−1(O(ptl, utl))
=
s
λ1(OT (ptl)O(ptl))
λ2(OT (ptl)O(ptl)) + u2
tl
=
σmin(O(ptl))
q
σ2max(O(ptl)) + u2
tl
(22)
Equation
22
gives
the
main
lower
bound.
Note
that
C−1(O(ptl, utl)) cannot be determined since target’s control
input, utl, is unknown. However, we know that ||utl||2 ≤
11
utl,max. Therefore,
C−1(O(ptl, utl)) ≥
σmin(O(ptl))
q
σ2max(O(ptl)) + u2
tl,max
(23)
This yields our main lower bound result.
PROOF FOR COROLLARY 1
Proof: The local observability matrix for one-sensor-
target, si −tl system can be derived from Equation 5 as,
Oi(ptl, utl) =
xtl −xsi
ytl −ysi
ulx
uly

.
(24)
The sensor-target relative state contribution is
Oi(ptl) =
xtl −xsi
ytl −ysi

.
(25)
The si −tl system is weakly locally observable if Oi(ptl, utl)
has full column rank, i.e., (xtl −xsi)uly ̸= (ytl −ysi)ulx.
However, the sensor does not know the target’s control input,
utl.
Given the symmetric matrix by sensor-target relative state
contribution of si −tl system,
OT
i (ptl)Oi(ptl) =
(xtl −xsi)2, (xtl −xsi)(ytl −ysi)
(xtl −xsi)(ytl −ysi), (ytl −ysi)2

,
(26)
we have,



σmin(Oi(ptl)) =
p
λmin(OT
i (ptl)Oi(ptl)) = 0,
σmax(Oi(ptl)) =
p
λmax(OT
i (ptl)Oi(ptl))
=
p
(xtl −xsi)2 + (ytl −ysi)2.
(27)
Thus,
from
Equation
22,
the
lower
bound
for
C−1(Oi(ptl, utl)) is
σmin(Oi(ptl))
q
σ2max(Oi(ptl))+u2
tl
= 0. Consequently,
the lower bound cannot be controlled by the sensor.
PROOF FOR COROLLARY 2
Proof: According to Equation 14, we have,
σmin(O(ptl, utl))
σmax(O(ptl, utl)) =
p
λmin(O(ptl, utl))
p
λmax(O(ptl, utl))
.
(28)
Following Equations 18 and 21, we have the lower bound for
λmin(O(ptl,utl))
λmax(O(ptl,utl)), described as
λmin(O(ptl, utl))
λmax(O(ptl, utl)) ≥
λmin(OT (ptl)O(ptl))
λmax(OT (ptl)O(ptl)) + u2
tl
,
(29)
Now, we equivalently rewrite the statement of the theorem
(using eigenvalues instead of singular values) as: if



λmin(O
′ T (ptl)O
′(ptl))
λmax(O′ T (ptl)O′(ptl)) ≥
λmin(OT (ptl)O(ptl))
λmax(OT (ptl)O(ptl)),
λmin(O
′T (ptl)O
′(ptl)) ≥λmin(OT (ptl)O(ptl))
(30)
then
λmin(O
′T (ptl)O
′(ptl))
λmax(O
′T (ptl)O
′(ptl)) + u2
tl
≥
λmin(OT (ptl)O(ptl))
λmax(OT (ptl)O(ptl)) + u2
tl
(31)
where the λ and λ′ denotes the eigenvalues before and after the
sensors increase C−1(O(ptl)) and σmin(O(ptl), respectively.
We start with the left-hand side of Equation 31 to get,
λ
′
min,l
λ
′
max,l + u2
tl
−
λmin,l
λmax,l + u2
tl
=
λ
′
min,lλmax,l −λ
′
max,lλmin,l
(λ
′
max,l + u2
tl)(λmax,l + u2
tl)
+
u2
tl(λ
′
min,l −λmin,l)
(λ
′
max,l + u2
tl)(λmax,l + u2
tl)
(32)
where λ
′
min,l, λ
′
max,l, λmin,l and λmax,l denote the simpli-
fied forms of λmin(O
′T (ptl)O
′(ptl)), λmax(O
′T (ptl)O
′(ptl)),
λmin(OT (ptl)O(ptl)) and λmax(OT (ptl)O(ptl)), respectively.
Note that Equation 30 can be reordered to match the numerator
in the second line of Equation 32. Then we have,
λ
′
min,l
λ
′
max,l + u2
tl
−
λmin,l
λmax,l + u2
tl
≥0.
(33)
Hence the claim is proved.
Remark 2 Equation 30 is sufficient, but not necessary con-
dition to guarantee Equation 31. This is because Equation 31
can be established with a weaker condition,
λ
′
min,lλmax,l −λ
′
max,lλmin,l + u2
tl(λ
′
min,l −λmin,l) ≥0.
We choose the stricter condition (Equation 30) because it is
conceptually easy to separate and eliminate the influence on
the degree of observability from target’s control input, utl,
which is unknown and uncontrolled.
PROOF FOR THEOREM 3
We first give the proofs of the properties of the symmetric
observability matrix by sensor-target relative state contribu-
tion, O(ptl). Then we obtain the similar result for the sym-
metric observability matrix, O(ptl, utl) by a minor extension.
For the target tl, denote its sensor-target relative state vector as
ril = [xtl−xsi, ytl−ysi], i ∈{1, 2, · · · , N}. Denote its ground
sensor-target relative state set as V = {r1l, r2l, · · · , rNl}. For
a given W ⊆V, we form RW = [R0l, rwl]T with a (pos-
sibly empty) existing matrix R0l and the associated sensor-
target relative vector rwl ∈W. We calculate the associated
symmetric observability matrix by sensor-target relative state
contribution as O(ptl)W = RT
wlRwl. To simplify notation, we
write O(ptl)W as OW.
Lemma 1 The set function mapping subsets W ⊆V to
the trace of the associated symmetric observability matrix by
sensor-target relative state contribution, f(W) = trace(OW)
is modular (submodular) and monotone increasing.
Proof: The symmetric observability matrix by sensor-
target relative state contribution associated with W, OW can
be calculated as
OW = RT
wlRwl =
X
rwl∈W
rT
wlrwl.
(34)
12
Thus, for any W ⊆V , OW is simply a sum of the symmetric
observability matrix by sensor-target relative state contribution
associated with the individual rows of RW. Given the trace is
a linear matrix function, we have
f(W)
=
trace(OW)
=
trace
X
rwl∈W
rT
wlrwl
=
X
rwl∈W
trace(rT
wlrwl).
(35)
If no sensors are assigned to the target tl, define trace(∅) = 0.
Then we have f(W) = trace(OW) is a modular (submodular)
and monotone increasing set function.
Lemma 2 The set function mapping subsets W ⊆V to
the rank of the associated symmetric observability matrix by
sensor-target relative state contribution, f(W) = rank(OW)
is submodular and monotone increasing.
Proof: Given two linear transformations Q1, Q2 ∈Rn×n,
we have
rank(Q1 + Q2)
= rank(Q1) + rank(Q2)
−dim(range(Q1) ∩range(Q2)).
(36)
From [36], we know that a set function f : 2V →R
is submodular if and only if the derived set functions fr :
2V−{r} →R
fr(W) = f(W ∪{r}) −f(W),
are monotone decreasing for all r ∈V. We can form the
marginal gain functions for rank measure as
fr(W) = rank(OW∪r) −rank(OW)
= rank(Or) −dim(range(OW) ∩range(Or)).
(37)
Note that, rank(Or) is a constant and dim(range(OW)) only
increases with W. Thus, fr is monotone decreasing which
means f(W) = rank(QW) is a submodular function. From
the additivity property of the OW (Equation 34), it is clear
that f(W) = rank(QW) is monotone increasing.
Lemma 3 The set function mapping subsets W ⊆V to
the log det of the associated symmetric observability ma-
trix by sensor-target relative state contribution, f(W) =
log det(OW) is submodular and monotone increasing if OW
is non-singular.
Proof: We use the similar idea to show the submodularity
of the log det measure, namely, showing that the derived set
functions, fr : 2V−{r} →R
fr(W) = log det(OW∪r) −log det(OW)
= log det(OW + Or) −log det(OW),
are monotone decreasing for any r ∈V. Take any W1 ⊆W2 ⊆
V −{r}. By the additivity property of the OW (Equation 34),
it is clear that W1 ⊆W2 ⇒OW1 ⪯OW2. Define O(γ) =
OW1 + γ(OW2 −OW1) for γ ∈[0, 1]. Clearly, O(0) = OW1
and O(1) = OW2. Now define
ˆfr(O(γ)) = log det(O(γ) + Or) −log det(O(γ)).
(38)
Note that ˆfr(O(0)) = ˆfr(OW1) and ˆfr(O(1)) = ˆfr(OW2).
We have
d
dγ
ˆfr(O(γ))
= d
dγ [log det(O(γ) + Or) −log det(O(γ))]
= trace[(O(γ) + Or)−1(OW2 −OW1)]
−trace[(O(γ))−1(OW2 −OW1)]
= trace[((O(γ) + Or)−1 −(O(γ))−1)(OW2 −OW1)]
≤0.
(39)
The second equality follows by the matrix derivative formula
d
dt log det X(γ) = trace[X(γ)−1 d
dγ X(γ)] [37]. Notably, since
O(γ) ⪰0 and Or ⪰0, we have O(γ) + Or ⪰O(γ) and thus
(O(γ) + Or)−1 −(O(γ))−1 ⪯0. Given (O(γ) + Or)−1 −
(O(γ))−1 ⪯0, and OW2 −OW1 ⪰0, the last inequality
holds. Since
ˆfr(O(1)) = ˆfr(O(0)) +
Z 1
0
d
dγ
ˆfr(O(γ))dγ,
it follows that ˆfr(O(1)) = ˆfr(OW2) ≤ˆfr(O(0)) = ˆfr(OW1).
Thus, we have fr is monotone decreasing, and f is submodu-
lar. Similarly, the additivity property of the OW (Equation 34)
shows that f is monotone increasing.
However, the proof of the monotonicity and submodularity
for the log det is based on the condition that O(ptl) is
non-singular. Otherwise, the conclusion does not hold. For
example, if a single sensor is assigned to target tl, O(ptl)
is always singular (see the proof of Corollary 1), and thus
log det O(ptl) = −∞. If no sensors are assigned, we define
the empty set case as log det(∅) = 0. Then, the function is
not monotone increasing.
The proof of the monotonicity and submodularity for the
trace, rank and log det of the symmetric observability matrix,
O(ptl, utl) := OT (ptl, utl)O(ptl, utl) is similar to the proof
for that of the symmetric observability matrix by the sensor-
target relative state contribution, O(ptl) as provided above.
Because, from Equation 13, we know,
O(ptl, utl) = O(ptl) + OT (utl)O(utl).
(40)
The unknown control input contribution OT (utl)O(utl) ⪰0
does not affect the properties of the measures for the symmetric
observability matrix, O(ptl, utl), since assigning sensors only
influences the sensor-target relative state contribution part,
O(ptl) . But for the log det of symmetric observability matrix,
we need to guarantee O(ptl, utl) is non-singular.
13
REFERENCES
[1] B. Grocholsky, “Information-theoretic control of multiple sensor plat-
forms,” 2002.
[2] S. Jiang, R. Kumar, and H. E. Garcia, “Optimal sensor selection for
discrete-event systems with partial observation,” IEEE Transactions on
Automatic Control, vol. 48, no. 3, pp. 369–381, 2003.
[3] J. R. Spletzer and C. J. Taylor, “Dynamic sensor planning and control
for optimally tracking targets,” The International Journal of Robotics
Research, vol. 22, no. 1, pp. 7–20, 2003.
[4] J. L. Williams, “Information theoretic sensor management,” Ph.D. dis-
sertation, Massachusetts Institute of Technology, 2007.
[5] S. Kamath, E. Meisner, and V. Isler, “Triangulation based multi target
tracking with mobile sensor networks,” in Robotics and Automation,
2007 IEEE International Conference on.
IEEE, 2007, pp. 3283–3288.
[6] M. M. Zavlanos and G. J. Pappas, “Dynamic assignment in dis-
tributed motion planning with local coordination,” IEEE Transactions
on Robotics, vol. 24, no. 1, pp. 232–242, 2008.
[7] O. Tekdas and V. Isler, “Sensor placement for triangulation-based lo-
calization,” IEEE transactions on Automation Science and Engineering,
vol. 7, no. 3, pp. 681–685, 2010.
[8] C. Nam and D. A. Shell, “When to do your own thing: Analysis of cost
uncertainties in multi-robot task allocation at run-time,” in Robotics and
Automation (ICRA), 2015 IEEE International Conference on.
IEEE,
2015, pp. 1249–1254.
[9] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Sensor placement for
optimal kalman filtering: Fundamental limits, submodularity, and algo-
rithms,” in American Control Conference (ACC), 2016.
IEEE, 2016,
pp. 191–196.
[10] ——, “Near-optimal sensor scheduling for batch state estimation: Com-
plexity, algorithms, and limits,” in Decision and Control (CDC), 2016
IEEE 55th Conference on.
IEEE, 2016, pp. 2695–2702.
[11] V. Tzoumas, N. A. Atanasov, A. Jadbabaie, and G. J. Pappas, “Schedul-
ing nonlinear sensors for stochastic process estimation,” in American
Control Conference (ACC), 2017.
IEEE, 2017, pp. 580–585.
[12] F. Yang and N. Chakraborty, “Algorithm for optimal chance constrained
linear assignment,” in Robotics and Automation (ICRA), 2017 IEEE
International Conference on.
IEEE, 2017, pp. 801–808.
[13] S. Chopra, G. Notarstefano, M. Rice, and M. Egerstedt, “A distributed
version of the hungarian method for multirobot assignment,” IEEE
Transactions on Robotics, vol. 33, no. 4, pp. 932–947, 2017.
[14] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval
research logistics quarterly, vol. 2, no. 1-2, pp. 83–97, 1955.
[15] A. S. Gadre and D. J. Stilwell, “Toward underwater navigation based on
range measurements from a single location,” in Robotics and Automa-
tion, 2004. Proceedings. ICRA’04. 2004 IEEE International Conference
on, vol. 5.
IEEE, 2004, pp. 4472–4477.
[16] G. Papadopoulos, M. F. Fallon, J. J. Leonard, and N. M. Patrikalakis,
“Cooperative localization of marine vehicles using nonlinear state es-
timation,” in Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ
International Conference on.
IEEE, 2010, pp. 4874–4879.
[17] F. Arrichiello, G. Antonelli, A. P. Aguiar, and A. Pascoal, “An observ-
ability metric for underwater vehicle localization using range measure-
ments,” Sensors, vol. 13, no. 12, pp. 16 191–16 215, 2013.
[18] R. K. Williams and G. S. Sukhatme, “Observability in topology-
constrained multi-robot target tracking,” in Robotics and Automation
(ICRA), 2015 IEEE International Conference on.
IEEE, 2015, pp.
1795–1801.
[19] P. Tokekar, J. Vander Hook, and V. Isler, “Active target localization
for bearing based robotic telemetry,” in Proceedings of IEEE/RSJ
International Conference on Intelligent Robots and Systems.
IEEE,
2011, pp. 488–493.
[20] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, “An analysis
of approximations for maximizing submodular set functions–ii,” in
Polyhedral combinatorics.
Springer, 1978, pp. 73–87.
[21] J. Vondr´ak, “Optimal approximation for the submodular welfare problem
in the value oracle model,” in Proceedings of the fortieth annual ACM
symposium on Theory of computing.
ACM, 2008, pp. 67–74.
[22] R. Hermann and A. Krener, “Nonlinear controllability and observability,”
IEEE Transactions on automatic control, vol. 22, no. 5, pp. 728–740,
1977.
[23] A. J. Krener and K. Ide, “Measures of unobservability,” in Decision
and Control, 2009 held jointly with the 2009 28th Chinese Control
Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference
on.
IEEE, 2009, pp. 6401–6406.
[24] F. J. ´Alvarez, T. Aguilera, J. A. Paredes, and J. A. Moreno, “Acoustic tag
identification based on noncoherent fsk detection with portable devices,”
IEEE Transactions on Instrumentation and Measurement, vol. 67, no. 2,
pp. 270–278, 2018.
[25] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and
controllability in complex dynamical networks,” IEEE Transactions on
Control of Network Systems, vol. 3, no. 1, pp. 91–101, 2016.
[26] T. H. Cormen, Introduction to algorithms.
MIT press, 2009.
[27] S. Mart´ıNez and F. Bullo, “Optimal sensor placement and motion
coordination for target tracking,” Automatica, vol. 42, no. 4, pp. 661–
668, 2006.
[28] G. Hollinger, S. Singh, J. Djugash, and A. Kehagias, “Efficient multi-
robot search for a moving target,” The International Journal of Robotics
Research, vol. 28, no. 2, pp. 201–219, 2009.
[29] T. H. Chung, J. W. Burdick, and R. M. Murray, “A decentralized motion
coordination strategy for dynamic target tracking,” 2006.
[30] G. Huang, K. Zhou, N. Trawny, and S. I. Roumeliotis, “A bank of
maximum a posteriori (map) estimators for target tracking,” IEEE
Transactions on Robotics, vol. 31, no. 1, pp. 85–103, 2015.
[31] L. Zhou and P. Tokekar, “Active target tracking with self-triggered
communications,” in Proceedings of the IEEE International Conference
on Robotics and Automation (ICRA), 2017.
[32] ——, “Active target tracking with self-triggered communications in
multi-robot teams,” IEEE Transactions on Automation Science and
Engineering, no. 99, pp. 1–12, 2018.
[33] R. Khodayi-mehr, Y. Kantaros, and M. M. Zavlanos, “Distributed
state estimation using intermittently connected robot networks,” arXiv
preprint arXiv:1805.01574, 2018.
[34] G. Strang, Linear algebra and its applications.
Academic Press, 1976.
[35] J. N. Franklin, Matrix theory.
Courier Corporation, 2012.
[36] L. Lov´asz, “Submodular functions and convexity,” in Mathematical
Programming The State of the Art.
Springer, 1983, pp. 235–257.
[37] K. B. Petersen, M. S. Pedersen et al., “The matrix cookbook,” Technical
University of Denmark, vol. 7, no. 15, p. 510, 2008.
Lifeng Zhou received the B.S. degree in Automation
from Huazhong University of Science and Technol-
ogy, Wuhan, China, in 2013, the M.Sc. degree in
Automation from Shanghai Jiao Tong University,
Shanghai, China, in 2016. He is currently pursuing
the Ph.D. degree in Electrical and Computer Engi-
neering, Virginia Tech, Blacksburg, VA, USA.
His research interests include multi-robot coordi-
nation, event-based control, sensor assignment and
risk-averse decision making.
Pratap Tokekar is an Assistant Professor in the
Department of Electrical and Computer Engineering
at Virginia Tech. Previously, he was a Postdoctoral
Researcher at the GRASP lab of University of
Pennsylvania. He obtained his Ph.D. in Computer
Science from the University of Minnesota in 2014
and Bachelor of Technology degree in Electron-
ics and Telecommunication from College of Engi-
neering Pune, India in 2008. He is a recipient of
the NSF CISE Research Initiation Initiative award.
His research interests include algorithmic and field
robotics, and cyber physical systems, and their applications to precision
agriculture and environmental monitoring.