Sensor Placement
A sensor network is a network of small, cheap devices equipped with sensing, communication and computation capabilities. With concurrent advances in robotics, embedded sensing, computation and communication technologies, sensor networks are becoming increasingly popular in automation applications such as surveillance, inventory control and traffic management.
The presence of a sensor-network in a robot's workspace can provide robust, scalable solutions to a number of fundamental robotics problems. As an example, consider the localization problem whose solution is a prerequisite for many robotics applications. 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 camera-network in such an environment and the robots can query these sensors for localization -- instead of relying on on-board sensors and customized applications. Other robotics problems which can benefit from the existence of a sensor network include navigation, search and surveillance.
In the present work, we address 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. We focus 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 mathematical programming 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.
Poster
Back to RSN webpage