A computationally efficient method has been developed to enable optimization of the placement of sensors for the purpose of diagnosis of a complex engineering system (e.g., an aircraft or spacecraft). The method can be used both in (1) designing a sensor system in which the number and positions of sensors are initially not known and must be determined and (2) adding sensors to a pre-existing system to increase the diagnostic capability.

The optimal-sensor-placement problem can be summarized as involving the following concepts, issues, and subproblems:

  • Degree of Diagnosability — This is a concept for characterizing the set of faults that can be discriminated by use of a given set of sensors.
  • Minimal Sensor Set — The idea is one of finding a minimal set of sensors that guarantees a specific degree of diagnosability.
  • Minimal-Cost Sensors — In a case in which different sensors are assigned with different costs, it is desired to choose the least costly set of sensors that affords a specific degree of diagnosability.

A System of Four Multiplier and Three Adder Gates serves as an example for illustrating the concept of ARRs and a signature matrix. In this example, there are three sensors that measure the variables f, g, and h. Each element of the matrix is 1 or 0 if the ARR listed in the row containing that element is or is not, respectively, affected by a fault in the gate listed in the column containing that element.
The development of the present method for solving the optimal-sensor-placement problem began with a rigorous mathematical description of the problem, leading to a very efficient algorithm for its solution. This method incorporates elements of a method, developed by the same innovators, for solving the diagnosis problem. Aspects of this diagnostic method and developments leading up to it were reported in several previous NASA Tech Briefs articles, the most recent and relevant being “High-Performance Algorithm for Solving the Diagnosis Problem” (NPO-41456), on the preceding page.

It was observed that in an algorithmic sense, the sensor-placement problem is an extension of the diagnosis problem and that both problems can be mapped to a special case of the 0/1 integer-programming (IP) problem. The only difference is that in the optimal-sensor-placement problem, the objective function, in the most general case, is no longer linear. However, the constraints are still linear and defined by a 0/1 matrix.

The solution of the sensor-placement problem starts with the formulation of a structural model of the system to be diagnosed. The structural analysis of the system and the potential information to be collected by each sensor are combined into a set of equations usually called the analytical redundant relations (ARRs). One also takes account of additional sensors and the ARRs of those sensors that, if used, would provide a desired degree of diagnosability. The information from all the ARRs is summarized in a signature matrix (see figure). Then the optimal-sensor-placement problem can be formulated as an IP problem involving the signature matrix.

In the present method, the IP problem is solved by a variant of the traditional branch-and-bound algorithm, which is among the algorithms heretofore commonly used to solve the IP problem. Briefly, the traditional branch-and-bound algorithm includes finding lower and upper bounds on solutions, successively dividing (branching) the IP problem into subproblems on the basis of the bounds, and eliminating any subproblem, the lower bound of which exceeds the upper bound of another subproblem. The branching, bounding, and elimination are repeated until all subproblems are eliminated. The present new variant of the branch-and-bound algorithm is similar to the one used in the aforementioned method for solving the diagnosis problem and offers orders-of-magnitude speedup over prior exhaustive-search algorithms.

This work was done by Amir Fijany and Farrokh Vatan of Caltech for NASA’s Jet Propulsion Laboratory.

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to:

Innovative Technology Assets Management


Mail Stop 202-233

4800 Oak Grove Drive

Pasadena, CA 91109-8099

(818) 354-2240

E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Refer to NPO-42481, volume and number of this NASA Tech Briefs issue, and the page number.

This Brief includes a Technical Support Package (TSP).
Efficient Method for Optimizing Placement of Sensors

(reference NPO-42481) is currently available for download from the TSP library.

Don't have an account? Sign up here.