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.
| Original language | English (US) |
|---|---|
| Article number | 5427001 |
| Pages (from-to) | 681-685 |
| Number of pages | 5 |
| Journal | IEEE Transactions on Automation Science and Engineering |
| Volume | 7 |
| Issue number | 3 |
| DOIs | |
| State | Published - 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:
Copyright 2010 Elsevier B.V., All rights reserved.
Keywords
- Approximation algorithms
- localization
- sensor network deployment