The problem of sensor placement for triangulation-based localisation

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).