Scheduling in the ANTS Challenge Problem using Distributed, Soft Graph Coloring

(The approach described below deals only with the constraints arising from the radar heads - that only one per sensor unit can scan at any given time. It does not deal with the constraints on communication.)

This approach to the scheduling aspect of the challenge problem can be summarized as follows: virtual resources, comprised of three physical radar heads and each capable of tracking a target, are defined; the physical radar constraints are lifted to mutual exclusion constraints on the virtual resources; the virtual resources are scheduled by assigning time slots in a cyclic schedule, so that mutually exclusive resources activate in different time slots.

In this formulation, scheduling is isomorphic to graph coloring, where the virtual resources correspond to nodes in a graph, mutual exclusion constraints correspond to edges, and timeslots correspond to colors. Details follow.

First, an initialization phase is performed:

Analyze geometry to identify best scanning combinations

Constraint 1 requires targets be scanned simultaneously by, preferably, three radar heads. So we analyze the geometry of the sensor network and identify contiguous regions that are best scanned by the same three radar heads (where “best” is determined by the radar heads’ sensitivity equation relating distance and angle to signal strength). For example, with six sensor units placed at the corners of a regular hexagon, the scan regions form the pattern shown to the right. Note that the three heads corresponding to any given region are necessarily on different sensor units and so can all be scanned simultaneously.

Define virtual resources representing triangulators

A virtual resource is defined to represent each scanning region identified by the geometry analysis. Each virtual resource is comprised of three radar heads and is capable of triangulating a single target; i.e., each virtual resource is capable of accomplishing a tracking task.

Compute the constraints on the collection of virtual resources

Each virtual resource is comprised of three physical radar heads. For any two virtual resources, a mutual exclusion constraint exists if any of the radar heads making up one of the virtual resources is on the same sensor unit as any of the radar heads making up the second virtual resource, due to Constraint 2. Two virtual resources are said to be neighbors if there exists a mutual exclusion constraint between them.

Assign virtual resources to scheduling agents

Each virtual resource is assigned to one scheduling agent that is resident on a computational device. Each scheduling agent is responsible for determining the actions of its virtual resources.

Then several simultaneous, ongoing processes are started:

Iteratively schedule

The scheduling agents continually communicate with their neighbors and attempt to improve their own schedules: specifically, they attempt to ensure that mutually exclusive resources are not scheduled to scan at the same time.

Continuously execute schedules

The resources continuously execute their scheduling agents’ current schedules. To accomplish this, an action scheduled for a virtual resource is decomposed into actions for each of its component resources (radar heads).

Resolve conflicts at physical resource level

It is likely that two mutually exclusive virtual resources are at least temporarily scheduled for simultaneous scanning. In such a case, when the virtual resource schedules are decomposed into actions for radar heads, at least one radar unit will end up with requests to scan two or more of its heads simultaneously. Since it can scan only one at a time, it prioritizes the requests based on the targets’ estimated positions.

Scheduling using Graph Coloring

In the form outlined above, scheduling virtual resources can be mapped onto graph coloring:

• Virtual resources correspond (1-to-1) to nodes in a graph.

• Mutual exclusion constraints correspond (1-to-1) to undirected edges: there is an edge between two nodes in the graph if and only if there is a mutual exclusion constraint between the corresponding virtual resources.

• In the graph coloring problem, the objective is to assign different colors to nodes that are connected by an edge. The equivalent objective in the scheduling problem is to assign mutually exclusive virtual resources different time slots in a schedule. Because each target is to be repeatedly scanned, the schedule is cyclic.

• The number of time slots in a schedule is limited by the maximum duration allowed between scans of a given target (the revisit time) compared with the duration of each scan (the dwell time). The number of time slots corresponds to the number of colors.

In graph coloring, a commonly used characteristic of a graph is its chromatic number which is the fewest number of colors required to color the graph so that no two nodes of the same color are connected by an edge. If we try to color a graph with fewer colors, we inevitably end up with conflicts (i.e., nodes of the same color connected by an edge): the equivalent situation in the scheduling problem occurs when the revisit period is too short compared with the dwell time.

More generally, the number of colors compared with the chromatic number gives a measure of the difficulty of the coloring problem: if the number of colors is less than or greater than the chromatic number, the coloring problem is over constrained or under constrained, respectively. If the number of colors is equal to the chromatic number, the coloring is critically constrained.

In summary, we can cast the scheduling of the virtual resources as a graph coloring problem, but that certainly does not mean that we can consider the problem solved! Graph coloring is just as difficult computationally as scheduling. Moreover, we still must achieve the coloring in a scalable, decentralized, robust manner. Nevertheless, viewing the problem as graph coloring does provide a useful, comparatively simple framework and we can exploit this in assessing the performance of a scheduler. This is detailed in the section on soft graph coloring.

Assessment of Performance

Most of our experiments to date have been conducted using a simulator of the challenge problem provided by Rome Lab. The results of two typical experiments are shown below.

• The triangular icons at the corners (left image) represent the radar heads.

• The target repeatedly moves counter-clockwise around a diamond-shaped track near the middle (the track is just visible as a blue line in the left image).

• The green/yellow/orange/red dots represent estimates of the target’s position at various times. Green means the estimate was accurate, red means poor, and yellow and orange are intermediate.

A histogram of the errors in the estimates is shown below. The r.m.s. error was 3.09 feet. Other statistics of interest are: average radar head power usage was 27% and the average number of messages sent per node per second was 0.9. These values are close to or better than the goals that have been established for the challenge problem.

Animation of Tracking

The system in action can be viewed as an AVI animation.

• There are 4 radar units, one at each corner - when the radar heads are active, they are displayed brightly.
• The blue sphere shows the true path of the target - it moves along a diamond path, the corners of which are marked (in blue).
• The little colored squares that fade in and out show the tracker’s estimates of the target’s position. They are green if the estimate is accurate, red if it is inaccurate and yellow/orange in between.
• The sphere with the attached arrow represents an estimate of the target’s position computed by interpolating between the discrete track estimates (see previous item). The arrow represents an estimate of the target’s velocity (direction and magnitude). The color coding is the same as the previous item (green=good, red=bad).

Further Information

Our presentation from the autumn 2000 ANTS meeting has similar material, plus a little bit extra.