WIXLIB

SUBMITTED TO IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING2The placement for forest fire example (32 towers)to its center is given and the number of centers is to be minimized,is also NP-Complete [10]. The converse problem can be easily seento be a special case of the SPP where the uncertainty function ischosen as U (si , sj , w) min{d(si , w), d(sj , w)}. Hence, SPP is atleast as hard as the converse k-center problem.0.60.40.22.52B. Related work1.5120.50Coverage and placement problems received a lot of attentionrecently. However, most of the existing work focuses on sensors thatare capable of estimating the state of the target independently. In thissection, we review work on the placement of sensors which jointlyestimate the states of targets.In [11], the problem of controlling the configuration of a sensorteam which employs triangulation for estimation is studied. Theauthors present a numerical, particle-filter based framework. In theirapproach, the optimal move at each time step is estimated bycomputing an n dimensional gradient numerically where n is the sizeof the joint configuration space of the team. This work solves a localplacement problem (around the target) for a small number of robots ateach time step. Instead, we focus on the global placement problemacross the entire work space. In [12], the problem of relocating asensor team whose members are restricted to lie on a circle andcharged with jointly estimating the location of the targets was studied.In the present work, we study more general environments on theplane. In [13], the authors study the problem of placing camerasin a polygonal workspace in such a way that for each point ofinterest, there are two cameras which can view the point at a “good”angle. The authors present a log-approximation for this problem.Their work can address occlusions. Our approximation algorithmhas a better performance ratio (it is a constant factor approximationalgorithm). The uncertainty metric is also more sophisticated as itincorporates distance and angle. However, we do not address the issueof occlusions in the workspace. The work in [14] studies the problemof assigning disjoint pairs of sensors to targets. The authors introducethe notion of Universal Placement where “good” assignments existregardless of the targets’ locations. In this work, the main focus ison multi-target tracking, and there is an explicit requirement thatthe sensor pairs be disjoint. The issue of minimizing the number ofsensors, which is the main focus of our current work, is not addressed.III. A G ENERAL D ISCRETIZED S OLUTIONIn this section, we present a general solution, based on integerlinear programming, to SPP. The formulation requires discretizingthe workspace W and the domain of sensor parameters Q.The Integer Linear Program (ILP) uses the following variables. Foreach possible sensor parameter j Q, we define a binary variableyj . If yj 1 after solving the ILP, a sensor with parameters j will beplaced. Other binary variables are ziu and xuij . The index u varies overall possible target locations in W, whereas i and j vary over Q. Inthe solution, variables ziu become 1 when the sensor with parametersi is assigned to target location u. Variables xuij are set to 1 if thetarget location u is monitored by sensors with parameters i and j.The complete ILP is given by:1 0.5 10 1.5 1 2 2.5 2Fig. 2. A terrain model of a forest, and a placement of 32 fire-towersachieving small localization uncertainty.minimizeXyj(1)jsubject toyj xuij i, j, uziu u(4)xuijX 0 2i i, j, u with U (i, j, u) U(2) (3)Xxuij ziu i, u(5)Xxuij zju j, u(6)jiEquation 1 is the objective function, i.e. the total number ofplaced sensors. The constraints on the placement are imposed byEquations 2 – 6. The first constraint (Equation 2) enforces that ifa sensor with parameters j will be assigned to a target u, thensuch a sensor must be placed in the solution. Equation 3 enforcessensing and quality constraints: it prevents sensor pairs which donot satisfy the constraints from being assigned to a target location.Equation 4 guarantees that two sensors are placed to monitor thetarget u. Equations 5 and 6 maintain consistency between variablesxuij and ziu . The variable xuij can be 1 if and only if i and j arethe parameters of the two sensors which are assigned to monitor thetarget at u. All the other xuij variables with same u but different iand j parameters will be 0 (due to Equation 4). Therefore, if i′ andj ′ are the parameters of the sensors to be assigned to the target at′′u′ , the sum of xui′ j ’s over all j’s (xuij ′ ’s over all i’s) will be equal tou′u′zi′ (zj ′ ).In the next section, we present an example where the ILP formulation is used to solve a practical fire-tower placement problem.A. An exampleIn this section, we demonstrate the utility of the ILP frameworkwith an example. Imagine the task of placing fire-towers in a forestwhich are used for localizing events such as forest fires. Alternatively,one can imagine the task of deploying beacons which are used byfirefighting robots for localization.When the terrain is non-planar, such as the one shown in Figure 2,visual occlusions must be addressed. For this purpose, we use the

SUBMITTED TO IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERINGfollowing uncertainty model: Let s1 and s2 be two (candidate) firetower locations and w be a target location. If both s1 and s2 can seew, we compute the uncertainty using the formula U (s1 , s2 , w) d(s1 ,w)d(s2 ,w)on the plane defined by s1 , s2 and w. Otherwise, sin s1 ws2 U (s1 , s2 , w) is infinite. Note that it is possible to introduce a moresophisticated uncertainty measure for a particular sensor.Suppose we are given the environment model shown in Figure 2,the error model mentioned above and an error threshold of 0.5. Tosetup the ILP, we first compute two sets of candidate sensor andtarget locations. We place a uniform grid on the x-y plane withresolution ζ and project the grid points onto the forest surface toobtain candidate sensor locations. These sensor locations correspondto the vertices of the triangles of the surface triangulation. To obtaincandidate target locations, we shift the original grid by ζ/2 in bothx and y directions. The projection of this new grid onto the forestsurface gives us candidate target locations. In terms of running time,the bottleneck is the number of xuij variables. Therefore, we focuson them. In this example, there are 357 candidate sensor locationsand 320 target locations which resulted in 40, 783, 680 xuij variables.Two simple optimizations are to disregard values with xuij 0 andto use only one of the duplicate pairs: xij and xji . This reduces thenumber of xuij variables to 113, 136.The resulting ILP was solved with CP LEX9.1.0 solver on aPC equipped with a 2 GB RAM and 3.20 GHz CPU. Solvers likeCPLEX, use branch-and-bound technique to solve ILPs. Since thenumber of variables is very large, the number of branch-and-boundoperations is increased proportionally. Hence, rather than waitinguntil the optimal solution is reached, we found the best solution after10, 000 branch-and-bound operations which took 35.54 CPU hours.The resulting placement has 32 fire-towers and is shown in Figure 2.The generality of the ILP-based solution comes at the expenseof computation time. When the number of variables is large, theILP takes too long. It is possible to design efficient algorithms withprovable performance guarantees for special cases of SPP. In the nextsection, we present such an algorithm for bearing-only localizationon the plane.IV. P LACEMENT FOR B EARING - ONLY T RIANGULATIONIn this section, we address the problem of placing bearing-onlysensors on the open plane to monitor the workspace given byan arbitrary subset of the plane. A common uncertainty functionassociated with this model isU (s1 , s2 , w) d(s1 , w)d(s2 , w) sin s1 ws2 (7)where d(x, y) denotes the Euclidean distance between x and yand θ s1 ws2 is the angle between the sensors and the target(Figure 1). The details of this derivation can be found in [8]. Ingeneral, Equation 7 suggests that better measurements are obtainedwhen the sensors are closer to the target and the angle is as close to90 degrees as possible.Even though we ignore occlusions caused by the environment, thisversion of the problem has applications in the placement of fire towersto monitor a (flat) forest and placement of omnidirectional camerasin convex environments.Let U be a desired uncertainty threshold and OP T be an optimalplacement which uses the minimum number of sensors such thatU (OP T, W) U . We will present an algorithm to compute aplacement S with S 3 OP T and U (S, W) 5.5U where S and OP T be the cardinalities of the corresponding placements.Our algorithm works for any workspace W R2 . We assume thatsensors can be placed anywhere in the plane. As we will see shortly,3the optimal placement can not afford to place cameras too far fromthe workspace. Let R U . The proposed placement algorithm consists oftwo phases. In the first phase, we choose a set of centers C whichwill be used to determine the location of the cameras. In the secondphase, we place cameras on circles whose centers coincide with thechosen centers and whose radii are at most 2R. We will show thatthis placement achieves bounded deviation from the optimal one interms of both the number of sensors and the performance guarantee.The centers are chosen by the following algorithm:Algorithm selectCenters(workspace W): C , W W while W 6 – c an arbitrary point in W– C C {c}– W W \ {w : d(c, w) 2R, w W }The following lemma shows that the number of centers is smallwith respect to OP T .Lemma 1: Let C be the set of centers chosen by selectCenters andOPT be an optimal placement. OP T C .Proof: For each center c C, let us define D(c, R) to be a diskcentered at c with radius R. Since the distance between the centersis at least 2R, the disks D(c, R) are pairwise disjoint. We claim thateach disk D(c, R) contains at least one camera in OPT, which provesthe lemma.Suppose the claim is not true and let c be a center such that OPThas no cameras in D(c, R). But then, for any si , sj OP T , theuncertainty in observing c will be:U (si , sj , c) d(si , c)d(sj , c) d(si , c)d(sj , c) R2 U sin si csj However, this means that OPT exceeds the uncertainty threshold onc. A contradiction!In the second phase, we use the set of centers to determine theplacement of cameras.Algorithm placeSensors(centers C): for each c C– Wc {w : d(c, w) 2R, w W }– Let T be any equilateralq triangle whose circumcircle is′′D(c, 2R ) where R 3 14 R– Place three sensors s1 , s2 , s3 on the vertices of T (SeeFigure 4).In Figure 3 we illustrate the two phases of the algorithm. We onlyshow the first two selected disk centers and the placement of sensorsinside their disks.Clearly, algorithm placeSensors places at most 3 OP T cameras (Lemma 1). All we need to show is that for any point win the workspace, we can find two sensors si and sj such thatU (si , sj , w) 5.5U . The next lemma shows the existence of suchcamera pairs.Lemma 2: Let S {s1 , s2 , s3 } be the set of three cameras placedby placeSensors inside D(c, 2R). For any point w Wc , there existsan assignment of two cameras si and sj , such that U (si , sj , w) 5.5U where 1 i, j 3.Proof:

SUBMITTED TO IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING4s1RRq23 14R2qm13 P313P233P32Fig. 4. This figure shows the partitioning of D(c, 2R) into three partitionsP 1 , P 2 and P 3 . Three sensors (s1 , s2 , s3 ) are placed on the equilateral′triangle’sq vertices which is determined by its circumcircle D(c, 2R ) where3 1′kkR R. Each partition P divided into subregions Pij where si and4ksj are the sensors assigned for points inside PijWe divide the set of points inside D(c, 2R) into three partitions:P 1 s1 s2 s3 , P 2 D(c, 2R′ ) \ P 1 and P 3 D(c, 2R) \D(c, 2R′ ) (See Figure 4).Let w be any point inside D(c, 2R). Throughout the proof, we usevarious geometric properties for the three cases: w P 1 , w P 2and w P 3 . For each P k , we present a proof for a subregion Pijksuch that U (si , sj , w) 5.5U is satisfied for all w Pijk . Theproof generalizes to all Pijk (hence to P k ) by symmetry.Case (w P 1 ):We divide P 1 into three regions using the bisectors of the triangleT and label them as shown in Figure 4. Let w be a point inside1P23. It can be easily verified that the followingthree inequalities ′ ′3R,d(shold, π3 s2 ws3 2π,d(s,w) 23 , w) 2 3R .2312R′ 2Hence, U (s2 , s3 , w) sin 5.4989U 5.5U (See Figure 5).π/3Case (w P 2 ):s1π3wc2π3s2lδγFig. 3. This figure shows the two phases of the placement algorithm. In thefirst phase, we choose disk centers (for clarity we show only the first twoselected centers which are represented with red circles whose radii are 2R).In the second phase, we place three sensors (blue circles) for each center asdescribed in algorithm placeSensors.2P13w′βα2Rs23P12m′132R′3 14R2R′s3Fig. 5. We divide P 1 s1 s2 s3 into three regions using the bisectorsof the triangle T . The shaded area shows the possible set of locations for wsuch that the assignment of s2 and s3 satisfies U (s2 , s3 , w) 5.5U .π3s3Fig. 6. We cut P 2 D(c, 2R′ ) \ P 1 into 6 regions by bisectors of2 shown in Figure 4. Fortriangle T . In this figure we consider the area P232 , the assignment of s and s satisfies U (s , s , w) 5.5U .any w P23232 3We partition P 2 into 6 equal parts using the bisectors of triangle2T (See Figure 4). Suppose w lies in region: P23. Let m13 be themiddle point of [s1 s3 ], and w′ and m′13 be the intersection points of the boundary of D(c, 2R′ ) with s2 w and s2 m13 , respectively. Forclarity, we use the same notation as in Figure 6, i.e. α s2 ws3 ,2β s2 w′ s3 , γ ws3 w′ and δ s1 s3 w′ . For any w P23,ππfollowing inequalities hold: (i) β 3 , (ii) 0 γ δ, (iii) 6 δ π3 , (iv) α β γ. Finally, using (i)–(iv), we can bound α s2 ws3 : π3 s2 ws3 2π. The distances d(s2 , w) and d(s3 , w)3are upper bounded by: d(s2 , w) d(s2 , m′13 ) 4R′ , d(s3 , w) d(s3 , m′13 ) 2R′ .8R′ 2Hence, U (s2 , s3 , w) sin 3.6659U 5.5U .π/33Case (w P ):Again, we partition P 3 into 6 equal regions using bisectors of3triangle T (See Figure 4). For any point w inside P13, we assign′cameras s1 and s3 . Let us say that w is the intersection point of the boundary of D(c, 2R′ ) with c w. Similarly, suppose that w′′ and s′′3 are intersection points of the boundary of D(c, 2R) with c w and c s3 , respectively. To obtain a bound on the uncertainty, we first establish a lower bound on sin( s1 ws3 ) sin (Angle (r, θ)), followedby an upper bound on the product d(s1 , w)d(s3 , w) M ult(r, θ).Finally, we show that both bounds are reached at the same point:w s′′3 .For the remaining part of the proof, we will use polar coordinatesas shown in Figure 7. We define uncertainty function U ncert(r, θ)in polar coordinates as follows: M ult(r,θ)sin(Angle(r,θ))M ult(r,θ) Angle(r,θ) qU ncert(r,θ)(r2 4rR′ sin θ 4R′2 )(r2 4rR′ cos(θ π6 ) 4R′ 2 )!„«2R′ r cos(θ π )6π arctan 2R′ r sin θ arctan3r cos θπr sin(θ )63where for all w P13, π/6 θ π/6 and 2R′ r 2R.3First, we show that for any w P13, M ult(r, θ) M ult(2R, π/6), then we show sin (Angle(r, θ)) sin (Angle(2R, π/6)) where (2R, π/6) corresponds to s′′3 .By Euclid’s exterior angle theorem (in any triangle the angleopposite the greater side is greater), we have d(s1 , w) d(s1 , w′′ )and d(s3 , w) d(s3 , w′′ ). Therefore, M ult(r, θ) M ult(2R, θ).By the extreme value theorem: M ult(2R, π/6) M ult(2R, θ) 3M ult(2R, π/6). Hence, for any w P13, M ult(r, θ) M ult(2R, π/6) holds.The angle s1 ws3 is always between s1 w′ s3 and s1 w′′ s3 where s1 w′ s3 2π/3. Therefore, sin( s1 ws3 )is lower bounded by min(sin( s1 w′′ s3 ), sin(2π/3)), i.e.

SUBMITTED TO IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING5yperformance guarantee of placeSensors, at the expense of increasingthe number of cameras by a factor k. The interested reader can finddifferent values of r(k) in [15].s1w′wV. C ONCLUSIONw′′RθrxR′s2s3s′′3In this paper, we introduced a novel sensor placement problemwhere pairs of sensors are used to obtain estimates about a target’slocation. We presented a general solution based on integer linearprogramming and an approximation algorithm for the special case ofbearing-only localization in the absence of obstacles. We are currentlyworking on extending the approximation guarantees to more complexenvironments. Preliminary results can be found in [16].R EFERENCESFig. 7.In this figure, we represent w in polar coordinates (r, θ).2 (See Figure 4), sin( s ws ) sin( s s′′ s ) andFor all w P13131 3 3d(s1 , w)d(s3 , w) d(s1 , s3 ′′ )d(s3 , s3 ′′ ). Hence, U (s2 , s3 , w) 5.5U .[1] V. Isler, “Placement and distributed deployment of sensorteams for triangulation based localization,” in Proc. IEEE Int.Conf. on Robotics and Automation, 2006. [Online]. Available:http://www.cs.rpi.edu/ isler/new/pub/pubs/isler06icra.pdf[2] O. Tekdas and V. Isler, “Sensor placement for triangulation basedsin (Angle(r, θ)) min (sin (Angle(2R, θ)) , sin(2π/3)). Thelocalization,” in Proc. IEEE Int. Conf. on Robotics and Automation,2007.function Angle(2R, θ) has its local minima and maxima at[3] A. Smith, H. Balakrishnan, M. Goraczko, and N. Priyantha, “Trackingθ π/6 and θ π/6, respectively and it is increasing in itsmoving devices with the cricket location system,” in MobiSys ’04:domain. This can be shown by investigating the domain and roots ofProceedings of the 2nd international conference on Mobile systems,the firstθ). Therefore,sin (Angle(r,θ)) applications, and services. New York, NY, USA: ACM Press, 2004, derivative of Angle(2R, pp. 190–202.min min sin Angle(2R, π6 ) , sin Angle(2R, π6 ) , sin( 2π) 3 [4] A. Nasipuri and R. el Najjar, “Experimental evaluation of an angle basedsin Angle(2R, π6 ) .indoor localization system,” in 4th International Symposium on ModelingM ult(2R, π/6)Finally, U (s2 , s3 , w) sin(Angle(2R, π/6)) 5.4989U and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006, pp.5.5U .1–9.[5] I. Rekleitis, D. Meger, and G. Dudek, “Simultaneous planning, loIn conclusion, placeSensors guarantees an uncertainty for all casescalization, and mapping in a camera sensor network,” Robotics andthat is not greater than 5.5U , i.e. U (W, S) 5.5U .Autonomous Systems, vol. 54, no. 11, pp. 921–932, November 2006.[6] S. N. Sinha, M. Pollefeys, and L. McMillan, “Camera network calibraRemark 1: We believe that the placement of the three sensorstion from dynamic silhouettes,” cvpr, vol. 01, pp. 195–202, 2004.[7] D. Devarajan, R. J. Radke, and H. Chung, “Distributed metric calibrationgiven in Algorithm placeSensors is optimal. To verify this, we numerof ad hoc camera networks,” ACM Trans. Sen. Netw., vol. 2, no. 3, pp.ically computed the error in localization as a function of the radius of380–403, 2006.the circle circumscribing the equilateral triangle formed by the three[8] A. Kelly, “Precision dilution in mobile robot position estimation,” insensors. The minimum value was achieved at radiusIntelligent Autonomous Systems, Amsterdam, Holland, 2003.p 1.25 which is[9] T. F. Gonzales, “Clustering to minimize the maximum interclustervery close to the radius used in the algorithm (2 3 1/4 1.2599).distance,” Theoretical Comput. Sci., no. 38, pp. 293–306, 1985.The small difference is due to discretization. To prove optimality, itremains to be shown that an optimal placement is symmetric around [10] J. Bar-Ilan and D. Peleg, “Approximation algorithms for selectingnetwork centers,” in Proc. 2nd Workshop on Algorithms and Datathe center. We believe that this claim is true. However we do notStructures, 1991, pp. 343–354.have a proof of this statement.[11] J. Spletzer and C. Taylor, “Dynamic sensor planning and control foroptimally tracking targets,” International Journal of Robotics Research,As a comparison, we ran the ILP program for the case wherevol. 22, no. 1, pp. 7–20, 2003.the environment is a disk of radius two. Recall that the ILP takes[12] S. Aranda, S. Martı́nez, and F. Bullo, “On optimal sensor placement anda threshold as input, and computes a placement with the smallestmotion coordination for target tracking,” in International Conference onnumber of sensors to achieve this threshold. It turns out that theRobotics and Automation, Barcelona, Spain, Apr. 2005.precise threshold value is critical. The value given by the argument [13] A. Efrat, J. S. B. Mitchell, and S. Har-Peled, “Approximation algorithms for two o

workspace is determined as follows: U(S,W) max w W min si,sj S U(si,sj,w) In other words, to establish the quality of a placement in a workspace, we take the largest uncertainty value over the entire workspace. To compute the uncertainty value for a specific location in the workspace, we find the best pair of sensors for that location.