Search NASA⌕ Search

SEARCH · Search NASA

Results for “randomized algorithms”

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 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
NASA NTRS1983

Numerical solution of the problem of flame propagation by the use of the random element method

A numerical, grid-free algorithm is presented for one-dimensional reaction-diffusion model of laminar flame propagation in premixed gases. It is based on the random element method we developed for the analysis of diffusional processes. The effect of combustion is taken into account by applying the principle of fractional steps to separate the process of diffusion, modeled by the random walk of computational elements, from the exothermic effects of chemical reaction, monitoring their strength. The validity of the algorithm is demonstrated by application to flame propagation problems for which exact solutions exist. The flame speed evaluated by its use oscillates around the exact value at a relatively small amplitude, while the temperature and species concentration profiles are self-correcting in their convergence to the exact solution. A satisfactory resolution is obtained by the use of quite a small number of computational elements which automatically adjust their distribution of fit sharp gradients.

Ghoniem, A. F.↗
NASA NTRSDate not supplied

Traffic Prediction for Uncommunicative Aircraft in Terminal Airspace: Development Framework and Performance Evaluations

This paper presents an air traffic prediction algorithm that takes observations of an aircraft and classifies aircraft type, estimates the aircraft's intent to and method of joining an airport traffic pattern, and predicts the aircaft's future trajectory. To develop algorithms that enable autonomous aircraft to safely insert into un-towered traffic patterns, several challenges need to be addressed. These challenges range from traffic detection to sensor fusion to own-ship trajectory replanning. Critical to a trajectory replanning algorithm is information regarding the future behavior of all traffic aircraft in the operational environment. The presented traffic prediction algorithm generates this information using regular measurements of traffic aircraft position and velocity to classify the aircraft by speed-class, estimate how the aircraft will approach the runway, and construct a predicted trajectory to the runway including future positions and velocities at specific times. The predictions of the presented algorithm are the necessary inputs for any downstream traffic pattern sequencing and own-ship trajectory planning routines. The presented algorithm is benchmarked using approximately 300 randomized traffic trajectories, spanning four vehicle weight classes and eight traffic entry types. While the algorithm can process multiple traffic vehicles in the terminal area, there is no prediction of traffic-on-traffic interaction. Each traffic vehicle is processed separately.

John D McMinn↗
NASA NTRS1993

Systems aspects of COBE science data compression

A general approach to compression of diverse data from large scientific projects has been developed and this paper addresses the appropriate system and scientific constraints together with the algorithm development and test strategy. This framework has been implemented for the COsmic Background Explorer spacecraft (COBE) by retrofitting the existing VAS-based data management system with high-performance compression software permitting random access to the data. Algorithms which incorporate scientific knowledge and consume relatively few system resources are preferred over ad hoc methods. COBE exceeded its planned storage by a large and growing factor and the retrieval of data significantly affects the processing, delaying the availability of data for scientific usage and software test. Embedded compression software is planned to make the project tractable by reducing the data storage volume to an acceptable level during normal processing.

Freedman, I.↗
NASA NTRS1976

Data processing/display design for the space shuttle/spacelab Electromagnetic Environment Experiment (EEE)

Methods for data analysis, data compression including universal coding, storage and retrieval on random access storage devices, and display were developed and implemented on the GSFC Interdata computer. The original 64 bit per frequency band representation was reduced to 10 bits through source coding/universal coding, a compression ratio of 6.4, prior to storage. Rapid encoding/decoding was achieved by the algorithms used so that rapid random access is retained.

Davisson, L. D.↗
NASA NTRS1971

Application of Monte Carlo techniques to optimization of high-energy beam transport in a stochastic environment

An algorithm employing a modified sequential random perturbation, or creeping random search, was applied to the problem of optimizing the parameters of a high-energy beam transport system. The stochastic solution of the mathematical model for first-order magnetic-field expansion allows the inclusion of state-variable constraints, and the inclusion of parameter constraints allowed by the method of algorithm application eliminates the possibility of infeasible solutions. The mathematical model and the algorithm were programmed for a real-time simulation facility; thus, two important features are provided to the beam designer: (1) a strong degree of man-machine communication (even to the extent of bypassing the algorithm and applying analog-matching techniques), and (2) extensive graphics for displaying information concerning both algorithm operation and transport-system behavior. Chromatic aberration was also included in the mathematical model and in the optimization process. Results presented show this method as yielding better solutions (in terms of resolutions) to the particular problem than those of a standard analog program as well as demonstrating flexibility, in terms of elements, constraints, and chromatic aberration, allowed by user interaction with both the algorithm and the stochastic model. Example of slit usage and a limited comparison of predicted results and actual results obtained with a 600 MeV cyclotron are given.

Parrish, R. V.↗
NASA NTRS2016

Applying Simulated Annealing to Problems in Model-Based Diagnosis

Generating all diagnoses is computationally intractable. Therefore, many of the state-of-the-art approaches are incomplete. Quantum computers may however offer a solution. The first commercially available quantum computer is being used to minimize polynomials that are difficult for classical simulated annealing but easy for quantum annealing. All problems in Model-based Diagnosis (MBD) can be transformed into a polynomial minimization problem, allowing one to apply a quantum algorithm called quantum annealing to solve MBD problems. To better understand the need for this quantum approach, we designed two simulated annealingdiagnostic algorithms tailored to run on a polynomial representation of MBD. These algorithms differ on their policy for random neighborhood variable selection. In addition, enhanced metrics were devised to provide more diagnostic coverage. Finally, these two simulated annealing algorithms were analyzed and empirically evaluated and compared against state-of-the-art probabilistic methods for MBD such as SAFARI using ISCAS-85.

Simulated annealing↗
NASA NTRS1985

Scattering Models and Basic Experiments in the Microwave Regime

The objectives of research over the next three years are: (1) to develop a randomly rough surface scattering model which is applicable over the entire frequency band; (2) to develop a computer simulation method and algorithm to simulate scattering from known randomly rough surfaces, Z(x,y); (3) to design and perform laboratory experiments to study geometric and physical target parameters of an inhomogeneous layer; (4) to develop scattering models for an inhomogeneous layer which accounts for near field interaction and multiple scattering in both the coherent and the incoherent scattering components; and (5) a comparison between theoretical models and measurements or numerical simulation.

Fung, A. K.↗
NASA NTRS2003

Quantum Adiabatic Algorithms and Large Spin Tunnelling

We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in this paper. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H (r) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H (r) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin-n/2 and provide a complete characterization of such paths.

Boulatov, A.↗
NASA NTRS2004

Precipitation and Latent Heating Distributions from Satellite Passive Microwave Radiometry: Evaluation of Estimates Using Independent Data - Part 2

Rainfall rate estimates from space-borne k&ents are generally accepted as reliable by a majority of the atmospheric science commu&y. One-of the Tropical Rainfall Measuring Mission (TRh4M) facility rain rate algorithms is based upon passive microwave observations fiom the TRMM Microwave Imager (TMI). Part I of this study describes improvements in the TMI algorithm that are required to introduce cloud latent heating and drying as additional algorithm products. Here, estimates of surface rain rate, convective proportion, and latent heating are evaluated using independent ground-based estimates and satellite products. Instantaneous, OP5resolution estimates of surface rain rate over ocean fiom the improved TMI algorithm are well correlated with independent radar estimates (r approx. 0.88 over the Tropics), but bias reduction is the most significant improvement over forerunning algorithms. The bias reduction is attributed to the greater breadth of cloud-resolving model simulations that support the improved algorithm, and the more consistent and specific convective/stratiform rain separation method utilized. The bias of monthly, 2.5 deg. -resolution estimates is similarly reduced, with comparable correlations to radar estimates. Although the amount of independent latent heating data are limited, TMI estimated latent heating profiles compare favorably with instantaneous estimates based upon dual-Doppler radar observations, and time series of surface rain rate and heating profiles are generally consistent with those derived from rawinsonde analyses. Still, some biases in profile shape are evident, and these may be resolved with: (a) additional contextual information brought to the estimation problem, and/or; (b) physically-consistent and representative databases supporting the algorithm. A model of the random error in instantaneous, 0.5 deg-resolution rain rate estimates appears to be consistent with the levels of error determined from TMI comparisons to collocated radar. Error model modifications for non-raining situations will be required, however. Sampling error appears to represent only a fraction of the total error in monthly, 2S0-resolution TMI estimates; the remaining error is attributed to physical inconsistency or non-representativeness of cloud-resolving model simulated profiles supporting the algorithm.

Yang, Song↗
NASA NTRS1990

Influence of atmospherically induced random wave fronts on diffraction imagery - A computer simulation model for testing image reconstruction algorithms

This paper is devoted to the development of a two-dimensional computer-simulation model that is based on the rigid constraints of optical diffraction theory with careful attention paid to the generation of sample realizations of Gaussian-distributed, spatially random, isotropic wave fronts that have zero-mean and prescribed-covariance functions. Given a sample realization of the wave front, the corresponding centered point-spread function and optical-transfer function are evaluated. A detailed study is made of the statistics of random wave-front tilt, point-spread function, modulus squared of transfer function, and phase of transfer function.

Barakat, Richard↗
NASA NTRS2003

Estimating Uncertainty in GPCP and TRMM Multi-Satellite Precipitation Estimates

One of the high-priority problems in satellite precipitation estimation is developing algorithms for estimating the errors in precipitation retrievals by individual sensors and subsequent multi-satellite combinations. Classically, we distinguish between "random" and "bias" errors, which do and do not, respectively average to zero over a "big enough" time/space sample. The current operational GPCP and TRMM multi-satellite algorithms are nearly unique in estimating random error for the monthly precipitation estimates from individual sensor systems (including gauge), following Huffman, and then making multi-sensor combinations. No routinely operational global precipitation produces estimates of bias error. Subsequently, a similar scheme has been followed to provide random error estimates for the Multi-satellite Precipitation Analysis (MPA) being computed in real time and after real time for TRMM. The Huffman algorithm for random error is briefly reviewed, including a discussion of the limitations imposed on the algorithm by standard monthly precipitation data sets. Starting from a very simple theoretical treatment of the histogram of precipitation samples in a month, an equation is developed that depends on the estimated average precipitation rate for the month, the number of samples in the month, and two constants. The constants are set separately for each source of precipitation estimate (such as "raingauge") by calibration at selected ground sites. We discuss recent work validating the random error estimates to highlight the successes and limitations of this first-generation approach. We then consider what information is needed from the individual sensor algorithms to facilitate additional accuracy in the estimation of random errors across the time/space span of climate regimes which a global estimation system must handle. In addition, the thorny issue of estimating bias is raised. Finally, the role of error estimates (and the qualitative errors!) in creating combinations of precipitation estimates from different individual sensors is discussed. This issue is particularly important when fine scales in space and time are being considered, say the 0.25 x 0.25-deg 3-hourly estimates in the MPA.

Huffman, G. J.↗
NASA NTRS1984

Computing approximate random Delta v magnitude probability densities

This paper describes the development and use of an algorithm to compute approximate statistics of the magnitude of a single random trajectory correction maneuver (TCM) Delta v vector. The TCM Delta v vector is modeled as a three component Cartesian vector each of whose components is a random variable having a normal (Gaussian) distribution with zero mean and possibly unequal standard deviations. The algorithm uses these standard deviations as input to produce approximations to (1) the mean and standard deviation of the magnitude of Delta v, (2) points of the probability density function of the magnitude of Delta v, and (3) points of the cumulative and inverse cumulative distribution functions of Delta v. The approximates are based on Monte Carlo techniques developed in a previous paper by the author and extended here. The algorithm described is expected to be useful in both pre-flight planning and in-flight analysis of maneuver propellant requirements for space missions.

Chadwick, C.↗
NASA NTRS1982

Numerical modelling of turbulent flow in a combustion tunnel

A numerical technique is presented for the analysis of turbulent flow associated with combustion. The technique uses Chorin's random vortex method (rvm), an algorithm capable of tracing the action of elementary turbulent eddies and their cumulative effects without imposing any restriction upon their motion. In the past, the rvm has been used with success to treat nonreacting turbulent flows, revealing in particular the mechanics of large-scale flow patterns, the so-called coherent structures. Introduced here is a flame propagation algorithm, also developed by Chorin, in conjunction with volume sources modelling the mechanical effects of the exothermic process of combustion. As an illustration of its use, the technique is applied to flow in a combustion tunnel where the flame is stabilized by a back-facing step. Solutions for both nonreacting and reacting flow fields are obtained which satisfactorily describe the essential features of turbulent combustion in a lean propane-air mixture that were observed in the laboratory by means of high speed Schlieren photography.

Ghoniem, A. F.↗
NASA NTRS1983

Numerical modeling of turbulent flow in a channel

Two-dimensional incompressible turbulent flow in a channel with a backward-facing step was studied numerically by Chorin's Random Vortex Method (RVM), an algorithm capable of tracing the action of elementary turbulent eddies and their cumulative effects without imposing any restrictions upon their motions. The step occurs in one side of a channel with otherwise flat, parallel walls; its height equals 1/3, 1/4 or 1/5 the width of the channel downstream. The main objective was to investigate the behavior of the large-scale turbulent eddies in a flow and the flow characteristics in the separated shear layer, the reattached zone, and the rebuilding boundary layer after reattachment. The unsteady vorticity field and the distribution of time-averaged turbulent statistics were obtained. The effects of expansion step height and initial boundary layer state were also studied. Comparisons were made with the available experimental results. The agreement is satisfactory in the velocity profiles and in the reattachment length, and fairly good in the turbulence profiles. Also a mechanism of the development of the reattaching turbulent flow was suggested by the numerical results.

Dai, Y. W.↗
NASA NTRS1983

Spatial inventory integrating raster databases and point sample data

A timber inventory of the Eldorado National Forest, located in east-central California, provides an example of the use of a Geographic Information System (GIS) to stratify large areas of land for sampling and the collection of statistical data. The raster-based GIS format of the VICAR/IBIS software system allows simple and rapid tabulation of areas, and facilitates the selection of random locations for ground sampling. Algorithms that simplify the complex spatial pattern of raster-based information, and convert raster format data to strings of coordinate vectors, provide a link to conventional vector-based geographic information systems.

Strahler, A. H.↗
NASA NTRS1990

A Boltzmann machine for the organization of intelligent machines

A three-tier structure consisting of organization, coordination, and execution levels forms the architecture of an intelligent machine using the principle of increasing precision with decreasing intelligence from a hierarchically intelligent control. This system has been formulated as a probabilistic model, where uncertainty and imprecision can be expressed in terms of entropies. The optimal strategy for decision planning and task execution can be found by minimizing the total entropy in the system. The focus is on the design of the organization level as a Boltzmann machine. Since this level is responsible for planning the actions of the machine, the Boltzmann machine is reformulated to use entropy as the cost function to be minimized. Simulated annealing, expanding subinterval random search, and the genetic algorithm are presented as search techniques to efficiently find the desired action sequence and illustrated with numerical examples.

Moed, Michael C.↗
NASA NTRS2010

Data transmission system and method

A method of transmitting data packets, where randomness is added to the schedule. Universal broadcast schedules using encoding and randomization techniques are also discussed, together with optimal randomized schedules and an approximation algorithm for finding near-optimal schedules.

Bruck, Jehoshua↗
NASA NTRSDate not supplied

Machine Learning Applications to Metal-Silicate Equilibria and their Insights into Core Formation

An extensive number of studies have experimentally investigated how elements distribute between metal and silicate phases, to better constrain core-mantle chemical equilibrium. Here, we present a new database compiling all (to our knowledge) experimental data on liquid metal-silicate partitioning from 118 peer-reviewed publications. We applied various machine learning techniques to gain further insights into these partitioning equilibria and their dependencies. We performed a network analysis to investigate the relationship between experiments and partition coefficients, which enables visualizing gaps in the experimental dataset and biases related to varying experimental conditions and analytical setup. In addition, semi-empirical thermodynamic models are commonly used to extrapolate these chemical reactions to the wide range of pressure, temperature and compositional conditions of planetary differentiation. These models are based on linear regressions that assume continuous relationship between partition coefficients and experimental variables. Here, we considered random forest regressions, which are algorithms based on ensembles of decision trees and does not consider continuous effects of each variable. The application of this regression significantly improves the prediction of metal-silicate partitioning for several elements including Ni, Si and Cr. We will show how this new approach improves our understanding of elemental exchange between metal and silicate and their implications for the Earth’s core formation.

siderophile element↗