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.
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
JPL
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
(818) 354-2240
E-mail:
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?
Overview
The document discusses a novel and efficient method developed by NASA's Jet Propulsion Laboratory (JPL) for optimizing the placement of sensors in diagnostic systems, identified as NPO-42481. The primary focus is on enhancing the diagnosability degree of systems, which refers to the ability to discriminate between different faults based on the information retrieved from sensors.
Key points include the challenges associated with sensor placement, where simply increasing the number of sensors does not guarantee improved diagnosability. The relevance of the information provided by each sensor and its correlation with other sensors is crucial. The document outlines several critical aspects of the sensor placement problem, including the need for a minimal sensor set that ensures a specific degree of diagnosability and the consideration of cost when selecting sensors.
Current methods for sensor placement are often ad hoc and rely on exhaustive search techniques, which limit their applicability to larger systems. The new method proposed in this document begins with a rigorous mathematical formulation of the sensor optimization problem, allowing for a more systematic approach. It leverages a branch-and-bound technique that significantly speeds up the process compared to standard algorithms.
The optimization process involves analyzing the structural model of the system and the potential information each sensor can provide, summarized in a signature matrix. The sensor placement problem is framed as a combinatorial problem, which can be mapped to a 0/1 Integer Programming (IP) problem. This approach allows for the identification of minimal cost sensors that achieve the desired level of diagnosability.
The document emphasizes the importance of optimal sensor placement in reducing system development costs and improving reliability. By minimizing the number of sensors while maximizing diagnosability, the proposed method aims to provide a more efficient design and operation of diagnostic systems. This systematic and efficient approach represents a significant advancement in the field, offering a solution that can be applied both at the design level and for enhancing existing systems.
In summary, the document presents a comprehensive overview of a new method for sensor placement optimization, addressing both technical and economic considerations, and highlights its potential impact on various technological and commercial applications.
