Optimal Deployment of Mobile Sensors for Target Tracking in 2D and 3D Spaces

Shiyu ZhaoBen M ChenTong H Lee

I.INTRODUCTION

FOR target tracking using mobile sensor networks,the placement of the sensors relative to the target can signi ficantly affect the tracking performance.What is the optimal sensor placement that can minimize target tracking uncertainty?This problem is of both theoretical and practical importance.

There are generally two kinds of mathematical formulations for optimal sensor placement problems in the literature:one is optimal control[1−3],and the other is parameter optimization[4−11].The optimal control formulation considers sensor placement and target tracking as a whole.The formulation is also referred to simultaneous localization and planning(SLAP)[2].As a comparison,the parameter optimization formulation only considers the sensor placement part and does not consider the target tracking part.It is assumed that an initial target estimate has already been obtained in other ways.Then the optimal sensor placement is determined based on this initial target estimate.In fact,the above two kinds of formulations lead to consistent results.For example,the work in[2]observed that when two sensors approach a target,the target information would be maximized when the angle subtended at the target by the two sensors is 90 deg.This observation actually has been analytically proved as an optimality condition based on the parameter optimization formulation in[4,6−7,13−14].It should be noted that analytical conclusions can be drawn based on the parameter optimization formulation,while only numerical results can be obtained from the optimal control formulation.Considering the analytical conclusions can provide us important insights into the effects of sensor placements on target tracking,we will adopt the parameter optimization formulation to study optimal sensor placement in this paper.

Although optimal sensor placement based on the parameter optimization formulation has been investigated extensively,most of the existing results are only applicable to 2D cases[4−8,10].Since many practical applications require 3D optimal sensor placements,the general results for 3D cases will be of great importance from the practical point of view.One main dif ficulty to analyze 3D optimal placements is that the complexity of the conventional objective function,the determinant of the Fisher information matrix(FIM),increases dramatically as the dimension increases from two to three.Motivated by that,a new objective function,which is analytically tractable in both 2D and 3D cases,has been proposed in[13].By employing recently developed frame theory,the work in[13]successfully proved the necessary and suf ficient conditions of optimal sensor placements in both 2D and 3D spaces.It is shown that the analytical results obtained based on the new objective function are consistent with the existing 2D results in the literature.Moreover,the work in[13]proposed a uni fied framework for analyzing the optimal placement problems of bearing-only,range-only and receivedsignal-strength sensor networks.

In addition to analytically determining optimal sensor placements,it is also practically important to study how to autonomously deploy the optimal placements.There are generally three approaches to autonomous optimal sensor deployment.1)One approach is to use the optimal control formulation mentioned above.2)The second approach is to develop numerical methods to solve the parameter optimization formulation.For example,by numerically maximizing the determinant of the FIM,sensor trajectory optimization algorithms can be obtained[3,9].Compared to the optimal control approach,the second one is easy to be designed and implemented,and various constraints of sensor trajectories can be easily included.3)The third approach is to design autonomous deployment algorithms based directly on analytical results of optimal sensor placement.For example,the work in[7]proposed a distributed motion coordination algorithm to autonomously deploy sensors for target tracking.Loosely speaking,that algorithm is designed based on the fact that a placement is optimal if range-only sensors are uniformly distributed around the target.However,one limitation of the approach used in[7]is that the uniformly distributed placement is merely a special case as pointed out by[13,Section 5.2].There are an in finite number of optimal placements that can optimize the objective function.These optimal placements may be more appropriate than the uniformly distributed one given certain initial placements and sensor trajectory constraints.More importantly,the uniformly distributed placement is optimal only if the sensors are equally weighted[13,Section 5.2].If some of the sensors can provide more accurate measurements than the others,the uniformly distributed one will no longer be optimal.With the above analysis,we will adopt the second numerical optimization approach to solve autonomous sensor deployment problems in this paper.

Based on the analytical results in[13],this work proposes a control strategy to autonomously deploy optimal placements of range-only sensors in 2D and 3D spaces.One main contribution of this work is that the control strategy can handle 3D autonomous deployment problems while the existing results are only applicable to 2D cases[1−3,7,9].The objective function to be minimized is composed of two terms:an inter-sensor potential and an external potential.The inter-sensor potential actually is the frame potential among the sensors[13];the sensor trajectory constraints are formulated as the external potential.A gradient control law is used to numerically to minimize the objective function such that an optimal placement can be achieved while the sensor trajectory constraints can be satis fied in the meantime.Since arti ficial potential approaches can handle various issues such as obstacle avoidance and collision avoidance among sensors,the proposed control strategy provides a flexible solution to practical autonomous optimal sensor deployment problems.In this paper,we further apply the control strategy to several speci fic scenarios.Simulation results verify the effectiveness of the proposed control strategy.It is also illustrated how the control strategy can improve target tracking performance.

II.OPTIMAL SENSOR PLACEMENT

Consider one target in Rdwhered=2 or 3.Suppose there aren(n≥d)range-only sensors.Following the existing work[4−7],we assume an initial target position estimatep∈Rdis available already.The optimal placement will be determined based onp.Denotesi∈Rdas the position of sensori(i∈{1,···,n}).The relative position of sensoriwith respect to the target isri=si−p.Thencan fully describe the sensor-target placement.The unit vector

represents the bearing of sensorirelative to the target,where‖·‖denotes the Euclidean norm of a vector or the Frobenius norm of a matrix.The above notations are illustrated by Fig.1.

Fig.1.A 3D sensor placement.

The measurement model of sensoriis expressed as

where

andmi∈R is the measurement corrupted by noisewi∈R.We assumewito be a zero-mean Gaussian noise with standard deviation asσi.By further assuming the measurement noises of different sensors are uncorrelated,the FIM given bynsensors is expressed as

wheredenotes the Jacobian ofhi(p)with respect top.We refer to[4,Section 3]for a detailed derivation of the FIM formula in(2).Substituting(1)into(2)yields

whereci=1/σi.Note we do not assume different sensors have the same noise level.Instead,σican be an arbitrary positive constant.

The conventional optimization criterion for optimal sensor placement is to maximize detF,which can be interpreted as maximizing the target information obtained by the sensors.This criterion,however,is not applicable to 3D cases as detFis not analytically tractable in 3D cases.Motivated by that,the work in[13]proposed a new objective function.Letbe the eigenvalues ofF.DenotePSince P,it is easy to obtainThe new objective function is defined as,whereId∈Rd×dis the identity matrix.Minimizingis to minimize the diversity of the eigenvalues ofF.A detailed discussion on the relationship between the new and the conventional objective functions is given in[13,Section 3.2].

A sensor placement is called optimal if it minimizes the objective function.By[13,Lemma 3.3],a placement is optimal if and only if it minimizes‖G‖2,where

By employing recently developed frame theory[15],necessary and suf ficient conditions of optimal placements that minimize‖G‖2are obtained as below[13].

Definition 1(Irregularity).For any positive non-increasing sequencewithc1≥···≥cn＞0,and any integerdsatisfying 1≤d≤n,denotek0as the smallest nonnegative integerkfor which

The integerk0is called the irregularity ofwith respect tod.Ifk0=0,the sequenceis called regular;otherwise,it is called irregular.

Theorem 1(Regular optimal placement).In Rdwithd=2 or 3,if the positive coef ficient sequenceis regular,then the objective function‖G‖2satisfies

The lower bound of‖G‖2is achieved if and only if

Theorem 2(Irregular optimal placement).In Rdwithd=2 or 3,if the positive coef ficient sequenceis irregular with irregularity ask0≥1,without loss of generality,can be assumed to be a non-increasing sequence,and then the objective function‖G‖2satisfies

The lower bound of‖G‖2is achieved if and only if

whereis an orthogonal set,andforms a regular optimal placement in the(d−k0)-dimensional orthogonal complement of.

Based on(5)and(7),optimal placements can be analytically constructed.The lower bounds of the objective function‖G‖2given in(4)and(6)are useful for numerically determining the optimality of a placement.The optimality error defined as the difference between‖G‖2and its lower bound can be used as a numerical indicator to evaluate the optimality of the placement.

RecallFgiven in(3)is a function of the sensor-target bearings,and irrelevant to the sensor-target ranges.The necessary and suf ficient conditions given in Theorems 1 and 2 are the conditions ofonly.As a result,the sensor-target ranges have no in fluence on the optimality of a placement.This feature is unique for rangeonly sensors.For other types of sensors such as bearing-only or received-signal-strength based sensors,the optimal placements will be in fluenced by sensor-target ranges[13].

III.AUTONOMOUSLY DEPLOY OPTIMAL SENSOR PLACEMENT

In practical applications,it is usually required to autonomously deploy an optimal sensor placement instead of manually deploying.In this section,we present a control strategy which can steer mobile sensors from an initial nonoptimal placement to an optimal one.In the meantime,the control strategy can ful fill given trajectory constraints of the mobile sensors.

A.Control Strategy

The mobile sensors usually cannot move freely in practical applications.For example,the trajectory of each sensor may be constrained on the boundary of a set in Rd.In order to autonomously deploy an optimal sensor placement,we need to solve two problems:1)minimize the objective function‖G‖2,and in the meantime 2)fulfill the trajectory constraint of each mobile sensor.Hence we define two artificial potentials.First,defineVI=‖G‖2as the inter-sensor potential.The placement is optimal if and only ifVIis minimized.Second,defineVEas the external potential corresponding to the sensor trajectory constraints.The sensor trajectory constraints are ful filled if and only ifVE=0.By combining the two potentials,we have the total potential as

wherekI,kE＞0.The gradient control law for sensoriis designed as

where▽sidenotes the gradient with respect tosi.The target is assumed to be stationary.Hence we have▽siVI=▽riVIasri=si−p.

B.Inter-sensor Force▽siVI

RecallandGT=G.Then the differential ofVIis

Furthermore,fromgi=ri/‖ri‖we have

wherePi=Id−gigTi∈Rd×dis an orthogonal projection matrix satisfyingandSubstituting(10)into(9)yields

Remark 1.The implementation of(11)requires all-toall communications among the sensors due to the termG.However,it is possible to implement(11)in a distributed way.To do that,each sensor needs to maintain an estimateofG,andshould converge toGgiven certain underlying graph.The distributed estimation ofGactually is an average consensus problem which has been investigated extensively(see,for example,[16−18]).

C.External Force▽siVE

The external potentialVEis chosen according to practical application requirements.Here we use two specific scenarios,one of which is 2D and the other is 3D,to demonstrate how control strategy(8)can be applied to practical problems.

1)A 2D scenario

Suppose the sensors can only move on an ellipse,while the stationary target is located arbitrarily inside the ellipse(see Fig.2).The position of sensorimust satisfy

wheres0∈R2is the center of the ellipse andQ=diag{1/a2,1/b2}∈R2×2witha＞0 andb＞0 as the lengths of the two semi-axes,respectively.According to the constraint,we chooseVEas

Fig.2.An illustration of the 2D scenario where all mobile sensors move on an ellipse.

Then it is straightforward to obtain

The implementation of(13)can be distributed because it only requires the information of sensori.The parameters of the ellipse such asQands0should be also known by sensori.

2)A 3D scenario

We now consider a 3D scenario that can be applied to cooperative air and ground surveillance[12,19].Suppose there are multiple unmanned aerial vehicles(UAVs)and unmanned ground vehicles(UGVs).Each vehicle is equipped with a range-only sensor that can measure the range to the target.The UAVs fly at fixed altitudes and the UGVs move on the ground with altitude as zero(see Fig.3).Denoteℓias the altitude of vehiclei.Then the external potentialVEcan be chosen as

wheree3=[0,0,1]T∈R3.Clearly,all the altitude constraints are satis fied if and only ifVE=0.It is straightforward to obtain

Fig.3.An illustration of the 3D scenario where each sensor moves at a fixed altitude.

D.Compatibility of VIand VE

The proposed gradient control law(8)guarantees that the gradientfor alliwill converge to zero.However,does not imply.To have that implication,the external potentialVEand the inter-sensor potentialVIshould becompatiblewith each other.By compatibility,we meanfor alliif only iffor alli.IfVEis not compatible withVI,it is possible thatwhileand.

We next proveis compatible withVEgiven in(12)or(14).To do that,we will showin(11)is impossible to be parallel toin(13)or(15).Firstly consider▽siVIin(11).Since,we have null(Pi)=span{gi}and hencePiri=0.As a result,

which means.Secondly,consider▽siVEgiven in(13)and(15).

1)In the 2D scenario,vectoris the normal vector of the ellipse at pointsi.Geometrically,it is clear thatis impossible to be orthogonal torifor anypinside the ellipse and anysion the ellipse.As a result,is not parallel to,and henceif and only iffor alli.

2)In the 3D scenario,vectoris the normal vector of the horizontal planes.DefineI={1,···,n},I＞0={i∈I:ℓi＞0}andI=0={i∈I:ℓi=0}.Geometrically,it is clear that ifℓi＞0,thenis impossible to be orthogonal tori.Henceis not parallel to▽siVIfor alli∈I＞0.As a result,for alli∈I＞0if and only iffor alli∈I＞0.Since the inter-sensor forces are mutual,if▽siVI=0 for all,then we haveP.Furthermore,sincerifor alli∈I=0is located in the plane withℓi=0,we have thatis within the plane and cannot be parallel to.Thusfor alli∈I=0if and only iffor all.Therefore,for alli∈Iif and only ififor alli∈I.

In fact,if the sensors are constrained on the smooth boundary of an arbitrary convex set in Rdand the target is located inside the convex set,the norm vectoris impossible to be parallel to.Hence the correspondingVEwill always be compatible with.We only consider the case that sensors are constrained on the boundary of a set in this paper.But more complicated issues such as obstacle avoidance and collision avoidance among sensors could also be solved by introducing more external potentials.At last,it should be noted that the compatibility ofVIandVEdoes not guarantee that the final converged placement is optimal.That is becausefor alliis only necessary but not sufficient for a placement to be optimal.This point has been discussed in[13].

IV .SIMULATIONS

We next present simulation results to verify the proposed control strategy for the 2D and 3D scenarios.We first consider two scenarios with static targets,then we consider a scenario with a dynamic target.It is assumed that the sensor networks have all-to-all communications.

A.Autonomous Sensor Deployment for Static Targets

1)2D scenario:In the 2D scenario,all sensors are constrained on an ellipse while the target is located inside the ellipse.The external forceis given in(13).The standard deviations of the sensor noises are assumed to be one,i.e.,σi=1 for alli.Note the final optimal placement is determined only by the relative values ofbut not the absolute values.As shown in Fig.4,given appropriate initial placements,the control strategy can steer sensors to optimal placements while ensuring the sensor trajectory constraints ful filled.The optimality error shown in Fig.4 refers to the difference between the objective function‖G‖2and its lower bound given in(4)or(6).As can be seen,the control strategy can ef ficiently reduce the optimality errors to zero.

Numerically,it is clear that the final placements in Fig.4 are optimal because the optimality errors converge to zero.We next analytically determine the optimality of the final placements based on the analytical results presented in[13].As shown in Fig.4(a),the angle subtended by the two sensors in the final placement is 90 deg.Hence we haveg1⊥g2in the final placement.Then the final placement is optimal by[13,Theorem 4.4].As shown in Fig.4(b),the sensors are steered to equally spaced angular positions around the target.The angle subtended by any two sensors in the final placement is 120 deg.This kind of equally spaced angular placements are optimal as concluded in[13,Section 5.2].At the first glance,it is intuitively unclear whether the final placement in Fig.4(c)is optimal.The final placement of the four sensors can be viewed as a combination of two sub-placements:the sub-placement of sensors 1 and 3,and the one of sensors 2 and 4.Note the angle subtended by sensors 1 and 3 and the one by sensors 2 and 4 are both 90 deg in the final placement.That meansg1⊥g3andg2⊥g4,and the two sub-placements are(regular)optimal,respectively.By[13,Theorem 5.6],the final placement in Fig.4(c)is optimal.

2)3D scenario:In the 3D scenario,it is assumed that each sensor is carried by a UAV or UGV that moves at a fixed altitude.The standard deviations of the sensor noises are assumed to be one,i.e.,σi=1 for alli.Simulation results withn=3 and 4 are respectively shown in Figs.5(a)and 5(b).As shown in Fig.5,the optimality errors in the two cases are both reduced to zero efficiently.

In Fig.5(a),the angle subtended by any two sensors is 90 deg in the final placement.That meansg1,g2,andg3are mutually orthogonal in the final placement.By[13,Theorem 4.4],the final placement is optimal.The final optimal placement shown in Fig.5(b)actually is the one given in[13,Fig.7(c)].In both cases ofn=3 andn=4,the final converged placements are optimal and the sensor position constraints are simultaneously fulfilled.

Fig.4.Sensor trajectories and optimality errors for the 2D scenario.

Fig.5.Sensor trajectories and optimality errors for the 3D scenario.

B.Autonomous Sensor Deployment for Dynamic Targets

Although it is assumed that the target is stationary,the proposed control strategy can also be applied to tracking of a dynamic target in practice.We next consider a 3D cooperative target tracking scenario.Suppose there are three UAVs flying at the same altitude.Each UAV carries a range-only sensor to measure the distance to the ground target.In the simulation,the target moves on a non- flat ground.The 3D maneuvering motion of the target is given as

See Fig.6 for the target trajectory.

In this cooperative target tracking scenario,all UAVs need to share their range measurements to estimate the target position,and move to form an optimal placement in the meantime.The autonomous optimal sensor deployment algorithm is summarized as Algorithm 1.

Algorithm 1.Autonomous optimal sensor deployment for target tracking

Step 1.Obtain an initial estimate of the target position(0).

Step 2.At timet,estimate the target position(t)using a centralized extended Kalman filter(EKF).The EKF is established based on the following process and measurement models:

Fig.6.Autonomous optimal sensor deployment to track a dynamic target(The target moves on the non- flat ground and the three UAVs fly at a fixed altitude.)

wheremi∈R is the measurement of sensori,andv∈R3andwi∈R for alliare white Gaussian noises.

Step 3.Based on(t),autonomously deploy the optimal sensor placement using the control strategy(8).

Step 4.At timet+1,go to Step 2.

The real initial position of the target isp(0)=[0,0,0]T,while the initial target estimate for the EKF is(0)=[−4,5,3]T.The standard deviation of noisewiis set as three meters.By Algorithm 1,the trajectories of the three moving sensors are obtained as shown in Fig.7.The behaviors of the three sensors in Fig.7 can be explained as the following:the three sensors attempt to form a placement where each angle subtended at the target by any two sensors is 90 deg.In order to illustrate how optimal placements can improve the target tracking performance,we compare the target estimation results in the cases of moving and stationary sensors.In the case of stationary sensors,the three sensors stay statically at the initial placement shown in Fig.7.The initial placement is obviously not optimal.The target estimation results in the two cases are shown in Fig.7.As can be seen,the target can be tracked accurately when the sensors are steered to maintain an optimal placement,while the tracking performance is worse when the sensors are stationary.Note the parameters of the EKF are the same in the two cases.

Fig.7.Target position estimation results by stationary and moving sensors.)

V.CONCLUSIONS

Based on the results in[13],this work presented a flexible control strategy for autonomously deploying optimal placements of range-only sensors for target tracking.Two practical scenarios were considered and solved using the proposed control strategy.The control strategy was also applied to a 3D cooperative target tracking scenario.It was shown that the target tracking performance can be improved when sensors are steered to maintain an optimal placement.

There are several directions for future research.First,this paper only considers the cases of all-to-all communications.Distributed autonomous deployment,distributed target tracking and the integration of them need to be investigated in the future.Second,this paper only considers homogenous sensor networks but not heterogeneous cases[20].Cooperative target tracking using heterogeneous sensor networks is a practically important topic for future research.

REFERENCES

[1]Ousingsawat J,Campbell M E.Optimal cooperative reconnaissance using multiple vehicles.Journal of Guidance,Control,and Dynamics,2007,30(1):122−132

[2]Sinclair A J,Prazenica R J,Jeffcoat D E.Optimal and feedback path planning for cooperative attack.Journal of Guidance,Control,and Dynamics,2008,31(6):1708−1715

[3]Oshman Y,Davidson P.Optimization of observer trajectories for bearings-only target localization.IEEE Transactions on Aerospace and Electronic Systems,1999,35(3):892−902

[4]Bishop A N,Fidan B,Anderson B D O,Do∨gganc¸ay K,Pathirana P N.Optimality analysis of sensor-target localization geometries.Automatica,2010,46(3):479−492

[5]Bishop A N,Jensfelt P.An optimality analysis of sensor-target geometries for signal strength based localization.In:Proceedings of the 5th International Conference on Intelligent Sensors,Sensor Networks and Information Processing.Melbourne,Australia:IEEE,2009.127−132

[6]Do∨ganc¸ay K,Hmam H.Optimal angular sensor separation for AOA localization.Signal Processing,2008,88(5):1248−1260

[7]Mart´ınez S,Bullo F.Optimal sensor placement and motion coordination for target tracking.Automatica,2006,42(4):661−668

[8]Zhang H.Two-dimensional optimal sensor placement.IEEE Transactions on Systems,Man,and Cybernetics,1995,25(5):781−792

[9]Do∨ganc¸ay K.Online optimization of receiver trajectories for scanbased emitter localization.IEEE Transactions on Aerospace and Electronic Systems,2007,43(3):1117−1125

[10]Isaacs J T,Klein D J,Hespanha J P.Optimal sensor placement for time difference of arrival localization.In:Proceedings of the 48th Conference on Decision and Control,2009 Held Jointly with the 2009 28th Chinese Control Conference.Shanghai,China:IEEE,2009.7878−7884

[11]Moreno-Salinas D,Pascoal A M,Aranda J.Optimal sensor placement for underwater positioning with uncertainty in the target location.In:Proceedings of the 2011 IEEE International Conference on Robotics and Automation.Shanghai,China:IEEE,2011.2308−2314

[12]Grocholsky B,Keller J,Kumar V,Pappas G.Cooperative air and ground surveillance.IEEE Robotics&Automation Magazine,2006,13(3):16−25

[13]Zhao S,Chen B M,Lee T H.Optimal sensor placement for target localisation and tracking in 2D and 3D.International Journal of Control,2013,86(10):1687−1704

[14]Zhao S,Chen B M,Lee T H.Optimal placement of bearing-only sensors for target localization.In:Proceedings of the 2012 American Control Conference.Montreal,Canada:IEEE,2012.5108−5113

[15]Casazza P G,Fickus M,Kova∨cevi´c J,Leon M T,Tremain J C.A physical interpretation of tight frames.In:Harmonic Analysis and Applications,Applied and Numerical Harmonic Analysis.Cambridge,MA:Birkh¨auser Boston,2006.51−76

[16]Olfati-Saber R,Murray R M.Consensus problems in networks of agents with switching topology and time-delays.IEEE Transactions on Automatic Control,2004,49(9):1520−1533

[17]Lin P,Jia Y M.Average consensus in networks of multi-agents with both switching topology and coupling time-delay.Physica A:Statistical Mechanics and Its Applications,2008,387(1):303−313

[18]Ren W,Cao Y C.Distributed Coordination of Multi-agent Networks.New York:Springer,2011

[19]Hu J W,Xu J,Xie L H.Cooperative search and exploration in robotic networks.Unmanned Systems,2013,1(1):121−142

[20]Meng W,Xie L H,Xiao W D.Optimality analysis of sensor-source geometries in heterogeneous sensor networks.IEEE Transactions on Wireless Communications,2013,12(4):1958−1967