Title :
Sensor Placement for Triangulation-Based Localization
Author :
Tekdas, Onur ; Isler, Volkan
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of Minnesota, Minneapolis, MN, USA
fDate :
7/1/2010 12:00:00 AM
Abstract :
Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation-based state estimation, where measurements from two sensors must be combined for an estimate. This problem is NP-hard in its most general from. For the general version, we present a solution framework based on integer linear programming and demonstrate its application in a fire-tower placement task. Next, we study the special case of bearing-only localization and present an approximation algorithm with a constant factor performance guarantee.
Keywords :
approximation theory; computational complexity; integer programming; linear programming; robots; sensors; NP-hard problem; approximation algorithm; bearing-only localization; constant factor performance guarantee; integer linear programming; localization uncertainty; sensor placement; triangulation-based localization; triangulation-based state estimation; Approximation algorithms; localization; sensor network deployment;
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
DOI :
10.1109/TASE.2009.2037135