Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

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 253 records · Page 14
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Requirements analysis, domain knowledge, and design

Two improvements to current requirements analysis practices are suggested: domain modeling, and the systematic application of analysis heuristics. Domain modeling is the representation of relevant application knowledge prior to requirements specification. Artificial intelligence techniques may eventually be applicable for domain modeling. In the short term, however, restricted domain modeling techniques, such as that in JSD, will still be of practical benefit. Analysis heuristics are standard patterns of reasoning about the requirements. They usually generate questions of clarification or issues relating to completeness. Analysis heuristics can be represented and therefore systematically applied in an issue-based framework. This is illustrated by an issue-based analysis of JSD's domain modeling and functional specification heuristics. They are discussed in the context of the preliminary design of simple embedded systems.

Potts, Colin↗
NASA NTRS1994

An investigation of the use of temporal decomposition in space mission scheduling

This research involves an examination of techniques for solving scheduling problems in long-duration space missions. The mission timeline is broken up into several time segments, which are then scheduled incrementally. Three methods are presented for identifying the activities that are to be attempted within these segments. The first method is a mathematical model, which is presented primarily to illustrate the structure of the temporal decomposition problem. Since the mathematical model is bound to be computationally prohibitive for realistic problems, two heuristic assignment procedures are also presented. The first heuristic method is based on dispatching rules for activity selection, and the second heuristic assigns performances of a model evenly over timeline segments. These heuristics are tested using a sample Space Station mission and a Spacelab mission. The results are compared with those obtained by scheduling the missions without any problem decomposition. The applicability of this approach to large-scale mission scheduling problems is also discussed.

Bullington, Stanley E.↗
NASA NTRS1995

Spectral ordering techniques for incomplete LU preconditoners for CG methods

The effectiveness of an incomplete LU (ILU) factorization as a preconditioner for the conjugate gradient method can be highly dependent on the ordering of the matrix rows during its creation. Detailed justification for two heuristics commonly used in matrix ordering for anisotropic problems is given. The bandwidth reduction and weak connection following heuristics are implemented through an ordering method based on eigenvector computations. This spectral ordering is shown to be a good representation of the heuristics. Analysis and test cases in two and three dimensional diffusion problems demonstrate when ordering is important, and when an ILU decomposition will be ordering insensitive. The applicability of the heuristics is thus evaluated and placed on a more rigorous footing.

Clift, Simon S.↗
NASA NTRS1997

Evaluating a Web-Based Interface for Internet Telemedicine

The objective is to introduce the usability engineering methodology, heuristic evaluation, to the design and development of a web-based telemedicine system. Using a set of usability criteria, or heuristics, one evaluator examined the Spacebridge to Russia web-site for usability problems. Thirty-four usability problems were found in this preliminary study and all were assigned a severity rating. The value of heuristic analysis in the iterative design of a system is shown because the problems can be fixed before deployment of a system and the problems are of a different nature than those found by actual users of the system. It was therefore determined that there is potential value of heuristic evaluation paired with user testing as a strategy for optimal system performance design.

Lathan, Corinna E.↗
NASA NTRS2011

Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a ppro~imate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.

Kaplan, Sezgin↗
NASA NTRS2017

Relevancy Ranking of Satellite Dataset Search Results

As the Variety of Earth science datasets increases, science researchers find it more challenging to discover and select the datasets that best fit their needs. The most common way of search providers to address this problem is to rank the datasets returned for a query by their likely relevance to the user. Large web page search engines typically use text matching supplemented with reverse link counts, semantic annotations and user intent modeling. However, this produces uneven results when applied to dataset metadata records simply externalized as a web page. Fortunately, data and search provides have decades of experience in serving data user communities, allowing them to form heuristics that leverage the structure in the metadata together with knowledge about the user community. Some of these heuristics include specific ways of matching the user input to the essential measurements in the dataset and determining overlaps of time range and spatial areas. Heuristics based on the novelty of the datasets can prioritize later, better versions of data over similar predecessors. And knowledge of how different user types and communities use data can be brought to bear in cases where characteristics of the user (discipline, expertise) or their intent (applications, research) can be divined. The Earth Observing System Data and Information System has begun implementing some of these heuristics in the relevancy algorithm of its Common Metadata Repository search engine.

science data management↗
NASA NTRS2019

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Hadfield, Stuart↗
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↗
DOE OSTI2021

Methods and data structures for efficient cross-referencing of physical-asset spatial identifiers

Described herein are methods, systems, and storage media having computer-processable instructions for cross-referencing in a computationally efficient manner different data sets each having pluralities of n-dimensional identifiers of physical assets. The disclosed cross-referencing approach can be used to determine relationships between different assets and their respective asset identifier strings. The relationships can be established based on user-selected heuristics. For example, at least two asset identifier strings can be compared, and user-defined heuristics can be applied to determine whether “a match” exists. A match can be defined according to the particular heuristic. In one instance, the comparison and heuristic can be applied to determine if two different asset identifier strings refer to a single physical asset.

Borkum, Mark I.↗
DOE OSTI2024

Anderson acceleration with approximate calculations: Applications to scientific computing

Here we provide rigorous theoretical bounds for Anderson acceleration (AA) that allow for approximate calculations when applied to solve linear problems. We show that, when the approximate calculations satisfy the provided error bounds, the convergence of AA is maintained while the computational time could be reduced. We also provide computable heuristic quantities, guided by the theoretical error bounds, which can be used to automate the tuning of accuracy while performing approximate calculations. For linear problems, the use of heuristics to monitor the error introduced by approximate calculations, combined with the check on monotonicity of the residual, ensures the convergence of the numerical scheme within a prescribed residual tolerance. Motivated by the theoretical studies, we propose a reduced variant of AA, which consists in projecting the least-squares used to compute the Anderson mixing onto a subspace of reduced dimension. The dimensionality of this subspace adapts dynamically at each iteration as prescribed by the computable heuristic quantities. We numerically show and assess the performance of AA with approximate calculations on: (i) linear deterministic fixed-point iterations arising from the Richardson's scheme to solve linear systems with open-source benchmark matrices with various preconditioners and (ii) non-linear deterministic fixed-point iterations arising from non-linear time-dependent Boltzmann equations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

HPC Node Performance and Energy Modeling with the Co-Location of Applications

Multicore processors have become an integral part of modern large-scale and high-performance parallel and distributed computing systems. This advance became necessary as the demand for increased system performance has exceeded the limits that single core processors can provide. Unfortunately, applications co-located on multicore processors can suffer from decreased performance and increased dynamic energy use as a result of access to shared resources, such as memory. Consequently, it is increasingly important to characterize the performance of applications that execute on these architectures. This work investigates some of the disadvantages of co-location, and presents a methodology for building models capable of utilizing varying amounts of information about a target application and its co-located applications to make predictions about the target application’s execution time and the system’s energy use under arbitrary co-locations of a wide range of application types. The proposed methodology is validated on three different server class Intel Xeon multicore processors using eleven applications from two scientific benchmark suites. The model’s utility for scheduling is also demonstrated in a simulated large-scale high-performance computing environment through the creation of a co-location aware scheduling heuristic. This heuristic demonstrates that scheduling using information generated with the proposed modeling methodology is capable of making significant improvements over a scheduling heuristic that is naive to co-location interference.

performance modeling, energy modeling, resource ma↗
DOE OSTI2018

An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

This paper is concerned with applying bandwidth and profile reduction reordering algorithms prior to computing an incomplete Cholesky factorization and using this as a preconditioner for the conjugate gradient method. Hundreds of reordering algorithms have been proposed to solve the problems of bandwidth and profile reductions since the mid-1960s. In previous publications, a large range of heuristics for bandwidth and/or profile reductions was reviewed. Based on this experience, 13 heuristics were selected as the most promising methods. These are evaluated in this paper along with a variant of the breadth-first search procedure that is proposed. Numerical results confirm the effectiveness of this modified reordering algorithm for linear systems derived from specific application areas. Moreover, the most promising heuristics for several application areas are identified when reducing the computational cost of the incomplete Cholesky-conjugate gradient method.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

A near-stationary subspace for ridge approximation

Response surfaces are common surrogates for expensive computer simulations in engineering analysis. However, the cost of fitting an accurate response surface increases exponentially as the number of model inputs increases, which leaves response surface construction intractable for high-dimensional, nonlinear models. Here we describe ridge approximation for fitting response surfaces in several variables. A ridge function is constant along several directions in its domain, so fitting occurs on the coordinates of a low-dimensional subspace of the input space. We review essential theory for ridge approximation – e.g., the best mean-squared approximation and an optimal low-dimensional subspace – and we prove that the gradient-based active subspace is near-stationary for the least-squares problem that defines an optimal subspace. Motivated by the theory, we propose a computational heuristic that uses an estimated active subspace as an initial guess for a ridge approximation fitting problem. We show a simple example where the heuristic fails, which reveals a type of function for which the proposed approach is inappropriate. We then propose a simple alternating heuristic for fitting a ridge function, and we demonstrate the effectiveness of the active subspace initial guess applied to an airfoil model of drag as a function of its 18 shape parameters.

42 ENGINEERING↗
DOE OSTI2017

A dynamic control approach for energy-efficient production scheduling on a single machine under time-varying electricity pricing

This paper proposes a dynamic control algorithm to enable an energy-aware single machine scheduling under the time-varying electricity pricing policy, in which price rates remain fixed day-to-day over the season. The key issue is to assign a set of jobs to available time periods where different electricity prices are assigned, while considering requested due dates of jobs so as to minimize total penalty costs for earliness and tardiness of jobs and total energy consumption costs, simultaneously. As the first contribution of this study, we develop a new mixed integer nonlinear programming (MINLP) model that aims at determining job arrival times and resulting earliness and tardiness of jobs and energy consumption costs for machine idle and normal processing. Second, an efficient heuristic approach based on continuous-time variable control models and algorithm is developed. The proposed heuristic adaptively changes job arrival times and due dates, which finally determine production sequence over the time periods of different electricity prices, machine turn-off, and machine idle with minimum energy consumption costs and just-in-time (JIT) penalty. Energy and JIT performance of the proposed approach is examined using real energy and machining parameters of a HAAS machine and compared to those of the metaheuristic approach. For relatively large size data groups, the proposed approach incurs about higher energy consumption costs on average, which are offset by up to lower JIT costs, resulting in lower total costs on average compared to the metaheuristic approach. Further, the proposed time-scaled heuristic algorithm yields extremely short computational time, which enables production managers to flexibly select proper production strategies and to implement them for different production environments.

42 ENGINEERING↗
DOE OSTI2025

Towards an Introspective Dynamic Model of Globally Distributed Computing Infrastructures

Large-scale scientific collaborations like ATLAS, Belle II, CMS, DUNE, and others involve hundreds of research institutes and thousands of researchers spread across the globe. These experiments generate petabytes of data, with volumes soon expected to reach exabytes. Consequently, there is a growing need for computation, including structured data processing from raw data to consumer-ready derived data, extensive Monte Carlo simulation campaigns, and a wide range of end-user analysis. To manage these computational and storage demands, centralized workflow and data management systems are implemented. However, decisions regarding data placement and payload allocation are often made disjointly and via heuristic means. A significant obstacle in adopting more effective heuristic or AI-driven solutions is the absence of a quick and reliable introspective dynamic model to evaluate and refine alternative approaches. In this study, we aim to develop such an interactive system using real-world data. By examining job execution records from the PanDA workflow management system, we have pinpointed key performance indicators such as queuing time, error rate, and the extent of remote data access. The dataset includes five months of activity. Additionally, we are creating a generative AI model to simulate time series of payloads, which incorporate visible features like category, event count, and submitting group, as well as hidden features like the total computational load—derived from existing PanDA records and computing site capabilities. These hidden features, which are not visible to job allocators, whether heuristic or AI-driven, influence factors such as queuing times and data movement.

kilic, Ozgur Ozan [Brookhaven National Laboratory ↗
DOE OSTI2015

Real-Time Corrective Switching in Response to Simultaneous Contingencies

The standard optimal power flow (OPF) problem is an economic dispatch (ED) problem combined with transmission constraints, which are based on a static topology. Prior research has demonstrated that cooptimization of generation dispatch and transmission topology results in cost savings. However, the computational complexity associated with topology control (TC) has been a major deterrent to its implementation. The proposed work investigates the application of a heuristic, a greedy algorithm, to improve the computational time for the TC problem while still maintaining the ability to find quality solutions. An expression is derived, which indicates the impact on the objective for a marginal change in the state of a transmission line. This expression is used to generate a priority list with potential candidate lines for switching, which may provide huge improvements to the system. The advantage of this method is that it is a fast heuristic as compared to using mixed integer programming (MIP) to find a solution. The heuristic is tested on real-time applications such as N-1 events, N - m events (m simultaneous contingencies), and cascading events. The proposed algorithm specifically targets cases that lead to load shedding in the system and provides a quick and efficient method to restore the loads by improving the deliverability of reserves via TC. Simulation results on the IEEE 73 bus test system and the IEEE 118 bus test system suggest a significant improvement in the amount of load served to the system with TC as opposed to without TC with minimal time and computation.

Electric power systems↗
DOE OSTI2013

The role of Rydberg and continuum levels in computing high harmonic generation spectra of the hydrogen atom using time-dependent configuration interaction

We study the role of Rydberg bound-states and continuum levels in the field-induced electronic dynamics associated with the High-Harmonic Generation (HHG) spectroscopy of the hydrogen atom. Time-dependent configuration-interaction (TD-CI) is used with very large atomic orbital (AO) expansions (up to L= 4 with sextuple augmentation and off-center functions) to describe the bound Rydberg levels, and some continuum levels. To address the lack of ionization losses in TD-CI with finite AO basis sets, we employed a heuristic lifetime for energy levels above the ionization potential. The heuristic lifetime model is compared against the conventional atomic orbital treatment (infinite lifetimes), and a third approximation which is TD-CI using only the bound levels (continuum lifetimes go to zero). The results suggest that spectra calculated using conventional TD-CI do not converge with increasing AO basis set size, while the zero lifetime and heuristic lifetime models converge to qualitatively similar spectra, with implications for how best to apply bound state electronic structure methods to simulate HHG. The origin of HHG spectral features including the cutoff and extent of interference between peaks is uncovered by separating field-induced coupling between different types of levels (ground state, bound Rydberg levels, and continuum) in the simulated electronic dynamics. Thus the origin of deviations between the predictions of the semi-classical three step model and the full simulation can be associated with particular physical contributions, which helps to explain both the successes and the limitations of the three step model.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

A Topology Optimization Framework to Facilitate Adoption of Advanced District Thermal Energy Systems

Advanced district thermal energy systems, which circulate water at temperatures near ambient conditions, and facilitate the utilization of waste heat and renewable thermal sources, can lower the carbon-intensity of urban districts, advancing the U.N. Sustainable Development Goals. Optimization of the network topology — the selection of the best subset of buildings and the best network to connect them, to minimize life cycle cost — can increase adoption of these system in appropriate applications. The potential "solution space" of the topology optimization problem grows factorially with the number of buildings in the district, motivating the consideration of a design heuristic. In this study, a heuristic for the network selection was evaluated with an exhaustive search, for a prototypical four-building district. For the prototypical district considered, the heuristic was effective in selecting an optimal network topology. Additionally, it was found that, in this case, the selection of the subset of buildings was more influential on the life cycle cost than the selection of the network topology. This work is part of a larger effort to develop a topology optimization framework for district thermal energy systems, which is anticipated to address barriers to adoption of ambient-temperature systems.

28 EE - Advanced Manufacturing Office (EE-5A)↗