Multi-sensor data association in delta-generalized labeled multi-Bernoulli filter

Problem

We are tracking a number of targets over time and obtain several observations. How do we know which observations come from which target?

This is a common problem in many applications including air traffic control, self-driving vehicles, computer vision, etc. 

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 method1: process each sensor's measurements sequentially
  2. Gibbs method2: 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
  Exact score Approximate score
Deterministic Sequential Combination
Stochastic sampling Cross entropy Gibbs

 

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.