Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “combinatorial”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
NASA NTRS2006

Advanced Catalysts for Fuel Cells

This viewgraph presentation reviews the development of catalyst for Fuel Cells. The objectives of the project are to reduce the cost of stack components and reduce the amount of precious metal used in fuel cell construction. A rapid combinatorial screening technique based on multi-electrode thin film array has been developed and validated for identifying catalysts for oxygen reduction; focus shifted from methanol oxidation in FY05 to oxygen reduction in FY06. Multi-electrode arrays of thin film catalysts of Pt-Ni and Pt-Ni-Zr have been deposited. Pt-Ni and have been characterized electrochemically and structurally. Pt-Ni-Zr and Pt-Ni films show higher current density and onset potential compared to Pt. Electrocatalytic activity and onset potential are found to be strong function of the lattice constant. Thin film Pt(59)Ni(39)Zr(2) can provide 10 times the current density of thin film Pt. Thin film Pt(59)Ni(39)Zr(2) also shows 65mV higher onset potential than Pt.

fuel cells↗
NASA NTRS2009

NASA Tech Briefs, February 2009

Tech Briefs are short announcements of innovations originating from research and development activities of the National Aeronautics and Space Administration. They emphasize information considered likely to be transferable across industrial, regional, or disciplinary lines and are issued to encourage commercial application. Topics covered include: Measuring Low Concentrations of Liquid Water in Soil; The Mars Science Laboratory Touchdown Test Facility; Non-Contact Measurement of Density and Thickness Variation in Dielectric Materials; Compact Microwave Fourier Spectrum Analyzer; InP Heterojunction Bipolar Transistor Amplifiers to 255 GHz; Combinatorial Generation of Test Suites; In-Phase Power-Combined Frequency Tripler at 300 GHz; Electronic System for Preventing Airport Runway Incursions; Smaller but Fully Functional Backshell for Cable Connector; Glove-Box or Desktop Virtual-Reality System; Composite Layer Manufacturing with Fewer Interruptions; Improved Photoresist Coating for Making CNT Field Emitters; A Simplified Diagnostic Method for Elastomer Bond Durability; Complex Multifunctional Polymer/Carbon-Nanotube Composites; Very High Output Thermoelectric Devices Based on ITO Nanocomposites; Reducing Unsteady Loads on a Piggyback Miniature Submarine; Ultrasonic/Sonic Anchor; Grooved Fuel Rings for Nuclear Thermal Rocket Engines; Pulsed Operation of an Ion Accelerator; Autonomous Instrument Placement for Mars Exploration Rovers; Mission and Assets Database; TCP/IP Interface for the Satellite Orbit Analysis Program (SOAP); Trajectory Calculator for Finite-Radius Cutter on a Lathe; Integrated System Health Management Development Toolkit.

Source record↗
NASA NTRS2009

Nanocomposite Strain Gauges Having Small TCRs

Ceramic strain gauges in which the strain-sensitive electrically conductive strips made from nanocomposites of noble metal and indium tin oxide (ITO) are being developed for use in gas turbine engines and other power-generation systems in which gas temperatures can exceed 1,500 F (about 816 C). In general, strain gauges exhibit spurious thermally induced components of response denoted apparent strain. When temperature varies, a strain-gauge material that has a nonzero temperature coefficient of resistance (TCR) exhibits an undesired change in electrical resistance that can be mistaken for the change in resistance caused by a change in strain. It would be desirable to formulate straingauge materials having TCRs as small as possible so as to minimize apparent strain. Most metals exhibit positive TCRs, while most semiconductors, including ITO, exhibit negative TCRs. The present development is based on the idea of using the negative TCR of ITO to counter the positive TCRs of noble metals and of obtaining the benefit of the ability of both ITO and noble metals to endure high temperatures. The noble metal used in this development thus far has been platinum. Combinatorial libraries of many ceramic strain gauges containing nanocomposites of various proportions of ITO and platinum were fabricated by reactive co-sputtering from ITO and platinum targets onto alumina- and zirconia-based substrates mounted at various positions between the targets.

Gregory, Otto↗
NASA NTRS2008

LOCAD-PTS: Operation of a New System for Microbial Monitoring Aboard the International Space Station (ISS)

Microorganisms within the space stations Salyut, Mir and the International Space Station (ISS), have traditionally been monitored with culture-based techniques. These techniques involve growing environmental samples (cabin water, air or surfaces) on agar-type media for several days, followed by visualization of resulting colonies; and return of samples to Earth for ground-based analysis. This approach has provided a wealth of useful data and enhanced our understanding of the microbial ecology within space stations. However, the approach is also limited by the following: i) More than 95% microorganisms in the environment cannot grow on conventional growth media; ii) Significant time lags occur between onboard sampling and colony visualization (3-5 days) and ground-based analysis (as long as several months); iii) Colonies are often difficult to visualize due to condensation within contact slide media plates; and iv) Techniques involve growth of potentially harmful microorganisms, which must then be disposed of safely. This report describes the operation of a new culture-independent technique onboard the ISS for rapid analysis (within minutes) of endotoxin and -1, 3-glucan, found in the cell walls of gram-negative bacteria and fungi, respectively. This technique involves analysis of environmental samples with the Limulus Amebocyte Lysate (LAL) assay in a handheld device. This handheld device and sampling system is known as the Lab-On-a-Chip Application Development Portable Test System (LOCAD-PTS). A poster will be presented that describes a comparative study between LOCAD-PTS analysis and existing culture-based methods onboard the ISS; together with an exploratory survey of surface endotoxin throughout the ISS. It is concluded that while a general correlation between LOCAD-PTS and traditional culture-based methods should not necessarily be expected, a combinatorial approach can be adopted where both sets of data are used together to generate a more complete story of the microbial ecology on the ISS.

Maule, J.↗
NASA NTRS2008

Low-Pt-Content Anode Catalyst for Direct Methanol Fuel Cells

Combinatorial experiments have led to the discovery that a nanophase alloy of Pt, Ru, Ni, and Zr is effective as an anode catalyst material for direct methanol fuel cells. This discovery has practical significance in that the electronic current densities achievable by use of this alloy are comparable or larger than those obtained by use of prior Pt/Ru catalyst alloys containing greater amounts of Pt. Heretofore, the high cost of Pt has impeded the commercialization of direct methanol fuel cells. By making it possible to obtain a given level of performance at reduced Pt content (and, hence, lower cost), the discovery may lead to reduction of the economic impediment to commercialization.

Narayanan, Sekharipuram↗
NASA NTRS2009

Physical Principle for Generation of Randomness

A physical principle (more precisely, a principle that incorporates mathematical models used in physics) has been conceived as the basis of a method of generating randomness in Monte Carlo simulations. The principle eliminates the need for conventional random-number generators. The Monte Carlo simulation method is among the most powerful computational methods for solving high-dimensional problems in physics, chemistry, economics, and information processing. The Monte Carlo simulation method is especially effective for solving problems in which computational complexity increases exponentially with dimensionality. The main advantage of the Monte Carlo simulation method over other methods is that the demand on computational resources becomes independent of dimensionality. As augmented by the present principle, the Monte Carlo simulation method becomes an even more powerful computational method that is especially useful for solving problems associated with dynamics of fluids, planning, scheduling, and combinatorial optimization. The present principle is based on coupling of dynamical equations with the corresponding Liouville equation. The randomness is generated by non-Lipschitz instability of dynamics triggered and controlled by feedback from the Liouville equation. (In non-Lipschitz dynamics, the derivatives of solutions of the dynamical equations are not required to be bounded.)

Zak, Michail↗
NASA NTRS2008

Tool Support for Parametric Analysis of Large Software Simulation Systems

The analysis of large and complex parameterized software systems, e.g., systems simulation in aerospace, is very complicated and time-consuming due to the large parameter space, and the complex, highly coupled nonlinear nature of the different system components. Thus, such systems are generally validated only in regions local to anticipated operating points rather than through characterization of the entire feasible operational envelope of the system. We have addressed the factors deterring such an analysis with a tool to support envelope assessment: we utilize a combination of advanced Monte Carlo generation with n-factor combinatorial parameter variations to limit the number of cases, but still explore important interactions in the parameter space in a systematic fashion. Additional test-cases, automatically generated from models (e.g., UML, Simulink, Stateflow) improve the coverage. The distributed test runs of the software system produce vast amounts of data, making manual analysis impossible. Our tool automatically analyzes the generated data through a combination of unsupervised Bayesian clustering techniques (AutoBayes) and supervised learning of critical parameter ranges using the treatment learner TAR3. The tool has been developed around the Trick simulation environment, which is widely used within NASA. We will present this tool with a GN&C (Guidance, Navigation and Control) simulation of a small satellite system.

Schumann, Johann↗
NASA NTRS2006

An Efficient Approach for the Reliability Analysis of Phased-Mission Systems with Dependent Failures

We consider the reliability analysis of phased-mission systems with common-cause failures in this paper. Phased-mission systems (PMS) are systems supporting missions characterized by multiple, consecutive, and nonoverlapping phases of operation. System components may be subject to different stresses as well as different reliability requirements throughout the course of the mission. As a result, component behavior and relationships may need to be modeled differently from phase to phase when performing a system-level reliability analysis. This consideration poses unique challenges to existing analysis methods. The challenges increase when common-cause failures (CCF) are incorporated in the model. CCF are multiple dependent component failures within a system that are a direct result of a shared root cause, such as sabotage, flood, earthquake, power outage, or human errors. It has been shown by many reliability studies that CCF tend to increase a system's joint failure probabilities and thus contribute significantly to the overall unreliability of systems subject to CCF.We propose a separable phase-modular approach to the reliability analysis of phased-mission systems with dependent common-cause failures as one way to meet the above challenges in an efficient and elegant manner. Our methodology is twofold: first, we separate the effects of CCF from the PMS analysis using the total probability theorem and the common-cause event space developed based on the elementary common-causes; next, we apply an efficient phase-modular approach to analyze the reliability of the PMS. The phase-modular approach employs both combinatorial binary decision diagram and Markov-chain solution methods as appropriate. We provide an example of a reliability analysis of a PMS with both static and dynamic phases as well as CCF as an illustration of our proposed approach. The example is based on information extracted from a Mars orbiter project. The reliability model for this orbiter considers the various phases of Launch, Cruise, Mars Orbit Insertion, and Orbit. Some of the CCF for the orbiter in this mission include environmental effects, such as micrometeoroids, human operator errors, and software errors.

reliability analysis↗
NASA NTRS2009

Complexity Science Applications to Dynamic Trajectory Management: Research Strategies

The promise of the Next Generation Air Transportation System (NextGen) is strongly tied to the concept of trajectory-based operations in the national airspace system. Existing efforts to develop trajectory management concepts are largely focused on individual trajectories, optimized independently, then de-conflicted among each other, and individually re-optimized, as possible. The benefits in capacity, fuel, and time are valuable, though perhaps could be greater through alternative strategies. The concept of agent-based trajectories offers a strategy for automation of simultaneous multiple trajectory management. The anticipated result of the strategy would be dynamic management of multiple trajectories with interacting and interdependent outcomes that satisfy multiple, conflicting constraints. These constraints would include the business case for operators, the capacity case for the Air Navigation Service Provider (ANSP), and the environmental case for noise and emissions. The benefits in capacity, fuel, and time might be improved over those possible under individual trajectory management approaches. The proposed approach relies on computational agent-based modeling (ABM), combinatorial mathematics, as well as application of "traffic physics" concepts to the challenge, and modeling and simulation capabilities. The proposed strategy could support transforming air traffic control from managing individual aircraft behaviors to managing systemic behavior of air traffic in the NAS. A system built on the approach could provide the ability to know when regions of airspace approach being "full," that is, having non-viable local solution space for optimizing trajectories in advance.

Sawhill, Bruce↗
NASA NTRS2009

Parametric Analysis of a Hover Test Vehicle using Advanced Test Generation and Data Analysis

Large complex aerospace systems are generally validated in regions local to anticipated operating points rather than through characterization of the entire feasible operational envelope of the system. This is due to the large parameter space, and complex, highly coupled nonlinear nature of the different systems that contribute to the performance of the aerospace system. We have addressed the factors deterring such an analysis by applying a combination of technologies to the area of flight envelop assessment. We utilize n-factor (2,3) combinatorial parameter variations to limit the number of cases, but still explore important interactions in the parameter space in a systematic fashion. The data generated is automatically analyzed through a combination of unsupervised learning using a Bayesian multivariate clustering technique (AutoBayes) and supervised learning of critical parameter ranges using the machine-learning tool TAR3, a treatment learner. Covariance analysis with scatter plots and likelihood contours are used to visualize correlations between simulation parameters and simulation results, a task that requires tool support, especially for large and complex models. We present results of simulation experiments for a cold-gas-powered hover test vehicle.

Gundy-Burlet, Karen↗
NASA NTRS2010

Image Segmentation Analysis for NASA Earth Science Applications

NASA collects large volumes of imagery data from satellite-based Earth remote sensing sensors. Nearly all of the computerized image analysis of this data is performed pixel-by-pixel, in which an algorithm is applied directly to individual image pixels. While this analysis approach is satisfactory in many cases, it is usually not fully effective in extracting the full information content from the high spatial resolution image data that s now becoming increasingly available from these sensors. The field of object-based image analysis (OBIA) has arisen in recent years to address the need to move beyond pixel-based analysis. The Recursive Hierarchical Segmentation (RHSEG) software developed by the author is being used to facilitate moving from pixel-based image analysis to OBIA. The key unique aspect of RHSEG is that it tightly intertwines region growing segmentation, which produces spatially connected region objects, with region object classification, which groups sets of region objects together into region classes. No other practical, operational image segmentation approach has this tight integration of region growing object finding with region classification This integration is made possible by the recursive, divide-and-conquer implementation utilized by RHSEG, in which the input image data is recursively subdivided until the image data sections are small enough to successfully mitigat the combinatorial explosion caused by the need to compute the dissimilarity between each pair of image pixels. RHSEG's tight integration of region growing object finding and region classification is what enables the high spatial fidelity of the image segmentations produced by RHSEG. This presentation will provide an overview of the RHSEG algorithm and describe how it is currently being used to support OBIA or Earth Science applications such as snow/ice mapping and finding archaeological sites from remotely sensed data.

Tilton, James C.↗
NASA NTRS2010

N channel JFET based digital logic gate structure

A circuit topography is presented which is used to create usable digital logic gates using N (negatively doped) channel Junction Field Effect Transistors (JFETs) and load resistors, level shifting resistors, and supply rails whose values are based on the direct current (DC) parametric distributions of those JFETs. This method has direct application to the current state of the art in high temperature, for example 300.degree. C. to 500.degree. C. and higher, silicon carbide (SiC) device production. The ability to produce inverting and combinatorial logic enables the production of pulse and edge triggered latches. This scale of logic synthesis would bring digital logic and state machine capabilities to devices operating in extremely hot environments, such as the surface of Venus, near hydrothermal vents, within nuclear reactors (SiC is inherently radiation hardened), and within internal combustion engines. The basic logic gate can be configured as a driver for oscillator circuits allowing for time bases and simple digitizers for resistive or reactive sensors. The basic structure of this innovation, the inverter, can be reconfigured into various analog circuit topographies through the use of feedback structures.

Krasowski, Michael J.↗
NASA NTRS2010

Fast Solution in Sparse LDA for Binary Classification

An algorithm that performs sparse linear discriminant analysis (Sparse-LDA) finds near-optimal solutions in far less time than the prior art when specialized to binary classification (of 2 classes). Sparse-LDA is a type of feature- or variable- selection problem with numerous applications in statistics, machine learning, computer vision, computational finance, operations research, and bio-informatics. Because of its combinatorial nature, feature- or variable-selection problems are NP-hard or computationally intractable in cases involving more than 30 variables or features. Therefore, one typically seeks approximate solutions by means of greedy search algorithms. The prior Sparse-LDA algorithm was a greedy algorithm that considered the best variable or feature to add/ delete to/ from its subsets in order to maximally discriminate between multiple classes of data. The present algorithm is designed for the special but prevalent case of 2-class or binary classification (e.g. 1 vs. 0, functioning vs. malfunctioning, or change versus no change). The present algorithm provides near-optimal solutions on large real-world datasets having hundreds or even thousands of variables or features (e.g. selecting the fewest wavelength bands in a hyperspectral sensor to do terrain classification) and does so in typical computation times of minutes as compared to days or weeks as taken by the prior art. Sparse LDA requires solving generalized eigenvalue problems for a large number of variable subsets (represented by the submatrices of the input within-class and between-class covariance matrices). In the general (fullrank) case, the amount of computation scales at least cubically with the number of variables and thus the size of the problems that can be solved is limited accordingly. However, in binary classification, the principal eigenvalues can be found using a special analytic formula, without resorting to costly iterative techniques. The present algorithm exploits this analytic form along with the inherent sequential nature of greedy search itself. Together this enables the use of highly-efficient partitioned-matrix-inverse techniques that result in large speedups of computation in both the forward-selection and backward-elimination stages of greedy algorithms in general.

Moghaddam, Baback↗
NASA NTRS2002

NASA Tech Briefs, April 2002

The contents include: 1) Application Briefs; 2) Sneak Preview of Sensors Expo; 3) The Complexity of the Diagnosis Problem; 4) Design Concepts for the ISS TransHab Module; 5) Characteristics of Supercritical Transitional Mixing Layers; 6) Electrometer for Triboelectric Evaluation of Materials; 7) Infrared CO2 Sensor With Built-In Calibration Chambers; 8) Solid-State Potentiometric CO Sensor; 9) Planetary Rover Absolute Heading Detection Using a Sun Sensor; 10) Concept for Utilizing Full Areas of STJ Photodetector Arrays; 11) Development of Cognitive Sensors; 12) Enabling Higher-Voltage Operation of SOl CMOS Transistors; 13) Estimating Antenna-Pointing Errors From Beam Squints; 14) Advanced-Fatigue-Crack-Growth and Fracture- Mechanics Program; 15) Software for Sequencing Spacecraft Actions; 16) Program Distributes and Tracks Organizational Memoranda; 16) Flat Membrane Device for Dehumidification of Air; 17) Inverted Hindle Mount Reduces Sag of a Large, Precise Mirror; 18) Heart-Pump-Outlet/Cannula Coupling; 19) Externally Triggered Microcapsules Release Drugs In Situ; 20) Combinatorial Drug Design Augmented by Information Theory; 21) Multiple-Path-Length Optical Absorbance Cell; 22) Model of a Fluidized Bed Containing a Mixture of Particles; 23) Refractive Secondary Concentrators for Solar Thermal Systems; 24) Cold Flow Calorimeter; 25) Methodology for Tracking Hazards and Predicting Failures; 26) Estimating Heterodyne-Interferometer Polarization Leakage; 27) An Efficient Algorithm for Propagation of Temporal- Constraint Networks; 28) Software for Continuous Replanning During Execution; 29) Surface-Launched Explorers for Reconnaissance/Scouting; 30) Firmware for a Small Motion-Control Processor; 31) Gear Bearings and Gear-Bearing Transmissions; and 32) Linear Dynamometer With Variable Stroke and Frequency.

Source record↗
NASA NTRS2010

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

NASA's space data-communications infrastructure, the Space Network and the Ground Network, provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft via orbiting relay satellites and ground stations. An implementation of the methods and algorithms disclosed herein will be a system that produces globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary search, a class of probabilistic strategies for searching large solution spaces, constitutes the essential technology in this disclosure. Also disclosed are methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithm itself. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally, with applicability to a very broad class of combinatorial optimization problems.

Rash, James L.↗
NASA NTRS2010

Extinction-to-Backscatter Ratios of Saharan Dust Layers Derived from In-Situ Measurements and CALIPSO Overflights During NAMMA

We determine the extinction-to-backscatter (Sa) ratios of dust using (1) airborne in-situ measurements of microphysical properties, (2) modeling studies, and (3) the Cloud-Aerosol Lidar and Infrared Pathfinder Satellite Observations (CALIPSO) observations recorded during the NASA African Monsoon Multidisciplinary Analyses (NAMMA) field experiment conducted from Sal, Cape Verde during Aug-Sept 2006. Using CALIPSO measurements of the attenuated backscatter of lofted Saharan dust layers, we apply the transmittance technique to estimate dust Sa ratios at 532 nm and a 2-color method to determine the corresponding 1064 nm Sa. This method yielded dust Sa ratios of 39.8 plus or minus 1.4 sr and 51.8 plus or minus 3.6 sr at 532 nm and 1064 nm, respectively. Secondly, Sa at both wavelengths is independently calculated using size distributions measured aboard the NASA DC-8 and estimates of Saharan dust complex refractive indices applied in a T-Matrix scheme. We found Sa ratios of 39.1 plus or minus 3.5 sr and 50.0 plus or minus 4 sr at 532 nm and 1064 nm, respectively, using the T-Matrix calculations applied to measured size spectra. Finally, in situ measurements of the total scattering (550 nm) and absorption coefficients (532 nm) are used to generate an extinction profile that is used to constrain the CALIPSO 532 nm extinction profile and thus generate a stratified 532 nm Sa. This method yielded an Sa ratio at 532 nm of 35.7 sr in the dust layer and 25 sr in the marine boundary layer consistent with a predominantly seasalt aerosol near the ocean surface. Combinatorial simulations using noisy size spectra and refractive indices were used to estimate the mean and uncertainty (one standard deviation) of these Sa ratios. These simulations produced a mean (plus or minus uncertainty) of 39.4 (plus or minus 5.9) sr and 56.5 (plus or minus 16.5) sr at 532 nm and 1064 nm, respectively, corresponding to percent uncertainties of 15% and 29%. These results will provide a measurements-based estimate of the dust Sa for use in backscatter lidar inversion algorithms such as CALIOP.

Omar, Ali H.↗
NASA NTRS2006

NASA Tech Briefs, October 2006

Topics covered include: Protein Sensors Based on Optical Ring Resonators; Phase Sensor for Aligning a Segmented Telescope Mirror; Control Software for Advanced Video Guidance Sensor; Generating Control Commands From Gestures Sensed by EMG; Multiple-Flat-Panel System Displays Multidimensional Data; 3D X-Ray Luggage-Screening System; Probe Station and Near-Field Scanner for Testing Antennas; Photodetector Arrays for Multicolor Visible/Infrared Imaging; Semiconductor Bolometers Give Background-Limited Performance; Multichannel X-Band Dielectric-Resonator Oscillator; Automatic Alignment of Displacement-Measuring Interferometer; Earth Observing System Data Gateway; Power User Interface; Mercury Shopping Cart Interface; Cassini Archive Tracking System; Architecture Adaptive Computing Environment; Computing Fault Displacements from Surface Deformations; Oxygen-Permeable, Hydrophobic Membranes of Silanized alpha-Al2O3; SiC Composite Turbine Vanes; Retaining Device for the Interior Structure of a Spacecraft Payload; Tool for Torquing Circular Electrical-Connector Collars; System for Continuous Deaeration of Hydraulic Oil; Solar-Powered Cooler and Heater for an Automobile Interior; Improved Oxygen-Beam Texturing of Glucose-Monitoring Optics; Tool for Two Types of Friction Stir Welding; Stationary Apparatus Would Apply Forces of Walking to Feet; Instrument Would Detect and Collect Biological Aerosols; Boundary Condition for Modeling Semiconductor Nanostructures; Miniature Distillation Column for Producing LOX From Air; Even Illumination from Fiber-Optic-Coupled Laser Diodes; Optically Driven Deformable Mirrors; Algorithm for Automated Detection of Edges of Clouds; Exploiting Quantum Resonance to Solve Combinatorial Problems; Hybrid Terrain Database; On Release of Microbe-Laden Particles from Mars Landers; A Concept for Run-Time Support of the Chapel Language; Thermoelectric Inhomogeneities in (Ag(sub 1-y)SbTe2)(sub x)(PbTe)(sub 1-x); and Spacecraft Escape Capsule.

Source record↗
NASA NTRS2005

Two Methods for Efficient Solution of the Hitting-Set Problem

A paper addresses much of the same subject matter as that of Fast Algorithms for Model-Based Diagnosis (NPO-30582), which appears elsewhere in this issue of NASA Tech Briefs. However, in the paper, the emphasis is more on the hitting-set problem (also known as the transversal problem), which is well known among experts in combinatorics. The authors primary interest in the hitting-set problem lies in its connection to the diagnosis problem: it is a theorem of model-based diagnosis that in the set-theory representation of the components of a system, the minimal diagnoses of a system are the minimal hitting sets of the system. In the paper, the hitting-set problem (and, hence, the diagnosis problem) is translated from a combinatorial to a computational problem by mapping it onto the Boolean satisfiability and integer- programming problems. The paper goes on to describe developments nearly identical to those summarized in the cited companion NASA Tech Briefs article, including the utilization of Boolean-satisfiability and integer- programming techniques to reduce the computation time and/or memory needed to solve the hitting-set problem.

Vatan, Farrokh↗