Sensor Placement

From RSN
Jump to: navigation, search

Motivation

Sensor network technology offers a scalable solution for localization of heterogeneous, independent robot teams operating in a large and complex environment: We can deploy a calibrated sensor-network in such an environment and the robots can query these sensors for localization -- instead of relying on on-board sensors and customized applications. A good placement scheme can improve the performance of sensor networks in applications such as intruder detection in surveillance, robot navigation using exteroceptive measurements, and providing location information to mobile devices for location-aware computing.

Most sensors employed for localization have a strong geometric structure associated with their sensing model. This structure plays a critical role in how information from multiple sensors can be combined. Our goal is to understand this geometric structure and design placement algorithms with strong theoretical performance guarantees that exploit this structure.

Contributions

We have primarily focused on designing placement schemes for bearing sensors. Bearing sensors are commonly used in robotic and networked sensor systems: monocular cameras, microphone/acoustic arrays, directional radio antennas, passive infrared receivers, etc., all measure bearing towards a target. We have studied the problem of placing sensors so that when a robot queries sensors to estimate its own position, the uncertainty in the position estimation is small. In general, there is a trade-off between the number of sensors and the uncertainty in the estimation.

Best-case and worst-case target estimate for the same sensors and target positions. We consider an adversarial model in [11]: an adversary chooses the true target location within a square environment, and chooses noisy measurements to maximize uncertainty and the goal is to place sensors to minimize this worst-case uncertainty.

In [10], we focused on triangulation-based localization where two sensors are needed for estimating the position of the robot. We make three main contributions:

  • First, we show, via a simple reduction, that the general sensor placement problem (where the uncertainty measure is arbitrary) is NP-Complete.
  • Second, we present an approximation algorithm for a geometric uncertainty model that deviates from the optimal solution only by a constant factor both in the number of cameras used and the uncertainty in localization.
  • Finally, we present a general framework based on integer linear programming (ILP) which, in practice, can be used to solve the placement problem for arbitrary uncertainty models while incorporating sensing constraints such as occlusions. We demonstrate the practical feasibility of this approach through simulations.

In [11], we focused on localization where measurements from all deployed sensors are used for estimation (and not just two sensors as is the case for triangulation-based placement). We considered bearing sensors with unknown but bounded noise. Bounded noise models provide a useful alternative to probabilistic models especially when a precise device model is not available (perhaps due to the difficulty of calibration or changing device parameters).

  • Our main result is a constant-factor approximation: We show by placing sensors on a triangular-grid, we achieve at most 5.7 times the uncertainty of an optimal algorithm using at most 9 times as many sensors.
  • 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.

Simulations

SensorPlacement.jpg

We demonstrate the utility of the ILP framework presented in [10] with an example. Imagine the task of placing fire-towers in a forest which are used for localizing events such as forest fires. The ILP gives a placement of 32 fire-towers achieving small localization uncertainty (shown in above figure).

Related Publications

2016
13Pratap Tokekar, Volkan Isler
Polygon guarding with orientation
Computational Geometry, 58: 97 - 109, 2016.
2014
12P. Tokekar, V. Isler
Polygon Guarding with Orientation
In Proc. International Conference on Robotics and Automation, 2014.
tech-report,.bib
2013
11P. Tokekar, V. Isler
Sensor Placement and Selection for Bearing Sensors with Bounded Uncertainty
In Proc. International Conference on Robotics and Automation, 2013.
pdf,tech-report,.bib
2010
10O. Tekdas, V. Isler
Sensor Placement for Triangulation Based Localization
IEEE Tran. Automation Science and Engineering, 7(3): 681--685, 2010.
pdf,.bib
2008
9V. Isler, M. Magdon-Ismail
Sensor Selection Problem in Arbitrary Dimensions
IEEE Tran. Automation Science and Engineering, 5(4): 651--660, 2008.
pdf,.bib
2007
8O. Tekdas, V. Isler
Sensor Placement Algorithms for Triangulation Based Localization
In Proc. IEEE Int. Conf. on Robotics and Automation, 2007.
pdf,.bib
2006
7V. Isler, R. Bajcsy
The Sensor Selection Problem for Bounded Uncertainty Sensing Models
IEEE Tran. Automation Science and Engineering, 4(3): 372--381, 2006.
pdf,.bib
6V. Isler
Placement and Distributed Deployment of Sensor Teams for Triangulation Based Localization
In Proc. IEEE Int. Conf. on Robotics and Automation, 2006.
pdf,.bib
2005
5V. Isler, S. Khanna, J. Spletzer, C.J. Taylor
Target Tracking with Distributed Sensors: The Focus of Attention Problem
Computer Vision and Image Understanding Journal(1-2): 225--247, 2005.
pdf,.bib
4V. Isler, R. Bajcsy
The Sensor Selection Problem for Bounded Uncertainty Sensing Models
In Information Processing in Sensor Networks (IPSN), 2005.
pdf,.bib
2004
3V. Isler, S. Kannan, K. Daniilidis, P.Valtr
VC-Dimension of Exterior Visibility
IEEE Trans. Pattern Analysis and Machine Intelligence, 26(5): 667--671, 2004.
pdf,.bib
2V. Isler, K. Daniilidis, S. Kannan
Sampling Based Sensor-Network Deployment
In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004.
pdf,.bib
2003
1V. Isler, J. Spletzer, S. Khanna, C.J. Taylor
Target Tracking with Distributed Sensors: The Focus of Attention Problem
In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.
pdf,.bib