# Sensor Placement

## 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.

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

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 | |

13 | Pratap Tokekar, Volkan IslerPolygon guarding with orientationComputational Geometry, 58: 97 - 109, 2016. |

2014 | |

12 | P. Tokekar, V. IslerPolygon Guarding with OrientationIn Proc. International Conference on Robotics and Automation, 2014. tech-report,.bib |

2013 | |

11 | P. Tokekar, V. IslerSensor Placement and Selection for Bearing Sensors with Bounded UncertaintyIn Proc. International Conference on Robotics and Automation, 2013. pdf,tech-report,.bib |

2010 | |

10 | O. Tekdas, V. IslerSensor Placement for Triangulation Based LocalizationIEEE Tran. Automation Science and Engineering, 7(3): 681--685, 2010. pdf,.bib |

2008 | |

9 | V. Isler, M. Magdon-IsmailSensor Selection Problem in Arbitrary DimensionsIEEE Tran. Automation Science and Engineering, 5(4): 651--660, 2008. pdf,.bib |

2007 | |

8 | O. Tekdas, V. IslerSensor Placement Algorithms for Triangulation Based LocalizationIn Proc. IEEE Int. Conf. on Robotics and Automation, 2007. pdf,.bib |

2006 | |

7 | V. Isler, R. BajcsyThe Sensor Selection Problem for Bounded Uncertainty Sensing ModelsIEEE Tran. Automation Science and Engineering, 4(3): 372--381, 2006. pdf,.bib |

6 | V. IslerPlacement and Distributed Deployment of Sensor Teams for Triangulation Based LocalizationIn Proc. IEEE Int. Conf. on Robotics and Automation, 2006. pdf,.bib |

2005 | |

5 | V. Isler, S. Khanna, J. Spletzer, C.J. TaylorTarget Tracking with Distributed Sensors: The Focus of Attention ProblemComputer Vision and Image Understanding Journal(1-2): 225--247, 2005. pdf,.bib |

4 | V. Isler, R. BajcsyThe Sensor Selection Problem for Bounded Uncertainty Sensing ModelsIn Information Processing in Sensor Networks (IPSN), 2005. pdf,.bib |

2004 | |

3 | V. Isler, S. Kannan, K. Daniilidis, P.ValtrVC-Dimension of Exterior VisibilityIEEE Trans. Pattern Analysis and Machine Intelligence, 26(5): 667--671, 2004. pdf,.bib |

2 | V. Isler, K. Daniilidis, S. KannanSampling Based Sensor-Network DeploymentIn IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004. pdf,.bib |

2003 | |

1 | V. Isler, J. Spletzer, S. Khanna, C.J. TaylorTarget Tracking with Distributed Sensors: The Focus of Attention ProblemIn IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. pdf,.bib |