Sensor placement for triangulation-based localization

Onur Tekdas, Volkan Isler

Research output: Contribution to journalArticlepeer-review

72 Scopus citations


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.

Original languageEnglish (US)
Article number5427001
Pages (from-to)681-685
Number of pages5
JournalIEEE Transactions on Automation Science and Engineering
Issue number3
StatePublished - Jul 2010

Bibliographical note

Funding Information:
Manuscript received April 06, 2009; revised September 13, 2009; accepted October 19, 2009. Date of publication March 08, 2010; date of current version July 02, 2010. This paper was recommended for publication by Associate Editor H. Tanner and Editor V. Kumar upon evaluation of the reviewers’ comments. This paper was presented in part at the IEEE International Conference on Robotics and Automation, 2006, and the IEEE International Conference on Robotics and Automation, 2007. This work is supported in part by the National Science Foundation (NSF) under Grant 0907658, 0917676 and Grant 0936710.

Copyright 2010 Elsevier B.V., All rights reserved.


  • Approximation algorithms
  • localization
  • sensor network deployment


Dive into the research topics of 'Sensor placement for triangulation-based localization'. Together they form a unique fingerprint.

Cite this