Scheduling in the ANTS Challenge Problem using Measurement Quality

In our second-year approach, the main idea is for each sensor to use local information about nearby targets and sensors to optimize its own measurements.

Nearby targets: Each sensor periodically transmits to nearby sensors the data it acquires from measurements. Each sensor thus has enough data from which to build tracks of nearby targets.
Nearby sensors: Each sensor periodically transmits to nearby sensors a schedule of its impending measurements. Each sensor thus has enough information to ensure that its own measurements coincide well with those of other, nearby sensors. (The sensors try to ensure that their scans of a given target are simultaneous.)

Developing local metrics to quantify measurement quality and cost allows each sensor to try to determine a schedule of measurements that optimizes the trade-off between quality and cost. Of course, because the sensors are distributed and operate autonomously, their schedules need to be made coherent to ensure that the expected quality is actually realized. This aspect is dealt with using an algorithm similar to that used for distributed graph coloring, in which stochastic activation of the sensors’ schedulers is used ensure convergence of the schedules without imposing unncessary sequentialiality.

Local Target Estimates

Each sensor may maintain tracks for zero, one or more targets in its vicinity, based on its own measurements and those from nearby sensors. Target tracks can be projected into the future to determine expected target trajectories. This allows sensors to decide where (and when) they should focus their attention.

Of course, predictions may be inaccurate, and the further into the future the projection is made the less accurate it is likely to be. So each sensor continually updates its tracks (as it receives new data), projections and measurement decisions. In this way, the sensors’ actions are continually adapted to target behavior.

Local Schedules

Each sensor decides for itself which measurements it will take, and when it will take them. It records its decisions as a schedule, and transmits its schedules to nearby sensors so that they can take its intentions into account when deciding their own schedules.

Once a schedule has determined a schedule, the schedule can be executed without further communication since all of the actions required by the schedule are local. Communication latency is thus side-stepped. More precisely, communication is required only when a schedule is updated, which occurs infrequently enough that the communication latency is tolerable.

Measurement Quality

When it needs to update its schedule, each sensor tries to determine a schedule of measurements that optimizes the quality-cost trade-off, given tracks of nearby targets and given the schedules of other, nearby sensors. Computing the costs is straightforward (it mainly involves determinining for how long each radar beam is activated) so only the computation of the (expected) quality will be considered here.

There are two main components to measurement quality:

Single-measurement, single-target quality: how well each measurement by itself scans a given target: To determine this, the target’s track is projected out to the time at which the measurement is to be taken, and the sensor’s theoretical signal model is used to determine how strong a signal will be received (based on the distance and direction from the sensor to the target).
Multiple-measurement, single-target quality: how well multiple measurements complement each other: One of the requirements of the challenge problem is for measurements of a given target to be taken approximately simultaneously. The quality of multiple measurements is thus determined by associating a time window with each measurement (which indicates the period over which the measurement could usefully be combined with other measurements) and then determining how much the time windows overlap.

A third component, interference between targets, is also taken into consideration but is not discussed here.

Experimental Results

Track for one target
Tracks for two targets

Experiments were performed with the challenge problem’s simulator using sensor and target configurations determined by Rome Lab. Our results are shown below.

The first figure shows a track generated by a single target moving along “dog bone” shaped path, marked in white. The small triangles mark the sensors’ positions (one sector head corresponds to each side). The colored blobs indicate estimates of the target’s position produced by the sensors: green indicates a good estimate, red and purple poor estimates.

The second figure shows tracks generated for two targets being tracked simultaneously along oval paths.

If you have an SVG-enabled browser (e.g., from Adobe), you can click on either image to view an animation of the tracking.

Overall, our simulator results are good: track error (computed as the r.m.s. difference between estimated positions and true positions) was less than 2 feet, which is below the level set for the challenge problem. Resource usage was a bit high, but can probably be lowered without greatly increasing track error. Communication usage, at 1 message per node per second, was well within the required limits.

So far, our results with the challenge problem hardware have not been as good as with the simulator. We attribute this to unanticipated sources of radar noise (caused by multi-path reflections and non-symmetrical target profile). We are currently working on reducing or accounting for these noise sources and hope to post hardware results in the near future.

Further Information

Technical Report KES.U.01.09 gives lots of detail about optimizing measurement quality based on probability distributions over target trajectories as well as fairly concrete implementation details of the scheduler.
Our presentation at the winter 2001 ANTS PI meeting gives a gentler introduction and also discusses how we perform multiple-target tracking using multiple, single-target trackers.