Determination of minimum number of sensors and their locations for an automated facility: An algorithmic approach

The authors present an algorithmic approach to determine the minimum number of sensors and their placements required to monitor the workspace. For a 2-D workspace this involves finding the minimal sensor placement to ‘see’ the edges of all the objects (polygons) in the workspace and the boundary of the workspace. The problem belongs to a class of geometric optimization problems called the art gallery problems and is a variant of the minimum guard cover problem (MGCP). Utilizing the concepts of visibility of a point, the authors characterize the problem of strong visibility of an edge in a polygon with holes. An efficient algorithm is presented which runs in time linear to the number of edges present to obtain the strong visibility polygon for an edge. The visibility polygons of all the edges give us a set of points which is sufficient to include the optimal placement of sensors. A set covering problem is then solved on this set of points to extract a minimal set of points that provides visibility of all the desired edges. The set covering problem is NP-complete and makes the overall approach NP-complete (the NMCP is also known to be NP-complete). However, the finite set of sufficient location points and efficient heuristics for the set covering problem make this method a viable one.