Optimal Multi-Sensor Based Multi Target Detection by Moving Sensors to the Maximal Clique in a Covering Graph

1. Introduction

The problem of multi-sensor target tracking has attracted a significant amount of interest over the past few years. The papers [Jung and Sukhatme, 2002] and Parker[2002] are especially relevant in the context of this paper as representative algorithms; we appraise these in specific scenarios in a subsequent section. Other pertinent approaches include a scheme for delegating and withdrawing robots to and from targets through the ALLIANCE architecture [Parker 1999], a strategy for maximizing coverage with mobile sensors [Sameera and Sukhatme 2004] and a method for sensor management in a distributed tracking setup [Horling et. al, 2003]. There is also a large volume of work in the context of using a network of static sensors to guide robots pursuing invaders [Schenato et. al 2005]. A more detailed citation of literature is avoided here due to strict page limits.

Our first objective in this paper is to analyze performance of existing solutions, and reformulate target detection as an optimization problem. Subsequently, we introduce the notion of covering graph to optimize the detections of a single sensor. Extending this technique to multiple sensors is in general nontrivial, involving searching over a discrete search space, which is accomplished by a tagging operation. These ideas are crucial in transforming a continuous search space into a discrete one, enabling us to find an optimal solution from among several disparate ones. In contrast almost all existing solutions employ some heuristic to determine a good solution in an uncountable search space. Finally, we test our algorithm against two others whose parameters are tweaked by hand to perform optimally. Nonetheless, our results show that our algorithm is able to perform better than compared approaches across a number of test cases.

2. Analysis of Existing Algorithms

In this section we examine the performance of two existing representative algorithms, those of [Parker 2002] and [Sukhatme 2002].

2.1 Parker's Algorithm

Fig.1 shows a set of targets, depicted by small unshaded squares, moving counter clockwise about a circle. The shaded squares represent sensors; one sensor, closest to the circle, is repelled away by the sensor-target repulsive force referred to in [Parker 2002]. Also, every target is outside the sensing range of every other sensor. It is evident that optimal detection will occur if instead of getting repelled away, the former sensor is attracted to the inside of the circle.

2.2 Sukhatme-Jung Algorithm

Fig 2 shows an environment partitioned into five regions by landmarks represented by the diagonal black lines. A sensor S is initially stationed in region 1. Targets are located along each edge of the dotted square ABCD . They move in the direction indicated by the arrows cyclically with uniform velocity. The dotted circle is the FOV (field of vision) region of a nonexistent sensor placed at its center O ; it is meant to touch the sides of the square, but offset for clarity. It is clear that optimal detection takes place at O . Due to the uniform velocity of sensor motion the urgency of all regions will be the same, causing the sensor to either remain in region 1 or switch continually from one region to an adjacent one. Hence the algorithm is unable to find the optimal positionO .

Both these algorithms perform very well in many scenarios, (such as the ones cited in their sources); the pathological runs shown above are exceptions to the rule. Parker's algorithm fails when target-sensor and sensor-sensor forces give conflicting results, and Sukhatme-Jung's becomes suboptimal due to the artificial division of the environment area into regions. The presence of these exceptions leads us to ask the question: Can the performance be improved further?

3. Problem Statement

We introduce the following definitions:

1. E is a bounded region in the plane, called the environment over which sensors and targets move. The precise shape of E is of little significance in what follows, hence will be assumed to be an A A square.
2. )} ( ).., ( 2 ), ( 1 { ) ( t n S t S t S t S is the snapshot of the set of sensors, at time instant . Each sensor has FOV A f .
3. )} ( ).., ( ), ( { ) ( 2 1 t T t T t T t T m is likewise the snapshot of the set of targets at time instant t .

Given ) 0 ( S as a set of points within E , and ) 0 ( T as a set of points on the edges of E . At every time instant .. 3 , 2 , 1 t , every target moves with a maximum speed of max v in an unknown direction. A sensor has a maximal speed of max s . Determine positions of ) (t S over time in such a way that the number of targets detected by at least one sensor is maximized. If there are several possible optimal solutions, we prefer those which maximize the number of detections by precisely one sensor. This last requirement minimizes redundant detections.

3.1 Preliminaries

If P is a point on the plane and 0 r , define ) (P C r (resp. ) (P D r ) as the circle (resp. closed disk) of radius

r centered at P ; also, define ) (P Dr as the exterior of ) (P D r . Define ) ( i S C as the circle of radius max s centered at i S (called the sensor circle of i S ) and ) ( j T C a circle of radius max v centered at j T (called the target circle of j T ). Define ) ( i S D and ) ( j T D correspondingly as sensor and target disks. Note that ) ( i S D f is the FOV disk of i S . Given a set P of points on the plane, define ) (P Hull as the vertex set of the convex hull of P .

We call the ordered pair )) ( ), ( ( 0 0 t T t S the configuration of the sensor-target system at time instant 0 t , and any set of consecutive configurations a configuration sequence. Define a configuration sequence to be feasible if the following condition holds: For every pair of consecutive time instants 1 ' , ' t t in the sequence, max | ) ' ( ) 1 ' ( | s t S t S i i for every sensor and max | ) ' ( ) 1 ' ( | v t T t T j j for every target; we will be interested only in feasible sequences hereafter. We define the number of k detections (resp. k detections) of the configuration as the number of targets detected by precisely (resp. at least) k sensors, and call k the order of detection. With these definitions, the problem seeks to maximize 1+ detections, preferring maximal 1-detections.

3.2 Solving a set of Quadratic Constraints

This section develops a technique to be used later in Section 4.2 to assign sensor positions in a multi-sensor system. Given two disjoint sets of targets, } ,.., , { 2 1 k inc T T T T and } ,.. { 2 , 1 l k k exc T T T T , we are asked to determine whether we can place a sensor that covers all targets in inc T and none of those in exc T . The problem reduces to determining if there exists a sensor position P for which

has a solution . [3.2] has a solution if and only if the intersection exc T i T i T D inc T i T i T D I f f ) ( ) ( is non-null; in

this case, every point in I is a solution. Further, suppose that [3.2a] has a solution, but with the additional constraint that f T P k || || 1 , it does not. This means that every circle of radius f which covers inc T also covers 1 k T . In such a case, 1 k T is said to be dependent on inc T ; in particular, if 1 k T falls within ) ( inc T Hull , it is always dependent on inc T .

4 Methodology

4.1Single Sensor System

Covering Graph

Consider the configuration )) ( ), ( ( 0 0 1 t T t S . We say that a point ) ( 1 S D P is a covering point with respect to 1 S , of a set T T ' of targets, currently within ) 1 (S D f , iff no target in T can escape out of ) (P C f in one time step. Observe that if P is a covering point of target ' T i T , then ) ( i T D P d , where max v f d . In the same scenario we say that every pair of targets in ' T is simultaneously coverable. Note that two targets are simultaneously coverable iff the (Euclidean) distance between them is at most d 2 . Define the covering graph )) ( ), ( ( t T t S CG of the configuration as a graph whose nodes are covered targets, and whose edges connect a pair of simultaneously coverable targets. From above, targets in ' T will form a clique in the covering graph. Further define a maximal clique in )) ( ), ( ( t T t S CG as one with the maximal number of vertices, noting that this could be non-unique.

It is easy to see that moving to a covering point of a maximal clique ensures that a maximum number of targets will be detected at the next time instant. We formalize this idea as follows: Define the covering function N S D CF ) 1 ( : which takes a point in ) 1 (S D to the number of targets that a sensor at that point will definitely cover in the next time step. The maximal values of the covering function will be attained at the points of intersection of ) ( ) ( j T f C i T f C , where ) 1 ( , S f D j i T , giving us an algorithm to move 1 S to a covering center of a maximal clique. 1 S visits each of the points of intersection of the form above, and moves to that which gives maximal detections; should there be no intersections, it moves to a covering point of any target it detects. This ensures a maximal number of detections in the next time step, and the algorithm runs in ) ( 2 m O time where m is the number of targets.

Number of Cliques

In this section we estimate the maximal number of cliques that can exist in ) ( 1 S D f . A clique in )) ( ), ( ( 1 1 t T t S CG has all its targets lying within a circle of radius max v f d as a result, the separation between two cliques is at least d . Consequently, the number of cliques in ) ( 1 S D f is at most the size of maximum set of points M that can be chosen in ) ( 1 S D f such that the distance between any every point in M , with its nearest neighbors in M , is d . Such an M can be constructed as follows. Choose a point )) ( ( 1 0 t S D P f ; draw the circle ) ( ' 0 P C C d , and mark off the vertices of a regular hexagon inscribed in it . Repeat the construction at every 6 1 , i P i until no more points within ) ( 1 S D f can be found. This leads to tiling of ) ( 1 S D f by regular hexagons of side d , leading to ) ) (( 2 d f O hexagons and clique centers.

4.2 Multi-sensor System

In this section we use ideas from previous sections to obtain an optimal solution to tracking with n sensors. The sensors share knowledge of the targets they see at every time instant, enabling each to build the global covering graph..

Taglists and Taglist types

To optimize 1+ detections is a nontrivial problem in general. We assume for the purpose that every target i T is tagged with a list of sensors, taglist T i . . Also, define T i T taglist i T i taglist T )} . , {( . . The point of introduc-

ing taglists- as claimed in Section 1- is to convert a continuous search space into a discrete one. When we say i T is tagged with a list S S ' , we try to see if i T can be covered by the sensors in ' S ; if this is feasible, then sensor positions can be assigned to sensors in ' S by the algorithm in Section 3.2, or else deemed impossible by the same. We formalize this in the following definitions.

Given ) ( 0 t S , an instance of taglist t T ). 1 ( 0 is said to be feasible iff for every sensor the intersection

is nonempty. Here ) , . ( i S taglist T Cover is the set of all targets covered by i S . We say that a point ) ( i S D P is a covering point with respect to i S , of a set T T ' of targets, currently detected by at least one sensor in the system, iff no target in T can escape out of ) (P C f in one time step. The covering graph and covering function of a sensor are defined correspondingly.

For a single sensor, optimality of detection hinged on the assurance that a certain number of targets would be seen the next time step. This assurance is formalized by the idea of a proper taglist in a multi-sensor system. A feasible instance of taglist t T ). 1 ( 0 is said to be proper iff for every sensor ) (t S i , targets in ) , . ( i S taglist T Cover are vertices of a clique in )) ( ), ( ( 0 0 t T t S CG i . It is difficult to construct proper taglists directly ; it is easier to take a shortcut through taglists which satisfy the hull property, defined next.

An instance of taglist t T ). 1 ( 0 is said to satisfy the hull property if and only if the following criterion holds for every subset ' T of targets in it. If every target in ' T is tagged with sensor i S , then every target located within ) ' (T Hull is also tagged with i S . Note that if an instance of taglist t T ). 1 ( 0 is proper, it also satisfies the hull property; the converse need not be true. We will use this property to generate proper taglists and later to compute the complexity of the multi-sensor system.

Finding the Optimal Solution

The Findopt routine finds the sensor assignment that guarantees maximal 1+ detections in the next time step. )) ( ), ( ( t T t S Findopt

0 0

1. Generate an initial proper taglist,Current for ) ( 0 t T . Compute ) ( 1 Current N and ) ( 1 Current N , which denote the number of 1+ and 1 detections in Current respectively.
2. For each proper taglist Next remaining do

1. Assign sensor positions corresponding to Current using the method in Section 3.2.

Finding all proper taglists

It remains to specify how we find proper taglists. Note that only sensors with overlapping FOV regions pose a difficulty, for otherwise we run the single-sensor algorithm on each sensor. The brute force approach would be to generate all possible taglists, check whether each is proper, and pass

it to Findopt , at the expense of having an 1 ), 2 ( k km O algorithm. This is too expensive a solution in time. Instead, we generate all taglists satisfying the convex hull property, which in general takes time sub-exponential in m , and check whether each is proper. This is formalized below.

sensors, the only proper taglist we generate corresponds to maximal clique detections by each sensor. If the sensors move in such a way that their FOV overlaps, we degenerate to the weakly overlapping case covered below.

that ) ( ' 0 t T is the set of targets detected by ' S , and further that ) ( ' ) ( ' ' 0 0 t T t T is detected by more than one sensor. Suppose that ) ( 0 t Q i is the set of cliques of k i t T t S CG i 1 )), ( ' ), ( ( 0 0 .

We generate the space of proper taglist instances for ) ( ' 0 t T as follows. Construct an iterator 1 I that traverses the space ) ( .. ) ( ) ( 0 0 2 0 1 t Q t Q t Q k . At every point of the traversal of 1 I , do the following. Tag every target that appears in one or more cliques with all sensors in whose FOV it falls. Suppose that ' ' ' T is that subset of ' ' T which is currently detected by more than one sensor in ' S . Construct iterator 2 I which goes over all possible combinations of sensor assignments to targets in ) ' ' ' (T Hull . Each of these satisfies the hull property. Output the resulting taglist if and only if it is proper.

We call ) ( ' 0 t S weakly overlapping iff for every ' S S i there exists at least one i j S j S : ' such that

) ( ) ( j S f D i S f D . Following the same notation as in the previous case, we generate the space of proper taglist instances as follows. 1 I has the same meaning as before. It is then possible to write 0 ' t S as ) ( ' .. ) ( ' ) ( ' ) ( ' 0 0 2 0 1 0 t S t S t S t S r , where sensors in each ) 0 ( ' t i S are strongly overlapping. Correspondingly

tor 2 I which goes over all possible sensor assignments to targets in r i t i T Hull 1 )) ( ' ' ' ( 0 , the Cartesian product of hulls; output the resulting taglist iff it is proper.

Complexity Analysis

A typical worst case scenario is one in which ) (t S is weakly overlapping. In this case 1 I runs over ) ) (( 2n d f O clique combinations, so the algorithm is exponential in the number of overlapping sensors. Suppose that there are n k k 1 : hulls for 2 I to consider, and that the i -th hull encloses, or has on its boundary, i m targets in all, and i m' vertices. Suppose further that all m targets are currently detected. Then 2 I takes ) ( 'i m n O iterations to traverse its space, and each iteration takes polynomial time in m in for computing the hulls, verifying hull points, and so on. Note that ) ( ) ( ' m o m o m i i except in rare cases, so that the run-time is sub-exponential, typically polynomial, in the number of detected targets.

In essence while the algorithm is exponential in number of overlapping sensors it is typically polynomial in the number of targets due to tags for only the targets that form the convex hull for a set of targets that constitute a clique. In steady state when sensors have diverged to maximize detections, the number of overlapping sensors is generally small, and this is specifically so when the area of E, is considerably greater than the total area covered by the sensors. Indeed when the total area covered by sensors is greater than or equal to area of E maximizing detections is trivially achieved.

5. Simulation and Results

5.1 Implementation Specifics

The optimal algorithm above, hereafter called OPT, as well as the representative algorithms of Parker and Sukhatme-Jung, have been implemented on an Intel P4 machine running Fedora Core 4 using the g++ compiler and Qt for graphical simulation. The specifics of each implementation are given below.

OPT Algorithm

This is essentially the same as the multi-sensor version presented in Section 4.2 with the restriction that, when OPT runs for 1 second, it terminates and outputs the most optimal solution generated thus far. This restriction ensures that OPT takes nearly the same time to output its solution as its adversaries.

Parker Algorithm

We implemented the A-COMMT version of the Parker algorithm. We set the sensing range of every sensor to the FOV of OPT sensors during comparison; predictive tracking and communication ranges do not matter for simulation. In addition, we tweaked the values of i dr and i do , corresponding to cut-off points for sensor-sensor and sensor-target forces, until they gave optimal performance. Specifically, we changed 1 do and 1 dr from one test case to another, observing that 1 2 1 5 . 1 2 . 1 do do do and 1 3 1 7 . 2 0 . 2 do do do gave best results; likewise did 1 2 1 4 . 2 8 . 1 dr dr dr . Furthermore, we scaled the weighted force vectors to an equal degree for all sensors.

Sukhatme-Jung Algorithm

We partitioned the square environment into a crossshaped topological map. We tweaked the urgency and availability thresholds from one test case to the next; in particular, 10 4 ty availabili and 8 4 urgency give maximal detections. The control parameter d was varied likewise across test cases till maximal detections were obtained; specifically, when the FOV or the number of sensors was decreased, we gave a small value to d , between 0.5 and 0.6, and large otherwise, between 1.5 and 1.8.

5.2 Tabulated Results

The environment is the square ] 500 , 0 [ ] 500 , 0 [ . Five sensors, each of FOV 50, are randomly placed in E , each with 50 max s . Targets emanate from five sources placed randomly on the edges of E every time instant. The speed of each target is uniformly distributed in ] 5 , 0 [ and angle uniformly distributed on ] 2 , 0 [ . In Tables 1-3, the rows indicate the order of the detection as a percentage rounded to the nearest integer, and the columns indicate the algorithm whose performance is noted. Tables 2 and 3 show readings of the form A|B, to be interpreted as follows. In table 2, A corresponds to the case of 7 sensors, and B to that of 3 sensors, as indicated in its caption. Table 3 is read similarly.

5.3 Performance Graphs

Fig. 3a (resp. 3b) shows how the number of 1+ detections varies with FOV(resp. number of sensors) for each algorithm. The performance gain of OPT over the earlier ones is evident for various sensor and FOV combinations as it gives consistently higher 1+ detections, despite the manual tweaking of its adversaries to achieve optimal performance.

6. Conclusions

A novel algorithm for multi-sensor based multi target detection has been formulated and analyzed in terms of its computational complexity. Comparison with other approaches in literature verifies its efficacy across diverse scenarios. Such a multi-sensor algorithm finds applications in border patrol, guarding of secured areas, search and rescue and warehouse surveillance.