Target tracking suing multiple auxiliary particle filtering

Target tracking using multiple auxiliary
particle filtering
Luis Úbeda-Medina , Ángel F. Garc´ıa-Fernández†
, Jesús Grajal
Universidad Politécnica de Madrid, Spain
†Aalto University, Finland
20th International Conference on Information Fusion, 2017.
July 10-13, 2017. Xi’an, China.
1

Outline
Multiple Filtering
Multiple Particle Filter
The Multiple Auxiliary Particle Filter
Simulations and results
Conclusions
2

Outline
Multiple Filtering
Conclusions
3

Bayesian ﬁltering
• Estimate the state Xk of the dynamic system,
computing its posterior PDF, p(Xk|z1:k)
4

Bayesian ﬁltering
• ... given the dynamic and measurement models
Xk
= f(Xk−1
, wk−1
)
zk
= h(Xk
, vk
)
4

Bayesian ﬁltering
Xk
= f(Xk−1
, wk−1
)
zk
= h(Xk
, vk
)
• ... using a two step recursion:
4

Bayesian ﬁltering
Xk
= f(Xk−1
, wk−1
)
zk
= h(Xk
, vk
)
• prediction
p(Xk
|z1:k−1
) =
ˆ
p(Xk
|Xk−1
)p(Xk−1
|z1:k−1
)dXk−1
4

Multiple ﬁltering
• Nonlinearities in the dynamic and measurement models
can make it hard to compute the posterior PDF,
specially for high-dimensional state spaces (the curse of
dimensionality)
5

Multiple ﬁltering
dimensionality)
• Multiple ﬁltering tries to alleviate the curse of
dimensionality, considering the state can be partitioned
into t components
Xk
= (xk
1)T
, (xk
2)T
, ..., (xk
t )T
T
5

Multiple ﬁltering
dimensionality)
• Multiple ﬁltering tries to alleviate the curse of
dimensionality, considering the state can be partitioned
into t components
Xk
= (xk
1)T
, (xk
2)T
, ..., (xk
t )T
T
• ... and instead computing the marginal posterior PDF of
each component (lower dimension)
p(xk
j |z1:k
) =
ˆ
p(Xk
|z1:k
)dXk
−{j}
5

Multiple ﬁltering
• Given the following assumptions:
6

Multiple ﬁltering
• The dynamic model can be expressed as
p(Xk
|Xk−1
) =
t
l=1
p(xk
l |xk−1
l )
6

Multiple ﬁltering
• The dynamic model can be expressed as
p(Xk
|Xk−1
) =
t
l=1
p(xk
l |xk−1
l )
• posterior independence
p(Xk
|z1:k
) =
t
l=1
p(xk
l |z1:k
)
6

Multiple ﬁltering
• The predicted density can be expressed as
p(Xk
|z1:k−1
) =
t
l=1
p(xk
l |z1:k−1
)
7

Multiple ﬁltering
p(Xk
|z1:k−1
) =
t
l=1
p(xk
l |z1:k−1
)
• So that the marginal posterior for xk
j becomes
p(xk
j |z1:k
) ∝
ˆ
p(zk
|Xk
)p(Xk
|z1:k−1
)dXk
−{j}
= p(xk
j |z1:k−1
)
ˆ
p(zk
|Xk
)p(Xk
−{j}|z1:k−1
)dXk
−{j}
7

Multiple ﬁltering
p(Xk
|z1:k−1
) =
t
l=1
p(xk
l |z1:k−1
)
• So that the marginal posterior for xk
j becomes
p(xk
j |z1:k
) ∝
ˆ
p(zk
|Xk
)p(Xk
|z1:k−1
)dXk
−{j}
= p(xk
j |z1:k−1
)
ˆ
p(zk
|Xk
)p(Xk
−{j}|z1:k−1
)dXk
−{j}
• The main diﬃculty is computing the“marginal likelihood”
l(xk
j )
ˆ
p(zk
|Xk
)p(Xk
−{j}|z1:k−1
)dXk
−{j}
7

Outline
Multiple Filtering
Conclusions
8

• First approach to multiple particle ﬁltering.
9

• Approximate each marginal posterior PDF with a
diﬀerent PF using N weighted particles
p(xk
j |z1:k
) ≈
N
i=1
ωk
j,i δ(xk
j − xk
j,i )
9

p(xk
j |z1:k
) ≈
N
i=1
ωk
j,i δ(xk
j − xk
j,i )
• weights are computed according to the principle of
importance sampling
ωk
j,i ∝
p(xk
j,i |z1:k)
qj (xk
j,i |z1:k)
9

p(xk
j |z1:k
) ≈
N
i=1
ωk
j,i δ(xk
j − xk
j,i )
• weights are computed according to the principle of
importance sampling
ωk
j,i ∝
p(xk
j,i |z1:k)
qj (xk
j,i |z1:k)
• with the importance sampling function being the prior PDF
qj (xk
j |z1:k
) ∝ p(xk
j |xk−1
j ) 9

• First order approximation of the “marginal likelihood”
10

• Compute ˆXk
−{j}
ˆXk
−{j} = (ˆx
k
1)T
, ..., (ˆx
k
j−1)T
, (ˆxk
j+1)T
, ..., (ˆx
k
t )T
T
10

• Compute ˆXk
−{j}
ˆXk
−{j} = (ˆx
k
1)T
, ..., (ˆx
k
j−1)T
, (ˆxk
j+1)T
, ..., (ˆx
k
t )T
T
• where
ˆxk
l ≈
N
i=1
ωk−1
l,i · x
k|k−1
l,i
10

• Compute ˆXk
−{j}
ˆXk
−{j} = (ˆx
k
1)T
, ..., (ˆx
k
j−1)T
, (ˆxk
j+1)T
, ..., (ˆx
k
t )T
T
• where
ˆxk
l ≈
N
i=1
ωk−1
l,i · x
k|k−1
l,i
• Assuming the approximation
p(Xk
−{j}|z1:k−1
) ≈ δ Xk
−{j} − ˆXk
−{j}
10

• Compute ˆXk
−{j}
ˆXk
−{j} = (ˆx
k
1)T
, ..., (ˆx
k
j−1)T
, (ˆxk
j+1)T
, ..., (ˆx
k
t )T
T
• where
ˆxk
l ≈
N
i=1
ωk−1
l,i · x
k|k−1
l,i
• Assuming the approximation
p(Xk
−{j}|z1:k−1
) ≈ δ Xk
−{j} − ˆXk
−{j}
• We approximate the “marginal likelihood” as
ˆ
p(zk
|Xk
)p(Xk
−{j}|z1:k−1
)dXk
−{j} ≈ p(zk
|xk
j , ˆXk
−{j})
10

Outline
Multiple Filtering
Conclusions
11

• MAPF takes advantage of auxiliary ﬁltering. This is, use
the current measurement at time k, zk, to improve the
way samples are drawn for the importance sampling
function.
12

function.
• MAPF uses an auxiliary PF to approximate the marginal
posterior PDF of each component of the partition of the
state.
12

function.
• MAPF uses an auxiliary PF to approximate the marginal
posterior PDF of each component of the partition of the
state.
• MAPF uses the approximation of the “marginal
likelihood” of MPF.
ˆ
p(zk
|Xk
)p(Xk
−{j}|z1:k−1
)dXk
−{j} ≈ p(zk
|xk
j , ˆXk
−{j})
12

• MAPF indirectly obtains samples from p(xk
j |z1:k
) using an
auxiliary variable aj .
13

j |z1:k
) using an
• Compute µk
j,i , a characterization of xk
j given xk−1
j,i , such as
µk
j,i = E[xk
j |xk−1
j,i ]
13

j |z1:k
) using an
• Compute µk
j given xk−1
j,i , such as
µk
j,i = E[xk
j |xk−1
j,i ]
• Sample aj,i according to
λj,i ∝ p(zk
|µk
j,i , ˆXk
−{j})ωk−1
i
13

j |z1:k
) using an
• Compute µk
j given xk−1
j,i , such as
µk
j,i = E[xk
j |xk−1
j,i ]
λj,i ∝ p(zk
|µk
j,i , ˆXk
−{j})ωk−1
i
• Using the index aj thus allows to draw particles that are prone
to obtain a higher likelihood with the current measurement zk
.
13

j |z1:k
) using an
• Compute µk
j given xk−1
j,i , such as
µk
j,i = E[xk
j |xk−1
j,i ]
λj,i ∝ p(zk
|µk
j,i , ˆXk
−{j})ωk−1
i
• Using the index aj thus allows to draw particles that are prone
to obtain a higher likelihood with the current measurement zk
.
• The importance sampling function of MAPF therefore draws
samples in a higher dimension from
qj (xk
j , aj |z1:k
) ∝ p(zk
|µk
j,aj
, ˆXk
−{j})p(xk
j |xk−1
j,aj
)ωk−1
j,aj
13

Outline
Multiple Filtering
Conclusions
14

Target dynamics
• 8 target trajectories were generated according to an
independent nearly-constant velocity model.
0 20 40 60 80 100 120
x position [m]
0
20
40
60
80
100
120
yposition[m]
1
2
3
4
5
6
7
8
15

Sensor model
• A nonlinear measurement model is considered. Each sensor
receives amplitude range-dependent measurements.
zk+1
i = hi (Xk+1
) + vk+1
i
hi (Xk+1
) =
t
j=1
SNR(dk+1
j,i )
SNR(dk+1
j,i ) =



SNR0 dk+1
j,i ≤ d0
SNR0
d2
0
(dk+1
j,i )2
dk+1
j,i > d0
16

Compared filters
• Jointly Auxiliary PF (JA) [1]
[1] M. R. Morelande, “Tracking multiple targets with a sensor network,” in Proceedings of the 9th International
Conference on Information Fusion (FUSION), 2006.
[2] Á. F. Garc´ıa-Fernández, J. Grajal, and M. Morelande, “Two-layer particle filter for multiple target detection and
tracking,” IEEE Transactions on Aerospace and Electronic Systems, vol. 49, no. 3, pp. 1569–1588, 2013.
[3] L. Úbeda-Medina, Á. F. Garc´ıa-Fernandez, and J. Grajal, “Generalizations of the auxiliary particle filter for
multiple target tracking,” in Proceedings of the 17th International Conference on Information Fusion (FUSION),
2014.
[4] M. F. Bugallo, T. Lu, and P. M. Djurić, “Target Tracking by Multiple Particle Filtering,” IEEE Aerospace
Conference, pp. 1–7, 2007.
17

Compared ﬁlters
• Parallel Partition PF (PP) [2]
2014.
17

Compared ﬁlters
• Auxiliary PP PF (APP) [3]
2014.
17

Compared ﬁlters
• Multiple PF (MPF) [4]
2014.
17

Compared ﬁlters
• Multiple PF (MPF) [4]
• Multiple Auxiliary PF (MAPF)
2014.
17

Tracking 2 targets
50 100 150 200 250 300 350 400 450 500
Number of particles
0
1
2
3
4
5
OSPApositionerror[m]
JA
PP
APP
MPF
MAPF
• MAPF is the best ﬁlter, closely followed by APP
18

Tracking 2 targets
50 100 150 200 250 300 350 400 450 500
Number of particles
0
1
2
3
4
5
JA
PP
APP
MPF
MAPF
• MAPF is the best ﬁlter, closely followed by APP
• A remarkably small number of particles is needed for MAPF
to obtain good tracking results 18

Tracking 6 targets
50 100 150 200 250 300 350 400 450 500
number of particles
1
2
3
4
5
6
7
OSPApositionerror[m] JA
PP
APP
MPF
MAPF
• The performance improvement of MAPF is bigger in this
higher-dimensional scenario.
19

Tracking 6 targets
50 100 150 200 250 300 350 400 450 500
number of particles
1
2
3
4
5
6
7
OSPApositionerror[m] JA
PP
APP
MPF
MAPF
• The performance improvement of MAPF is bigger in this
higher-dimensional scenario.
• JA acutely suﬀers the curse of dimensionality, as it considers
the whole state in the sampling procedure. 19

Tracking 8 targets
50 100 150 200 250 300 350 400 450 500
number of particles
2
3
4
5
6
7
JA
PP
APP
MPF
MAPF
• MAPF outperforms the rest of the ﬁlters, this time followed
by MPF.
20

Tracking 1 to 8 targets, 100 particles
1 2 3 4 5 6 7 8
number of targets
0
1
2
3
4
5
6
7
JA
PP
APP
MPF
MAPF
• Multiple ﬁlters such as MAPF and MPF remarkably deal to
increases in dimensionality.
21

Tracking 1 to 8 targets, 100 particles
1 2 3 4 5 6 7 8
number of targets
0
1
2
3
4
5
6
7
JA
PP
APP
MPF
MAPF
• Multiple ﬁlters such as MAPF and MPF remarkably deal to
increases in dimensionality.
• Overall, for 100 particles, MAPF is the best performing ﬁlter,
followed by APP and MPF. 21

Tracking 8 targets (zoom). Eq. execution time (I)
50 100 150 200 250 300 350 400 450 500
number of particles
0
0.5
1
1.5
2
2.5
3
3.5
meanexecutiontime[s]
PP
APP
MPF
MAPF
50 100 150 200 250 300 350 400 450 500
number of particles
2
2.5
3
3.5
4
PP
APP
MPF
MAPF
• MAPF and APP have a higher computational cost.
22

Tracking 8 targets (zoom). Eq. execution time (I)
50 100 150 200 250 300 350 400 450 500
number of particles
0
0.5
1
1.5
2
2.5
3
3.5
PP
APP
MPF
MAPF
50 100 150 200 250 300 350 400 450 500
number of particles
2
2.5
3
3.5
4
PP
APP
MPF
MAPF
• MAPF and APP have a higher computational cost.
• Considering a different number of particles for each filter such
that they all have similar computational cost, MAPF is still
the best performing filter. 22

Tracking 8 targets (zoom). Eq. execution time (II)
50 100 150 200 250 300 350 400 450 500
number of particles
0
0.5
1
1.5
2
2.5
3
3.5
PP
APP
MPF
MAPF
50 100 150 200 250 300 350 400 450 500
number of particles
2
2.5
3
3.5
4
PP
APP
MPF
MAPF
• This behavior also holds for diﬀerent computational costs.
23

Tracking 8 targets (zoom). Eq. execution time (III)
50 100 150 200 250 300 350 400 450 500
number of particles
0
0.5
1
1.5
2
2.5
3
3.5
PP
APP
MPF
MAPF
50 100 150 200 250 300 350 400 450 500
number of particles
2
2.5
3
3.5
4
PP
APP
MPF
MAPF
• This behavior also holds for diﬀerent computational costs.
24

Outline
Multiple Filtering
Conclusions
25

Conclusions
• Multiple particle ﬁltering shows a remarkable
performance in high-dimensional nonlinear systems.
26

Conclusions
• In this paper, we have formalized the use of auxiliary
ﬁltering within the multiple particle ﬁltering framework.
26

Conclusions
• In this paper, we have formalized the use of auxiliary
ﬁltering within the multiple particle ﬁltering framework.
• We have demonstrated through simulations in an MTT
scenario with nonlinear measurements that the MAPF
can outperform the MPF as well as other MTT
algorithms.
26

Thank you
Further questions:
luis.ubeda@upm.es
27

Target tracking suing multiple auxiliary particle filtering

Recommended

More Related Content

What's hot (20)

Similar to Target tracking suing multiple auxiliary particle filtering (20)

Recently uploaded (20)

Target tracking suing multiple auxiliary particle filtering