 
DARPA ANTS Web page ANTS Web pageControlling Computational Cost:Structure, Phase Transitions, and Randomization 

IISI
Home
CIS Home CS Home 
Research
team
Principal Investigator: Bart Selman CoPrincipal Investigators: Carla Gomes and Scott Kirkpatrick Others:
Ramon Bejar and Bhaskar Krishnamachari


Overall
Goal and Techniques
The overall goal is the design of reliable, robust and scalable constraint satisfaction methods for largescale, 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.
The goal in this problem is to track the position of a set of moving targets located within an area using fixed Doppler radarbased 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.





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


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


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. 



The other parameter is the detection range of the sensors. We can consider this parameter as going from zero (when the sensor cannot detect targets at any distance) to 1 (when he can detect targets located at the maximal distance we can find targets). Figure 6 shows the results of a similar experiment, but now the random configurations are generated in such a way that each sensor is able to detect targets within a normalized range R. 



We observe in both cases a sharp transition from almost no soluble instances to almost soluble instances around a critical value of the key parameter. This behavior is similar to the one observed in other NPcomplete problems. 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:
PresentationsANTS PI Meeting. Tahoe City, California. April 2001. (Powerpoint presentation)Netmeeting. October 2001. (Powerpoint presentation) Tracking dynamics (preliminary) (Powerpoint presentation) The latest simulation results! Note: First let the browser do a complete download of the animated gif. This may take one or two minutes. After that, the gif will run in realtime. References
In Workshop on Distributed Constraint Reasoning, IJCAI'01 (to appear), 2001. (PDF file) In Proc. of UAI97, 1997. In Proc. of AAAI'97, pages 221226, 1997. In Proceedings of the 15th National Conference on Artificial Intelligence, AAAI'98, Madison/WI, USA, pages 431437. AAAI Press, 1998. Science, 220:671680, 1983. Nature, 400(8), 1999. Artificial Intelligence, 81(12):273295, 1996. 

IISI
Home
CIS Home CS Home 