Browse Prior Art Database

# Approximate Joint Probabilistic Data Associations Algorithms

IP.com Disclosure Number: IPCOM000111220D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 133K

IBM

## Related People

Roecker, JA: AUTHOR

## Abstract

Disclosed is an algorithm to compute an approximation of the Joint Probabilistic Data Association (JPDA) probabilities for target tracking systems. This algorithm avoids the exponentially increasing computational loading of the optimal algorithms as the number of targets increases. The approach is to avoid computing all of the possible joint target-to-measurement association events which increase exponentially with the number of targets and concentrate on computing only highly likely target-to-measurement joint events for the calculations.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

Approximate Joint Probabilistic Data Associations Algorithms

Disclosed is an algorithm to compute an approximation of the
Joint Probabilistic Data Association (JPDA) probabilities for target
tracking systems.  This algorithm avoids the exponentially increasing
targets increases.  The approach is to avoid computing all of the
possible joint target-to-measurement association events which
increase exponentially with the number of targets and concentrate on
computing only highly likely target-to-measurement joint events for
the calculations.

The JPDA filter is described in (1).  Its use in multiple
target tracing is to estimate the state, position, velocity,
acceleration, etc, of a target when there are clutter measurements
and other targets present.  The idea is to extend an existing track
with the weighted sum of measurements which are close to that track's
predicted measurement.  These weights are the probabilities that the
measurements came from the target in the track.  When there are
multiple targets in track, this probability calculation uses an
unexceptable amount of computer time.  fast optimal algorithms use an
exponentially increasing amount of computer time as the number of
targets increases (2).  This disclosure is a procedure to calculate
an approximation to the JPDA probabilities that only increases
polynomially as the number of targets increases but is more accurate
than the very fast approximations that increase linearly with the
number of targets (3,4).

The optimal algorithm calculates all possible joint events of
track-to-measurement associations and misses.  A joint event has a
track assigned to only one measurement and a measurement assigned to
only one track.  In a joint event, a track does not have to be
assigned to a measurement indicating that the target was not seen and
an measurement does not have to be assigned to a track indicating the
measurement was from clutter.  An example of a track-to-measurement
joint event is as follows:

Tracks: 1, 2, 3, 4, 5
Measurements: i, j, k, l, m, n

One possible joint event would be track 1 and measurement i,
track 2 and measurement k, track 4 and measurement m, track 5 and
measurement n, track 3 is missed and measurements j and l are
clutter.  The number of combinations of joint events grows
exponentially as the number of tracks increases; therefore, any
optimal algorithm which computes probabilities for all joint events
will increase in compute usage exponentially.  The fast linear
algorithms in (3,4) limit the number of assignments in a joint event.
In other words, all tracks and measurements are not included in
individual probability calculations.  This algorithm, however, limits
the number of full joint events.  This means that all of the tracks
and measurements are included in the probability calculations.  The
idea is t...