DARPA ANTS DARPA

Principal Investigator: Bart Selman

Co-Principal Investigators: Carla Gomes and Scott Kirkpatrick

Others:  Ramon Bejar and Bhaskar Krishnamachari
 
 

The overall goal is the design of reliable, robust and scalable constraint satisfaction methods for large-scale, computationally demanding applications, such as dynamic resource allocation, logistics, planning and scheduling.

Our vision is to develop  principled controlled hardness aware systems, in which the computational demands are dynamically adjusted taking into consideration the available computational resources. Figure 1 outlines this approach. To operate away from the critical region, the system needs to use tools that evaluate properties of the problem that allow to detect whether we are in the critical region. Once the system knows this information, it can decide to reformulate certain parts of the problem that will allow to put the problem away from the critical region. Operating away from the critical region is important, because at that point the system consumes more resources to solve the problem.

Figure 1:  Phase transition aware system

To achieve this goal, we propose to develop new techniques and methods for the principled control of computational cost. Our approach builds on our work on:

 Linking phase transition phenomena with computational cost [3, 6, 7]. We will extend the phase transition analysis to structured domains and more general constraint satisfaction tasks. This will require the development of new measures of "constrainedness" and related statistical properties of problem instances.
Randomized Search techniques. Randomization is a powerful mechanism to increase overall predictability. For example, in "Simulated Annealing" the noise level is used to escape from local minima in a controlled manner [5]. Also, the understanding of characteristics of systematic complete search methods explains why "rapid restarts" [4] and "portfolio" strategies [2] are very effective. We address the challenge of devising good restart and portfolio strategies for problems that have not been solved before.

Ants Challenge Problem - Sensor Domain

The goal in this problem is to track the position of a set of moving targets located within an area using fixed Doppler radar-based sensors. Each sensor covers a circular area. Hence, a sensor will be able to track only targets that are within a given distance from it.

To estimate the location of a target, at least three different sensors must get measures of the relative position and velocity of the  target at the same time. So, the three  scanning areas of these three sensors must overlap and the overlapped region should contain the target. It is expected that one 'agent', which can be a process running in one of the sensors, will collect these measurements to calculate the target's position. Every different target must be tracked by a set of a least three overlapping sensors, and one of these sensors will be the one collecting measurement data and calculating the target's position. We further assume that each sensor can only be involved in tracking one target at a time.

Figure 2:  Sensor testbed problem

Formal Models

As a starting point for studying the computational complexity, we have created two formal models for representing the problem. They are graph models that capture relevant aspects of the problem.

In the first one we have a bipartite graph where one set of vertices represent the
sensors and the other one the targets. We have an edge between a sensor and a target if the target is within the scope of the radar of the sensor. With this model, we can find a solution to the problem by finding a matching between sensors and targets such that every target is matched with three different sensors and one sensor is only matched with at most one target. Figure 3 shows this graph model for a possible instance of the problem with 2 targets and 12 sensors. The green edges represent a valid solution to the problem.

Figure 3:  First graph model for the sensor domain problem

The second model is an extension of the first one, in which now we also consider edges
between pairs of sensor vertices. These edges indicate communication links between the two connected sensors, meaning that the two sensors can communicate with each other. In this model, a valid solution must assign to every target a set of three sensors such that there  exists a edge between every pair of sensors from the set of three sensors selected. Figure 4 shows this graph model for a possible instance of the problem with 2 targets and 12 sensors. As before, the green edges represent a valid solution to the problem.

Figure 4:  Second graph model for the sensor domain problem

Average Case Complexity and Phase Transition Phenomena Results

Initial results [1] indicate that the computational complexity is closely related to two key parameters of the system. One of them is the communication level between the sensors nodes. This level goes from zero (when there are no communication links) to 1 (when all the pairs of sensors have a communication link between them).  Figure 5 shows the results of an experiment with  random configurations of 9 sensors and 3 targets such that there is a communication link between two sensors with probability p. The plot shows the probability that a random configuration of the problem, obtained with a particular value for p, has solution, e.g. all the targets can be tracked by the sensors.

Figure 5: Phase transition in the solvability of the problem when increasing the communication capacity

Figure 6: Phase transition in the solvability of the problem when increasing the radar range

Future Work

We plan to perform a more detailed study of the characteristics of this problem that change the complexity of finding solutions for Distributed CSP (DCSP) algorithms solving a DCSP model of the problem. In that direction, we have started to model the problem as a DCSP. In DCSPs, we have a set of agents and every agent has his own problem (a CSP) that he has to solve. However, there exists also constraints between variables of different agents that the involved agents must also satisfy when finding a solution to their own CSPs. We have started to consider a DCSP model in which we have a different tracker agent for every target. Every tracker agent has a set of variables that represent the different sensors. A solution to the DCSP model, that represents a solution to the original problem, is an assignment of sensors to tracker agents such that:

•  The three sensors selected by the tracker agent have the target within their detection distance and have a communication edge between them.

•  Every tracker agent must ensure that the sensors he selects are not selected by some other tracker agent.

By using that DCSP model, we can study how different structural properties
of the communication network or the constraint network between agents produce
a high computational or communication cost between agents until they solve
the problem.

Presentations

References

1

R. Bejar, B. Krishnamachari, C. Gomes, and B. Selman.

Distributed constraint satisfaction in a wireless sensor tracking system.
In Workshop on Distributed Constraint Reasoning, IJCAI'01 (to appear), 2001. (PDF file) 

 

2

Carla P. Gomes and Bart Selman.

Algorithm portfolio design: Theory vs. practice.
In Proc. of UAI-97, 1997. 

 

3

Carla P. Gomes and Bart Selman.

Problem structure in the presence of perturbations.
In Proc. of AAAI'97, pages 221-226, 1997. 

 

4

Carla P. Gomes, Bart Selman, and Henry Kautz.

Boosting combinatorial search through randomization.
In Proceedings of the 15th National Conference on Artificial Intelligence, AAAI'98, Madison/WI, USA, pages 431-437. AAAI Press, 1998. 

 

5

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.

Optimization by simulated annealing.
Science, 220:671-680, 1983. 

 

6

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky.

Determining computational complexity from characteristic 'phase transitions'.
Nature, 400(8), 1999. 

 

7

Bart Selman and Scott Kirkpatrick.

Critical behavior in the computational cost of satisfiability testing.
Artificial Intelligence, 81(1-2):273-295, 1996.