Grid-based SensorDCSP

1 Introduction

In recent years we have seen an increasing interest in Dis­ tributed Constraint Satisfaction Problem (DisCSP) formula­ tions to model combinatorial problems arising in multi-agent environments [Yokoo, 200 1]. Recently, an interesting bench­ mark for DisCSP algorithms, called SensorDCSP, has been introduced in [Fernandez et al., 2002]. Inspired by distributed applications arising in networked systems, SensorDCSP in­ volves a network of distributed sensors simultaneously track­ ing multiple mobile objects. An instance of SensorDCSP is defined by a set of sensors, a set of mobiles which are to be tracked by the sensors, and two sets of visibility and compat­ ibility constraints specifying which sensors can communicate one with another and which sensors can track which mobiles, respectively. The goal is to allocate three sensors to track each mobile, such that all these triplets of sensors are pair­ wise disjoint, and the sensors in each such triplet are mutually compatible and can track the mobile they are assigned to. The analysis in [Fernandez et al., 2002] addresses the complexity Universitat de Lleida Jaume II, 69. Lleida, Spain of SensorDCSP, as well as its empirical evaluation, consid­ ering the performance and scalability of alternative DisCSP algorithms on various scenarios in a truly networked environ­ ment.

*Research supported by AFOSR, grant F49620-0l-l-0076 (In­ telligent Information Systems Institute) and F49620-0l-l-0361 (MURI grant on Cooperative Control of Distributed Autonomous Vehicles in Adversarial Environments),. CICYT, TIC2001-1577C03-03 and DARPA, F30602-00-2-0530 (Controlling Computa­ tional Cost: Structure, Phase Transitions and Randomization) and F30602-00-2-0558 (Configuring Wireless Transmission and Decen­ tralized Data Processing for Generic Sensor Networks). The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of AFOSR, DARPA, or the U.S. Government.

In this work we extend SensorDCSP by providing it with an underlying spatial structure. In SensorDCSP, the con­ straints of communication between sensors and visibility of mobiles are independent of their physical location. In con­ trast to SensorDCSP, the spatial limitations for both com­ munication between sensors and visibility of the mobiles are captured by a geometrical structure in our new benchmark, providing a more realistic framework. We refer to our ge­ ometrically enriched benchmark as Grid-based SensorDCSP or just GSensorDCSP. We provide both an analytical com­ plexity analysis of GSensorDCSP and an empirical study of a characteristic DisCSP algorithm on various instances of this problem.

2 GSensorDCSP: Definition and Complexity

GSensorDCSP is a specific variant of the general SensorD­ CSP, enriched by a spatial structure: we have multiple sen­ sors S = {s1 , · · · , sm}, multiple objects (mobiles) T = { t1 , · · · , tn} which are to be tracked by the sensors su~ject to visibility and compatibility constraints, and the goal IS to decide whether there exists an allocation of three sensors to each object, while keeping these triplets of sensors pair-wise disjoint. However, the visibility and compatibility constraints in GSensorDCSP relate to the physical limitations of the sen­ sors and the terrain on which the sensors are located.

In GSensorDCSP, the sensors are located on the nodes of a uniform grid, and the mobiles are located within the surface enclosed by this grid; this way the grid specifies the gener­ ally trackable region. The physical limitations of the sen­ sors are modeled by the notions of kc-compatibility and kv­ visibility. The kc-compatibility window for a sensor s;, de­ noted as Ckc (s;), corresponds to the set of all sensors that are at most kc general (rectilinear and/or diagonal) hops from s; . For example, the black sensors in Figure 1(a) correspond to 2-compatibility window for the gray sensor. Similarly, the kv­ visibility window for a mobile tj, denoted as Vkv (tj), corre­ sponds to the set of all sensors that are at most k general hops around tj. For example, the black sensors in Figure 1(b) cor­ respond to 2-visibility window for the square mobile. Finally, if each sensor s; of a given GSensorDCSP problem instance can communicate only with some sensors within Ckc (s;), then the set of compatibility constraints of this instance is called kc-restricted. The notion of kv-restricted visibility is defined similarly.

Studying the worst-case complexity of GSensorDCSP we formally show that:

1. Any GSensorDCSP instance with !-restricted visibility is solvable in low polynomial time, and
2. GSensorDCSP with kv-restricted visibility is NPcomplete for all kv 2 2.

The former is shown by a reduction to the problem of feasible integer flow in bipartite graphs, while the latter is shown by a non-trivial reduction from 3-SAT and is valid even for the problems with !-restricted compatibility.

3 Connecting Locality and Constrainedness

While the physical limitations of the sensors in GSensorD­ CSP are modeled via the locality windows, the terrain limita­ tions are modeled via incomplete compatibility and visibility within the windows. Problem instances of any GSensorDCSP sub-class (kc, kv) can be ordered according to the local con­ strainedness, i.e., the average number of sensors that a sensor can communicate with and the average number of sensors that can track a mobile. In our experiments, for each pair of lo­ cality parameters (kc, kv ), we define a random distribution of GSensorDCSP instances via two parameters Pv, Pc E (0, 1] that control the density of visibility and compatibility: The probability that two sensors s; and Sj will be compatible is given by Pc if (s;, Sj) E ([:kc (s;), otherwise, it is equal to 0. Clearly, higher value for Pc and Pv correspond to better conditions for communication and tracking, respectively.

For our first experiments with the AWC [Yokoo, 1994] al­ gorithm, we consider different sets of instances with 25 sen­ sors (grid 5 x 5), and 5 mobiles, with every set generated with different values for the parameters Pc and Pv. The parame­ ters Pc and Pv are ranging from 0.1 to 1 with an increment of 0.1, giving a total number of 100 data sets, where every set contains 50 instances. Given our formal complexity re­ sults, we consider several hard subclasses of GSensorDCSP corresponding to kv = 2. For instance, Figure 3(a) shows the ratio of the satisfiable instances (Psad as a function of Pc and Pv for kv = 2 with kc = 1 and kc = 2. As in the case of general SensorDCSP [Fernandez et al., 2002], when both probabilities are low, the instances generated are mostly un­ satisfiable, while for high probabilities most of the instances are satisfiable. Both for kc = 1 and kc = 2, the transition be­ tween the satisfiable and unsatisfiable regions occurs within a narrow range of the density parameters. Observe that, for kc = 1 this range corresponds to significantly higher values of Pc and Pv, comparatively to these for kc = 2 and kc = 2. However, the form of the transition for various values of kc is very similar.

Consistently with the general SensorDCSP, we observe that the phase transition of GSensorDCSP coincides with the region where the hardest instances occur. For instance, Fig­ ure 3(b) shows the mean solution time with respect to the density parameters Pv and Pc for the problem instances with 25 sensors, 5 mobiles, kv = 3, and kc = 1. Somewhat less expected result is depicted in Figure 3(c) for the case of kv = 1 (and kc = 1), which we showed to be polyno­ mial by a reduction to the problem of feasible integral flow in bipartite graphs. Despite the fact that AWC is a general purpose algorithm, Figure 3( c) shows that these tractable in­ stances are relatively easy for AWC. able to "detect and ex­ ploit" the tractable without being aware of its existence.

Extending the evaluation, we consider different sets of instances for several orders of the problem (grids of 25100 sensors), and several levels of decomposition (kc, kv E {2, 3, 4, 5} ). The analysis of these sets of instances clearly shows both exponential dependence of the mean solution time on the size of the grid, and, somewhat more interestingly, growth of the slope of this dependence with kv.

4 Dynamic GSensorDCSP

As an additional extension of the GSensorDCSP domain, we consider the dynamics of the mobiles, in order to determine under which conditions (number of sensors and mobiles, ve­ locities, trajectories, etc.) generic DisCSP algorithms are able to track the mobiles in real time. More formally, a dynamic GSensorDCSP problem can be seen as an ordered sequence of static GSensorDCSP problems II1 , · · · , IIN. The static problems of the sequence only differ in the positions of the mobiles and hence the visibility between sensors and mobiles. Observe that, if no assumptions are made about the relation­ ship between the positions of the mobiles in II; and Ili+1 , it is natural to solve these problems independently (naive ap­ proach). However, mobile dynamics are typically far from being chaotic. A first approximation is to consider linear tra­ jectories. In this case, changes between the subsequent prob­ lems are governed by a clear model. An approach that a priori seems to be promising for dealing with the dynamic prob­ lem is to initialize the search for II; by the solution already achieved for ni-l (solution repairing approach).

In order to compare the naive and the solution repairing approach, we have performed experiments where we solve dynamic GSensorDCSP problems with both approaches. Fig­ ure 3 depicts the cumulative probability distributions of solv­ ing II; for two different problems. One of them is obtained from the 50 % Psat point of GSensorDCSP and the other from the 70 % Psat point.

Our results show that we can exploit the previous solution and that, assuming certain reasonable constraints on the mo­ bile movements, we can benefit from solution repairing over the naive approach. More interestingly, it also follows that the relative attractiveness of solution repairing is higher in the region of hardest instances.

5 Conclusions and Future Work

We believe that GSensorDCSP provides a realistic framework for the analysis of the DisCSP algorithms, and we hope it will contribute to the further research in this area. For the dynamic version, a next step would be to consider the effect of several kinds of trajectories in the performance of the so­ lution repairing approach. Finally, a further step towards an even more realistic DisCSP benchmark would be to consider its optimization version: maximizing the number of tracked mobiles. In this extended distributed benchmark, it would be interesting to study the existence of the easy-hard complex­ ity patterns that have been observed in classical optimization problems [Slaney and Walsh, 2002].