e-Merge-ANT Project

A Toolkit to Create Run-time Ant Generators, Aggregators and Synthesizers — and a Demonstration Application

Principal Investigators: Dr Stephen Fitzpatrick & Dr Cordell Green
Co-Investigator: Prof. Lambert Meertens

Sponsor: DARPA/IXO ANTS

Here is a more detailed presentation of the Ants project.

Objective

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.

Approach

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.

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

Specific FY 03 Objectives

Technology Transition

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.