Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic 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 433 records · Page 24

A diagnosis system using object-oriented fault tree models

Spaceborne computing systems must provide reliable, continuous operation for extended periods. Due to weight, power, and volume constraints, these systems must manage resources very effectively. A fault diagnosis algorithm is described which enables fast and flexible diagnoses in the dynamic distributed computing environments planned for future space missions. The algorithm uses a knowledge base that is easily changed and updated to reflect current system status. Augmented fault trees represented in an object-oriented form provide deep system knowledge that is easy to access and revise as a system changes. Given such a fault tree, a set of failure events that have occurred, and a set of failure events that have not occurred, this diagnosis system uses forward and backward chaining to propagate causal and temporal information about other failure events in the system being diagnosed. Once the system has established temporal and causal constraints, it reasons backward from heuristically selected failure events to find a set of basic failure events which are a likely cause of the occurrence of the top failure event in the fault tree. The diagnosis system has been implemented in common LISP using Flavors.

Iverson, David L.↗

Probabilistic Calibration of Expensive Models using Efficiently Trained Surrogates

Calibration of computational models in the presence of uncertainty is often cast as a Bayesian inference problem and solved via sampling methods, e.g., Markov chain Monte Carlo. When the computational model is expensive, this task becomes intractable due to the large number of samples required to accurately estimate the posterior distribution of the calibration parameters. A popular solution to this problem is to use machine learning to develop a faster-to-evaluate, lower-fidelity substitute for the original model to serve as a surrogate while solving the inference problem. Although considered an offline cost, generating training data to construct this surrogate model can still be an expensive task in practice. An active learning algorithm is presented that focuses training on improving surrogate accuracy specifically in and around the bulk of the posterior distribution, as this is where the model is exercised during calibration. Candidate samples are drawn from families of distributions related to an approximation of the posterior. The sample maximizing predictive variance is then selected for evaluation by the original computational model, yielding a label for the training point. Iterating this approach increases efficiency relative to space filling designs (e.g., Latin hypercube sampling) by avoiding low probability points. Practical considerations are discussed, including the benefits of using a sequential Monte Carlo sampling approach, convergence heuristics, and the importance of both exploration and exploitation given that the true posterior is unknown a priori.

uncertainty quantification↗

Practical and Optimal Sequential Bayesian Experimental Design for Complex Systems Incorporating Human Experimenter Preferences (Final Scientific/Technical Report)

Experiments are indispensable for developing models of complex systems. Carefully designed experiments can provide substantial savings for these expensive data-acquisition opportunities. However, designs based on heuristics are often suboptimal for systems with multiphysics, nonlinear dynamics, and uncertain and noisy environments. Optimal experimental design, while leveraging predictive models, seeks to systematically quantify and maximize the value of experiments. In this project, we focused on the design of multiple experiments, where current approaches are largely suboptimal: batch-design does not adapt to new data acquired during the experiment campaign (no feedback), and greedy/myopic design ignores future dynamics and consequences (no lookahead). We developed the mathematical framework and computational methods for sequential optimal experimental design (sOED) for complex systems. We enabled tractable model-based sOED in a rigorous manner through novel algorithms based on reinforcement learning, and investigated the effects of human experimenters on the design process. Our methods are fully Bayesian, able to quantify and update uncertainty in a principled manner. The traits aimed by our approach—mathematical rigor and optimality, human effects and uncertainty quantification, computational practicality—are crucial for elevating the standards of artificial intelligence (AI) to support decision-making in scientific domains, and contribute toward trust and realistic adoption of AI in experimental design practice.

97 MATHEMATICS AND COMPUTING↗

A Component-Sizing Methodology for a Hybrid Electric Vehicle Using an Optimization Algorithm

Many leading companies in the automotive industry have been putting tremendous effort into developing new powertrains and technologies to make their products more energy efficient. Evaluating the fuel economy benefit of a new technology in specific powertrain systems is straightforward; and, in an early concept phase, obtaining a projection of energy efficiency benefits from new technologies is extremely useful. However, when carmakers consider new technology or powertrain configurations, they must deal with a trade-off problem involving factors such as energy efficiency and performance, because of the complexities of sizing a vehicle’s powertrain components, which directly affect its energy efficiency and dynamic performance. As powertrains of modern vehicles become more complicated, even more effort is required to design the size of each component. This study presents a component-sizing process based on the forward-looking vehicle simulator “Autonomie” and the optimization algorithm “POUNDERS”; the supervisory control strategy based on Pontryagin’s Minimum Principle (PMP) assures sufficient computational system efficiency. We tested the process by applying it to a single power-split hybrid electric vehicle to determine optimal values of gear ratios and each component size, where we defined the optimization problem as minimizing energy consumption when the vehicle’s dynamic performance is given as a performance constraint. The suggested sizing process will be helpful in determining optimal component sizes for vehicle powertrain to maximize fuel efficiency while dynamic performance is satisfied. Indeed, this process does not require the engineer’s intuition or rules based on heuristics required in the rule-based process.

33 ADVANCED PROPULSION SYSTEMS↗

Automated clustering-based workload characterization

The demands placed on the mass storage systems at various federal agencies and national laboratories are continuously increasing in intensity. This forces system managers to constantly monitor the system, evaluate the demand placed on it, and tune it appropriately using either heuristics based on experience or analytic models. Performance models require an accurate workload characterization. This can be a laborious and time consuming process. It became evident from our experience that a tool is necessary to automate the workload characterization process. This paper presents the design and discusses the implementation of a tool for workload characterization of mass storage systems. The main features of the tool discussed here are: (1)Automatic support for peak-period determination. Histograms of system activity are generated and presented to the user for peak-period determination; (2) Automatic clustering analysis. The data collected from the mass storage system logs is clustered using clustering algorithms and tightness measures to limit the number of generated clusters; (3) Reporting of varied file statistics. The tool computes several statistics on file sizes such as average, standard deviation, minimum, maximum, frequency, as well as average transfer time. These statistics are given on a per cluster basis; (4) Portability. The tool can easily be used to characterize the workload in mass storage systems of different vendors. The user needs to specify through a simple log description language how the a specific log should be interpreted. The rest of this paper is organized as follows. Section two presents basic concepts in workload characterization as they apply to mass storage systems. Section three describes clustering algorithms and tightness measures. The following section presents the architecture of the tool. Section five presents some results of workload characterization using the tool.Finally, section six presents some concluding remarks.

Pentakalos, Odysseas I.↗

Advances in analytical chemistry

Implementation of computer programs based on multivariate statistical algorithms makes possible obtaining reliable information from long data vectors that contain large amounts of extraneous information, for example, noise and/or analytes that we do not wish to control. Three examples are described. Each of these applications requires the use of techniques characteristic of modern analytical chemistry. The first example, using a quantitative or analytical model, describes the determination of the acid dissociation constant for 2,2'-pyridyl thiophene using archived data. The second example describes an investigation to determine the active biocidal species of iodine in aqueous solutions. The third example is taken from a research program directed toward advanced fiber-optic chemical sensors. The second and third examples require heuristic or empirical models.

Arendale, W. F.↗

Empirical results on scheduling and dynamic backtracking

At the Honeywell Technology Center (HTC), we have been working on a scheduling problem related to commercial avionics. This application is large, complex, and hard to solve. To be a little more concrete: 'large' means almost 20,000 activities, 'complex' means several activity types, periodic behavior, and assorted types of temporal constraints, and 'hard to solve' means that we have been unable to eliminate backtracking through the use of search heuristics. At this point, we can generate solutions, where solutions exist, or report failure and sometimes why the system failed. To the best of our knowledge, this is among the largest and most complex scheduling problems to have been solved as a constraint satisfaction problem, at least that has appeared in the published literature. This abstract is a preliminary report on what we have done and how. In the next section, we present our approach to treating scheduling as a constraint satisfaction problem. The following sections present the application in more detail and describe how we solve scheduling problems in the application domain. The implemented system makes use of Ginsberg's Dynamic Backtracking algorithm, with some minor extensions to improve its utility for scheduling. We describe those extensions and the performance of the resulting system. The paper concludes with some general remarks, open questions and plans for future work.

Boddy, Mark S.↗

Avoiding space robot collisions utilizing the NASA/GSFC tri-mode skin sensor

Sensor based robot motion planning research has primarily focused on mobile robots. Consider, however, the case of a robot manipulator expected to operate autonomously in a dynamic environment where unexpected collisions can occur with many parts of the robot. Only a sensor based system capable of generating collision free paths would be acceptable in such situations. Recently, work in this area has been reported in which a deterministic solution for 2DOF systems has been generated. The arm was sensitized with 'skin' of infra-red sensors. We have proposed a heuristic (potential field based) methodology for redundant robots with large DOF's. The key concepts are solving the path planning problem by cooperating global and local planning modules, the use of complete information from the sensors and partial (but appropriate) information from a world model, representation of objects with hyper-ellipsoids in the world model, and the use of variational planning. We intend to sensitize the robot arm with a 'skin' of capacitive proximity sensors. These sensors were developed at NASA, and are exceptionally suited for the space application. In the first part of the report, we discuss the development and modeling of the capacitive proximity sensor. In the second part we discuss the motion planning algorithm.

Prinz, F. B.↗

Aircraft Turbofan Engine Health Estimation Using Constrained Kalman Filtering

Kalman filters are often used to estimate the state variables of a dynamic system. However, in the application of Kalman filters some known signal information is often either ignored or dealt with heuristically. For instance, state variable constraints (which may be based on physical considerations) are often neglected because they do not fit easily into the structure of the Kalman filter. This paper develops an analytic method of incorporating state variable inequality constraints in the Kalman filter. The resultant filter is a combination of a standard Kalman filter and a quadratic programming problem. The incorporation of state variable constraints increases the computational effort of the filter but significantly improves its estimation accuracy. The improvement is proven theoretically and shown via simulation results obtained from application to a turbofan engine model. This model contains 16 state variables, 12 measurements, and 8 component health parameters. It is shown that the new algorithms provide improved performance in this example over unconstrained Kalman filtering.

Simon, Dan↗

Domain-specific compilers for dynamic simulations of quantum materials on quantum computers

Abstract Simulation of the dynamics of quantum materials is emerging as a promising scientific application for noisy intermediate-scale quantum (NISQ) computers. Due to their high gate-error rates and short decoherence times, however, NISQ computers can only produce high-fidelity results for those quantum circuits smaller than some given circuit size. Dynamic simulations, therefore, pose a challenge as current algorithms produce circuits that grow in size with each subsequent time-step of the simulation. This underscores the crucial role of quantum circuit compilers to produce executable quantum circuits of minimal size, thereby maximizing the range of physical phenomena that can be studied within the NISQ fidelity budget. Here, we present two domain-specific (DS) quantum circuit compilers for the Rigetti and IBM quantum computers, specifically designed to compile circuits simulating dynamics under a special class of time-dependent Hamiltonians. The compilers outperform state-of-the-art general-purpose compilers in terms of circuit size reduction by around 25%–30% as well as wall-clock compilation time by around 40% (dependent on system size and simulation time-step). Drawing on heuristic techniques commonly used in artificial intelligence, both compilers scale well with simulation time-step and system size. Code for both compilers is open-source and packaged into a full-stack quantum simulation software with tutorials included for ease of use for future researchers wishing to perform dynamic simulations of quantum materials on quantum computers. As our DS compilers provide significant improvements in both compilation time and simulation fidelity, they provide a building block for accelerating progress toward physical quantum supremacy.

Physics↗

The numerical solution of the Helmholtz equation for wave propagation problems in underwater acoustics

The Helmholtz Equation (-delta-K(2)n(2))u=0 with a variable index of refraction, n, and a suitable radiation condition at infinity serves as a model for a wide variety of wave propagation problems. A numerical algorithm was developed and a computer code implemented that can effectively solve this equation in the intermediate frequency range. The equation is discretized using the finite element method, thus allowing for the modeling of complicated geometrices (including interfaces) and complicated boundary conditions. A global radiation boundary condition is imposed at the far field boundary that is exact for an arbitrary number of propagating modes. The resulting large, non-selfadjoint system of linear equations with indefinite symmetric part is solved using the preconditioned conjugate gradient method applied to the normal equations. A new preconditioner is developed based on the multigrid method. This preconditioner is vectorizable and is extremely effective over a wide range of frequencies provided the number of grid levels is reduced for large frequencies. A heuristic argument is given that indicates the superior convergence properties of this preconditioner.

Bayliss, A.↗

Safe Deep Reinforcement Learning for Robust Frequency and Voltage-Constrained Networked Microgrid Restoration

Here, this paper proposes a safe soft actor-critic reinforcement learning (RL) algorithm–based controller for networked microgrid restoration. It formulates the post black-start start as a finite-horizon constrained Markov decision process. The RL agent co-optimizes real and reactive power set-points for both grid-forming and grid-following inverters under explicit voltage and frequency constraints, while enforcing proper power sharing via the Mean Active Power Sharing Index (MPSI) and Mean Reactive Power Sharing Index (MQSI). Numerical results obtained on the IEEE 123-bus distribution system show that the proposed method achieves a mean voltage build-up time of 0.01 s without breaching the 5% sharing-violation budget under various load scenarios, considering MPSI and MQSI indices. These findings demonstrate that the proposed method yields fast and safe black-start schedules without resorting to heuristic penalties.

Selim, Alaa [Dartmouth College, Hanover, NH (Unite↗

Variational Quantum Linear Solver

Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the re quired circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare |x$\rangle$ such that A|x$\rangle$ ∝ |b$\rangle$. We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C $⩾$ ϵ 2 /κ 2 , where C is the VQLS cost function and κ is the condition number of A. We present efficient quantum circuits to estimate C, while providing evidence for the classical hardness of its estimation. Using Rigetti’s quantum computer, we success fully implement VQLS up to a problem size of 1024 × 1024. Finally, we numerically solve nontrivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ, κ, and the system size N.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

High-Performance Computing Optimization for Aladyn – Adaptive Neural Network Molecular Dynamics Mini-Application

This report provides a description and performance evaluation of the optimization techniques for high performance computing (HPC) implementation of the open source Computational Materials mini-application Aladyn (https://github.com/nasa/aladyn). Aladyn is a basic molecular dynamics code written in FORTRAN 2003, which is designed to demonstrate the use of adaptive neural networks (ANNs) in atomistic simulations. The role of ANNs is to efficiently reproduce the very complex energy landscape resulting from the atomic interactions in materials with the accuracy of the more expensive quantum mechanics-based calculations. The ANN is trained on a large set of atomic structures calculated using the density functional theory (DFT) method. While achieving orders of magnitude faster computational performance than DFT, the ANN-based approach was still very computationally demanding compared to the conventional approach of using empirically fitted energy functions. After its initial development, Aladyn was evaluated and optimized by experts at the NASA Advanced Supercomputing (NAS) division to exploit modern supercomputer architectures. The code has been optimized for execution on multicore central processing units (CPUs), including Intel® Skylake microarchitecture, and on graphic accelerators, such as Nvidia® V100 graphic processing units (GPUs), using Open Multi-Processing (OpenMP) and Open Accelerators (OpenACC) programming interfaces. The optimization achieved a speedup of 4.7 times the baseline version on CPU performance and an additional 2.4 times on CPU+GPU performance. Atomistic computer simulations are a fundamental tool in materials research to model material properties form physics-based first principles. Atomic interaction, governed by Quantum Mechanics (QM) require sophisticated and highly computationally demanding mathematical models to calculate [1]. Classical methods use approximate functional forms, empirically fitted through a set of variable parameters to emulate atomic energies as direct functions of atomic coordinates [2]. While empirical potentials are computationally much simpler, allowing simulations of large-scale systems of up to a trillion (1012) atoms [3], they are substantially less accurate compared to quantum calculations and applicable only to very specific atomic configurations or predefined crystallographic phases. A recently suggested approach is to use heuristic machine learning methods [4], such as those based on Adaptive Neural Networks (ANNs) to predict atomic energies, after being trained on a sufficiently large database of QM-calculated structures [5,6]. This approach reduces significantly the computational complexity, allowing for simulations of orders of magnitude larger systems compared to QM-based methods without compromising accuracy. Still, compared to classical methods using empirical energy functions, ANN methods remain two- to three orders of magnitude more computationally demanding. Hence, the computational cost of simulations, together with the need for extensive training of ANNs, still makes the practical implementation of ANN-based methods quite challenging. The purpose of the Aladyn mini-application software [7], available as open source at https://github.com/nasa/aladyn, is to be a testbed for exploring possible optimization strategies to develop highly scalable parallel algorithms for ANN-based atomistic simulations. Aladyn is aimed at utilizing the architecture of the high-end modern highperformance computing (HPC) hardware based on multicore central processing units (CPUs) equipped with graphic processing unit (GPU) accelerators. Specifically, the goal is to optimize the performance on a single HPC compute node, before implementing scaling to multi-node parallelization using message passing interface (MPI). At the same time, the open source code of Aladyn can serve as a training model for students and professors in academia.

Yamakov, Vesselin I.↗

Enhanced Control, Optimization, and Integration of Distributed Energy Applications (ECO-IDEA)

With support from the U.S. Department of Energy Solar Energy Technologies Office, the National Renewable Energy Laboratory (NREL) partnered with Xcel Energy, Schneider Electric, Varentec, and Electric Power Research Institute (EPRI) to meet the goals of the Enabling Extreme Real-Time Grid Integration of Solar Energy (ENERGISE) program. This project developed and validated an innovative data-enhanced hierarchical control architecture that enables the efficient, reliable, resilient, and secure operation of future distribution systems with a high penetration of distributed energy resources like solar energy. The architecture enables a hybrid control approach where a centralized control layer is complemented by distributed control algorithms for solar inverters and autonomous control of grid edge devices. It is fully interoperable and includes all the cybersecurity aspects necessary for reliable and secure system operation. The hybrid approach can seamlessly integrate multiple voltage-regulation technologies, both at central and grid-edge levels, which enables reliable and efficient system operation in the face of unpredictable conditions. The overarching goal of the Eco-Idea project is to develop, validate, and deploy a unique and innovative Data-Enhanced Hierarchical Control (DEHC) architecture that comprehensively addresses the formidable challenges associated with proliferation of high penetration of distributed PV such as reverse power flows, transients from variability of PV systems, feeder load balancing, and voltage stability. These issues are exposing the weaknesses of existing grid operations and controls - including, but not limited to, lack of grid situational awareness, heuristic and slow-acting control actions, latency of control for emergency situations, and points of failure in communications. The proposed architecture will comprehensively resolve the deficiencies of current operational settings - where monitoring and control solutions proposed across industry and academia may not be interoperable and may not coexist in the same system - and will enable an efficient, reliable, resilient, and secure operation of future distribution systems with penetration of solar energy well beyond current limits. The DEHC architecture was developed and validated rigorously through hardware-in-loop simulations in the laboratory environment and deployed on the field.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Noise-induced barren plateaus in variational quantum algorithms

Abstract Variational Quantum Algorithms (VQAs) may be a path to quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) computers. A natural question is whether noise on NISQ devices places fundamental limitations on VQA performance. We rigorously prove a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau (i.e., vanishing gradient). Specifically, for the local Pauli noise considered, we prove that the gradient vanishes exponentially in the number of qubits n if the depth of the ansatz grows linearly with n . These noise-induced barren plateaus (NIBPs) are conceptually different from noise-free barren plateaus, which are linked to random parameter initialization. Our result is formulated for a generic ansatz that includes as special cases the Quantum Alternating Operator Ansatz and the Unitary Coupled Cluster Ansatz, among others. For the former, our numerical heuristics demonstrate the NIBP phenomenon for a realistic hardware noise model.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Towards large-scale quantum optimization solvers with few qubits

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $m={{\mathcal{O}}}({n}^{k})$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m , respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Improving Search Properties in Genetic Programming

With the advancing computer processing capabilities, practical computer applications are mostly limited by the amount of human programming required to accomplish a specific task. This necessary human participation creates many problems, such as dramatically increased cost. To alleviate the problem, computers must become more autonomous. In other words, computers must be capable to program/reprogram themselves to adapt to changing environments/tasks/demands/domains. Evolutionary computation offers potential means, but it must be advanced beyond its current practical limitations. Evolutionary algorithms model nature. They maintain a population of structures representing potential solutions to the problem at hand. These structures undergo a simulated evolution by means of mutation, crossover, and a Darwinian selective pressure. Genetic programming (GP) is the most promising example of an evolutionary algorithm. In GP, the structures that evolve are trees, which is a dramatic departure from previously used representations such as strings in genetic algorithms. The space of potential trees is defined by means of their elements: functions, which label internal nodes, and terminals, which label leaves. By attaching semantic interpretation to those elements, trees can be interpreted as computer programs (given an interpreter), evolved architectures, etc. JSC has begun exploring GP as a potential tool for its long-term project on evolving dextrous robotic capabilities. Last year we identified representation redundancies as the primary source of inefficiency in GP. Subsequently, we proposed a method to use problem constraints to reduce those redundancies, effectively reducing GP complexity. This method was implemented afterwards at the University of Missouri. This summer, we have evaluated the payoff from using problem constraints to reduce search complexity on two classes of problems: learning boolean functions and solving the forward kinematics problem. We have also developed and implemented methods to use additional problem heuristics to fine-tune the searchable space, and to use typing information to further reduce the search space. Additional improvements have been proposed, but they are yet to be explored and implemented.

Janikow, Cezary Z.↗