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 397 records · Page 22
All sourcesNASA NTRSDOE OSTI
NASA NTRS1990

An approach to rescheduling activities based on determination of priority and disruptivity

A constraint-based scheduling system called SPIKE is being used to create long term schedules for the Hubble Space Telescope. Feedback for the spacecraft or from other ground support systems may invalidate some scheduling decisions and those activities concerned must be reconsidered. A function rescheduling priority is defined which for a given activity performs a heuristic analysis and produces a relative numerical value which is used to rank all such entities in the order that they should be rescheduled. A function disruptivity is also defined that is used to place a relative numeric value on how much a pre-existing schedule would be changed in order to reschedule an activity. Using these functions, two algorithms (a stochastic neural network approach and an exhaustive search approach) are proposed to find the best place to reschedule an activity. Prototypes were implemented and preliminary testing reveals that the exhaustive technique produces only marginally better results at much greater computational cost.

Sponsler, Jeffrey L.↗
DOE OSTI2024

Alternating Direction Decomposition with Strong Bounding and Convexification (ADDSBC) for Solving Security Constrained AC Unit Commitment Problems

This project aims to develop efficient and robust computational methods for solving the security-constrained unit commitment and alternating current optimal power flow problem (SC-UC-ACOPF). The SC-UC-ACOPF problem is at the center of the short-term operation of the U.S. Power Grid. It is solved every week, every day, and every 10 minutes to plan for the optimal action of electricity generation and consumption by minimizing the generation cost and maintaining power system reliability against potential disruptions of equipment failures. In mathematical terms, SC-UC-ACOPF is a challenging large-scale mixed-integer nonlinear optimization model. This means that the decisions involve both discrete variables, e.g. the turning on and off of generators and switching of transmission lines and transformers, and continuous decisions, e.g. the amount of energy generated by each generator and the power flows in the power grid. The physics of the power flow is described by nonlinear equations involving real and reactive power and bus voltages. Another key feature is the large number of contingencies, i.e. the system needs to stay reliable in face of failure of any one equipment, such as transmission lines and generators. The U.S. power grids are extremely complicated and large scale with more than 5,000 generators, 50,000 buses, and 100,000 high-voltage transmission lines, making the SC-UC-ACOPF a very large-scale computation challenge. The research developed in this project aims to solve the SC-UC-ACOPF problems in the three timescales, i.e. weekly, daily, and every 10-min. The proposed computational methods are built on a principled algorithmic approach of decomposition and penalization. More specifically, the algorithm develops spatial and temporal decomposition by exploiting the strong temporal coupling and weak spatial coupling of the UC problem and the complementary feature, i.e. weak temporal coupling and strong spatial coupling of the ACOPF problem. The algorithm also leverages recent progresses in strong convex relaxation of ACOPF. A unique feature of the proposed approach is that it generates a valid, global upper bound on the optimal maximum profit. In this way, a global optimality gap is available to measure the quality of the solution. To further speed up computation, the research team has developed a plethora of effective heuristics to strengthen the iterative penalty-based decomposition framework. For instance, a heuristic is developed to construct inner approximations of the time coupling constraints within the time decoupled problems. Contingencies are pre-screened and low-rank matrix computation is exploited to find the almost unique solution to each contingency. A novel heuristic for line switching is proposed and tested with positive impacts on instances where line switching is beneficial. Taking a systematic approach and carefully handling every detail of the problem pays off. The TIM-GO’s performance throughout the trials and the final event was stellar. TIM-GO garnered the second highest total prize money and is ranked in the top three positions across all categories of comparison.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1998

PLUM: Parallel Load Balancing for Unstructured Adaptive Meshes

Dynamic mesh adaption on unstructured grids is a powerful tool for computing large-scale problems that require grid modifications to efficiently resolve solution features. Unfortunately, an efficient parallel implementation is difficult to achieve, primarily due to the load imbalance created by the dynamically-changing nonuniform grid. To address this problem, we have developed PLUM, an automatic portable framework for performing adaptive large-scale numerical computations in a message-passing environment. First, we present an efficient parallel implementation of a tetrahedral mesh adaption scheme. Extremely promising parallel performance is achieved for various refinement and coarsening strategies on a realistic-sized domain. Next we describe PLUM, a novel method for dynamically balancing the processor workloads in adaptive grid computations. This research includes interfacing the parallel mesh adaption procedure based on actual flow solutions to a data remapping module, and incorporating an efficient parallel mesh repartitioner. A significant runtime improvement is achieved by observing that data movement for a refinement step should be performed after the edge-marking phase but before the actual subdivision. We also present optimal and heuristic remapping cost metrics that can accurately predict the total overhead for data redistribution. Several experiments are performed to verify the effectiveness of PLUM on sequences of dynamically adapted unstructured grids. Portability is demonstrated by presenting results on the two vastly different architectures of the SP2 and the Origin2OOO. Additionally, we evaluate the performance of five state-of-the-art partitioning algorithms that can be used within PLUM. It is shown that for certain classes of unsteady adaption, globally repartitioning the computational mesh produces higher quality results than diffusive repartitioning schemes. We also demonstrate that a coarse starting mesh produces high quality load balancing, at a fraction of the cost required a fine initial mesh. Results indicate that our parallel load balancing strategy will remain viable on large numbers of processors.

Oliker, Leonid↗
DOE OSTI2021

Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3. We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. Furthermore, the resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2022

Topology Optimization of 3D Flow Fields for Flow Batteries

We report as power generated from renewables becomes more readily available, the need for power-efficient energy storage devices, such as redox flow batteries, becomes critical for successful integration of renewables into the electrical grid. An important aspect of a redox flow battery is the planar flow field, which is usually composed of two-dimensional channels etched into a backing plate. As reactant-laden electrolyte flows into the flow battery, the channels in the flow field distribute the fluid throughout the reactive porous electrode. We utilize topology optimization to design flow fields with full three-dimensional geometry variation, i.e., 3D flow fields. Specifically, we focus on vanadium redox flow batteries and use the optimization algorithm to generate 3D flow fields evolved from standard interdigitated flow fields by minimizing the electrical and flow pressure power losses. To understand how these 3D designs improve performance, we analyze the polarization of the reactant concentration and exchange current within the electrode to highlight how the designed flow fields mitigate the presence of electrode dead zones. While interdigitated flow fields can be heuristically engineered to yield high performance by tuning channel and land dimensions, such a process can be laborious; this work provides a framework for automating that design process.

25 ENERGY STORAGE↗
NASA NTRSDate not supplied

A Multilevel Approach For SolvingLarge-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization

Quantum approximate optimization is one ofthe promising candidates for useful quantum computation,particularly in the context of finding approximate solutionsto Quadratic Unconstrained Binary Optimization (QUBO)problems. However, the existing quantum processing units(QPUs) are of relatively small size, and canonical mappingsof QUBO via the Ising model require one qubit per vari-able, rendering direct large-scale optimization infeasible.In classical optimization, a general strategy for addressingmany large-scale problems is via multilevel/multigrid meth-ods, where the large target problem is iteratively coarsenedand the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentallytest how existing QPUs perform when used as a sub-solverwithin such a multilevel strategy. To this aim, we com-bine and extend (via additional classical processing steps)the recently proposed Noise-Directed Adaptive Remapping(NDAR) and Quantum Relax&Round (QRR) algorithms.We first demonstrate the effectiveness of our heuristicextensions on Rigetti’s superconducting transmon deviceAnkaa-2. We find approximate solutions to10instances offully connected82-qubit Sherrington-Kirkpatrick graphswith random integer-valued coefficients obtaining normal-ized approximation ratios (ARs) in the range∼0.98−1.0,and the same class with real-valued coefficients (ARs∼0.94−1.0). Then, we implement the extended NDAR andQRR algorithms as subsolvers in the multilevel algorithmfor6large-scale graphs with at most∼27,000variables.In practice, the QPU (with classical post-processing steps)is used to find approximate solutions to dozens of at most82-qubit problems, which are iteratively used to constructthe global solution. We observe that quantum optimizationresults are competitive in terms of the quality of solutionswhen compared to classical heuristics used as subsolverswithin the multilevel approach.Reproducibility: source code and data are available at[TBA upon acceptance]

quantum computing↗
NASA NTRS1993

Space Shuttle Main Engine performance analysis

For a number of years, NASA has relied primarily upon periodically updated versions of Rocketdyne's power balance model (PBM) to provide space shuttle main engine (SSME) steady-state performance prediction. A recent computational study indicated that PBM predictions do not satisfy fundamental energy conservation principles. More recently, SSME test results provided by the Technology Test Bed (TTB) program have indicated significant discrepancies between PBM flow and temperature predictions and TTB observations. Results of these investigations have diminished confidence in the predictions provided by PBM, and motivated the development of new computational tools for supporting SSME performance analysis. A multivariate least squares regression algorithm was developed and implemented during this effort in order to efficiently characterize TTB data. This procedure, called the 'gains model,' was used to approximate the variation of SSME performance parameters such as flow rate, pressure, temperature, speed, and assorted hardware characteristics in terms of six assumed independent influences. These six influences were engine power level, mixture ratio, fuel inlet pressure and temperature, and oxidizer inlet pressure and temperature. A BFGS optimization algorithm provided the base procedure for determining regression coefficients for both linear and full quadratic approximations of parameter variation. Statistical information relative to data deviation from regression derived relations was also computed. A new strategy for integrating test data with theoretical performance prediction was also investigated. The current integration procedure employed by PBM treats test data as pristine and adjusts hardware characteristics in a heuristic manner to achieve engine balance. Within PBM, this integration procedure is called 'data reduction.' By contrast, the new data integration procedure, termed 'reconciliation,' uses mathematical optimization techniques, and requires both measurement and balance uncertainty estimates. The reconciler attempts to select operational parameters that minimize the difference between theoretical prediction and observation. Selected values are further constrained to fall within measurement uncertainty limits and to satisfy fundamental physical relations (mass conservation, energy conservation, pressure drop relations, etc.) within uncertainty estimates for all SSME subsystems. The parameter selection problem described above is a traditional nonlinear programming problem. The reconciler employs a mixed penalty method to determine optimum values of SSME operating parameters associated with this problem formulation.

Santi, L. Michael↗
NASA NTRS2011

Automatic Tie Pointer for In-Situ Pointing Correction

The MARSAUTOTIE program generates tie points for use with the Mars pointing correction software "In-Situ Pointing Correction and Rover Microlocalization," (NPO-46696) Soft ware Tech Briefs, Vol. 34, No. 9 (September 2010), page 18, in a completely automated manner, with no operator intervention. It takes the place of MARSTIE, although MARSTIE can be used to interactively edit the tie points afterwards. These tie points are used to create a mosaic whose seams (boundaries of input images) have been geometrically corrected to reduce or eliminate errors and mis-registrations. The methods used to find appropriate tie points for use in creating a mosaic are unique, having been designed to work in concert with the "MARSNAV" program to be most effective in reducing or eliminating geometric seams in a mosaic. The program takes the input images and finds overlaps according to the nominal pointing. It then finds the most interesting areas using a scene activity metric. Points with higher scene activity are more likely to correlate successfully in the next step. It then uses correlation techniques to find matching points in the overlapped image. Finally, it performs a series of steps to reduce the number of tie points to a manageable level. These steps incorporate a number of heuristics that have been devised using experience gathered by tie pointing mosaics manually during MER operations. The software makes use of the PIG library as described in "Planetary Image Geometry Library" (NPO-46658), NASA Tech Briefs, Vol. 34, No. 12 (December 2010), page 30, so it is multi-mission, applicable without change to any in-situ mission supported by PIG. The MARSAUTOTIE algorithm is automated, so it requires no user intervention. Although at the time of this reporting it has not been done, this program should be suitable for integration into a fully automated mosaic production pipeline.

Deen, Robert G/↗
NASA NTRS2024

Automated Detection of Spurious Signals in VLBI Phase Calibration Data

In this memorandum, a set of processing strategies for automatic masking of phase calibration tones is outlined as implemented in the software package PIMA in the task Generate Phase Calibration Mask, or GEPM. The task relies on a robust procedure of cleaning phase calibration data before employing several mathematical strategies designed to selectively identify spurious signals from phase calibration tones. These strategies were derived as more rigorous implementations of heuristics traditionally used by analysts in manually identifying problematic phase calibration data. The task is intended to automate the process of generating a phase calibration mask and in so doing increase the speed and regularity of VLBI analysis. At the outset of the project, a series of goals were identified to evaluate the success of this mask generation. This included the development of an algorithm to identify and mask short-term (defined as less than 10 seconds in length) spurious signals affecting phase calibration data, the development of an algorithm to identify and mask phase calibration tones affected by constant radio-frequency interference, the implementation of a detection scheme for identifying large jumps in phase calibration phase caused by clock breaks, and finally a method of reporting phase calibration health metrics to the user. Processing of over 10 experiments has demonstrated that the final form of the task GEPM as detailed in this technical memorandum satisfies each of these conditions and satisfactorily performs the task of automatic phase calibration data masking, although the wide variety in quality and characteristics of phase calibration data makes a single solution to the problem quite difficult. A series of user inputs have therefore been defined to assist analysts in tailoring automatic masking to specific stations and phase calibration generators. The vast majority of applicable code was written in FORTRAN to increase execution speed and ease of interfacing with the existing code base in PIMA, but a wrapper function in Python was also written to allow for a simpler method of interacting with GEPM and inputting relevant parameters. In addition to this report, thorough documentation was added to the already existing repositories associated with PIMA as a whole.

Geodesy↗
NASA NTRS1987

Iterative-deepening heuristic search for optimal and semi-optimal resource allocation

It is demonstrated that when iterative-deepening A asterisk (IDA asterisk) is applied to one type of resource allocation problem, it uses far less storage than A asterisk, but opens far more nodes and thus has unacceptable time complexity. This is shown to be due, at least in part, to the low-valued effective branching factor that is a characteristic of problems with real-valued cost functions. The semi-optimal, epsilon-admissible IDA asterisk sub epsilon search algorithm that the authors described was shown to open fewer nodes than both A asterisk and IDA asterisk with storage complexity proportional to the depth of the search tree.

Bridges, Susan M.↗
NASA NTRS2021

Machine Learning Based Path Planning for Improved Rover Navigation

Enhanced AutoNav (ENav), the baseline surface navigation software for NASA’s Perseverance rover, sorts a list of candidate paths for the rover to traverse, then uses the Approximate Clearance Evaluation (ACE) algorithm to evaluate whether the most highly ranked paths are safe. ACE is crucial for maintaining the safety of the rover, but is computationally expensive. If the most promising candidates in the list of paths are all found to be infeasible, ENav must continue to search the list and run time-consuming ACE evaluations until a feasible path is found. In this paper, we present two heuristics that, given a terrain heightmap around the rover, produce cost estimates that more effectively rank the candidate paths before ACE evaluation. The first heuristic uses Sobel operators and convolution to incorporate the cost of traversing high-gradient terrain. The second heuristic uses a machine learning (ML) model to predict areas that will be deemed untraversable by ACE. We used physics simulations to collect training data for the ML model and to run Monte Carlo trials to quantify navigation performance across a variety of terrains with various slopes and rock distributions. Compared to ENav's baseline performance, integrating the heuristics can lead to a significant reduction in ACE evaluations and average computation time per planning cycle, increase path efficiency, and maintain or improve the rate of successful traverses. This strategy of targeting specific bottlenecks with ML while maintaining the original ACE safety checks provides an example of how ML can be infused into planetary science missions and other safety-critical software.

Yue, Yisong↗
NASA NTRSDate not supplied

Physics Informed Neural Nets for Systems Health Management

To facilitate and solve the prediction problem, awareness of the current health state of the system is key, since it is necessary to perform condition-based predictions. To accurately predict the future state of any system, it is required to possess knowledge of its current health state and future operational conditions. Development in data-driven algorithms in regression of complex nonlinear functions and classification tasks have generated a growing interest in artificial intelligence for industrial applications. Complex multi-physics models as well as digital twins, once purely built on physics and corresponding simplified lumped parameter iterations, can now benefit from machine learning algorithms to mitigate the lack of understanding of some complex behavior. The research work presents application of physics-informed neural nets application to a representative electric powertrain for unmanned aerial vehicles. The model is composed of physics-derived and empirical equations, integrated with connected networks that are strategically placed within the model to substitute equations that are subject to large uncertainty. Polynomial fit driven by heuristics or empirical observations can be substituted by more flexible networks that can minimize the error between model predictions and observations without being restricted to a predefined functional form. This modeling strategy allows training of networks deep inside the model and unknown parameters in a single learning stage.

Physics Informed↗
DOE OSTI2023

Adaptive language model training for molecular design

Abstract The vast size of chemical space necessitates computational approaches to automate and accelerate the design of molecular sequences to guide experimental efforts for drug discovery. Genetic algorithms provide a useful framework to incrementally generate molecules by applying mutations to known chemical structures. Recently, masked language models have been applied to automate the mutation process by leveraging large compound libraries to learn commonly occurring chemical sequences (i.e., using tokenization) and predict rearrangements (i.e., using mask prediction). Here, we consider how language models can be adapted to improve molecule generation for different optimization tasks. We use two different generation strategies for comparison, fixed and adaptive. The fixed strategy uses a pre-trained model to generate mutations; the adaptive strategy trains the language model on each new generation of molecules selected for target properties during optimization. Our results show that the adaptive strategy allows the language model to more closely fit the distribution of molecules in the population. Therefore, for enhanced fitness optimization, we suggest the use of the fixed strategy during an initial phase followed by the use of the adaptive strategy. We demonstrate the impact of adaptive training by searching for molecules that optimize both heuristic metrics, drug-likeness and synthesizability, as well as predicted protein binding affinity from a surrogate model. Our results show that the adaptive strategy provides a significant improvement in fitness optimization compared to the fixed pre-trained model, empowering the application of language models to molecular design tasks.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1994

Using Induction to Refine Information Retrieval Strategies

Conceptual information retrieval systems use structured document indices, domain knowledge and a set of heuristic retrieval strategies to match user queries with a set of indices describing the document's content. Such retrieval strategies increase the set of relevant documents retrieved (increase recall), but at the expense of returning additional irrelevant documents (decrease precision). Usually in conceptual information retrieval systems this tradeoff is managed by hand and with difficulty. This paper discusses ways of managing this tradeoff by the application of standard induction algorithms to refine the retrieval strategies in an engineering design domain. We gathered examples of query/retrieval pairs during the system's operation using feedback from a user on the retrieved information. We then fed these examples to the induction algorithm and generated decision trees that refine the existing set of retrieval strategies. We found that (1) induction improved the precision on a set of queries generated by another user, without a significant loss in recall, and (2) in an interactive mode, the decision trees pointed out flaws in the retrieval and indexing knowledge and suggested ways to refine the retrieval strategies.

Baudin, Catherine↗
NASA NTRS2015

Kodiak: An Implementation Framework for Branch and Bound Algorithms

Recursive branch and bound algorithms are often used to refine and isolate solutions to several classes of global optimization problems. A rigorous computation framework for the solution of systems of equations and inequalities involving nonlinear real arithmetic over hyper-rectangular variable and parameter domains is presented. It is derived from a generic branch and bound algorithm that has been formally verified, and utilizes self-validating enclosure methods, namely interval arithmetic and, for polynomials and rational functions, Bernstein expansion. Since bounds computed by these enclosure methods are sound, this approach may be used reliably in software verification tools. Advantage is taken of the partial derivatives of the constraint functions involved in the system, firstly to reduce the branching factor by the use of bisection heuristics and secondly to permit the computation of bifurcation sets for systems of ordinary differential equations. The associated software development, Kodiak, is presented, along with examples of three different branch and bound problem types it implements.

Smith, Andrew P.↗
NASA NTRS1998

Fuzzy Adaptive Control for Intelligent Autonomous Space Exploration Problems

The principal objective of the research reported here is the re-design, analysis and optimization of our newly developed neural network fuzzy adaptive controller model for complex processes capable of learning fuzzy control rules using process data and improving its control through on-line adaption. The learned improvement is according to a performance objective function that provides evaluative feedback; this performance objective is broadly defined to meet long-range goals over time. Although fuzzy control had proven effective for complex, nonlinear, imprecisely-defined processes for which standard models and controls are either inefficient, impractical or cannot be derived, the state of the art prior to our work showed that procedures for deriving fuzzy control, however, were mostly ad hoc heuristics. The learning ability of neural networks was exploited to systematically derive fuzzy control and permit on-line adaption and in the process optimize control. The operation of neural networks integrates very naturally with fuzzy logic. The neural networks which were designed and tested using simulation software and simulated data, followed by realistic industrial data were reconfigured for application on several platforms as well as for the employment of improved algorithms. The statistical procedures of the learning process were investigated and evaluated with standard statistical procedures (such as ANOVA, graphical analysis of residuals, etc.). The computational advantage of dynamic programming-like methods of optimal control was used to permit on-line fuzzy adaptive control. Tests for the consistency, completeness and interaction of the control rules were applied. Comparisons to other methods and controllers were made so as to identify the major advantages of the resulting controller model. Several specific modifications and extensions were made to the original controller. Additional modifications and explorations have been proposed for further study. Some of these are in progress in our laboratory while others await additional support. All of these enhancements will improve the attractiveness of the controller as an effective tool for the on line control of an array of complex process environments.

Esogbue, Augustine O.↗
DOE OSTI2020

Aggregation and data driven identification of building thermal dynamic model and unmeasured disturbance

An aggregate model is a single-zone equivalent of a multi-zone building, and is useful for many purposes, including model based control of large heating, ventilation and air conditioning (HVAC) equipment. This paper deals with the problem of simultaneously identifying an aggregate thermal dynamic model and unknown disturbances from input–output data of multi-zone buildings. The unknown disturbance is a key challenge since it is not measurable but non-negligible. In this paper, we first present a principled method to aggregate a multi-zone building model into a single zone model, and show the aggregation is not as trivial as it has been assumed in the prior art. We then provide a method to identify the parameters of the model and the unknown disturbance for this aggregate (single-zone) model. Finally, we test our proposed identification algorithm to data collected from a multi-zone building testbed in Oak Ridge National Laboratory. A key insight provided by the aggregation method allows us to recognize under what conditions the estimation of the disturbance signal will be necessarily poor and uncertain, even in the case of a specially designed test in which the disturbances affecting each zone are known (as the case of our experimental testbed). This insight is used to provide a heuristic that can be used to assess when the identification results are likely to have high or low accuracy.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗