How Smart Does an Agent Need to Be Scott Kirkpatrick1 and Johannes J Schneider1 2 1 Hebrew University of Jerusalem Israel and 2 Johannes Gutenberg University Mainz Germany Abstract The classic distributed computation is done by atoms molecules or spins in vast numbers each equipped with nothing more than knowledge of their immediate neighborhood and the rules of statistical mechanics Such agents 10 23 or more of them are able to form liquids and solids from gases realize extremely complex ordered states such as liquid crystals and even decode encrypted messages I ll describe a study done for a sensor array challenge problem in which we have based our approach on old fashioned simulated annealing to accomplish target acquisition and tracking under the rules of statistical mechanics We believe the many additional constraints that occur in the real problem can be folded step by step into this stochastic approach The results have applicability to other network management problems on scales where a distributed solution will be mandatory Introduction A very old idea in distributed computing and communication is the network that selforganizes to perform some local function of moderate complexity and then communicates its discoveries to some wider world that is interested In military communications this might take the form of sensor arrays of simple inexpensive units sprinkled behind a rapidly advancing force in battle to provide communications or around a sensitive installation to create a defensive perimeter We recently participated in a study of an application of this sort From our experience we concluded that understanding the complexity of these self organizing systems is critical to achieving their objectives and is sorely neglected in the most popular approaches to programming them The study which we joined in midstream had been envisioned as an exercise in multi agent distributed programming with negotiation protocols These were to be employed to resolve a difficult optimization problem which would frequently require settling for locally sub optimal results in order to meet challenging real time constraints with acceptable solution quality The sensors in this array are Doppler radars rather useless individually but capable of tracking targets if three or more of the radars can lock onto a single foreign object for a sufficient time In possible applications such as protecting a aircraft carrier during refueling one could imagine having a few thousand such antennas floating in the sea But for research and demo purposes controlling four to twenty such antennas was considered quite challenging Thus the temptation was strong to write very special case agents and evolve very specific negotiation protocols as overloads and other problems were discovered One of the other groups in this study was planning to develop a target 1 selection protocol with negotiation that would support 64 antennas observing a dozen or so targets and simulate it on a 32 processor server cluster but not in real time Working with Bart Selman and the Intelligent Information Systems Institute of Cornell University we were asked to determine if there might be phase transitions or other threshold phenomena blocking the way to success in this endeavor and if so what to do about it We wrote a simulation of the target assignment and tracking problem Because of our concern with complexity and its scaling we treated the antennas as spins not agents and looked first for a Hamiltonian that would give them the right behavior counting on statistical mechanics and temperature to handle the negotiation part It worked rather well although there were a few inventions required to find a way to make everything work What follows is lightly edited from our progress reports After describing our effort we conclude with comments on the role of phase transitions in this sort of large scale engineering problems as they continue to grow in scale over future decades Physics inspired negotiation for Sensor Array self organization We implemented a family of models which borrow insights and techniques from statistical physics and use them to solve the sensor challenge problem under a series of increasing restrictive real time constraints We describe results with fairly difficult communications constraints and moving targets covering the phases from target acquisition to tracking The method can deal with momentary overloads of targets by gracefully degrading coverage in the most congested areas but picking up adequate coverage as soon as the target density decreases in those areas and holding it long enough for the target s characteristics to be determined and a response initiated Our utility function based approach could be extended to include more system specific constraints yet remained efficient enough to scale to larger numbers of sensors Our model consists of 100s of sensors attempting to track a number of targets The sensors are limited by their ability to communicate quickly and directly with neighboring sensors and can see targets only over a finite range which probably exceeds the range over which they can communicate with one another We take the communication limits to be approximately the values that arise in the Seabot deployment by MITRE This is modeled probabilistically Initially we assumed that there is 90 probability of a communication link working between two neighboring sensors 50 probability at twice that distance and 10 probability at three times that distance using a Fermi function for the calculation at an arbitrary distance Subsequently we explored other characteristic cutoff ranges for communications using the same functional form for the probability of communication At the start of each simulation we use this function to decide which communication links are working The range at which a target can be tracked is a parameter which we vary from a minimum of 1 5 times a typical neighbor distance to 4 times this distance Sensors are placed on a regular lattice with positions varied from the lattice sites by a random displacement of up to 0 1 times the lattice spacing We considered three lattice arrangements to give different spatial densities honeycomb sometimes called hexagonal was the least dense then square lattice then triangular lattice But the precise lattice geometry made little difference beyond the changes in sensor density that resulted so most work was carried out with a square array of sensors randomly