TY - GEN
T1 - Sensor placement and selection for bearing sensors with bounded uncertainty
AU - Tokekar, Pratap
AU - Isler, Volkan
PY - 2013
Y1 - 2013
N2 - We study the problem of placing bearing sensors so as to estimate the location of a target in a square environment. We consider sensors with unknown but bounded noise: the true location of the target is guaranteed to be in a 2α-wedge around the measurement, where α is the maximum noise. The quality of the placement is given by the area or diameter of the intersection of measurements from all sensors in the worst-case (i.e. regardless of the target's location). We study the bi-criteria optimization problem of placing a small number of sensors while guaranteeing a worst-case bound on the uncertainty. Our main result is a constant-factor approximation: We show that in general when α ≤ Π/4, at most 9n* sensors placed on a triangular grid has diameter and area uncertainty of at most 5.88U D* and 7.76UA* respectively, where n*,UD* and UA* are the number of sensors, diameter and area uncertainty of an optimal algorithm. In obtaining these results, we present some structural properties which may be of independent interest. We also show that in the triangular grid placement, only a constant number of sensors need to be activated to achieve the desired uncertainty, a property that can be used for designing energy/bandwidth efficient sensor selection schemes.
AB - We study the problem of placing bearing sensors so as to estimate the location of a target in a square environment. We consider sensors with unknown but bounded noise: the true location of the target is guaranteed to be in a 2α-wedge around the measurement, where α is the maximum noise. The quality of the placement is given by the area or diameter of the intersection of measurements from all sensors in the worst-case (i.e. regardless of the target's location). We study the bi-criteria optimization problem of placing a small number of sensors while guaranteeing a worst-case bound on the uncertainty. Our main result is a constant-factor approximation: We show that in general when α ≤ Π/4, at most 9n* sensors placed on a triangular grid has diameter and area uncertainty of at most 5.88U D* and 7.76UA* respectively, where n*,UD* and UA* are the number of sensors, diameter and area uncertainty of an optimal algorithm. In obtaining these results, we present some structural properties which may be of independent interest. We also show that in the triangular grid placement, only a constant number of sensors need to be activated to achieve the desired uncertainty, a property that can be used for designing energy/bandwidth efficient sensor selection schemes.
UR - http://www.scopus.com/inward/record.url?scp=84887297724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887297724&partnerID=8YFLogxK
U2 - 10.1109/ICRA.2013.6630920
DO - 10.1109/ICRA.2013.6630920
M3 - Conference contribution
AN - SCOPUS:84887297724
SN - 9781467356411
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 2515
EP - 2520
BT - 2013 IEEE International Conference on Robotics and Automation, ICRA 2013
T2 - 2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Y2 - 6 May 2013 through 10 May 2013
ER -