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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 289 records · Page 16

All sources NASA NTRS DOE OSTI

NASA NTRS1990

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.↗

NASA NTRS1994

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↗

NASA NTRS2003

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↗

NASA NTRS2003

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↗

NASA NTRS2011

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↗

NASA NTRS2017

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↗

NASA NTRSDate not supplied

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↗

NASA NTRS2021

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↗

NASA NTRSDate not supplied

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↗

NASA NTRSDate not supplied

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↗

DOE OSTI2018

Bandwidth preemption for high-priority data transfer on dedicated channels

Bandwidth reservation has been increasingly used to provide QoS for various network applications. To accommodate a high-priority bandwidth reservation request (BRR), the bandwidth scheduler sometimes needs to preempt existing bandwidth reservations that have been made for BRRs with a lower priority, which is traditionally known as connection preemption. When such preemption is unavoidable, one primary goal of bandwidth scheduling is to minimize the disruption to existing reservations. In this paper, we study the problem of bandwidth reservation preemption for two types of BRRs, bandwidth- and data transfer oriented, respectively, on one given link of the scheduling network with two different objectives: (i) minimize the number and then the total bandwidth of existing bandwidth reservations to be preempted, and (ii) minimize the total bandwidth and then the number of existing bandwidth reservations to be preempted. We prove these four problems to be NP-complete and propose a heuristic algorithm for each. We also design baseline heuristic algorithms for performance comparison. Extensive simulation results show that the proposed heuristic algorithms outperform those in comparison.

Rao, Nageswara↗

DOE OSTI2017

Sustainable network design for multi-purpose pellet processing depots under biomass supply uncertainty

This work develops a two-stage stochastic mixed-integer programming model to manage multi- purpose pellet processing depots under feedstock supply uncertainty. The proposed optimization model would help to minimize cost and to mitigate emissions from the supply chain network. We consider three alternative Biomass Processing and Densi cation Depot (BPDD) technologies; namely, conventional pellet processing, high moisture pellet processing, and ammonia ber expansion. These three technologies pre-process/pre-treat and densify different types of biomass into more highly densi ed intermediate products for different markets in order to improve movability and overall supply network performance in terms of costs and emissions. A hybrid decomposition algorithm was developed that combines sample average approximation with an enhanced Progressive Hedging (PH) algorithm to solve this challenging NP -hard problem. Some heuristics such as Rolling Horizon (RH) heuristic, variable xing technique were later applied to further enhance the PH algorithm. Mississippi and Alabama were selected as a testing ground and ArcGIS was employed to visualize and validate the modeling results. The results of the analysis reveal promising insights that could lead to recommendations to help decision makers achieve a more cost-effective environmentally-friendly supply chain network.

09 BIOMASS FUELS↗

DOE OSTI2024

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↗

DOE OSTI2026

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↗

DOE OSTI2014

Modeling transmission line constraints in two-stage robust unit commitment problem

Integration of renewable energy sources and demand response poses new challenges to system operators as they increase the uncertainty of the power supply and demand. Recently, robust optimization techniques are applied to the unit commitment problem with uncertainty as an alternative to the stochastic programming approaches. However, it remains challenging to solve the robust unit commitment model with full transmission line constraints. In this paper, we propose novel acceleration techniques for solving two-stage robust unit commitment problem with consideration of full transmission line constraints. We use 1) the cutting-plane algorithm for the master problem, which dynamically includes critical transmission line constraints, and 2) column-generation methods, including the branch-and-price-and-cut algorithm and heuristic approaches, for the subproblems, which add only necessary transmission line dual variables on the fly. Furthermore, computational results for the modified IEEE 118-bus system show that the combination of the cutting-plane algorithm and the heuristic column-generation approach greatly reduces the total solution time of the two-stage robust unit commitment problem.

Heuristic algorithms↗

DOE OSTI2014

Topology Control for Load Shed Recovery

This paper introduces load shed recovery actions for transmission networks by presenting the dc optimal load shed recovery with transmission switching model (DCOLSR-TS). The model seeks to reduce the amount of load shed, which may result due to transmission line and/or generator contingencies, by modifying the bulk power system topology. Since solving DCOLSR-TS is computationally difficult, the current work also develops a heuristic (MIP-H), which improves the system topology while specifying the required sequence of switching operations. Experimental results on a list of N-1 and N-2 critical contingencies of the IEEE 118-bus test case demonstrate the advantages of utilizing MIP-H for both on-line load shed recovery and recurring contingency-response analysis. This is reinforced by the introduction of a parallelized version of the heuristic (Par-MIP-H), which solves the list of critical contingencies close to 5x faster than MIP-H with 8 cores and up to 14x faster with increased computational resources. The current work also tests MIP-H on a real-life, large-scale network in order to measure the computational performance of this tool on a real-world implementation.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2021

Usability Evaluation of the Innovation Portal and Integrated Capability Analysis Platform

The usability evaluation of the ICAP and IP tools was conducted as part of the United States (U.S.) Department of Energy (DOE) Light Water Reactor Sustainability (LWRS) ION effort with two evaluators for the Idaho National Laboratory. Many nuclear operations in the United States are facing challenges of increased business, operations, and maintenance costs due to subsidized renewables and natural gas. The commercial NPP industry has looked to other industries to develop methods such as Integrated Operations (IO) to use available technologies to reduce operating costs. One concept for reducing costs that has been developed is the Integrated Operations for Nuclear (ION). A capability Stack model was developed as part of the ION effort to break down information related to People, Technology, Processes, and Governance (PTPG). The Innovation Portal (IP) and Integrated Capability Analysis Platform (ICAP) were created from the Capability Stack model as part of the ION effort to help utilities reduce O&M costs by identifying work reduction opportunities. Two heuristic evaluations and a cognitive walkthrough of the ICAP and IP tools were completed to identify usability issues to further develop the tools for use in the ION effort. Usability issues identified were rated by priority levels and across both tools. The priority levels identified were high (5), medium (11), and low (10). Recommendation were made to help reduce usability issues of the systems and help increase the user response rate of using the systems once they are implemented for utilities. Future work on designs for the IP tool and additional heuristic evaluations and external testing are being developed to continue refinement of the ICAP and IP tools for the ION effort.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

DOE OSTI2016

River stage influences on uranium transport in a hydrologically dynamic groundwater-surface water transition zone

In this study, a well-field within a uranium (U) plume in the groundwater-surface water transition zone was monitored for a 3 year period for water table elevation and dissolved solutes. The plume discharges to the Columbia River, which displays a dramatic spring stage surge resulting from snowmelt. Groundwater exhibits a low hydrologic gradient and chemical differences with river water. River water intrudes the site in spring. Specific aims were to assess the impacts of river intrusion on dissolved uranium (U aq ), specific conductance (SpC), and other solutes, and to discriminate between transport, geochemical, and source term heterogeneity effects. Time series trends for U aq and SpC were complex and displayed large temporal and well-to-well variability as a result of water table elevation fluctuations, river water intrusion, and changes in groundwater flow directions. The wells were clustered into subsets exhibiting common behaviors resulting from the intrusion dynamics of river water and the location of source terms. Hot-spots in U aq varied in location with increasing water table elevation through the combined effects of advection and source term location. Heuristic reactive transport modeling with PFLOTRAN demonstrated that mobilized U aq was transported between wells and source terms in complex trajectories, and was diluted as river water entered and exited the groundwater system. While U aq time-series concentration trends varied significantly from year-to-year as a result of climate-caused differences in the spring hydrograph, common and partly predictable response patterns were observed that were driven by water table elevation, and the extent and duration of river water intrusion.

54 ENVIRONMENTAL SCIENCES↗