Search NASA⌕ Search

SEARCH · Search NASA

Results for “Heuristic Optimization”

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
All sourcesNASA NTRSDOE OSTI
NASA NTRS2017

Efficient Trajectory Options Allocation for the Collaborative Trajectory Options Program

The Collaborative Trajectory Options Program (CTOP) is a Traffic Management Initiative (TMI) intended to control the air traffic flow rates at multiple specified Flow Constrained Areas (FCAs), where demand exceeds capacity. CTOP allows flight operators to submit the desired Trajectory Options Set (TOS) for each affected flight with associated Relative Trajectory Cost (RTC) for each option. CTOP then creates a feasible schedule that complies with capacity constraints by assigning affected flights with routes and departure delays in such a way as to minimize the total cost while maintaining equity across flight operators. The current version of CTOP implements a Ration-by-Schedule (RBS) scheme, which assigns the best available options to flights based on a First-Scheduled-First-Served heuristic. In the present study, an alternative flight scheduling approach is developed based on linear optimization. Results suggest that such an approach can significantly reduce flight delays, in the deterministic case, while maintaining equity as defined using a Max-Min fairness scheme.

Rodionova, O.↗
NASA NTRS2022

Predicting Unreinforced Fabric Mechanical Behavior with Recurrent Neural Networks

Unreinforced woven fabrics are widely employed in various high-performance applications, including parachute deployment systems, airbags, and ballistic armor. The analysis of such materials is inherently complex due to the multiscale structure of these materials, and the dependence of macroscale behavior on changes that occur at lower scales. Previously, NASA’s Multiscale Analysis Tool (NASMAT) showed its capability in predicting unreinforced fabric behavior at the macroscale by capturing finite rotations that occur at the mesoscale. Though effective, the tool can face high computational cost for large, complex problems, motivating the need for the development of a surrogate model that can capture the same behavior. A recurrent neural network (RNN) was developed and trained on virtual NASMAT data to mimic the physics-based solutions while improving the computational runtime. The architecture of the RNN to best simulate the fabric behavior was carefully crafted based on heuristic knowledge of predicting physics-based temporal data, manual hyperparameter case studies, and Hyperband optimization.. The resultant model was able to predict a variety of stress-strain curves for fabrics with different mesoscale geometries, and was further validated by comparing to experimental data for the K706 style Kevlar plain-weave fabric, demonstrating the ability of the model to effectively capture the geometric changes in the fabric without explicitly calculating them, as is done in NASMAT. Furthermore, the tool showed its ability to improve on the runtime by a factor of 10 for fabric solutions compared to the multiscale tool, which would further enable the simulation of complex loading scenarios on unreinforced fabrics.

Fabric↗
NASA NTRS1989

Minimum-variance reduced-order estimation algorithms from Pontrygin's minimum principle

A uniform derivation of minimum-variance reduced-order (MVRO) filter-smoother algorithms from Pontrygin's Minimum Principle is presented. An appropriate performance index for a general class of reduced order estimation problem is formulated herein to yield optimal results over the entire time interval of estimation. These results provide quantitative criteria for measuring the performance of certain classes of heuristically designed, suboptimal reduced-order estimators as well as explicit guidance to the suboptimal filter design process with both continuous and discrete filter-smoother algorithms being considered. By the duality principle, the algorithms of reduced-order estimation can be easily extended to the deterministic problems of optimal control (i.e., the regulator and linear tracking problem).

Ebrahimi, Yaghoob S.↗
DOE OSTI2024

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗
DOE OSTI2025

An Optimization-Based Law of Mass Action Precipitation/Dissolution Model

Rare earth elements (REE) and many other critical minerals are necessary for the manufacturing of modern everyday technologies, including microchips, batteries and electric motors. Recovery of these materials typically involves aqueous systems which can be modeled as chemical equilibrium problems. One common method for solving these problems is the law of mass action approach (LMA), where a system of non-linear equations involving the equilibrium constants is solved. However, despite being theoretically simple, these problems are in practice very difficult to solve. Currently, the use of iterative heuristics based on saturation indices to decide on which species and reactions to include in the calculations is the state of the art to arrive at a solution. Here, we present an optimization-based alternative to solve chemical equilibria problems involving precipitation/dissolution reactions without the need for such heuristics. Our approach is first validated against the LMA software MINTEQ and PHREEQC for a number of case studies, and then applied to a novel REE recovery process reported in the literature. Overall, our approach was found to have close agreement with MINTEQ and PHREEQC, and we were able to successfully replicate the reported yield and purity for the published REE process.

42 ENGINEERING↗
NASA NTRS1990

Evolutionary tree reconstruction

It is described how Minimum Description Length (MDL) can be applied to the problem of DNA and protein evolutionary tree reconstruction. If there is a set of mutations that transform a common ancestor into a set of the known sequences, and this description is shorter than the information to encode the known sequences directly, then strong evidence for an evolutionary relationship has been found. A heuristic algorithm is described that searches for the simplest tree (smallest MDL) that finds close to optimal trees on the test data. Various ways of extending the MDL theory to more complex evolutionary relationships are discussed.

Cheeseman, Peter↗
NASA NTRS1996

Algorithms for Automatic Alignment of Arrays

Aggregate data objects (such as arrays) are distributed across the processor memories when compiling a data-parallel language for a distributed-memory machine. The mapping determines the amount of communication needed to bring operands of parallel operations into alignment with each other. A common approach is to break the mapping into two stages: an alignment that maps all the objects to an abstract template, followed by a distribution that maps the template to the processors. This paper describes algorithms for solving the various facets of the alignment problem: axis and stride alignment, static and mobile offset alignment, and replication labeling. We show that optimal axis and stride alignment is NP-complete for general program graphs, and give a heuristic method 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. We also show how local graph contractions can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. We show how to model the static offset alignment problem using linear programming, and we show that loop-dependent mobile offset alignment is sometimes necessary for optimum performance. We describe an algorithm with for determining mobile alignments for objects within do loops. We also identify situations in which replicated alignment is either required by the program itself or can be used to improve performance. We describe an algorithm based on network flow that replicates objects so as to minimize the total amount of broadcast communication in replication.

Chatterjee, Siddhartha↗
NASA NTRSDate not supplied

Planning Satellite Swarm Measurements for Climate Models: Comparing Dynamic Constraint Processing and MILP Methods

We present D-SHIELD, a challenging climate science application to plan coordinated measurements (observations) for a constellation of satellites, each containing two different sensors, each with 61 pointing angle options. The L-band and P-band radar sensors collect data fed into a soil moisture model which tracks and predicts soil moisture across 1.67 million Ground Positions (GP). Soil moisture is an important predictor of wildfires, and then a predictor of floods, landslides and debris flow after a fire. Each measurement covers multiple GP due to the sensor footprint. Each GP has a "model error" which represents the uncertainty of the the soil moisture state prediction. Model error changes at different rates for each GP as the time since last observation increases and after significant events like rain. The planner's goal is to select measurements which maximize soil moisture model improvement (reduce model uncertainty). This problem is combinatorically explosive, involving many degrees of freedom for planner choices. Good domain heuristics can find solutions within a reasonable time for our application needs but cannot be proven optimal. In this paper we compare two different planning approaches to this problem: Dynamic Constraint Processing (DCP) and Mixed Integer Linear Programming (MILP). We match inputs and metrics for both DCP and MILP algorithms to enable a direct apples-to-apples comparison. We demonstrate and discuss the trades between DCP flexibility and performance vs. MILP's promise of provable optimality.

Rich Levinson↗
NASA NTRS2002

CATS-based Air Traffic Controller Agents

This report describes intelligent agents that function as air traffic controllers. Each agent controls traffic in a single sector in real time; agents controlling traffic in adjoining sectors can coordinate to manage an arrival flow across a given meter fix. The purpose of this research is threefold. First, it seeks to study the design of agents for controlling complex systems. In particular, it investigates agent planning and reactive control functionality in a dynamic environment in which a variety perceptual and decision making skills play a central role. It examines how heuristic rules can be applied to model planning and decision making skills, rather than attempting to apply optimization methods. Thus, the research attempts to develop intelligent agents that provide an approximation of human air traffic controller behavior that, while not based on an explicit cognitive model, does produce task performance consistent with the way human air traffic controllers operate. Second, this research sought to extend previous research on using the Crew Activity Tracking System (CATS) as the basis for intelligent agents. The agents use a high-level model of air traffic controller activities to structure the control task. To execute an activity in the CATS model, according to the current task context, the agents reference a 'skill library' and 'control rules' that in turn execute the pattern recognition, planning, and decision-making required to perform the activity. Applying the skills enables the agents to modify their representation of the current control situation (i.e., the 'flick' or 'picture'). The updated representation supports the next activity in a cycle of action that, taken as a whole, simulates air traffic controller behavior. A third, practical motivation for this research is to use intelligent agents to support evaluation of new air traffic control (ATC) methods to support new Air Traffic Management (ATM) concepts. Current approaches that use large, human-in-the-loop simulations are unquestionably valuable for this purpose, but pose considerable logistical, fiscal, and experimental control problems. First, data analysis is extremely complicated, owing simply to the large number of participants and data sources in such simulations. In addition, experienced human air traffic controllers working adjacent sectors tend to flexibly adapt to the evolving control problem - potentially shifting to other strategies than those under investigation. In addition, their performance is tightly coupled to the control interface, which in the development phase may support some concepts and supporting strategies better than others. A simple shift in strategy by one controller can change the character of a particular traffic scenario dramatically, which makes experimental comparison of ATC performance under different traffic scenarios difficult. Training a given team of controllers on operations under a new ATM concept for a sufficient period of time could avert such difficulties, but instituting an adequate training program is expensive and logistically difficult.

Callantine, Todd J.↗
DOE OSTI2025

A New Hybrid Quantum-Classical Algorithm for Solving the Unit Commitment Problem

Solving problems related to planning and operations of large-scale power systems is challenging on classical computers due to their inherent nature as mixed-integer and nonlinear problems. Quantum computing provides new avenues to approach these problems. We develop a hybrid quantum-classical algorithm for the Unit Commitment (UC) problem in power systems which aims at minimizing the total cost while optimally allocating generating units to meet the hourly demand of the power loads. The hybrid algorithm combines a variational quantum algorithm (VQA) with a classical Benders-type heuristic. The resulting algorithm computes approximate solutions to UC in three stages: i) a collection of UC vectors capable meeting the power demand with lowest possible operating costs is generated based on VQA; ii) a classical sequential least squares programming (SLSQP) routine is leveraged to find the optimal power level corresponding to a predetermined number of candidate vectors; iii) in the last stage, the approximate solution of UC along with generating units power level combination is given. To demonstrate the effectiveness of the presented method, three different systems with 3 generating units, 10 generating units, and 26 generating units were tested for different time periods. In addition, convergence of the hybrid quantum-classical algorithm for select time periods is proven out on IonQ's Forte system.

Aboumrad, Willie [IonQ, Inc]↗
DOE OSTI2025

Trust Your Gut: Comparing Human and Machine Inference from Noisy Visualizations

People commonly utilize visualizations not only to examine a given dataset, but also to draw generalizable conclusions about the underlying models or phenomena. Prior research has compared human visual inference to that of an optimal Bayesian agent, with deviations from rational analysis viewed as problematic. However, human reliance on non-normative heuristics may prove advantageous in certain circumstances. We investigate scenarios where human intuition might surpass idealized statistical rationality. In two experiments, we examine individuals’ accuracy in characterizing the parameters of known data-generating models from bivariate visualizations. Our findings indicate that, although participants generally exhibited lower accuracy compared to statistical models, they frequently outperformed Bayesian agents, particularly when faced with extreme samples. Participants appeared to rely on their internal models to filter out noisy visualizations, thus improving their resilience against spurious data. However, participants displayed overconfidence and struggled with uncertainty estimation. They also exhibited higher variance than statistical machines. Our findings suggest that analyst gut reactions to visualizations may provide an advantage, even when departing from rationality. These results carry implications for designing visual analytics tools, offering new perspectives on how to integrate statistical models and analyst intuition for improved inference and decision-making. The data and materials for this paper are available at https://osf.io/qmfv6

human-machine collaboration↗
DOE OSTI2024

Improving Self-Driving Labs: Quantifying System-Level Experiment Repeatability and Broadening Instrument-Level Compatibility

Modular Autonomous Research System (MARS) is a self-driving laboratory (SDL) which performs wet-lab science with peptide-lanthanide combinations in an automated and, ultimately, an autonomous manner to aid in soil analysis for domestic lithium mining. Autonomous experimentation involves automated experimentation, experiment planning, and active learning. MARS consists of a 6-axis robotic arm (UR5e) on a linear rail, pipette robots (Opentrons 2), and microplate readers. These components transport, operate on, and collect data with chemical solutions in standard labware. For effective autonomy, MARS must perform system-level labware operations repeatably, plan experiments autonomously, and be portable between research-domains. Repeatability is evaluated by labware placement precision, such that future operations can properly locate labware, as well as the elapsed time, so that low variance mean estimates of experiment duration can inform high-level researcher decision making. Autonomous experiment planning is the next step to decouple experimentation from human management; however, there is a conflict between the ideal system-level experiment goals and the constraints imposed by instruments’ limitations. Sub-domain portability is a long-term goal to extend MARS’ research beyond the chemistry of peptide-lanthanide binding to other sub-domains without having to invest significant overhead to system retrofitting. To address these goals, we manually trained the robotic arm labware placement and modelled statistical failurerate and uncertainty Additionally, we benchmarked the duration and variance of each experiment sub-operation as a heuristic for research decision making. Next, we use a parameterized geometric program (PGP) approach to design experiments that optimize system-level objectives and satisfy instrument-level constraints. Lastly, we proposed a Python framework to maximize MARS’ extensibility to other scientific sub-domains through a JSON-based experiment specification.

36 MATERIALS SCIENCE↗
NASA NTRS1989

A real-time expert system for self-repairing flight control

An integrated environment for specifying, prototyping, and implementing a self-repairing flight-control (SRFC) strategy is described. At an interactive workstation, the user can select paradigms such as rule-based expert systems, state-transition diagrams, and signal-flow graphs and hierarchically nest them, assign timing and priority attributes, establish blackboard-type communication, and specify concurrent execution on single or multiple processors. High-fidelity nonlinear simulations of aircraft and SRFC systems can be performed off-line, with the possibility of changing SRFC rules, inference strategies, and other heuristics to correct for control deficiencies. Finally, the off-line-generated SRFC can be transformed into highly optimized application-specific real-time C-language code. An application of this environment to the design of aircraft fault detection, isolation, and accommodation algorithms is presented in detail.

Gaither, S. A.↗
NASA NTRS1998

Performance Analysis and Portability of the PLUM Load Balancing System

The ability to dynamically adapt an unstructured mesh is a powerful tool for solving computational problems with evolving physical features; however, an efficient parallel implementation is rather difficult. To address this problem, we have developed PLUM, an automatic portable framework for performing adaptive numerical computations in a message-passing environment. PLUM requires that all data be globally redistributed after each mesh adaption to achieve load balance. We present an algorithm for minimizing this remapping overhead by guaranteeing an optimal processor reassignment. We also show that the data redistribution cost can be significantly reduced by applying our heuristic processor reassignment algorithm to the default mapping of the parallel partitioner. Portability is examined by comparing performance on a SP2, an Origin2000, and a T3E. Results show that PLUM can be successfully ported to different platforms without any code modifications.

Oliker, Leonid↗
NASA NTRS2012

Calibration of Airframe and Occupant Models for Two Full-Scale Rotorcraft Crash Tests

Two full-scale crash tests of an MD-500 helicopter were conducted in 2009 and 2010 at NASA Langley's Landing and Impact Research Facility in support of NASA s Subsonic Rotary Wing Crashworthiness Project. The first crash test was conducted to evaluate the performance of an externally mounted composite deployable energy absorber under combined impact conditions. In the second crash test, the energy absorber was removed to establish baseline loads that are regarded as severe but survivable. Accelerations and kinematic data collected from the crash tests were compared to a system integrated finite element model of the test article. Results from 19 accelerometers placed throughout the airframe were compared to finite element model responses. The model developed for the purposes of predicting acceleration responses from the first crash test was inadequate when evaluating more severe conditions seen in the second crash test. A newly developed model calibration approach that includes uncertainty estimation, parameter sensitivity, impact shape orthogonality, and numerical optimization was used to calibrate model results for the second full-scale crash test. This combination of heuristic and quantitative methods was used to identify modeling deficiencies, evaluate parameter importance, and propose required model changes. It is shown that the multi-dimensional calibration techniques presented here are particularly effective in identifying model adequacy. Acceleration results for the calibrated model were compared to test results and the original model results. There was a noticeable improvement in the pilot and co-pilot region, a slight improvement in the occupant model response, and an over-stiffening effect in the passenger region. This approach should be adopted early on, in combination with the building-block approaches that are customarily used, for model development and test planning guidance. Complete crash simulations with validated finite element models can be used to satisfy crash certification requirements, thereby reducing overall development costs.

Annett, Martin S.↗
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗
NASA NTRS1976

On optimal control of linear systems in the presence of multiplicative noise

This correspondence considers the problem of optimal regulator design for discrete time linear systems subjected to white state-dependent and control-dependent noise in addition to additive white noise in the input and the observations. A pseudo-deterministic problem is first defined in which multiplicative and additive input disturbances are present, but noise-free measurements of the complete state vector are available. This problem is solved via discrete dynamic programming. Next is formulated the problem in which the number of measurements is less than that of the state variables and the measurements are contaminated with state-dependent noise. The inseparability of control and estimation is brought into focus, and an 'enforced separation' solution is obtained via heuristic reasoning in which the control gains are shown to be the same as those in the pseudo-deterministic problem. An optimal linear state estimator is given in order to implement the controller.

Joshi, S. M.↗