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

Ram Pandit, Placid M. Ferreira

Research output: Contribution to journalArticlepeer-review

Abstract

We present an algorithmic approach to determine the minimum number of sensors and their placements required to monitor the workplace. 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, we 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 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 MGCP 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.

Original languageEnglish (US)
Pages (from-to)231-239
Number of pages9
JournalEuropean Journal of Operational Research
Volume63
Issue number2
DOIs
StatePublished - Dec 10 1992

Keywords

  • Facilities
  • combinatorial analysis
  • location
  • optimization
  • planning

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Determination of minimum number of sensors and their locations for an automated facility: An algorithmic approach'. Together they form a unique fingerprint.

Cite this