Search NASA⌕ Search

SEARCH · Search NASA

Results for “Search 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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
DOE OSTI2026

Sampling two-dimensional isometric tensor network states

Sampling a quantum system’s underlying probability distributions is an important computational task, e.g., for quantum advantage experiments and quantum Monte Carlo algorithms. Tensor networks are an invaluable tool for efficiently representing states of large quantum systems with limited entanglement. Algorithms for sampling one-dimensional (1D) tensor networks are well-established and utilized in several 1D tensor network methods. In this paper we introduce two novel sampling algorithms for two-dimensional (2D) isometric tensor network states (isoTNS) that generalize existing 1D tensor network sampling algorithms. Our first proposed algorithm performs independent sampling and yields a single configuration together with its associated probability. The second algorithm employs a greedy search strategy to identify high-probability configurations and their corresponding probabilities. Numerical results demonstrate the effectiveness of these algorithms across quantum states with varying entanglement and system size.

Dumitrescu, Eugene [ORNL] (ORCID:0000000158519567)↗
NASA NTRS2003

Phase Retrieval Using a Genetic Algorithm on the Systematic Image-Based Optical Alignment Testbed

NASA s Marshall Space Flight Center s Systematic Image-Based Optical Alignment (SIBOA) Testbed was developed to test phase retrieval algorithms and hardware techniques. Individuals working with the facility developed the idea of implementing phase retrieval by breaking the determination of the tip/tilt of each mirror apart from the piston motion (or translation) of each mirror. Presented in this report is an algorithm that determines the optimal phase correction associated only with the piston motion of the mirrors. A description of the Phase Retrieval problem is first presented. The Systematic Image-Based Optical Alignment (SIBOA) Testbeb is then described. A Discrete Fourier Transform (DFT) is necessary to transfer the incoming wavefront (or estimate of phase error) into the spatial frequency domain to compare it with the image. A method for reducing the DFT to seven scalar/matrix multiplications is presented. A genetic algorithm is then used to search for the phase error. The results of this new algorithm on a test problem are presented.

Taylor, Jaime R.↗
NASA NTRS2019

Search for Intermediate Mass Black Hole Binaries in the First and Second Observing Runs of the Advanced LIGO and VIRGO Network

Gravitational-wave astronomy has been firmly established with the detection of gravitational waves from the merger of ten stellar-mass binary black holes and a neutron star binary. This paper reports on the all-sky search for gravitational waves from intermediate mass black hole binaries in the first and second observing runs of the Advanced LIGO and Virgo network. The search uses three independent algorithms: two based on matched filtering of the data with waveform templates of gravitational-wave signals from compact binaries, and a third, model-independent algorithm that employs no signal model for the incoming signal. No intermediate mass black hole binary event is detected in this search. Consequently, we place upper limits on the merger rate density for a family of intermediate mass black hole binaries. In particular, we choose sources with total masses 𝑀=𝑚1+𝑚2∈[120,800] 𝑀⊙ and mass ratios 𝑞=𝑚2/𝑚1∈[0.1,1.0]. For the first time, this calculation is done using numerical relativity waveforms (which include higher modes) as models of the real emitted signal. We place a most stringent upper limit of 0.20 Gpc−3 yr−1 (in comoving units at the 90% confidence level) for equal-mass binaries with individual masses 𝑚1,2=100 𝑀⊙ and dimensionless spins 𝜒1,2=0.8 aligned with the orbital angular momentum of the binary. This improves by a factor of ∼5 that reported after Advanced LIGO’s first observing run.

B. P. Abbott↗
NASA NTRS1988

Search Problems in Mission Planning and Navigation of Autonomous Aircraft

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planner system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Problem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes the flight trajectory by creating the control commands to fly the aircraft.

Krozel, James A.↗
DOE OSTI2025

Design of lightweight BCC multi-principal element alloys with enhanced hydrogen storage using a machine learning-driven genetic algorithm

Body-centered cubic (BCC) based multi-principal element alloy (MPEA) hydrides have demonstrated significant potential for compact and efficient hydrogen storage. In this work, we first leverage machine learning (ML) models to predict the hydrogen affinity, storage capacity and phase stability of BCC MPEAs, creating a unique hydrogen-to-metal (H/M) predictor for materials with unprecedented performance. We developed a metaheuristic optimizer high-throughput framework by interfacing ML models with a genetic algorithm for the accelerated search of {Mg, Al, Ti, V, Cr, Mn, Fe, Co, Ni, Cu, Nb, Mo} based lightweight BCC MPEAs with improved hydrogen storage characteristics. We report five new MPEAs with a predicted gravimetric hydrogen storage capacity of around 3.5 wt% or more, including Cr 0.09 Mg 0.73 Ti 0.18 (4.25 wt% H) and Cr 0.21 Nb 0.11 Ti 0.35 V 0.33 (3.5 wt% H). The electronic structure of the top-performing composition, Cr 0.09 Mg 0.73 Ti 0.18 , was analyzed using density functional theory (DFT) to understand the reasons for its improved hydrogen storage properties compared to TiFe (1.90 wt% H), LaNi 5 (1.37 wt% H) or BCC MPEAs like TiVNbCr (3.70 wt% H). Temperature-dependent molecular dynamics (MD) studies were further performed on optimized BCC MPEAs to qualitatively study hydrogen mobility and analyze the effect of different elemental composition on bulk hydrogen diffusion. Our findings demonstrate how a ML assisted genetic algorithm framework can be used for efficient search of stable, lightweight and cost-effective MPEAs while minimizing the need for expensive ab initio calculations.

DFT↗
NASA NTRS2021

A Uniform Search for Nearby Planetary Companions to Hot Jupiters in TESS Data Reveals Hot Jupiters Are Still Lonely

We present the results of a uniform search for additional planets around all stars with confirmed hot Jupiters observed by the Transiting Exoplanet Survey Satellite (TESS) in its Cycle 1 survey of the southern ecliptic hemisphere. Our search comprises 184 total planetary systems with confirmed hot Jupiters with Rp > 8 R⊕ and orbital period <10 days. The Transit Least Squares algorithm was utilized to search for periodic signals that may have been missed by other planet search pipelines. While we recovered 169 of these confirmed hot Jupiters, our search yielded no new statistically validated planetary candidates in the parameter space searched (P < 14 days). A lack of planet candidates nearby hot Jupiters in the TESS data supports results from previous transit searches of each individual system, now down to the photometric precision of TESS. This is consistent with expectations from a high-eccentricity migration formation scenario, but additional formation indicators are needed for definitive confirmation. We injected transit signals into the light curves of the hot Jupiter sample to probe the pipeline's sensitivity to the target parameter space, finding a dependence proportional to ${R}_{p}^{2.32}{P}^{-0.88}$ for planets within 0.3 ≤ Rp ≤ 4 R⊕ and 1 ≤ P ≤ 14 days. A statistical analysis accounting for this sensitivity provides a median and 90% confidence interval of ${7.3}_{-7.3}^{+15.2} \% $ for the rate of hot Jupiters with nearby companions in this target parameter space. This study demonstrates how TESS uniquely enables comprehensive searches for nearby planetary companions to nearly all the known hot Jupiters.

Benjamin J Hord↗
NASA NTRS1994

Maximum-likelihood soft-decision decoding of block codes using the A* algorithm

The A* algorithm finds the path in a finite depth binary tree that optimizes a function. Here, it is applied to maximum-likelihood soft-decision decoding of block codes where the function optimized over the codewords is the likelihood function of the received sequence given each codeword. The algorithm considers codewords one bit at a time, making use of the most reliable received symbols first and pursuing only the partially expanded codewords that might be maximally likely. A version of the A* algorithm for maximum-likelihood decoding of block codes has been implemented for block codes up to 64 bits in length. The efficiency of this algorithm makes simulations of codes up to length 64 feasible. This article details the implementation currently in use, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained with this implementation of the A* algorithm for several codes.

Ekroot, L.↗
NASA NTRS1992

Robot path planning for space-truss assembly

Construction, repair, and maintenance of space-based structures will require extensive planning of operations in order to effectively carry out these tasks. The path planning algorithm described here is a general approach to generating paths that guarantee collision avoidance for a single chain nonredundant or redundant robot. The algorithm uses a graph search of feasible points in position space, followed by a local potential field method that guarantees collision avoidance among objects, structures, and the robot arm as well as conformance to joint limit constraints. This algorithm is novel in its computation of goal attractive potential fields in Cartesian space, and computation of obstacle repulsive fields in robot joint space. These effects are combined to generate robot motion. Computation is efficiently implemented through the computation of the robot arm Jacobian and not the full inverse arm kinematics. These planning algorithms have been implemented and evaluated using existing space-truss designs, and are being integrated into the RPI-CIRSSE Testbed environment.

Muenger, Rolf↗
NASA NTRS2021

Thermal Conductivity Estimation from Transient Test Data with Embedded Thermocouples using Genetic Algorithm Optimization

Inverse heat transfer methodology previously developed to estimate thermal properties of high temperature fibrous insulation from embedded thermocouples was applied to the thermoplastic polymer, polyether-ether-ketone (PEEK). A small experimental setup was utilized to test the PEEK sample between temperatures of 300 K and 525 K at atmospheric pressure. Cylindrical plugs of PEEK with three thermocouples embedded at various depths were incorporated in the test sample. The experimental PEEK thermocouple data were used as the boundary and initial conditions of a one-dimensional numerical thermal model to predict the internal temperatures of the material. The thermal conductivity of PEEK was estimated with the Continuous Genetic Algorithm optimization technique by searching for the coefficients of a functional form of thermal conductivity that minimized the difference between the experimentally measured and model predicted internal temperature values. The thermal testing, one-dimensional numerical thermal model, optimization algorithm, analysis, and results are presented.

Thermal Properties↗
NASA NTRS1991

A parallel trajectory optimization tool for aerospace plane guidance

A parallel trajectory optimization algorithm is being developed. One possible mission is to provide real-time, on-line guidance for the National Aerospace Plane. The algorithm solves a discrete-time problem via the augmented Lagrangian nonlinear programming algorithm. The algorithm exploits the dynamic programming structure of the problem to achieve parallelism in calculating cost functions, gradients, constraints, Jacobians, Hessian approximations, search directions, and merit functions. Special additions to the augmented Lagrangian algorithm achieve robust convergence, achieve (almost) superlinear local convergence, and deal with constraint curvature efficiency. The algorithm can handle control and state inequality constraints such as angle-of-attack and dynamic pressure constraints. Portions of the algorithm have been tested. The nonlinear programming core algorithm performs well on a variety of static test problems and on an orbit transfer problem. The parallel search direction algorithm can reduce wall clock time by a factor of 10 for this part of the computation task.

Psiaki, Mark L.↗
NASA NTRS1987

Collision detection for spacecraft proximity operations

Collision Detection for Spacecraft Proximity Operations This thesis describes the development of a new collision detection algorithm to be used when two spacecraft are operating in the same vicinity. The two spacecraft are modelled as unions of convex polyhedra, where the polyhedron resulting from the union may be either convex or nonconvex. The relative motion of the two spacecraft is assumed to be such that one vehicle is moving with constant linear and angular velocity with respect to the other. The algorithm determines if a collision is possible and, if so, predicts the time when the collision will take place. The theoretical basis for the new collision detection algorithm is the C-function formulation of the configuration space approach recently introduced by researchers in robotics. Three different types of C-functions are defined that model the contacts between the vertices, edges, and faces of the polyhedra representing the two spacecraft. These C-functions are used to formulate three "collision" conditions. The first of these conditions limits the points representing potential collisions to the zeros of the C-functions. The new algorithm is fundamentally a search for the smallest zero of any C-function that satisfies the second and third collision conditions. The C-functions are shown to be transcendental functions of time for the assumed trajectory of the moving spacecraft. The zeros of these functions cannot be expressed in dosed form. Therefore, numerical search procedures are developed to find aLl of the zeros of a C-function in specified bounded intervals of time. These bounded intervals of time are found by examining the second and third collision conditions. The capabilities of the new algorithm are demonstrated for several example cases. These include examples of collisions determined by zeros of each of the three different types of C-functions. In addition to predicting the time of first contact of the polyhedra, the algorithm identifies the features of the two polyhedra that are touching at this time. The new collision detection algorithm is the first such algorithm that is capable of solving the collision detection problem exactly for the case where the moving object has constant linear and angular velocities. This is a significant improvement on previous collision detection algorithms described in the literature. In particular, the ability to handle constant angular velocity represents a more realistic type of rotational motion than those which have been used in other algorithms.

Robin M Vaughan↗
NASA NTRS2014

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

Tree encoding of Gaussian sources

Tree codes are known to be capable of performing arbitrarily close to the rate-distortion function for any memoryless source and single-letter fidelity criterion. Tree coding and tree search strategies are investigated for the discrete-time memoryless Gaussian source encoded for a signal-power-to-mean-squared-error ratio of about 30 dB (about 5 binary digits per source output). Also, a theoretical lower bound on average search effort is derived. Two code search strategies (the Viterbi algorithm and the stack algorithm) were simulated in assembly language on a large digital computer. After suitable modifications, both strategies yielded encoding with a signal-to-distortion ratio about 1 dB below the limit set by the rate-distortion function. Although this performance is better than that of any previously known instrumentable scheme, it unfortunately requires search computation of the order of 100,000 machine cycles per source output encoded.

Dick, R. J.↗
NASA NTRS1998

Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes

A code trellis is a graphical representation of a code, block or convolutional, in which every path represents a codeword (or a code sequence for a convolutional code). This representation makes it possible to implement Maximum Likelihood Decoding (MLD) of a code with reduced decoding complexity. The most well known trellis-based MLD algorithm is the Viterbi algorithm. The trellis representation was first introduced and used for convolutional codes [23]. This representation, together with the Viterbi decoding algorithm, has resulted in a wide range of applications of convolutional codes for error control in digital communications over the last two decades. There are two major reasons for this inactive period of research in this area. First, most coding theorists at that time believed that block codes did not have simple trellis structure like convolutional codes and maximum likelihood decoding of linear block codes using the Viterbi algorithm was practically impossible, except for very short block codes. Second, since almost all of the linear block codes are constructed algebraically or based on finite geometries, it was the belief of many coding theorists that algebraic decoding was the only way to decode these codes. These two reasons seriously hindered the development of efficient soft-decision decoding methods for linear block codes and their applications to error control in digital communications. This led to a general belief that block codes are inferior to convolutional codes and hence, that they were not useful. Chapter 2 gives a brief review of linear block codes. The goal is to provide the essential background material for the development of trellis structure and trellis-based decoding algorithms for linear block codes in the later chapters. Chapters 3 through 6 present the fundamental concepts, finite-state machine model, state space formulation, basic structural properties, state labeling, construction procedures, complexity, minimality, and sectionalization of trellises. Chapter 7 discusses trellis decomposition and subtrellises for low-weight codewords. Chapter 8 first presents well known methods for constructing long powerful codes from short component codes or component codes of smaller dimensions, and then provides methods for constructing their trellises which include Shannon and Cartesian product techniques. Chapter 9 deals with convolutional codes, puncturing, zero-tail termination and tail-biting.Chapters 10 through 13 present various trellis-based decoding algorithms, old and new. Chapter 10 first discusses the application of the well known Viterbi decoding algorithm to linear block codes, optimum sectionalization of a code trellis to minimize computation complexity, and design issues for IC (integrated circuit) implementation of a Viterbi decoder. Then it presents a new decoding algorithm for convolutional codes, named Differential Trellis Decoding (DTD) algorithm. Chapter 12 presents a suboptimum reliability-based iterative decoding algorithm with a low-weight trellis search for the most likely codeword. This decoding algorithm provides a good trade-off between error performance and decoding complexity. All the decoding algorithms presented in Chapters 10 through 12 are devised to minimize word error probability. Chapter 13 presents decoding algorithms that minimize bit error probability and provide the corresponding soft (reliability) information at the output of the decoder. Decoding algorithms presented are the MAP (maximum a posteriori probability) decoding algorithm and the Soft-Output Viterbi Algorithm (SOVA) algorithm. Finally, the minimization of bit error probability in trellis-based MLD is discussed.

Lin, Shu↗
NASA NTRS1991

Intelligent perturbation algorithms for space scheduling optimization

Intelligent perturbation algorithms for space scheduling optimization are presented in the form of the viewgraphs. The following subject areas are covered: optimization of planning, scheduling, and manifesting; searching a discrete configuration space; heuristic algorithms used for optimization; use of heuristic methods on a sample scheduling problem; intelligent perturbation algorithms are iterative refinement techniques; properties of a good iterative search operator; dispatching examples of intelligent perturbation algorithm and perturbation operator attributes; scheduling implementations using intelligent perturbation algorithms; major advances in scheduling capabilities; the prototype ISF (industrial Space Facility) experiment scheduler; optimized schedule (max revenue); multi-variable optimization; Space Station design reference mission scheduling; ISF-TDRSS command scheduling demonstration; and example task - communications check.

Kurtzman, Clifford R.↗
DOE OSTI2024

Advances in ArborX to support exascale applications

ArborX is a performance portable geometric search library developed as part of the Exascale Computing Project (ECP). In this paper, we explore a collaboration between ArborX and a cosmological simulation code HACC. Large cosmological simulations on exascale platforms encounter a bottleneck due to the in-situ analysis requirements of halo finding, a problem of identifying dense clusters of dark matter (halos). This problem is solved by using a density-based DBSCAN clustering algorithm. With each MPI rank handling hundreds of millions of particles, it is imperative for the DBSCAN implementation to be efficient. In addition, the requirement to support exascale supercomputers from different vendors necessitates performance portability of the algorithm. We describe how this challenge problem guided ArborX development, and enhanced the performance and the scope of the library. We explore the improvements in the basic algorithms for the underlying search index to improve the performance, and describe several implementations of DBSCAN in ArborX. Further, we report the history of the changes in ArborX and their effect on the time to solve a representative benchmark problem, as well as demonstrate the real world impact on production end-to-end cosmology simulations.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1981

A method for obtaining reduced-order control laws for high-order systems using optimization techniques

A method of synthesizing reduced-order optimal feedback control laws for a high-order system is developed. A nonlinear programming algorithm is employed to search for the control law design variables that minimize a performance index defined by a weighted sum of mean-square steady-state responses and control inputs. An analogy with the linear quadractic Gaussian solution is utilized to select a set of design variables and their initial values. To improve the stability margins of the system, an input-noise adjustment procedure is used in the design algorithm. The method is applied to the synthesis of an active flutter-suppression control law for a wind tunnel model of an aeroelastic wing. The reduced-order controller is compared with the corresponding full-order controller and found to provide nearly optimal performance. The performance of the present method appeared to be superior to that of two other control law order-reduction methods. It is concluded that by using the present algorithm, nearly optimal low-order control laws with good stability margins can be synthesized.

Mukhopadhyay, V.↗
NASA NTRS1991

Genetic algorithm based input selection for a neural network function approximator with applications to SSME health monitoring

A genetic algorithm is used to select the inputs to a neural network function approximator. In the application considered, modeling critical parameters of the space shuttle main engine (SSME), the functional relationship between measured parameters is unknown and complex. Furthermore, the number of possible input parameters is quite large. Many approaches have been used for input selection, but they are either subjective or do not consider the complex multivariate relationships between parameters. Due to the optimization and space searching capabilities of genetic algorithms they were employed to systematize the input selection process. The results suggest that the genetic algorithm can generate parameter lists of high quality without the explicit use of problem domain knowledge. Suggestions for improving the performance of the input selection process are also provided.

Peck, Charles C.↗