McGill Computer Networks Research Lab

Objective

Create mappings between targets and observations

1. Each target is mapped to at most one observation per sensor
2. Each observation is mapped to at most one target

Each mapping is assigned a score

Select the mappings with highest scores

Solvable for single-sensor tracking

NP-hard for multi-sensor tracking

Solution

Existing methods:

1. Sequential method¹: process each sensor's measurements sequentially
2. Gibbs method²: use Gibbs sampling to generate associations

Novel methods:

1. Combination method: combine locally optimal single-sensor association maps
2. Cross entropy method: construct a sampling distribution over the space of all possible associations

These four methods can be classifed in two ways:

1. map generation: deterministic vs stochastic sampling
2. map ranking: exact score vs approximate score

Reference:

1: F. Papi, "Multi-sensor $\delta$-GLMB filter for multi-target tracking using Doppler only measurements,” in Europen Intell. Security Inform. Conf., Sept. 2015, pp. 83–89

2: B. N. Vo and B. Vo, "Multi-sensor multi-object tracking with the generalized labeled multi-Bernoulli filter," available on arxiv

Results

We implement the $\delta$-generalized labeled multi-Bernoulli filter and use the four algorithms to generate data associations

• Linear dynamic and measurement model
• ​Average of 15 clutter measurements per sensor per time step
• Performance metric:

1. optimal subpattern assignment matrix (OSPA) to measure error in number of targets and their positions
2. total runtime for the entire simulation

Fig. 1 True target tracks (blue dots) and sensor positions (red crosses)

Fig. 2 Average OSPA with respect to measurement noise level

The overall tracking performance degrades as the measurement noise level increases. The cross entropy method has consistenly the best tracking performance followed by the sequential methods. The combination and cross entropy methods have the worst performance as they use the approximate ranking function. 

Fig. 3 Average runtime with respect to measurement noise level

The sequential and combination methods have fairly consistent runtime regardless of measurement noise level. For the Gibbs and cross entropy methods, the stochastic sampling generates more maps and by extension higher workload when the measurement noise increases. Therefore,  the total runtime increases linearly with measurement noise level. 

Yu, J. Y., A. - A. Saucan, M. Coates, and M. Rabbat, "Algorithms for the Multi-Sensor Assignment Problem in the Delta-Generalized Labeled multi-Bernoulli Filter", IEEE 7th CAMSAP, Accepted, 2017.

Yu, J. Y., A. - A. Saucan, M. Coates, and M. Rabbat, "Multi-Sensor Data Assignment Algorithms in the Delta-Generalized Labeled multi-Bernoulli Filter", IEEE Trans. Signal Proc., Submitted, 2017.