Minimax Sensor Location and
Bayesian Estimation of the Probability of Detection
NSF Award Number: DMI-0400140
Award Period: 3/2004 - 3/2008
Tom M. Cavalier
Enrique del Castillo
Industrial and Manufacturing Engineering
The Pennsylvania State University
310 Leonhard Building
University Park, Pennsylvania 16802 USA

Abstract:
This grant provided funding for the development of mathematical techniques for locating a finite number of sensors to detect an event in a given region. The objective in this sensor location problem is to minimize the maximum probability of non-detection where the underlying region consists of a line, a piecewise-linear curve, or a continuous planar region represented by a convex polyhedron. The problem has a multitude of applications, including the location of aircraft detection sensors, the placement of sentries along a border to detect enemy penetration, the detection of nuclear tests, and the detection of natural and hazardous man-made events.

Estimation of the probability of detection involves testing for complete spatial randomness. If events exhibit this property, then a uniform distribution may be appropriate. Otherwise, historical event data can be modeled as a spatial non-homogeneous Poisson process defined on the region. The mean rate of event occurrences can be estimated using a Bayesian approach that incorporates prior beliefs about the likelihood of events in different subregions within the region to be monitored.

The sensor location problem is a difficult nonlinear nonconvex programming problem even in the case of two sensors. Heuristic algorithms based on Voronoi polygons were developed in this study. The Voronoi algorithms can quickly generate high-quality solutions and were compared with differential evolution and a minimax solver.

Extensions have also been addressed in which line-of-sight sensors are considered and visibility is obstructed by an obstacle. In this case the objective is to locate sensors to maximize the visible area of the region, or equivalently to minimize the area of the shadow produced by the obstacle. A global optimal algorithm was developed for the case when a single convex obstacle is contained in a convex region. Other extensions are currently being studied.

Related Publications:

  • Cavalier, T.M., E. del Castillo, W.A. Conner, Minimax Sensor Location in the Plane, Proceedings of 2006 NSF DMII Grantees Conference, St. Louis, Missouri, July 2006.
  • Cavalier, T.M., W.A. Conner, E. del Castillo, S.I. Brown, A Heuristic Algorithm for Minimax Sensor Location in the Plane, European Journal of Operational Research 182:42-55 (2007).
  • Cavalier, T.M., W.A. Conner, E. del Castillo, Minimax Sensor Location to Monitor a Piecewise Linear Curve, Proceedings of 2008 NSF Engineering Research and Innovation Conference, Knoxville, Tennessee, January 2008.
  • Conner, W.A., T.M. Cavalier, E. del Castillo, Minimax Sensor Location to Monitor a Piecewise Linear Boundary, under review, International Journal of Operational Research (2008).
  • Conner, W.A., T.M. Cavalier, Maximizing Visibility in a Convex Polygon with a Convex Obstacle, under review, Computational Geometry, (2008).

    • Related Conference Presentations:

  • Conner, W.A., T.M. Cavalier, E. del Castillo, Solving the Minimax Sensor Location Problem: Towards the Largest Peak, INFORMS Conference, San Francisco, CA, November 2005.
  • Conner, W.A., T.M. Cavalier, E. del Castillo, Solving the Minimax Sensor Location Problem for Border Protection, INFORMS Conference, Pittsburgh, PA, November 2006.

    • Downloadable Software:
    A graphical user interface (GUI) was developed so that the planar sensor location algorithm [Cavalier, et al. EJOR 182:42-55 (2007)] can be run as a java applet. In order for this program to run on your computer, you will need to have Java Runtime Environment and Java 3D 1.5.1 API installed. After downloading and unzipping SensorPlot.zip, please read the README.txt file for detailed instructions.