Share Email Print

Proceedings Paper

Extremal optimization for sensor report pre-processing
Author(s): Pontus Svenson
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

We describe the recently introduced extremal optimization algorithm and apply it to target detection and association problems arising in pre-processing for multi-target tracking. Extremal optimization is based on the concept of self-organized criticality, and has been used successfully for a wide variety of hard combinatorial optimization problems. It is an approximate local search algorithm that achieves its success by utilizing avalanches of local changes that allow it to explore a large part of the search space. It is somewhat similar to genetic algorithms, but works by selecting and changing bad chromosomes of a bit-representation of a candidate solution. The algorithm is based on processes of self-organization found in nature. The simplest version of it has no free parameters, while the most widely used and most efficient version has one parameter. For extreme values of this parameter, the methods reduces to hill-climbing and random walk searches, respectively. Here we consider the problem of pre-processing for multiple target tracking when the number of sensor reports received is very large and arrives in large bursts. In this case, it is sometimes necessary to pre-process reports before sending them to tracking modules in the fusion system. The pre-processing step associates reports to known tracks (or initializes new tracks for reports on objects that have not been seen before). It could also be used as a pre-process step before clustering, e.g., in order to test how many clusters to use. The pre-processing is done by solving an approximate version of the original problem. In this approximation, not all pair-wise conflicts are calculated. The approximation relies on knowing how many such pair-wise conflicts that are necessary to compute. To determine this, results on phase-transitions occurring when coloring (or clustering) large random instances of a particular graph ensemble are used.

Paper Details

Date Published: 9 August 2004
PDF: 10 pages
Proc. SPIE 5429, Signal Processing, Sensor Fusion, and Target Recognition XIII, (9 August 2004); doi: 10.1117/12.542027
Show Author Affiliations
Pontus Svenson, Swedish Defence Research Agency (Sweden)

Published in SPIE Proceedings Vol. 5429:
Signal Processing, Sensor Fusion, and Target Recognition XIII
Ivan Kadar, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?