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

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.

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 hardware actions.
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 positions.
Implemented a scheduler that performs distributed hill-climbing on the metric.
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 simulator.
Developed a simulator for distributed constraint optimization to investigate dynamics of the distributed scheduler.
Showed how communication latency can be accommodated by the distributed scheduler.

Specific FY 03 Objectives

Refine integration of the distributed scheduler and tracker with the challenge problem hardware, to accommodate high noise environments.
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 application.

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.