A Toolkit to Create Run-time Ant Generators, Aggregators and
Synthesizers and a Demonstration Application
Dr Stephen Fitzpatrick
Dr Cordell Green
Prof. Lambert Meertens
Here is a more detailed presentation of the Ants project
The objective of Kestrel’s ANTs project is to apply formal
specification and synthesis techniques to real-time, distributed
resource management of distributed networks of sensors. Resource
management must operate in real time and with limited, localized
information, and must compete with the sensors for communication and
data processing resources. Kestrel will demonstrate its work using a
network of simple radars, that have limited communication and
processing capabilities, to perform target detection and tracking.
Kestrel’s e-Merge-ANT project uses distributed, anytime, approximate
scheduling to achieve scalable, efficient, real-time coordination of
large networks of simple, local sensors.
Each sensor’s actions are continually scheduled over reasonable
time periods and the schedules communicated to other sensors (those
with which it can usefully interact). This enables each sensor to
adjust its own schedule to best coordinate with its colleagues.
Scheduling is the key to overcoming latency in the system. Latency
is caused by communication contention and non-zero durations of
In optimizing its schedule, each sensor also takes into account
the state of the real world in its vicinity (since the data it should
acquire is influenced by the real world).
Knowledge about the real world is maintained by each sensor by
combining its own measurements with measurements sent to it by other
sensors (i.e., the sensors perform distributed data fusion).
Scheduling is an optimization process: each sensor computes a
local quality metric on its own schedule and adjusts its schedule to
optimize the metric. The local quality metrics of course reflect
coordination with other sensors in acquiring useful data.
Scheduling is an ongoing, continual process: under static
conditions, the combined quality of all of the schedules increases;
scheduling and execution of the schedule proceed in parallel.
The emphasis is on local interactions and computations, since this is
the key to scalability. Because scheduling is highly distributed, it
is robust against local failures.
Kestrel is validating its approach through a practical implementation
for the program’s challenge problem: real-time target tracking using a
network of simple radars.
Kestrel is investigating the dynamics of the underlying algorithms
using abstract constraint optimization problems (such as distributed,
real-time graph coloring). Experiments using these abstract problems
have shown that the algorithmic framework is scalable, robust and
efficient (in terms of communication).
They have also revealed interesting properties regarding the balance
between speed of adaptation (i.e., how quickly schedules adjust to
changing real-world parameters) and stability: frequent rescheduling
allows rapid adaptation, but too frequent rescheduling induces
thrashing, whereby each sensor is making poor scheduling decisions
because too much of its information is out-of-date because many of its
colleagues are simultaneously changing their own schedules. A simple
method has been developed for adjusting the adaptation-stability
balance using stochastic damping - it has proven to be effective in
the abstract problems.
FY 02 Accomplishments
Developed a metric to capture the combined quality of schedules
with respect to sensor coordination in scanning targets.
Enhanced the metric using probabilistic knowledge of target
Implemented a scheduler that performs distributed hill-climbing on
Implemented a distributed target tracker to enable sensors to
maintain knowledge about their real-world vicinity based on their own
measurements and those of nearby sensors.
Integrated the distributed scheduler and tracker with the
program’s challenge problem.
Performed challenge problem demonstrations using hardware and a
Developed a simulator for distributed constraint optimization to
investigate dynamics of the distributed scheduler.
Showed how communication latency can be accommodated by the
Specific FY 03 Objectives
Refine integration of the distributed scheduler and tracker with
the challenge problem hardware, to accommodate high noise
Develop a modeling tool for distributed sensor networks to show
how the distributed scheduler performs on very large systems.
Pursue analysis of the distributed scheduler to see if dynamical
properties can be proven.
Capture the problem-independent structure of the distributed
scheduler in formal specifications and refinements to allow reuse in
other problems/applications and to facilitate analysis.
Pursue focused transition with DARPA/DoD selected technology and
Over the next year, Kestrel will integrate its software with a
platform chosen by DARPA/DoD that exhibits typical problems
encountered in practical sensor networks. Kestrel will show how its
technology can address these problems in practice.
The algorithmic framework used for the distributed scheduler may be
viewed as distributed constraint optimization or distributed
hill-climbing. These are developing fields of research. Kestrel is
participating in various conferences and workshops to help establish
the foundations in both the problem structure and the algorithmics.
Distributed constraint optimization, particularly in the form of
distributed scheduling, may be applicable to logistics applications in
the military, industry and commerce. Kestrel is investigating how it
can incorporate the techniques developed under its e-Merge-ANT project
into logistics applications that it is developing.