Kestrel's e-Merge-ANT project is part of the ANTS programme sponsored by DARPA/ITO to investigate the problem of coordinating a large distributed network of resources to accomplish high-value tasks that may have stringent real-time requirements when the network may be subject to high loads.
For example, resources may be sensors and tasks may be target tracking (the tasks may be considered "high-value" when, for example, the targets being tracked are missiles). The load on the network is determined by the number and type of targets, and may vary from light (no targets present, just do background scans) to heavy (more targets than the network could track even if operating at full efficiency).
Coordination among the resources is required to ensure that targets get assigned to appropriate sensors (e.g., ones that are close), and to ensure that individual sensors do not become over-loaded (a single sensor is able to track only a finite number of targets simultaneously). Moreover, a single task may require multiple sensors to act coherently (e.g., to take simultaneous measurements to triangulate a target's position).
Tasks are not generally known a priori: e.g., targets are detected at essentially random positions and times by background scans and may be present for unknown durations. The real-time requirements arise from the tasks themselves having dynamic states: e.g., the fact that a target is moving means that there is a finite amount of time between its being detected and its moving out of sensor range, and that time must be used to determine which sensors should track it, to inform those sensors to begin tracking, and to actually carry out the tracking. (In other words, the more time spent deciding who should track, the less time left for actually tracking.)
It is an assumption in the ANTS programme that the resource network may be large (possible containing tens of thousands of resources) and that the network's communication has significant latency (large enough that it must be taken into account when trying to coordinate the resources) and may be unreliable; for example, communication may take place through low-power radio communication that can be jammed.
Moreover, communication is assumed to be expensive, partly because it consumes energy, but more importantly because it reveals the resources' positions to adversaries (e.g., a target may be able to locate and attack a passive sensor based on the sensor's radio emissions).
Finally, the resources may not be continuously available because the resources themselves may be damaged by adversaries.
Any system that is designed to coordinate the resource network must address the following technical challenges:
In contrast, when the network is critically loaded, the computational costs may become much greater: if the load is just below critical, the number of ways to assign all of the tasks to resources is small and so finding one is difficult; if the load is just above critical, determining that the tasks' requirements are not met by any assignment may take a long time.
This peak in the computational complexity near some critical region is called a phase transition. The practical ramifications of the existence of phase transitions is that the coordination system must find ways to avoid the critical regions if it is to achieve real-time responsiveness as the load varies.