Search NASA⌕ Search

SEARCH · Search NASA

Results for “pattern search”

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 19 records

Pattern Search Methods for Linearly Constrained Minimization

We extend pattern search methods to linearly constrained minimization. We develop a general class of feasible point pattern search algorithms and prove global convergence to a Karush-Kuhn-Tucker point. As in the case of unconstrained minimization, pattern search methods for linearly constrained problems accomplish this without explicit recourse to the gradient or the directional derivative. Key to the analysis of the algorithms is the way in which the local search patterns conform to the geometry of the boundary of the feasible region.

Lewis, Robert Michael↗

On the Local Convergence of Pattern Search

We examine the local convergence properties of pattern search methods, complementing the previously established global convergence properties for this class of algorithms. We show that the step-length control parameter which appears in the definition of pattern search algorithms provides a reliable asymptotic measure of first-order stationarity. This gives an analytical justification for a traditional stopping criterion for pattern search methods. Using this measure of first-order stationarity, we analyze the behavior of pattern search in the neighborhood of an isolated local minimizer. We show that a recognizable subsequence converges r-linearly to the minimizer.

Dolan, Elizabeth D.↗

Pattern Search Algorithms for Bound Constrained Minimization

We present a convergence theory for pattern search methods for solving bound constrained nonlinear programs. The analysis relies on the abstract structure of pattern search methods and an understanding of how the pattern interacts with the bound constraints. This analysis makes it possible to develop pattern search methods for bound constrained problems while only slightly restricting the flexibility present in pattern search methods for unconstrained problems. We prove global convergence despite the fact that pattern search methods do not have explicit information concerning the gradient and its projection onto the feasible region and consequently are unable to enforce explicitly a notion of sufficient feasible decrease.

Lewis, Robert Michael↗

A Globally Convergent Augmented Lagrangian Pattern Search Algorithm for Optimization with General Constraints and Simple Bounds

We give a pattern search adaptation of an augmented Lagrangian method due to Conn, Gould, and Toint. The algorithm proceeds by successive bound constrained minimization of an augmented Lagrangian. In the pattern search adaptation we solve this subproblem approximately using a bound constrained pattern search method. The stopping criterion proposed by Conn, Gould, and Toint for the solution of this subproblem requires explicit knowledge of derivatives. Such information is presumed absent in pattern search methods; however, we show how we can replace this with a stopping criterion based on the pattern size in a way that preserves the convergence properties of the original algorithm. In this way we proceed by successive, inexact, bound constrained minimization without knowing exactly how inexact the minimization is. So far as we know, this is the first provably convergent direct search method for general nonlinear programming.

Lewis, Robert Michael↗

Searching for patterns in remote sensing image databases using neural networks

We have investigated a method, based on a successful neural network multispectral image classification system, of searching for single patterns in remote sensing databases. While defining the pattern to search for and the feature to be used for that search (spectral, spatial, temporal, etc.) is challenging, a more difficult task is selecting competing patterns to train against the desired pattern. Schemes for competing pattern selection, including random selection and human interpreted selection, are discussed in the context of an example detection of dense urban areas in Landsat Thematic Mapper imagery. When applying the search to multiple images, a simple normalization method can alleviate the problem of inconsistent image calibration. Another potential problem, that of highly compressed data, was found to have a minimal effect on the ability to detect the desired pattern. The neural network algorithm has been implemented using the PVM (Parallel Virtual Machine) library and nearly-optimal speedups have been obtained that help alleviate the long process of searching through imagery.

Paola, Justin D.↗

Design of the VISITOR Tool: A Versatile ImpulSive Interplanetary Trajectory OptimizeR

The design of trajectories for interplanetary missions represents one of the most complex and important problems to solve during conceptual space mission design. To facilitate conceptual mission sizing activities, it is essential to obtain sufficiently accurate trajectories in a fast and repeatable manner. To this end, the VISITOR tool was developed. This tool modularly augments a patched conic MGA-1DSM model with a mass model, launch window analysis, and the ability to simulate more realistic arrival and departure operations. This was implemented in MATLAB, exploiting the built-in optimization tools and vector analysis routines. The chosen optimization strategy uses a grid search and pattern search, an iterative variable grid method. A genetic algorithm can be selectively used to improve search space pruning, at the cost of losing the repeatability of the results and increased computation time. The tool was validated against seven flown missions: the average total mission (Delta)V offset from the nominal trajectory was 9.1%, which was reduced to 7.3% when using the genetic algorithm at the cost of an increase in computation time by a factor 5.7. It was found that VISITOR was well-suited for the conceptual design of interplanetary trajectories, while also facilitating future improvements due to its modular structure.

Corpaccioli, Luca↗

Piezoelectric impedance-based high-accuracy damage identification using sparsity conscious multi-objective optimization inverse analysis

Two elements are essential in structural health monitoring utilizing dynamic responses: response measurement with high-frequency contents, i.e., small characteristic wavelengths, that can adequately reflect damage features, and effective inverse identification analysis that is however oftentimes under-determined. The advancement of smart structure integration has led to active interrogation through frequency-sweeping piezoelectric impedance measurement at high frequency range. In this research we develop a multi-objective optimization formulation for the identification of damage location and severity utilizing piezoelectric impedance. While one optimization objective is to match the response measurement with finite element model prediction in the damage parametric space, the other is the number of locations of damage, i.e., the sparsity of damage index as the solution vector, since damage usually occurs within a small number of locations. This multi-objective formulation fits well the under-determined nature of damage identification, as it naturally provides multiple solutions as basis for further elucidation. The challenge remaining is how to find a small solution set that can include the actual damage scenario. Here we develop a novel inverse identification framework utilizing the intelligent swarm optimizer which possesses flexibility for enhancement. We first embed a sparsity enforcement process into the population generation of the optimizer, which yields a solution repository intrinsically possessing sparsity. We then apply reinforcement learning so the agents can adaptively opt for local strategies with the aim of enriching the searching patterns to diversify the solutions. Through the incorporation of a Q-table, searching toward more promising directions will be rewarded. Our case analyses employing experimental data indicate that this sparsity-conscious multi-objective particle swarm optimization technique can lead to a small solution set which generally encompasses the true damage scenario. This effectively solves the structural damage identification problem with piezoelectric impedance measurement.

Yang Zhang↗

Efficient Algorithm for Rectangular Spiral Search

An algorithm generates grid coordinates for a computationally efficient spiral search pattern covering an uncertain rectangular area spanned by a coordinate grid. The algorithm does not require that the grid be fixed; the algorithm can search indefinitely, expanding the grid and spiral, as needed, until the target of the search is found. The algorithm also does not require memory of coordinates of previous points on the spiral to generate the current point on the spiral.

Brugarolas, Paul↗

Optimal Multi-Agent Search and Rescue Using Potential Field Theory

This paper presents an algorithm for efficient search and rescue using a multi-agent system of vehicles. The algorithm uses an artificial potential field combined with a time-varying reward function for visiting various points within the search area. The reward function is used to weight the attractiveness of these points in the potential field, and collision avoidance terms are used to repel vehicles from each other, which has the additional effect of reducing duplication of searching efforts. The algorithm generates velocity commands in real-time based on communication with the other vehicles. This framework allows vehicles to react in a dynamic environment, which is a significant advantage to simply following a-priori defined trajectories. Simulation results are presented to demonstrate the ability of the algorithm to cover the search area effectively. The algorithm is also compared to an exhaustive lawn-mower search pattern. This comparison is done via a Monte Carlo simulation with randomized target initial conditions and trajectories. The time to find the target improved by 16 and 30% in the mean and median, respectively. Additionally, this paper presents a method for analyzing the upper bound for time to find a target under the potential field guidance algorithm assuming a radially expanding search area.

John R Cooper↗

A digital algorithm for spectral deconvolution with noise filtering and peak picking: NOFIPP-DECON

Noise-filtering, peak-picking deconvolution software incorporates multiple convoluted convolute integers and multiparameter optimization pattern search. The two theories are described and three aspects of the software package are discussed in detail. Noise-filtering deconvolution was applied to a number of experimental cases ranging from noisy, nondispersive X-ray analyzer data to very noisy photoelectric polarimeter data. Comparisons were made with published infrared data, and a man-machine interactive language has evolved for assisting in very difficult cases. A modified version of the program is being used for routine preprocessing of mass spectral and gas chromatographic data.

Edwards, T. R.↗

Optimization of system reliability by the sequential unconstrained minimization technique

The reliability of a complex system was optimized by a new approach for implementing the sequential unconstrained minimization technique (SUMT) with the aid of Hooke and Jeeves pattern search and heuristic programming. Two optimization problems were considered. In the first, the system reliability was maximized subject to a nonlinear weight constraint. In the second, the weight of the system was minimized without violating the requirements of the minimal system reliability and the minimum reliability for each component. The sensitivities of the system reliability and that of the system weight to the reliability of each component were determined under optimal conditions.

Hwang, C. L.↗

An automated approach to design of solid rockets utilizing a special internal ballistics model

A pattern search technique is presented, which is utilized in a computer program that minimizes the sum of the squares of the differences, at various times, between a desired thrust-time trace and that calculated with a special mathematical internal ballistics model of a solid propellant rocket motor. The program is demonstrated by matching the thrust-time trace obtained from static tests of the first Space Shuttle SRM starting with input values of 10 variables which are, in general, 10% different from the as-built SRM. It is concluded that an excellent match is obtained.

Sforzini, R. H.↗

Convective heating of solid propellant during ignition

A pattern search optimization procedure is used to deduce from test data on the solid rocket boosters of the Space Shuttle the convective heat transfer coefficients between the igniter and main motor combustion gases and the surface of the solid propellant by utilizing a spatial and temporal ignition transient analysis. The 'best' convective coefficients are found which will minimize the overall deviation of the analytical prediction from the ignition transient test data. Computationally, this is achieved by treating the motor in such a way that only four optimization variables must be determined. The resulting coefficients greatly improve the prediction capabilities of the ignition transient analysis for the Space Shuttle SRM.

Murph, J. E.↗

Manual of phosphoric acid fuel cell power plant optimization model and computer program

An optimized cost and performance model for a phosphoric acid fuel cell power plant system was derived and developed into a modular FORTRAN computer code. Cost, energy, mass, and electrochemical analyses were combined to develop a mathematical model for optimizing the steam to methane ratio in the reformer, hydrogen utilization in the PAFC plates per stack. The nonlinear programming code, COMPUTE, was used to solve this model, in which the method of mixed penalty function combined with Hooke and Jeeves pattern search was chosen to evaluate this specific optimization problem.

Lu, C. Y.↗

Solid-propellant rocket motor internal ballistics performance variation analysis, phase 5

The results of research aimed at improving the predictability of internal ballistics performance of solid-propellant rocket motors (SRM's) including thrust imbalance between two SRM's firing in parallel are presented. Static test data from the first six Space Shuttle SRM's is analyzed using a computer program previously developed for this purpose. The program permits intentional minor design biases affecting the imbalance between any two SMR's to be removed. Results for the last four of the six SRM's, with only the propellant bulk temperature as a non-random variable, are generally within limits predicted by theory. Extended studies of internal ballistic performance of single SRM's are presented based on an earlier developed mathematical model which includes an assessment of grain deformation. The erosive burning rate law used in the model is upgraded and made more general. Excellent results are obtained in predictions of the performances of five different SRM's of quite different sizes and configurations. These SRM's all employ PBAN type propellants with ammonium perchlorate oxidizer and 16 to 20% aluminum except one which uses carboxyl terminated butadiene binder. The only non-calculated parameters in the burning rate equations that are changed for the different SRM's are the zero crossflow velocity burning rate coefficients and exponents. The results, in general, confirm the importance of grain deformation. The improved internal ballistic model makes practical development of an effective computer program for application of an optimization technique to SRM design which is also demonstrated. The program uses a pattern search technique to minimize the difference between a desired thrust-time trace and one calculated based on the internal ballistic model.

Sforzini, R. H.↗

Geostationary microwave imagers detection criteria

Geostationary orbit is investigated as a vantage point from which to sense remotely the surface features of the planet and its atmosphere, with microwave sensors. The geometrical relationships associated with geostationary altitude are developed to produce an efficient search pattern for the detection of emitting media and metal objects. Power transfer equations are derived from the roots of first principles and explain the expected values of the signal-to-clutter ratios for the detection of aircraft, ships, and buoys and for the detection of natural features where they are manifested as cold and warm eddies. The transport of microwave power is described for modeled detection where the direction of power flow is explained by the Zeroth and Second Laws of Thermodynamics. Mathematical expressions are derived that elucidate the detectability of natural emitting media and metal objects. Signal-to-clutter ratio comparisons are drawn among detectable objects that show relative detectability with a thermodynamic sensor and with a short-pulse radar.

Stacey, J. M.↗

Decision-theoretic control of EUVE telescope scheduling

This paper describes a decision theoretic scheduler (DTS) designed to employ state-of-the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems and using probabilistic inference to aggregate this information in light of the features of a given problem. The Bayesian Problem-Solver (BPS) introduced a similar approach to solving single agent and adversarial graph search patterns yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.

Hansson, Othar↗