Search NASA⌕ Search

SEARCH · Search NASA

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 163 records · Page 9

Inverse problems: Fuzzy representation of uncertainty generates a regularization

In many applied problems (geophysics, medicine, and astronomy) we cannot directly measure the values x(t) of the desired physical quantity x in different moments of time, so we measure some related quantity y(t), and then we try to reconstruct the desired values x(t). This problem is often ill-posed in the sense that two essentially different functions x(t) are consistent with the same measurement results. So, in order to get a reasonable reconstruction, we must have some additional prior information about the desired function x(t). Methods that use this information to choose x(t) from the set of all possible solutions are called regularization methods. In some cases, we know the statistical characteristics both of x(t) and of the measurement errors, so we can apply statistical filtering methods (well-developed since the invention of a Wiener filter). In some situations, we know the properties of the desired process, e.g., we know that the derivative of x(t) is limited by some number delta, etc. In this case, we can apply standard regularization techniques (e.g., Tikhonov's regularization). In many cases, however, we have only uncertain knowledge about the values of x(t), about the rate with which the values of x(t) can change, and about the measurement errors. In these cases, usually one of the existing regularization methods is applied. There exist several heuristics that choose such a method. The problem with these heuristics is that they often lead to choosing different methods, and these methods lead to different functions x(t). Therefore, the results x(t) of applying these heuristic methods are often unreliable. We show that if we use fuzzy logic to describe this uncertainty, then we automatically arrive at a unique regularization method, whose parameters are uniquely determined by the experts knowledge. Although we start with the fuzzy description, but the resulting regularization turns out to be quite crisp.

Kreinovich, V.↗

Aligning parallel arrays to reduce communication

Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array expressions. Here, we examine alignment for more general program graphs. We show that optimal alignment is NP-complete in this setting, so we study heuristic methods. This paper makes two contributions. First, we show how local graph transformations can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. Second, we give a heuristic that can explore the space of possible solutions in a number of ways. We show that some of these strategies can give better solutions than a simple greedy approach proposed earlier. Our algorithms have been implemented; we present experimental results showing their effect on the performance of some example programs running on the CM-5.

Sheffler, Thomas J.↗

EDNA: Expert fault digraph analysis using CLIPS

Traditionally fault models are represented by trees. Recently, digraph models have been proposed (Sack). Digraph models closely imitate the real system dependencies and hence are easy to develop, validate and maintain. However, they can also contain directed cycles and analysis algorithms are hard to find. Available algorithms tend to be complicated and slow. On the other hand, the tree analysis (VGRH, Tayl) is well understood and rooted in vast research effort and analytical techniques. The tree analysis algorithms are sophisticated and orders of magnitude faster. Transformation of a digraph (cyclic) into trees (CLP, LP) is a viable approach to blend the advantages of the representations. Neither the digraphs nor the trees provide the ability to handle heuristic knowledge. An expert system, to capture the engineering knowledge, is essential. We propose an approach here, namely, expert network analysis. We combine the digraph representation and tree algorithms. The models are augmented by probabilistic and heuristic knowledge. CLIPS, an expert system shell from NASA-JSC will be used to develop a tool. The technique provides the ability to handle probabilities and heuristic knowledge. Mixed analysis, some nodes with probabilities, is possible. The tool provides graphics interface for input, query, and update. With the combined approach it is expected to be a valuable tool in the design process as well in the capture of final design knowledge.

Dixit, Vishweshwar V.↗

Search Space Characterization for a Telescope Scheduling Application

This paper presents a technique for statistically characterizing a search space and demonstrates the use of this technique within a practical telescope scheduling application. The characterization provides the following: (i) an estimate of the search space size, (ii) a scaling technique for multi-attribute objective functions and search heuristics, (iii) a "quality density function" for schedules in a search space, (iv) a measure of a scheduler's performance, and (v) support for constructing and tuning search heuristics. This paper describes the random sampling algorithm used to construct this characterization and explains how it can be used to produce this information. As an example, we include a comparative analysis of an heuristic dispatch scheduler and a look-ahead scheduler that performs greedy search.

Bresina, John↗

Theory of Collective Intelligence

In this chapter an analysis of the behavior of an arbitrary (perhaps massive) collective of computational processes in terms of an associated "world" utility function is presented We concentrate on the situation where each process in the collective can be viewed as though it were striving to maximize its own private utility function. For such situations the central design issue is how to initialize/update the collective's structure, and in particular the private utility functions, so as to induce the overall collective to behave in a way that has large values of the world utility. Traditional "team game" approaches to this problem simply set each private utility function equal to the world utility function. The "Collective Intelligence" (COIN) framework is a semi-formal set of heuristics that recently have been used to construct private utility. functions that in many experiments have resulted in world utility values up to orders of magnitude superior to that ensuing from use of the team game utility. In this paper we introduce a formal mathematics for analyzing and designing collectives. We also use this mathematics to suggest new private utilities that should outperform the COIN heuristics in certain kinds of domains. In accompanying work we use that mathematics to explain previous experimental results concerning the superiority of COIN heuristics. In that accompanying work we also use the mathematics to make numerical predictions, some of which we then test. In this way these two papers establish the study of collectives as a proper science, involving theory, explanation of old experiments, prediction concerning new experiments, and engineering insights.

Nash equilibrium↗

Implied alignment: a synapomorphy-based multiple-sequence alignment method and its use in cladogram search

A method to align sequence data based on parsimonious synapomorphy schemes generated by direct optimization (DO; earlier termed optimization alignment) is proposed. DO directly diagnoses sequence data on cladograms without an intervening multiple-alignment step, thereby creating topology-specific, dynamic homology statements. Hence, no multiple-alignment is required to generate cladograms. Unlike general and globally optimal multiple-alignment procedures, the method described here, implied alignment (IA), takes these dynamic homologies and traces them back through a single cladogram, linking the unaligned sequence positions in the terminal taxa via DO transformation series. These "lines of correspondence" link ancestor-descendent states and, when displayed as linearly arrayed columns without hypothetical ancestors, are largely indistinguishable from standard multiple alignment. Since this method is based on synapomorphy, the treatment of certain classes of insertion-deletion (indel) events may be different from that of other alignment procedures. As with all alignment methods, results are dependent on parameter assumptions such as indel cost and transversion:transition ratios. Such an IA could be used as a basis for phylogenetic search, but this would be questionable since the homologies derived from the implied alignment depend on its natal cladogram and any variance, between DO and IA + Search, due to heuristic approach. The utility of this procedure in heuristic cladogram searches using DO and the improvement of heuristic cladogram cost calculations are discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

Non-NASA Center↗

Runway Scheduling Using Generalized Dynamic Programming

A generalized dynamic programming method for finding a set of pareto optimal solutions for a runway scheduling problem is introduced. The algorithm generates a set of runway fight sequences that are optimal for both runway throughput and delay. Realistic time-based operational constraints are considered, including miles-in-trail separation, runway crossings, and wake vortex separation. The authors also model divergent runway takeoff operations to allow for reduced wake vortex separation. A modeled Dallas/Fort Worth International airport and three baseline heuristics are used to illustrate preliminary benefits of using the generalized dynamic programming method. Simulated traffic levels ranged from 10 aircraft to 30 aircraft with each test case spanning 15 minutes. The optimal solution shows a 40-70 percent decrease in the expected delay per aircraft over the baseline schedulers. Computational results suggest that the algorithm is promising for real-time application with an average computation time of 4.5 seconds. For even faster computation times, two heuristics are developed. As compared to the optimal, the heuristics are within 5% of the expected delay per aircraft and 1% of the expected number of runway operations per hour ad can be 100x faster.

optmization↗

Quantum Approximate Optimization with Hard and Soft Constraints

Challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms. Small universal quantum computers will emerge in the next year or two, enabling a substantial broadening of the types of quantum heuristics that can be investigated beyond quantum annealing. The immediate question is What experiments should we prioritize that will give us insight into quantum heuristics? One leading candidate is the quantum approximate optimization algorithm (QAOA) metaheuristic. Here, we provide a framework for designing QAOA circuits for a variety of combinatorial optimization problems with both hard constraints that must be met and soft constraints whose violation we wish to minimize. We work through a number of examples, and discuss design principles and implementation considerations.

Hadfield, Stuart↗

A Hybrid Approach to Labeling Datasets in Earth Science Publications

NASA Data Centers provide the public with thousands of datasets that result in published papers, reports, and conference proceedings. Collecting accurate metrics on usage of these datasets is key to connecting different areas of knowledge and evaluating the datasets’ impact. While most of the datasets have Digital Object Identifiers (DOIs) assigned, most publications do not cite them hampering the automated search of these publications. Instead, articles mention attributes like organization, instrument, mission, variable, or a publication describing the dataset. Often only domain experts can deduce the dataset that was used in the publication text. The lack of a citation slows the spread of information and reduces the research’s impact. With thousands of papers produced each year, an automated means of labeling datasets is critical. This paper explores a hybrid approach of heuristics and a Natural Language Processing (NLP) Named Entity Recognition (NER) model to find and label the datasets used within Earth Science papers. Heuristics are used to produce the labelled sentences and any potential dataset candidates that can be derived from a sentence. The heuristic labels the sentences with the names of mission, instrument, re-analysis models, and science keywords taken from the Global Change Master Directory (GCMD) ontology. Additionally, it uses those labels to generate the dataset citation candidates. If the mission, instrument, and variable are sufficient to create the citation for the dataset the citation and the label the domain expert reviews the output without going through the NLP model. If the extracted label is not sufficient to label the dataset on its own, the sentence and its associated dataset labels will be inputted into the NER model. The model outputs the labeled sentence and the potential dataset candidates with their associated probabilities. The domain expert then reviews the NER model’s output and the correct labels are determined. The newly labelled papers can then be used as additional training data. This creates an iterative process for the approach to continuously improve. Because all the possible mentions are gathered by the model, the domain expert can quickly and easily label the papers resulting in large time savings.

Jacob Atkins↗

Development of Near-term Urban Air Mobility Routes and Airspace Integration

Growing interest in Urban Air Mobility (UAM) has been demonstrated by a great deal of investment in related research made by industry, government, and academia. Based on this research effort along with considerations of the maturing concept for UAM airspace integration, a cognitive walkthrough exercise and a human-in-the-loop simulation were conducted with controller subject matter experts (SMEs) to evaluate Dallas-Fort Worth (DFW) current day helicopter routes for near-term use as UAM routes. One of the outcomes of this work is a set of heuristics that should be applied when designing UAM routes in the future. The following heuristics were identified as critical to UAM route design: the proximity of routes to surrounding airports (including approach and departure paths of traditional commercial traffic), the configuration of surrounding airports, avoiding congested or heavily populated areas, avoiding route segments that would go through several sectors, avoiding route segments that would go in and out of Class B airspace, creating routes outside of Class B airspace when able, using routes with two-way, altitude-separated traffic when able, minimizing the length of the route, avoiding commonly placed Temporary Flight Restrictions, and creating Non-Movement Areas or UNICOM Areas. This paper describes each of these identified heuristics and relevant examples based on a human-in-the-loop study conducted using the DFW area airspace.

Urban Air Mobility↗

Deep Neural Network Based Convergence Classification for Computational Fluid Dynamics

A supervised deep learning approach is coupled with heuristic convergence criteria to construct a classification model for detecting the completion (convergence) of computational fluid dynamics (CFD) simulations. Heuristic convergence criteria alone are not always sufficient and more complex decisions are often left to a human analyst. The proposed approach leverages heuristic convergence criteria as well as two deep neural network (DNN) models, one binary and one multi-class, to improve the efficiency and consistency of convergence classification across a wide range of flight regimes. The DNN models presented are each trained on a subset of ascent aerodynamic CFD simulations for NASA’s Space Launch System and were produced using NASA’s unstructured Navier-Stokes solver FUN3D. Individual solutions are analyzed intermittently and are classified as sufficiently converged, further iterations required, or switch from steady Reynolds Averaged Navier-Stokes (RANS) to unsteady RANS CFD based on the iterative histories of four aerodynamic coefficients. The implemented classification model is shown to produce solutions that closely correlate to solutions produced by a human analyst. This work lays groundwork for expanding the capabilities of DNNs for automating and improving more of the CFD process.

SLS↗

A NASA Perspective on Quantum Computing: Algorithmic Opportunities and Challenges

In the last couple of decades, the world has seen several stunning instances of quantum algorithms that provably outperform the best classical algorithms. For most problems, however, it is currently unknown whether quantum algorithms can provide an advantage, and if so how to design quantum algorithms that realize such advantages. Today, classical heuristics are used to solve many of the most challenging computational problems arising in the practical world, algorithms that have been shown to be effective empirically but have not been mathematically proven to outperform other approaches. With the advent of quantum advantage, the ability of current quantum hardware to do certain computations beyond the ability of even that largest supercomputers, we have an unprecedented opportunity to explore heuristic quantum algorithms. The next few years will be exciting as empirical testing of quantum heuristic algorithms becomes more and more feasible. The talk will begin overview of the NASA QuAIL team’s ongoing quantum computing investigations, and then focus on both near-term and longer term algorithms for optimization, including distributed algorithms.

quantum computing↗

Aerial drone fleet deployment optimization with endogenous battery replacements for direct delivery of time-sensitive products

Aerial drones offer a distinct potential to reduce the delivery time and energy consumption for the delivery of time-sensitive and small products. However, there is still a need in the relevant industry to understand the performance of drone-based delivery under different business needs and drone operating conditions. We studied a drone deployment optimization problem for direct delivery of time-sensitive products with release dates to customers maintaining a specified time window. This paper presents a new mixed-integer programming model, new valid inequalities, a new greedy heuristic algorithm, and a Genetic algorithm to help business owners optimally schedule and route their drone fleet minimizing the required fleet size, the required number of additional batteries, and total energy consumption. A realistic feature of the optimization method is that instead of replacing the drone battery after each return to the depot, it keeps track of the remaining energy in the drone battery and decides on battery replacements accounting for the drone routing and the user-specified minimum required battery energy. Numerical results based on real data from drone flight tests and prepared food delivery industry provide insights into the effect of different practical drone operating parameters on the required fleet size, the required number of battery replacements, and energy consumption. Here, results demonstrate that the proposed heuristic algorithm substantially outperforms the accelerated CPLEX in runtime while sacrificing the solution quality by a small amount. Additionally, results show that using a mixed fleet of hexacopter and quadcopter drones reduces the total energy consumption by 48.52% compared to using a homogeneous fleet of only hexacopters.

Drone energy consumption↗

A Flexible Forwarding Scheme to Improve Latency-Bound Irregular P2P Communication in MPI

We propose an algorithm to efficiently perform latency-bound communication scenarios that consist of many small messages. In these parallel scenarios, processes typically pass around a lot of small-sized messages of a few KBs of size. Performing communication operations with P2P MPI routines or collective MPI routines (including neighborhood collectives) in such scenarios may not always yield the optimal results and may not resolve the latency bottleneck. To this end, we develop a regular structure called virtual process topology (VPT) on which the messages can be communicated in a structured and controlled manner. Using parameters of this topology, one can tune the rate of aggression in tackling the latency costs. We demonstrate that our communication algorithm is preferable to MPI P2P and collective routines for latency-bound communication and it can easily be adapted only by replacing calls to MPI routines in a parallel application. We show how to adapt existing topology-aware mapping heuristics to address the volume overhead due to communicating messages on the VPT. Moreover, we propose a novel swap-based mapping heuristic to address this overhead by optimizing the maximum volume handled by a process. Experiments on synthetic communication graphs as well as real-world applications such as parallel Canonical Polyadic sparse tensor decomposition and parallel sparse matrix-dense matrix multiplication show that our approach is a powerful way of overcoming the bottlenecks posed by sparse and latency-bound irregular communication.

communication algorithm↗

Richtmyer–Meshkov instability when a shock is reflected for fluids with arbitrary equation of state

First predicted by Richtmyer in 1960 and experimentally confirmed by Meshkov in 1969, the Richtmyer–Meshkov instability (RMI) is crucial in fields such as physics, astrophysics, inertial confinement fusion and high-energy-density physics. These disciplines often deal with strong shocks moving through condensed materials or high-pressure plasmas that exhibit non-ideal equations of state (EoS), thus requiring theoretical models with realistic fluid EoS for accurate RMI simulations. Approximate formulae for asymptotic growth rates, like those proposed by Richtmyer, are helpful but rely on heuristic prescriptions for compressible materials. These prescriptions can sometimes approximate the RMI growth rate well, but their accuracy remains uncertain without exact solutions, as the fully compressible RMI growth rate is influenced by both vorticity deposited during shock refraction and multiple sonic wave refractions. This study advances previous work by presenting an analytic, fully compressible theory of RMI for reflected shocks with arbitrary EoS. It compares theoretical predictions with heuristic prescriptions using ideal gas, van der Waals gas and three-term constitutive equations for simple metals, the latter being analysed with detailed and simplified ideal-gas-like EoS. We additionally offer an alternative explicit approximate formula for the asymptotic growth rate. The comprehensive model also incorporates the effects of constant-amplitude acoustic waves at the interface, associated with the D'yakov–Kontorovich instability in shocks.

Napieralski, Mario (ORCID:0009000692344901)↗

On the Dependence of Simulated Convection on Domain Size in CRMs

Abstract We present a heuristic model to explain the suppression of deep convection in convection‐resolving models (CRMs) with a small number of grid columns, such as those used in super‐parameterized or multi‐scale modeling framework (MMF) general circulation models (GCM) of the atmosphere. Domains with few grid columns require greater instability to sustain convection because they force a large convective fraction, driving strong compensating subsidence warming. Updraft dilution, which is stronger for reduced horizontal grid spacing, enhances this effect. Thus, suppression of deep convection in CRMs with few grid columns can be reduced by increasing grid spacing. Radiative‐convective equilibrium simulations using standalone CRM simulations with the System for Atmospheric Modeling (SAM) and using GCM‐coupled CRM simulations with the Energy Exascale Earth System Model (E3SM)‐MMF confirm the heuristic model results.

CRM↗

High-throughput computation of electric polarization in solids via Berry flux diagonalization

Electric polarization in the absence of an externally applied electric field is a key property of polar materials, but the standard interpolation-based ab initio approach to compute polarization differences within the modern theory of polarization presents challenges for automated high-throughput calculations. Berry flux diagonalization [J. Bonini et al., Phys. Rev. B 102, 045141 (2020)] has been proposed as an efficient and reliable alternative, though it has yet to be widely deployed. Here, we assess Berry flux diagonalization using ab initio calculations of a large set of materials, introducing and validating heuristics that ensure branch alignment with a minimal number of intermediate interpolated structures. Our automated implementation of Berry flux diagonalization succeeds in cases where prior interpolation-based workflows fail due to band-gap closures or branch ambiguities. Benchmarking with ab initio calculations of 176 candidate ferroelectrics, we demonstrate the efficacy of the approach on a broad range of insulating materials and obtain accurate effective polarization values with fewer interpolated structures than prior automated interpolation-based workflows. Our real-space heuristics that can predict gauge stability a priori from ionic displacements enable a general automated framework for reliable polarization calculations and efficient high-throughput screening of chemically and structurally diverse polar insulators. These results establish Berry flux diagonalization as a robust and efficient method to compute the effective polarization of solids and to accelerate the data-driven discovery of functional polar materials.

Poteshman, Abigail N. [University of Chicago, IL (↗

Artificial-intelligence-driven shot reduction in quantum measurement

Variational Quantum Eigensolver (VQE) provides a powerful solution for approximating molecular ground state energies by combining quantum circuits and classical computers. However, estimating probabilistic outcomes on quantum hardware requires repeated measurements (shots), incurring significant costs as accuracy increases. Optimizing shot allocation is thus critical for improving the efficiency of VQE. Current strategies rely heavily on hand-crafted heuristics requiring extensive expert knowledge. This paper proposes a reinforcement learning (RL)-based approach that automatically learns shot assignment policies to minimize total measurement shots while achieving convergence to the minimum of the energy expectation in VQE. The RL agent assigns measurement shots across VQE optimization iterations based on the progress of the optimization. This approach reduces VQE's dependence on static heuristics and human expertise. When the RL-enabled VQE is applied to a small molecule, a shot reduction policy is learned. The policy demonstrates transferability across systems and compatibility with other wavefunction Ansätze. In addition to these specific findings, this work highlights the potential of RL for automatically discovering efficient and scalable quantum optimization strategies.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗