Search NASA⌕ Search

SEARCH · Search NASA

Results for “Hybrid 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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

The analysis of control trajectories using symbolic and database computing

This final report comprises the formal semi-annual status reports for this grant for the periods June 30-December 31, 1993, January 1-June 30, 1994, and June 1-December 31, 1994. The research supported by this grant is broadly concerned with the symbolic computation, mixed numeric-symbolic computation, and database computation of trajectories of dynamical systems, especially control systems. A review of work during the report period covers: trajectories and approximating series, the Cayley algebra of trees, actions of differential operators, geometrically stable integration algorithms, hybrid systems, trajectory stores, PTool, and other activities. A list of publications written during the report period is attached.

Grossman, Robert↗
NASA NTRS2011

The Development of the Puerto Rico Lightning Detection Network for Meteorological Research

A land-based Puerto Rico Lightning Detection Network (PR-LDN) dedicated to the academic research of meteorological phenomena has being developed. Five Boltek StormTracker PCI-Receivers with LTS-2 Timestamp Cards with GPS and lightning detectors were integrated to Pentium III PC-workstations running the CentOS linux operating system. The Boltek detector linux driver was compiled under CentOS, modified, and thoroughly tested. These PC-workstations with integrated lightning detectors were installed at five of the University of Puerto Rico (UPR) campuses distributed around the island of PR. The PC-workstations are left on permanently in order to monitor lightning activity at all times. Each is networked to their campus network-backbone permitting quasi-instantaneous data transfer to a central server at the UPR-Bayam n campus. Information generated by each lightning detector is managed by a C-program developed by us called the LDN-client. The LDN-client maintains an open connection to the central server operating the LDN-server program where data is sent real-time for analysis and archival. The LDN-client also manages the storing of data on the PC-workstation hard disk. The LDN-server software (also an in-house effort) analyses the data from each client and performs event triangulations. Time-of-arrival (TOA) and related hybrid algorithms, lightning-type and event discriminating routines are also implemented in the LDN-server software. We also have developed software to visually monitor lightning events in real-time from all clients and the triangulated events. We are currently monitoring and studying the spatial, temporal, and type distribution of lightning strikes associated with electrical storms and tropical cyclones in the vicinity of Puerto Rico.

Legault, Marc D.↗
NASA NTRS2004

Second-Generation Six-Limbed Experimental Robot

The figure shows the LEMUR II - the second generation of the Limbed Excursion Mechanical Utility Robot (LEMUR), which was described in "Six-Legged Experimental Robot" (NPO-20897), NASA Tech Briefs, Vol. 25, No. 12 (December 2001), page 58. The LEMUR II incorporates a number of improvements, including new features, that extend its capabilities beyond those of its predecessor, which is now denoted the LEMUR I. To recapitulate: the LEMUR I was a six-limbed robot for demonstrating robotic capabilities for assembly, maintenance, and inspection. The LEMUR I was designed to be capable of walking autonomously along a truss structure toward a mechanical assembly at a prescribed location and to perform other operations. The LEMUR I was equipped with stereoscopic video cameras and image-data-processing circuitry for navigation and mechanical operations. It was also equipped with a wireless modem, through which it could be commanded remotely. Upon arrival at a mechanical assembly, the LEMUR I would perform simple mechanical operations with one or both of its front limbs. It could also transmit images to a host computer. Each of the six limbs of the LEMUR I was operated independently. Each of the four rear limbs had three degrees of freedom (DOFs), while each of the front two limbs had four DOFs. The front two limbs were designed to hold, operate, and/or be integrated with tools. The LEMUR I included an onboard computer equipped with an assortment of digital control circuits, digital input/output circuits, analog-to-digital converters for input, and digital-to-analog (D/A) converters for output. Feedback from optical encoders in the limb actuators was utilized for closed-loop microcomputer control of the positions and velocities of the actuators. The LEMUR II incorporates the following improvements over the LEMUR I: a) The drive trains for the joints of the LEMUR II are more sophisticated, providing greater torque and accuracy. b) The six limbs are arranged symmetrically about a hexagonal body platform instead of in straight lines along the sides. This symmetrical arrangement is more conducive to omnidirectional movement in a plane. c) The number of degrees of freedom of each of the rear four limbs has been increased by one. Now, every limb has four degrees of freedom: three at the hip (or shoulder, depending on one s perspective) and one at the knee (or elbow, depending on one s perspective). d) Now every limb (instead of only the two front limbs) can perform operations. For this purpose, each limb is tipped with an improved quick-release mechanism for swapping of end-effector tools. e) New end-effector tools have been developed. These include an instrumented rotary driver that accepts all tool bits that have 0.125-in. (3.175-mm)-diameter shanks, a charge-coupled-device video camera, a super bright light-emitting diode for illuminating the work area of the robot, and a generic collet tool that can be quickly and inexpensively modified to accept any cylindrical object up to 0.5 in. (12.7 mm) in diameter. f) The stereoscopic cameras are mounted on a carriage that moves along a circular track, thereby providing for omnidirectional machine vision. g) The control software has been augmented with software that implements innovations reported in two prior NASA Tech Briefs articles: the HIPS algorithm ["Hybrid Image-Plane/Stereo Manipulation" (NPO-30492), Vol. 28, No. 7 (July 2004), page 55] and the CAMPOUT architecture ["An Architecture for Controlling Multiple Robots" (NPO-30345), Vol. 28, No. 10 (October 2004), page 65].

Kennedy, Brett↗
NASA NTRS1983

Analyses of large quasistatic deformations of inelastic bodies by a new hybrid-stress finite element algorithm - Applications

A new hybrid-stress finite element algorithm suitable for analyzing large quasistatic deformations of inelastic solids is presented and its feasibility and performance are demonstrated with examples. The algorithm provides extremely accurate bifurcation analysis which is stable with respect to variation in the finite element mesh, so long as the same type of element is used in every mesh. When the mesh element is varied, the result changes in a predictable manner. The method does not necessarily lead to an upper or lower bound for the critical load. An explicit forward gradient scheme is used to improve stability and is shown to be useful also for elongation-dominated deformations. The application of the method to the onset of necking in plane extension and to deformation and stress in plane extension of an elasticoviscous fluid with an array of cylindrical voids is given in detail.

Reed, K. W.↗
DOE OSTI2020

An Adaptive Optimizer for Measurement-Frugal Variational Algorithms

Variational hybrid quantum-classical algorithms (VHQCAs) have the potential to be useful in the era of near-term quantum computing. However, recently there has been concern regarding the number of measurements needed for convergence of VHQCAs. Here, we address this concern by investigating the classical optimizer in VHQCAs. We introduce a novel optimizer called individual Coupled Adaptive Number of Shots (iCANS). This adaptive optimizer frugally selects the number of measurements (i.e., number of shots) both for a given iteration and for a given partial derivative in a stochastic gradient descent. We numerically simulate the performance of iCANS for the variational quantum eigensolver and for variational quantum compiling, with and without noise. In all cases, and especially in the noisy case, iCANS tends to out-perform state-of-the-art optimizers for VHQCAs. We therefore believe this adaptive optimizer will be useful for realistic VHQCA implementations, where the number of measurements is limited.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

The potential of quantum annealing for rapid solution structure identification

Abstract The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing’s performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1997

Two Improved Algorithms for Envelope and Wavefront Reduction

Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficient 0(nlogn + m) time implementation of the Sloan algorithm, where n is the number of rows (vertices), and m is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler Reverse Cuthill-Mckee algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning.

Kumfert, Gary↗
DOE OSTI2025

A New Hybrid Quantum-Classical Algorithm for Solving the Unit Commitment Problem

Solving problems related to planning and operations of large-scale power systems is challenging on classical computers due to their inherent nature as mixed-integer and nonlinear problems. Quantum computing provides new avenues to approach these problems. We develop a hybrid quantum-classical algorithm for the Unit Commitment (UC) problem in power systems which aims at minimizing the total cost while optimally allocating generating units to meet the hourly demand of the power loads. The hybrid algorithm combines a variational quantum algorithm (VQA) with a classical Benders-type heuristic. The resulting algorithm computes approximate solutions to UC in three stages: i) a collection of UC vectors capable meeting the power demand with lowest possible operating costs is generated based on VQA; ii) a classical sequential least squares programming (SLSQP) routine is leveraged to find the optimal power level corresponding to a predetermined number of candidate vectors; iii) in the last stage, the approximate solution of UC along with generating units power level combination is given. To demonstrate the effectiveness of the presented method, three different systems with 3 generating units, 10 generating units, and 26 generating units were tested for different time periods. In addition, convergence of the hybrid quantum-classical algorithm for select time periods is proven out on IonQ's Forte system.

Aboumrad, Willie [IonQ, Inc]↗
DOE OSTI2021

Incorporating Valve Switching Losses Into a Static Optimal Control Algorithm for the Hybrid Hydraulic-Electric Architecture (HHEA)

The Hybrid Hydraulic-Electric Architecture (HHEA) has, in recent years, been proposed as an energy efficient alternative to conventional load-sensing architectures in mobile machines such as excavators and wheel-loaders. HHEA leverages the advantages of hydraulic power and electric power to eliminate throttling valves while also improving the energy and control performance of the system. The architecture utilizes a set of common pressure rails to provide a majority of power and and a small electric motor driven pump to modulate this power to meet the exact demand. Previous work has developed a computationally efficient Lagrange Multiplier approach for determining the optimal pressure rail selections that minimizes the energy losses in the system. The static model used considers only the energy use for each pressure rail selection but not the losses associated with the valves during the transition. This paper presents an approach to include the switching losses in the model and in the optimization procedure. To capture the switching losses, switching events between different rails and at various input and output flow rates were simulated with consideration of valve spool dynamics. A parameterized model that summarizes the losses is then obtained, allowing switching losses to be added to the previous energy analysis. The performance of the switching loss model was compared with reference data obtained from a high-fidelity simulation model. To incorporate the switching losses into optimal control algorithm, an efficient dynamic programming approach that prevents frequent switching is adopted in place of the Lagrange multiplier approach. The overall effect of switching losses on the energy consumption and optimal control decisions is presented. In general, switching losses contribute to about 9–10% of input energy.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2024

Improving the Concrete Crack Detection Process via a Hybrid Visual Transformer Algorithm

Inspections of concrete bridges across the United States represent a significant commitment of resources, given their biannual mandate for many structures. With a notable number of aging bridges, there is an imperative need to enhance the efficiency of these inspections. This study harnessed the power of computer vision to streamline the inspection process. Our experiment examined the efficacy of a state-of-the-art Visual Transformer (ViT) model combined with distinct image enhancement detector algorithms. We benchmarked against a deep learning Convolutional Neural Network (CNN) model. These models were applied to over 20,000 high-quality images from the Concrete Images for Classification dataset. Traditional crack detection methods often fall short due to their heavy reliance on time and resources. This research pioneers bridge inspection by integrating ViT with diverse image enhancement detectors, significantly improving concrete crack detection accuracy. Notably, a custom-built CNN achieves over 99% accuracy with substantially lower training time than ViT, making it an efficient solution for enhancing safety and resource conservation in infrastructure management. These advancements enhance safety by enabling reliable detection and timely maintenance, but they also align with Industry 4.0 objectives, automating manual inspections, reducing costs, and advancing technological integration in public infrastructure management.

42 ENGINEERING↗
NASA NTRS1990

A hybrid M-algorithm/sequential decoder for convolutional and trellis codes

The Viterbi Algorithm (VA) is optimum in the sense of being maximum likelihood for decoding codes with a trellis structure. However, since the VA is in fact an exhaustive search of the code trellis, the complexity of the VA grows exponentially with the constraint length upsilon. This limits its application to codes with small values of upsilon and relatively modest coding gains. The M-Algorithm (MA) is a limited search scheme which carries forward M paths in the trellis, all of the same length. All successors of the M paths are extended at the next trellis depth, and all but the best M of these are dropped. Since a limited search convolutional decoder will flounder indefinitely if one of the paths in storage is not the correct one, the data are usually transmitted in blocks. It has been shown that the performance of the MA approaches the VA at high signal to noise ratios (SNR's) with an M which is far less than the 2 sup upsilon states in the full trellis. Thus the MA can be used with larger values of upsilon, making larger coding gains possible at high SNR's. However, it still requires a relatively large fixed computational effort to achieve good performance.

Wang, Fu-Quan↗
DOE OSTI2022

Utilizing Reinforcement Learning to Continuously Improve a Primitive-Based Motion Planner

We report in this paper describes how the performance of motion primitive-based planning algorithms can be improved using reinforcement learning. Specifically, we describe and evaluate a framework that autonomously improves the performance of a primitive-based motion planner. The improvement process consists of three phases: exploration, extraction, and reward updates. This process can be iterated continuously to provide successive improvement. The exploration step generates new trajectories, and the extraction step identifies new primitives from these trajectories. These primitives are then used to update rewards for continued exploration. This framework required novel shaping rewards, development of a primitive extraction algorithm, and modification of the Hybrid A* algorithm. The framework is tested on a navigation task using a nonlinear F-16 model. The framework autonomously added 91 motion primitives to the primitive library and reduced average path cost by 21.6 seconds, or 35.75% of the original cost. The learned primitives are applied to an obstacle field navigation task, which was not used in training, and reduced path cost by 16.3 seconds, or 24.1%. Additionally, two heuristics for the modified Hybrid A* algorithm are designed to improve effective branching factor.

42 ENGINEERING↗
NASA NTRS2007

Hybrid-dual-fourier tomographic algorithm for a fast three-dimensionial optical image reconstruction in turbid media

A reconstruction technique for reducing computation burden in the 3D image processes, wherein the reconstruction procedure comprises an inverse and a forward model. The inverse model uses a hybrid dual Fourier algorithm that combines a 2D Fourier inversion with a 1D matrix inversion to thereby provide high-speed inverse computations. The inverse algorithm uses a hybrid transfer to provide fast Fourier inversion for data of multiple sources and multiple detectors. The forward model is based on an analytical cumulant solution of a radiative transfer equation. The accurate analytical form of the solution to the radiative transfer equation provides an efficient formalism for fast computation of the forward model.

Alfano, Robert R.↗
NASA NTRS1996

Induction as Knowledge Integration

Two key issues for induction algorithms are the accuracy of the learned hypothesis and the computational resources consumed in inducing that hypothesis. One of the most promising ways to improve performance along both dimensions is to make use of additional knowledge. Multi-strategy learning algorithms tackle this problem by employing several strategies for handling different kinds of knowledge in different ways. However, integrating knowledge into an induction algorithm can be difficult when the new knowledge differs significantly from the knowledge the algorithm already uses. In many cases the algorithm must be rewritten. This paper presents Knowledge Integration framework for Induction (KII), a KII, that provides a uniform mechanism for integrating knowledge into induction. In theory, arbitrary knowledge can be integrated with this mechanism, but in practice the knowledge representation language determines both the knowledge that can be integrated, and the costs of integration and induction. By instantiating KII with various set representations, algorithms can be generated at different trade-off points along these dimensions. One instantiation of KII, called RS-KII, is presented that can implement hybrid induction algorithms, depending on which knowledge it utilizes. RS-KII is demonstrated to implement AQ-11, as well as a hybrid algorithm that utilizes a domain theory and noisy examples. Other algorithms are also possible.

Smith, Benjamin D.↗