Title: The problem of sensor placement for triangulation-based localisation

Authors: Anna Gorbenko; Maxim Mornev; Vladimir Popov; Andrey Sheka

Addresses: Department of Intelligent Systems and Robotics, Ural State University, 620083 Ekaterinburg, Lenin st., 51, Russian Federation ' Department of Intelligent Systems and Robotics, Ural State University, 620083 Ekaterinburg, Lenin st., 51, Russian Federation ' Department of Intelligent Systems and Robotics, Ural State University, 620083 Ekaterinburg, Lenin st., 51, Russian Federation ' Department of Intelligent Systems and Robotics, Ural State University, 620083 Ekaterinburg, Lenin st., 51, Russian Federation

Abstract: Recent technological advances have facilitated the widespread use of sensor networks in many applications. In particular, deploying many sensors in a workspace provides a valuable alternative to on-board localisation for mobile robots. Coverage and placement problems for sensors which jointly estimate the states of targets received considerable attention recently. In this paper, we consider the problem of sensor placement for triangulation-based localisation. The problem is non-deterministic polynomial-time hard in its most general form. We present a reformulation of an existing integer linear programme for the problem where we transform the original to an equivalent integer linear programme with less number of variables. We consider an approach to solve the problem that is based on constructing a logical model for the problem. In particular, we give explicit polynomial reductions from the decision version of the problem to satisfiability problem (SAT) and 3-satisfiability problem (3SAT).

Keywords: sensor networks; robot localisation; triangulation-based localisation; sensor placement; integer linear programming; NP-hardness; logical models; satisfiability problem; GAs; genetic algorithms; local search algorithms; mobile robots.

DOI: 10.1504/IJAAC.2011.042855

International Journal of Automation and Control, 2011 Vol.5 No.3, pp.245 - 253

Received: 04 Jul 2011
Accepted: 06 Aug 2011
Published online: 17 Apr 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article