ANTS Challenge Problem

The ANTS program has defined a common challenge problem for its resource management projects. The challenge problem uses a set of simple radar sensors networked using radio communication. The objective is to coordinate the radar sensors to track moving targets while minimizing power and communication usage.

The following are some constraints that must be observed:

1. Each target requires at least two, and preferably three, sensors to scan it simultaneously for triangulation.

2. Each radar sensor has three radar heads, each of which is capable of scanning one target. However, only one of the heads on a given sensor can scan at any given time.

3. The radar heads can be powered on and off independently, but there is a delay of around three seconds following power turning on during which the measurements from a head are unreliable.

4. There are eight channels (frequencies) available for radio communication. If two or more messages overlap in time on the same channel, all of those messages are corrupted.

5. Each sensor can be connected to a PC for computational tasks (coordination and track fusion).

Our general approach to the challenge problem is based on distributed, anytime scheduling, in which each sensor’s actions are determined by a local agent, based on what the agent expects the targets to do and what it expects other, nearby sensors to do.

Year 1 approach: Scheduling using soft graph coloring

In the first year of our project, we developed a distributed scheduler based on soft graph coloring.

Year 2 approach: Scheduling using measurement quality metrics

In the second year of our project, we generalized our approach by introducing local metrics that gauge the (expected) quality of a sensor’s measurements.