Search NASA⌕ Search

SEARCH · Search NASA

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 505 records · Page 28

Autonomously Calibrating a Quadrupole Mass Spectrometer

A computer program autonomously manages the calibration of a quadrupole ion mass spectrometer intended for use in monitoring concentrations and changes in concentrations of organic chemicals in the cabin air of the International Space Station. The instrument parameters calibrated include the voltage on a channel electron multiplier, a discriminator threshold, and an ionizer current. Calibration is achieved by analyzing the mass spectrum obtained while sweeping the parameter ranges in a heuristic procedure, developed by mass spectrometer experts, that involves detection of changes in signal trends that humans can easily recognize but cannot necessarily be straightforwardly codified in an algorithm. The procedure includes calculation of signal-to-noise ratios, signal-increase rates, and background-noise-increase rates; finding signal peaks; and identifying peak patterns. The software provides for several recovery-from-error scenarios and error-handling schemes. The software detects trace amounts of contaminant gases in the mass spectrometer and notifies associated command- and-data-handling software to schedule a cleaning. Furthermore, the software autonomously analyzes the mass spectrum to determine whether the parameters of a radio-frequency ramp waveform are set properly so that the peaks of the mass spectrum are at expected locations.

Lee, Seungwon↗

A Convex Guidance Algorithm for Formation Reconfiguration

In this paper, a reconfiguration guidance algorithm for formation flying spacecraft is presented. The formation reconfiguration guidance problem is first formulated as a continuous-time minimum-fuel or minimum-energy optimal control problem with collision avoidance and control constraints. The optimal control problem is then discretized to obtain a finite dimensional parameter optimization problem. In this formulation, the collision avoidance constraints are imposed via separating planes between each pair of spacecraft. A heuristic is introduced to choose these separating planes that leads to the convexification of the collision avoidance constraints. Additionally, convex constraints are imposed to guarantee that no collisions occur between discrete time samples. The resulting finite dimensional optimization problem is a second order cone program, for which standard algorithms can compute the global optimum with deterministic convergence and a prescribed level of accuracy. Consequently, the formation reconfiguration algorithm can be implemented onboard a spacecraft for real-time operations.

formation reconfiguration↗

Biomimetic model-based advanced control strategy integrated with multi-agent optimization for nonlinear chemical processes

Here, a novel framework is proposed for integrating biomimetic-based advanced control and multi-agent optimization approaches for nonlinear chemical process applications. In particular, a Biologically-Inspired Optimal Control Strategy, denoted as BIO-CS, is combined with multi-agent optimization (MAO) techniques to provide optimal solutions for dynamic systems. In this combined framework, the BIO-CS algorithm employs gradient-based optimal control solvers for the intermediate problems associated with the leader-follower agents’ local interactions. Also, the MAO uses the capabilities of heuristic-based optimization techniques by sharing process information to obtain optimal operating setpoints for the controller considering an overall process objective. The applicability of the proposed method is demonstrated using a nonlinear, multivariable, process model of a fermentation system. Specifically, the optimal operating points are computed by the MAO implementation for setpoint tracking, trajectory tracking and plant-model mismatch scenarios for BIO-CS application. Results of the developed framework are compared to a gradient-based Sequential Quadratic Programming (SQP) technique and a classical proportional-integral (PI) controller in terms of optimization and control studies, respectively. As an additional contribution, BIO-CS is also cast as a model predictive controller (MPC) for the first time and compared to the agent-based BIO-CS approach in terms of computational time and tracking error. Closed-loop control results show up to 46% improvement in tracking performance during transient for the multi-agent BIO-CS when compared to BIO-CS as MPC for additional computational expense. The obtained results illustrate the capabilities of this novel integrated framework including BIO-CS as MPC to achieve desired nonlinear system performance for various scenarios.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Application of a directed search to global steering of single gimballed CMGs

A guided depth-first search that manages null motion about torque-producing trajectories calculated with a singularity-robust (SR) inverse is proposed as a practical feedforward steering law that can globally avoid (or minimize the impact of) singular states in minimally-redundant single gimballed CMG systems. Cost and heuristic functions are defined to guide the search procedure in improving CMG trajectories. On-orbit implementation of the steering law is proposed as an extension to momentum management algorithms. A set of simulation examples is presented, illustrating the search performance for a 4-CMG pyramid-mounted array. Sensitivities of feedforward gimbal trajectories are examined in the presence of unmodeled disturbances, and techniques are proposed for avoiding excessive divergence.

Paradiso, Joseph A.↗

An architecture for the development of real-time fault diagnosis systems using model-based reasoning

Presented here is an architecture for implementing real-time telemetry based diagnostic systems using model-based reasoning. First, we describe Paragon, a knowledge acquisition tool for offline entry and validation of physical system models. Paragon provides domain experts with a structured editing capability to capture the physical component's structure, behavior, and causal relationships. We next describe the architecture of the run time diagnostic system. The diagnostic system, written entirely in Ada, uses the behavioral model developed offline by Paragon to simulate expected component states as reflected in the telemetry stream. The diagnostic algorithm traces causal relationships contained within the model to isolate system faults. Since the diagnostic process relies exclusively on the behavioral model and is implemented without the use of heuristic rules, it can be used to isolate unpredicted faults in a wide variety of systems. Finally, we discuss the implementation of a prototype system constructed using this technique for diagnosing faults in a science instrument. The prototype demonstrates the use of model-based reasoning to develop maintainable systems with greater diagnostic capabilities at a lower cost.

Hall, Gardiner A.↗

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Advanced Interactive Display Formats for Terminal Area Traffic Control

This research project deals with an on-line dynamic method for automated viewing parameter management in perspective displays. Perspective images are optimized such that a human observer will perceive relevant spatial geometrical features with minimal errors. In order to compute the errors at which observers reconstruct spatial features from perspective images, a visual spatial-perception model was formulated. The model was employed as the basis of an optimization scheme aimed at seeking the optimal projection parameter setting. These ideas are implemented in the context of an air traffic control (ATC) application. A concept, referred to as an active display system, was developed. This system uses heuristic rules to identify relevant geometrical features of the three-dimensional air traffic situation. Agile, on-line optimization was achieved by a specially developed and custom-tailored genetic algorithm (GA), which was to deal with the multi-modal characteristics of the objective function and exploit its time-evolving nature.

Grunwald, Arthur J.↗

Advanced Interactive Display Formats for Terminal Area Traffic Control

This research project deals with an on-line dynamic method for automated viewing parameter management in perspective displays. Perspective images are optimized such that a human observer will perceive relevant spatial geometrical features with minimal errors. In order to compute the errors at which observers reconstruct spatial features from perspective images, a visual spatial-perception model was formulated. The model was employed as the basis of an optimization scheme aimed at seeking the optimal projection parameter setting. These ideas are implemented in the context of an air traffic control (ATC) application. A concept, referred to as an active display system, was developed. This system uses heuristic rules to identify relevant geometrical features of the three-dimensional air traffic situation. Agile, on-line optimization was achieved by a specially developed and custom-tailored genetic algorithm (GA), which was to deal with the multi-modal characteristics of the objective function and exploit its time-evolving nature.

Grunwald, Arthur J.↗

Alternative mixed integer linear programming optimization for joint job scheduling and data allocation in grid computing

This paper presents a novel approach to the joint optimization of job scheduling and data allocation in grid computing environments. We formulate this joint optimization problem as a mixed integer quadratically constrained program. To tackle the nonlinearity in the constraint, we alternatively fix a subset of decision variables and optimize the remaining ones via Mixed Integer Linear Programming (MILP). We solve the MILP problem at each iteration via an off-the-shelf MILP solver. Our experimental results show that our method significantly outperforms existing heuristic methods, employing either independent optimization or joint optimization strategies. We have also verified the generalization ability of our method over grid environments with various sizes and its high robustness to the algorithm setting.

97 MATHEMATICS AND COMPUTING↗

Cost function dependent barren plateaus in shallow parametrized quantum circuits

Variational quantum algorithms (VQAs) optimize the parameters θ of a parametrized quantum circuit V(θ) to minimize a cost function C. While VQAs may enable practical applications of noisy quantum computers, they are nevertheless heuristic methods with unproven scaling. Here, we rigorously prove two results, assuming V(θ) is an alternating layered ansatz composed of blocks forming local 2-designs. Our first result states that defining C in terms of global observables leads to exponentially vanishing gradients (i.e., barren plateaus) even when V(θ) is shallow. Hence, several VQAs in the literature must revise their proposed costs. On the other hand, our second result states that defining C with local observables leads to at worst a polynomially vanishing gradient, so long as the depth of V(θ) is Ο(logn). Our results establish a connection between locality and trainability. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.

97 MATHEMATICS AND COMPUTING↗

Pressurized Water Reactor Gadolinia Pin Location Optimization

This report presents the results of lattice optimization studies performed to find optimum locations for gadolinia burnable absorber (BA) rods in pressurized water reactor (PWR) lattice fuel designs. Initial excess reactivity suppression allows core designers to further improve operational economics by extending cycle length. Gadolinia BAs are commonly used in boiling water reactor assembly designs for this purpose. In recent years, gadolinia absorbers have been used in PWR designs owing to their longer effectiveness for reactivity suppression compared with common BAs used in PWR assemblies. This report examines the optimum gadolinia pin placement in 17 × 17 PWR lattices at different fuel and gadolinia concentrations for optimized lattice performance, using the SCALE/Polaris lattice physics code. The completed work is continuation of the Light Water Reactor LEU+ Lattice Optimization (ORNL/TM-2021/2366) project. An optimization driver called the metaheuristic optimization tool (MOT) is used to automate domain space exploration and optimization of the lattice designs. Heuristics from previous light-water reactor (LWR) lattice optimization studies were used to construct the objective function and define the domain space for optimization. This work successfully demonstrated that the optimization algorithms of MOT can generate feasible, nonproprietary PWR lattice designs with gadolinia.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

A low-communication, parallel algorithm for solving PDEs based on range decomposition

This work proposes a new, low-communication algorithm for solving PDEs on massively parallel computers. The range decomposition (RD) algorithm exposes coarse-grain parallelism by applying nested iteration and adaptive mesh refinement locally before performing a global communication step. Just a few such steps are observed to be sufficient to obtain accuracy within a small multiple of discretization error. The target applications are petascale and exascale machines, where hierarchical parallelism is required and traditional parallel numerical PDE communication patterns are costly because of message latency. The RD algorithm uses a partition of unity to equally distribute the error, and thus, the work. The computational advantages of this approach are that the decomposed problems can be solved in parallel without any communication until the partitioned solutions are summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. This paper introduces the method and explains the details of the communication step. Two performance models are developed, showing that the latency cost associated with a traditional parallel implementation of nested iteration is proportional to log(P) 2 , whereas the RD method reduces the communication latency to log(P), while maintaining similar bandwidth costs. Numerical results for two problems, Laplace and advection diffusion, demonstrate the enhanced performance, and a heuristic argument explains why the method converges quickly.

97 MATHEMATICS AND COMPUTING↗

Application of stochastic optimization to nuclear power plant asset management decisions

We describe the development and application of stochastic optimization models and algorithms to address an issue of critical importance in the strategic allocation of resources; namely, the selection of a portfolio of capital investment projects under the constraints of a limited and uncertain budget. This issue is significant and one that faces decision-makers across all industries. The objective of this strategic decision process is generally self evident - to maximize the value obtained from the portfolio of selected projects (with value usually measured in terms of the portfolio's net present value). However, heretofore, many organizations have developed processes to make these investment decisions using simplistic rule-based rank-ordering schemes. This approach has the significant limitation of not accounting for the (often large) uncertainties in the costs or economic benefits associated with the candidate projects or in the uncertainties in the actual funds available to be expended over the projected period of time. As a result, the simple heuristic approaches that typically are employed in industrial practice generate outcomes that are non-optimal and do not achieve the level of benefits intended. In this paper we describe the results of research performed to utilize stochastic optimization models and algorithms to address this limitation by explicitly incorporating the evaluation of uncertainties in the analysis and decision making process. (authors)

97 MATHEMATICS AND COMPUTING↗

Fast Active-Set Thresholding Method for Nonnegative Least Squares

Nonnegative Least Squares (NNLS) is a fundamental constrained optimization problem encountered in many applications such as image deblurring, signal processing, nonnegative matrix factorization, magnetic microscopy, and hyperspectral imaging. Active-set based methods are a common class of algorithms for solving NNLS which identify the optimal variable set of the NNLS solution. They do so by iteratively solving a series of unconstrained least squares problems, identifying which variables violate the nonnegativity constraints, and then swapping variables in/out of consideration until the optimal set of variables is found. Several variations improving upon this method exist in the literature. In this work, we propose an active-set swap heuristic which further improves upon existing active-set based methods for NNLS. Our optimizations are based upon adding multiple variables to the passive set within a threshold of the smallest gradient value and removing variables within a similar threshold of the closest boundary constraint. We leverage these optimizations to yield a Fast Active-Set Thresholding NNLS (FAST-NNLS) algorithm which significantly outperforms the existing state-of-the-art NNLS algorithms for a wide range of problems. Rigorous convergence guarantees are proven for the proposed method. We demonstrate the effectiveness of our proposed method on multiple synthetic datasets and two realworld text analysis applications. In doing so, we present the most comprehensive NNLS solver comparison in the literature to date.

Cobb, Benjamin [Georgia Institute of Technology]↗

A topological screening heuristic for low-energy, high-index surfaces

Robust ab initio investigations of nanoparticle surface properties require a method to identify candidate low-energy surface facets a priori . By assuming that low-energy surfaces are planes with high atomic density, we devise an efficient algorithm to screen for low-energy surface orientations, even if they have high ( hkl ) miller indices. We successfully predict the observed low-energy, high-index {$10\overline{12} $} and {$10\bar{1}4 $} surfaces of hematite α-Fe 2 O 3 , the {311} surfaces of cuprite Cu 2 O, and the {112} surfaces of anatase TiO 2 . We further tabulate candidate low-energy surface orientations for nine of the most common binary oxide structures. Screened surfaces are found to be generally applicable across isostructural compounds with varying chemistries, although relative surface energies between facets may vary based on the preferred coordination of the surface atoms.

36 MATERIALS SCIENCE↗

Streaming Solutions for Fine-Grained Network Traffic Measurements and Analysis

Online network traffic measurements and analysis is critical for detecting and preventing any real-time anomalies in the network. We propose, implement, and evaluate an online, adaptive measurement platform, which utilizes real-time traffic analysis results to refine subsequent traffic measurements. Central to our solution is the concept of Multi-Resolution Tiling (MRT), a heuristic approach that performs sequential analysis of traffic data to zoom into traffic subregions of interest. However, MRT is sensitive to transient traffic spikes. In this paper, we propose three novel traffic streaming algorithms that overcome the limitations of MRT and can cater to varying degrees of computational and storage budgets, detection latency, and accuracy of query response. We evaluate our streaming algorithms on a highly parallel and programmable hardware as well as a traditional software-based platforms. The algorithms demonstrate significant accuracy improvement over MRT in detecting anomalies consisting of synthetic hard-to-track elephant flows and global icebergs. Our proposed algorithms maintain the worst-case complexities of the MRT while incurring only a moderate increase in average resource utilization.

97 MATHEMATICS AND COMPUTING↗

Hierarchical Control of Megawatt-Scale Charging Stations for Electric Trucks with Distributed Energy Resources

Electrifying medium- and heavy-duty trucks is critical to decarbonizing the transportation sector. Energy needs of electric trucks will likely require megawatt-scale charging stations, which could significantly stress the electric distribution grid. Distributed energy resources (DER) can alleviate this stress and reduce charging costs with proper management. To that end, this work develops a hierarchical predictive control algorithm for future multi-port megawatt-scale charging stations that can provide real-time energy management for stations, decide charging rates, dispatch energy storage system (ESS), and provide grid voltage support. We integrate three algorithmic components: (i) an energy management optimization (EMO) that provides supervisory control to DER assets and charging loads at minute scale, (ii) a real-time energy management system (RT-EMS) that heuristically compensates for fast disturbances at sub-second scale, and (iii) a model predictive control (MPC)-based battery management system (BMS) that communicates future charging demands to the EMO, to manage the overall megawatt-scale site. Additionally, validation in a controller hardware-in-the-loop (CHIL) environment shows that the hierarchical controller can reduce the total energy consumption from the grid by approximately 28% compared to an uncontrolled case for the station configuration in this paper, without impacting charging time.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Data analysis using scale-space filtering and Bayesian probabilistic reasoning

This paper describes a program for analysis of output curves from Differential Thermal Analyzer (DTA). The program first extracts probabilistic qualitative features from a DTA curve of a soil sample, and then uses Bayesian probabilistic reasoning to infer the mineral in the soil. The qualifier module employs a simple and efficient extension of scale-space filtering suitable for handling DTA data. We have observed that points can vanish from contours in the scale-space image when filtering operations are not highly accurate. To handle the problem of vanishing points, perceptual organizations heuristics are used to group the points into lines. Next, these lines are grouped into contours by using additional heuristics. Probabilities are associated with these contours using domain-specific correlations. A Bayes tree classifier processes probabilistic features to infer the presence of different minerals in the soil. Experiments show that the algorithm that uses domain-specific correlation to infer qualitative features outperforms a domain-independent algorithm that does not.

Kulkarni, Deepak↗