Search NASA⌕ Search

SEARCH · Search NASA

Results for “Randomized algorithm”

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 289 records · Page 16
All sourcesNASA NTRSDOE OSTI
NASA NTRS1984

A Simple Algorithm for the Metric Traveling Salesman Problem

An algorithm was designed for a wire list net sort problem. A branch and bound algorithm for the metric traveling salesman problem is presented for this. The algorithm is a best bound first recursive descent where the bound is based on the triangle inequality. The bounded subsets are defined by the relative order of the first K of the N cities (i.e., a K city subtour). When K equals N, the bound is the length of the tour. The algorithm is implemented as a one page subroutine written in the C programming language for the VAX 11/750. Average execution times for randomly selected planar points using the Euclidean metric are 0.01, 0.05, 0.42, and 3.13 seconds for ten, fifteen, twenty, and twenty-five cities, respectively. Maximum execution times for a hundred cases are less than eleven times the averages. The speed of the algorithms is due to an initial ordering algorithm that is a N squared operation. The algorithm also solves the related problem where the tour does not return to the starting city and the starting and/or ending cities may be specified. It is possible to extend the algorithm to solve a nonsymmetric problem satisfying the triangle inequality.

Grimm, M. J.↗
NASA NTRSDate not supplied

Algorithmic Classification of Raman Spectra Biosignatures: Improving Life Detection Confidence

“Agnostic” biosignatures – indicators of life (or the absence of life), independent of a particular biochemistry – are increasingly considered a high standard for life detection. The Ladder of Life Detection (2018) called for investigating how combinations of independent and different potential biosignatures affect confidence. To address this gap, statistical classification of elemental abundances, isotopic fractionation, and reflectance spectroscopy (VNIR) has been implemented. Raman spectroscopy, highly desirable due to its wide availability, has the potential to improve this predictive power. This work implemented biosignature classification algorithms on Raman data alone, in preparation for combination with the other data types. Raman spectroscopy data was collected from published databases and papers as part of a manually curated dataset of “indicative” and “non-indicative of life” samples. These currently include 61 non-indicative samples (meteorites, magnetite); 3 indicative living samples (bacteria); 20 indicative non-living samples (chalk, bone); and 12 indicative mixed (with non-indicative material) samples (soil, microbial mats). Laboratory work is ongoing to characterize additional samples, particularly a greater breadth of mixed systems. Spectra were interpolated, filtered with the Savitzsky-Golay filter, and de-noised. For a preliminary examination, agnostic features were manually extracted including mean intensity, number of peaks, and mean peak width. Different peak prominences and filtering polynomials were used to refine features. Classification algorithms were implemented: k-nearest neighbors (KNN), logistic regression (LR), linear support vector machines (SVM), random forest (RF), Gaussian naïve bayes (GNB). Lastly, Monte Carlo simulations on 1,000 50%-train-test-splits were used to validate classification performance and feature significance. The preliminary feature set achieved its highest AUC of 0.52 with LR, with no strongly discriminatory features. Work to improve feature extraction, such as through deep learning with back propagation, is planned. In future work, the Raman data will be combined with the other data types, and potentially new data types such as enantiomeric excess. This project was partially supported through the NASA Ames Project EXcellence (APEX) incubator program.

Astrobiology↗
NASA NTRS1997

Development, Validation, and Potential Enhancements to the Second-Generation Operational Aerosol Product at the National Environmental Satellite, Data, and Information Service of the National Oceanic and Atmospheric Administration

A revised (phase 2) single-channel algorithm for aerosol optical thickness, tau(sup A)(sub SAT), retrieval over oceans from radiances in channel 1 (0.63 microns) of the Advanced Very High Resolution Radiometer (AVHRR) has been implemented at the National Oceanic and Atmospheric Administration's National Environmental Satellite Data and Information Service for the NOAA 14 satellite launched December 30, 1994. It is based on careful validation of its operational predecessor (phase 1 algorithm), implemented for NOAA 14 in 1989. Both algorithms scale the upward satellite radiances in cloud-free conditions to aerosol optical thickness using an updated radiative transfer model of the ocean and atmosphere. Application of the phase 2 algorithm to three matchup Sun-photometer and satellite data sets, one with NOAA 9 in 1988 and two with NOAA 11 in 1989 and 1991, respectively, show systematic error is less than 10%, with a random error of sigma(sub tau) approx. equal 0.04. First results of tau(sup A)(sub SAT) retrievals from NOAA 14 using the phase 2 algorithm, and from checking its internal consistency, are presented. The potential two-channel (phase 3) algorithm for the retrieval of an aerosol size parameter, such as the Junge size distribution exponent, by adding either channel 2 (0.83 microns) from the current AVHRR instrument, or a 1.6-microns channel to be available on the Tropical Rainfall Measurement Mission and the NOAA-KLM satellites by 1997 is under investigation. The possibility of using this additional information in the retrieval of a more accurate estimate of aerosol optical thickness is being explored.

Stowe, Larry L.↗
NASA NTRS2020

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↗
NASA NTRS2010

Initialization and Restart in Stochastic Local Search: Computing a Most Probable Explanation in Bayesian Networks

For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary topologies. We also give a novel formalization of stochastic local search, with focus on initialization and restart, using probability theory and mixture models. Experimentally, we apply our methods to the problem of MPE computation, using a stochastic local search algorithm known as Stochastic Greedy Search. By carefully optimizing both initialization and restart, we reduce the MPE search time for application BNs by several orders of magnitude compared to using uniform at random initialization without restart. On several BNs from applications, the performance of Stochastic Greedy Search is competitive with clique tree clustering, a state-of-the-art exact algorithm used for MPE computation in BNs.

Mengshoel, Ole J.↗
NASA NTRS1998

Experimental Simulation of Active Control With On-line System Identification on Sound Transmission Through an Elastic Plate

An adaptive control algorithm with on-line system identification capability has been developed. One of the great advantages of this scheme is that an additional system identification mechanism such as an additional uncorrelated random signal generator as the source of system identification is not required. A time-varying plate-cavity system is used to demonstrate the control performance of this algorithm. The time-varying system consists of a stainless-steel plate which is bolted down on a rigid cavity opening where the cavity depth was changed with respect to time. For a given externally located harmonic sound excitation, the system identification and the control are simultaneously executed to minimize the transmitted sound in the cavity. The control performance of the algorithm is examined for two cases. First, all the water was drained, the external disturbance frequency is swept with 1 Hz/sec. The result shows an excellent frequency tracking capability with cavity internal sound suppression of 40 dB. For the second case, the water level is initially empty and then raised to 3/20 full in 60 seconds while the external sound excitation is fixed with a frequency. Hence, the cavity resonant frequency decreases and passes the external sound excitation frequency. The algorithm shows 40 dB transmitted noise suppression without compromising the system identification tracking capability.

Source record↗
NASA NTRS1977

Satellite Doppler data processing using a microcomputer

A microcomputer which was developed to compute ground radio beacon position locations using satellite measurements of Doppler frequency shift is described. Both the computational algorithms and the microcomputer hardware incorporating these algorithms were discussed. Results are presented where the microcomputer in conjunction with the NIMBUS-6 random access measurement system provides real time calculation of beacon latitude and longitude.

Schmid, P. E.↗
NASA NTRS1982

A statistical model for radar images of agricultural scenes

The presently derived and validated statistical model for radar images containing many different homogeneous fields predicts the probability density functions of radar images of entire agricultural scenes, thereby allowing histograms of large scenes composed of a variety of crops to be described. Seasat-A SAR images of agricultural scenes are accurately predicted by the model on the basis of three assumptions: each field has the same SNR, all target classes cover approximately the same area, and the true reflectivity characterizing each individual target class is a uniformly distributed random variable. The model is expected to be useful in the design of data processing algorithms and for scene analysis using radar images.

Frost, V. S.↗
NASA NTRS1982

Random element method for numerical modeling of diffusional processes

The random element method is a generalization of the random vortex method that was developed for the numerical modeling of momentum transport processes as expressed in terms of the Navier-Stokes equations. The method is based on the concept that random walk, as exemplified by Brownian motion, is the stochastic manifestation of diffusional processes. The algorithm based on this method is grid-free and does not require the diffusion equation to be discritized over a mesh, it is thus devoid of numerical diffusion associated with finite difference methods. Moreover, the algorithm is self-adaptive in space and explicit in time, resulting in an improved numerical resolution of gradients as well as a simple and efficient computational procedure. The method is applied here to an assortment of problems of diffusion of momentum and energy in one-dimension as well as heat conduction in two-dimensions in order to assess its validity and accuracy. The numerical solutions obtained are found to be in good agreement with exact solution except for a statistical error introduced by using a finite number of elements, the error can be reduced by increasing the number of elements or by using ensemble averaging over a number of solutions.

Ghoniem, A. F.↗
NASA NTRS1985

Advances and trends in structures and dynamics; Proceedings of the Symposium, Washington, DC, October 22-25, 1984

Among the topics discussed are developments in structural engineering hardware and software, computation for fracture mechanics, trends in numerical analysis and parallel algorithms, mechanics of materials, advances in finite element methods, composite materials and structures, determinations of random motion and dynamic response, optimization theory, automotive tire modeling methods and contact problems, the damping and control of aircraft structures, and advanced structural applications. Specific topics covered include structural design expert systems, the evaluation of finite element system architectures, systolic arrays for finite element analyses, nonlinear finite element computations, hierarchical boundary elements, adaptive substructuring techniques in elastoplastic finite element analyses, automatic tracking of crack propagation, a theory of rate-dependent plasticity, the torsional stability of nonlinear eccentric structures, a computation method for fluid-structure interaction, the seismic analysis of three-dimensional soil-structure interaction, a stress analysis for a composite sandwich panel, toughness criterion identification for unidirectional composite laminates, the modeling of submerged cable dynamics, and damping synthesis for flexible spacecraft structures.

Noor, A. K.↗
NASA NTRS1995

Stereo-Based Region-Growing using String Matching

We present a novel stereo algorithm based on a coarse texture segmentation preprocessing phase. Matching is performed using a string comparison. Matching sub-strings correspond to matching sequences of textures. Inter-scanline clustering of matching sub-strings yields regions of matching texture. The shape of these regions yield information concerning object's height, width and azimuthal position relative to the camera pair. Hence, rather than the standard dense depth map, the output of this algorithm is a segmentation of objects in the scene. Such a format is useful for the integration of stereo with other sensor modalities on a mobile robotic platform. It is also useful for localization; the height and width of a detected object may be used for landmark recognition, while depth and relative azimuthal location determine pose. The algorithm does not rely on the monotonicity of order of image primitives. Occlusions, exposures, and foreshortening effects are not problematic. The algorithm can deal with certain types of transparencies. It is computationally efficient, and very amenable to parallel implementation. Further, the epipolar constraints may be relaxed to some small but significant degree. A version of the algorithm has been implemented and tested on various types of images. It performs best on random dot stereograms, on images with easily filtered backgrounds (as in synthetic images), and on real scenes with uncontrived backgrounds.

Mandelbaum, Robert↗
NASA NTRS2011

Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a ppro~imate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.

Kaplan, Sezgin↗
NASA NTRS2016

Background-Oriented Schlieren used in a hypersonic inlet test at NASA GRC

Background Oriented Schlieren (BOS) is a derivative of the classical schlieren technology, which is used to visualize density gradients, such as shock wave structures in a wind tunnel. Changes in refractive index resulting from density gradients cause light rays to bend, resulting in apparent motion of a random background pattern. The apparent motion of the pattern is determined using cross-correlation algorithms (between no-flow and with-flow image pairs) producing a schlieren-like image. One advantage of BOS is its simplified setup which enables a larger field-of-view (FOV) than traditional schlieren systems. In the present study, BOS was implemented into the Combined Cycle Engine Large-Scale Inlet Mode Transition Experiment (CCE LIMX) in the 10x10 Supersonic Wind Tunnel at NASA Glenn Research Center. The model hardware for the CCE LIMX accommodates a fully integrated turbine based combined cycle propulsion system. To date, inlet mode transition between turbine and ramjet operation has been successfully demonstrated. High-speed BOS was used to visualize the behavior of the flow structures shock waves during unsteady inlet unstarts, a phenomenon known as buzz. Transient video images of inlet buzz were recorded for both the ramjet flow path (high speed inlet) and turbine flow path (low speed inlet). To understand the stability limits of the inlet, operation was pushed to the point of unstart and buzz. BOS was implemented in order to view both inlets simultaneously, since the required FOV was beyond the capability of the current traditional schlieren system. An example of BOS data (Images 1-6) capturing inlet buzz are presented.

Background-oriented schlieren↗
NASA NTRS2004

Application of Simulated Annealing and Related Algorithms to TWTA Design

Simulated Annealing (SA) is a stochastic optimization algorithm used to search for global minima in complex design surfaces where exhaustive searches are not computationally feasible. The algorithm is derived by simulating the annealing process, whereby a solid is heated to a liquid state and then cooled slowly to reach thermodynamic equilibrium at each temperature. The idea is that atoms in the solid continually bond and re-bond at various quantum energy levels, and with sufficient cooling time they will rearrange at the minimum energy state to form a perfect crystal. The distribution of energy levels is given by the Boltzmann distribution: as temperature drops, the probability of the presence of high-energy bonds decreases. In searching for an optimal design, local minima and discontinuities are often present in a design surface. SA presents a distinct advantage over other optimization algorithms in its ability to escape from these local minima. Just as high-energy atomic configurations are visited in the actual annealing process in order to eventually reach the minimum energy state, in SA highly non-optimal configurations are visited in order to find otherwise inaccessible global minima. The SA algorithm produces a Markov chain of points in the design space at each temperature, with a monotonically decreasing temperature. A random point is started upon, and the objective function is evaluated at that point. A stochastic perturbation is then made to the parameters of the point to arrive at a proposed new point in the design space, at which the objection function is evaluated as well. If the change in objective function values (Delta)E is negative, the proposed new point is accepted. If (Delta)E is positive, the proposed new point is accepted according to the Metropolis criterion: rho((Delta)f) = exp((-Delta)E/T), where T is the temperature for the current Markov chain. The process then repeats for the remainder of the Markov chain, after which the temperature is decremented and the process repeats. Eventually (and hopefully), a near-globally optimal solution is attained as T approaches zero. Several exciting variants of SA have recently emerged, including Discrete-State Simulated Annealing (DSSA) and Simulated Tempering (ST). The DSSA algorithm takes the thermodynamic analogy one step further by categorizing objective function evaluations into discrete states. In doing so, many of the case-specific problems associated with fine-tuning the SA algorithm can be avoided; for example, theoretical approximations for the initial and final temperature can be derived independently of the case. In this manner, DSSA provides a scheme that is more robust with respect to widely differing design surfaces. ST differs from SA in that the temperature T becomes an additional random variable in the optimization. The system is also kept in equilibrium as the temperature changes, as opposed to the system being driven out of equilibrium as temperature changes in SA. ST is designed to overcome obstacles in design surfaces where numerous local minima are separated by high barriers. These algorithms are incorporated into the optimal design of the traveling-wave tube amplifier (TWTA). The area under scrutiny is the collector, in which it would be ideal to use negative potential to decelerate the spent electron beam to zero kinetic energy just as it reaches the collector surface. In reality this is not plausible due to a number of physical limitations, including repulsion and differing levels of kinetic energy among individual electrons. Instead, the collector is designed with multiple stages depressed below ground potential. The design of this multiple-stage collector is the optimization problem of interest. One remaining problem in SA and DSSA is the difficulty in determining when equilibrium has been reached so that the current Markov chain can be terminated. It has been suggested in recent literature that simulating the thermodynamic properties opecific heat, entropy, and internal energy from the Boltzmann distribution can provide good indicators of having reached equilibrium at a certain temperature. These properties are tested for their efficacy and implemented in SA and DSSA code with respect to TWTA collector optimization.

Radke, Eric M.↗
NASA NTRS1998

Estimation of 3-D Cloud Effects on TOMS Satellite Retrieval of Surface UV Irradiance

To improve surface UV irradiance retrieval from the Total Ozone Mapping Spectrometer (TOMS) we simulate errors of the TOMS cloud correction algorithm for summertime broken cloud conditions. Cloud scenes (50 km by 50 km) are modeled by a normal random (Gaussian) field with a fixed lower boundary and conservative scattering. The model relates stochastic field characteristics with the cloud amount, mean cloud diameter and aspect ratio. Clouds are embedded into Rayleigh atmosphere with standard ozone profile. Radiative transfer calculations of the radiance at the top of the atmosphere and irradiance at the surface were performed using 3-D Monte Carlo (MC) code. The results are averaged over the satellite field of view on the surface (50 km by 50 km) and compared with TOMS predicted surface irradiance for the same scene reflectance. The TOMS algorithm assumes horizontally homogeneous Cl-type cloud between 3 km and 5.5 km. The effective optical depth is determined by fitting observed (MC) radiance at 380 nm. Having the same radiance at the satellite the homogeneous and broken cloud models predict different average irradiances at the surface. This is due to the differences in Bidirectional Reflection Distribution Function (BRDF) for homogeneous and broken cloud scenes with the same hemispherical albedo. For typical TOMS observational geometry at mid-latitudes the simulated single pixels errors may be as large as +/- 20%. Qualitatively these errors are due to the dominance of the non-horizontal cloud surfaces, which are not accounted for in the homogeneous cloud model. However, due to high variability of the real cloud shapes and types it is unclear how these single pixel errors would affect TOMS time-integrated UV exposure over extended periods (weeks to months) for different regions.

Krotkov, Nickolay A.↗
NASA NTRS2024

Spectral Correlation in MODIS Water-Leaving Reflectance Retrieval Uncertainty

Spectral remote sensing reflectance, Rrs(λ) (sr−1), is the fundamental quantity used to derive a host of bio-optical and biogeochemical properties of the water column from satellite ocean color measurements. Estimation of uncertainty in those derived geophysical products is therefore dependent on knowledge of the uncertainty in satellite-retrieved R rs . Furthermore, since the associated algorithms require R rs at multiple spectral bands, the spectral (i.e., band-to-band)error covariance in R rs is needed to accurately estimate the uncertainty in those derived properties. This study establishes a derivative-based approach for propagating instrument random noise, instrument systematic uncertainty, and forward model uncertainty into R rs as retrieved using NASA’s multiple-scattering epsilon (MSEPS) atmospheric correction algorithm, to generate pixel-level error covariance in R rs . The approach is applied to measurements from Moderate Resolution Imaging Spectroradiometer (MODIS) on the Aqua satellite and verified using Monte Carlo (MC) analysis. We also make use of this full spectral error covariance in R rs to calculate uncertainty in phytoplankton pigment chlorophyll-a concentration (chl a , mg/m 3 ) and diffuse attenuation coefficient of downwelling irradiance at 490 nm (K d (490), m -1 ). Accounting for the error covariance in R rs generally reduces the estimated relative uncertainty in chl a by ∼1-2% (absolute value) in waters with chl a < 0.25 mg/m 3 where the color index (CI) algorithm is used. The reduction is ∼5-10% in waters with chl a > 0.35 mg/m 3 where the blue-green ratio (OCX) algorithm is used. Such reduction can be higher than 30% in some regions. For K d (490), the reduction by error covariance is generally ∼2%, but can be higher than 20% in some regions. The error covariance in R rs is further verified through forward-calculating chl a from MODIS-retrieved and in situ R rs and comparing estimated uncertainty with observed differences. An 8-day global composite of propagated uncertainty shows that the goal of 35% uncertainty in chl a can be achieved over deep ocean waters (chl a ≤ 0.1 mg/m3). While the derivative-based approach generates reasonable error covariance in R rs some assumptions should be updated as our knowledge improves. These include the inter-band error correlation in top-of-atmosphere reflectance, and uncertainties in the calibration of MODIS 869 nm band, in ancillary data, and in the in situ data used for system vicarious calibration.

Ocean color↗
NASA NTRS2005

Online Bagging and Boosting

Bagging and boosting are two of the most well-known ensemble learning methods due to their theoretical performance guarantees and strong experimental results. However, these algorithms have been used mainly in batch mode, i.e., they require the entire training set to be available at once and, in some cases, require random access to the data. In this paper, we present online versions of bagging and boosting that require only one pass through the training data. We build on previously presented work by presenting some theoretical results. We also compare the online and batch algorithms experimentally in terms of accuracy and running time.

Oza, Nikunji C.↗