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 55 records · Page 3

All sources NASA NTRS DOE OSTI

NASA NTRS1990

Application of heuristic satellite plan synthesis algorithms to requirements of the WARC-88 allotment plan

Creation of an Allotment Plan for the Fixed Satellite Service at the 1988 Space World Administrative Radio Conference (WARC) represented a complex satellite plan synthesis problem, involving a large number of planned and existing systems. Solutions to this problem at WARC-88 required the use of both automated and manual procedures to develop an acceptable set of system positions. Development of an Allotment Plan may also be attempted through solution of an optimization problem, known as the Satellite Location Problem (SLP). Three automated heuristic procedures, developed specifically to solve SLP, are presented. The heuristics are then applied to two specific WARC-88 scenarios. Solutions resulting from the fully automated heuristics are then compared with solutions obtained at WARC-88 through a combination of both automated and manual planning efforts.

Heyward, Ann O.↗

NASA NTRS1990

Application of heuristic satellite plan synthesis algorithms to requirements of the WARC-88 allotment plan

Heyward, Ann O.↗

NASA NTRS1991

The min-conflicts heuristic: Experimental and theoretical results

This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching through the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been successfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.

Minton, Steven↗

NASA NTRS1993

Planning collision free paths for two cooperating robots using a divide-and-conquer C-space traversal heuristic

A method was developed to plan feasible and obstacle-avoiding paths for two spatial robots working cooperatively in a known static environment. Cooperating spatial robots as referred to herein are robots which work in 6D task space while simultaneously grasping and manipulating a common, rigid payload. The approach is configuration space (c-space) based and performs selective rather than exhaustive c-space mapping. No expensive precomputations are required. A novel, divide-and-conquer type of heuristic is used to guide the selective mapping process. The heuristic does not involve any robot, environment, or task specific assumptions. A technique was also developed which enables solution of the cooperating redundant robot path planning problem without requiring the use of inverse kinematics for a redundant robot. The path planning strategy involves first attempting to traverse along the configuration space vector from the start point towards the goal point. If an unsafe region is encountered, an intermediate via point is identified by conducting a systematic search in the hyperplane orthogonal to and bisecting the unsafe region of the vector. This process is repeatedly applied until a solution to the global path planning problem is obtained. The basic concept behind this strategy is that better local decisions at the beginning of the trouble region may be made if a possible way around the 'center' of the trouble region is known. Thus, rather than attempting paths which look promising locally (at the beginning of a trouble region) but which may not yield overall results, the heuristic attempts local strategies that appear promising for circumventing the unsafe region.

Weaver, Johnathan M.↗

NASA NTRS2004

Plan-graph Based Heuristics for Conformant Probabilistic Planning

In this paper, we introduce plan-graph based heuristics to solve a variation of the conformant probabilistic planning (CPP) problem. In many real-world problems, it is the case that the sensors are unreliable or take too many resources to provide knowledge about the environment. These domains are better modeled as conformant planning problems. POMDP based techniques are currently the most successful approach for solving CPP but have the limitation of state- space explosion. Recent advances in deterministic and conformant planning have shown that plan-graphs can be used to enhance the performance significantly. We show that this enhancement can also be translated to CPP. We describe our process for developing the plan-graph heuristics and estimating the probability of a partial plan. We compare the performance of our planner PVHPOP when used with different heuristics. We also perform a comparison with a POMDP solver to show over a order of magnitude improvement in performance.

Ramakrishnan, Salesh↗

NASA NTRS2010

Tuning Parameters in Heuristics by Using Design of Experiments Methods

With the growing complexity of today's large scale problems, it has become more difficult to find optimal solutions by using exact mathematical methods. The need to find near-optimal solutions in an acceptable time frame requires heuristic approaches. In many cases, however, most heuristics have several parameters that need to be "tuned" before they can reach good results. The problem then turns into "finding best parameter setting" for the heuristics to solve the problems efficiently and timely. One-Factor-At-a-Time (OFAT) approach for parameter tuning neglects the interactions between parameters. Design of Experiments (DOE) tools can be instead employed to tune the parameters more effectively. In this paper, we seek the best parameter setting for a Genetic Algorithm (GA) to solve the single machine total weighted tardiness problem in which n jobs must be scheduled on a single machine without preemption, and the objective is to minimize the total weighted tardiness. Benchmark instances for the problem are available in the literature. To fine tune the GA parameters in the most efficient way, we compare multiple DOE models including 2-level (2k ) full factorial design, orthogonal array design, central composite design, D-optimal design and signal-to-noise (SIN) ratios. In each DOE method, a mathematical model is created using regression analysis, and solved to obtain the best parameter setting. After verification runs using the tuned parameter setting, the preliminary results for optimal solutions of multiple instances were found efficiently.

Arin, Arif↗

NASA NTRS2016

Exact and Heuristic Algorithms for Runway Scheduling

This paper explores the Single Runway Scheduling (SRS) problem with arrivals, departures, and crossing aircraft on the airport surface. Constraints for wake vortex separations, departure area navigation separations and departure time window restrictions are explicitly considered. The main objective of this research is to develop exact and heuristic based algorithms that can be used in real-time decision support tools for Air Traffic Control Tower (ATCT) controllers. The paper provides a multi-objective dynamic programming (DP) based algorithm that finds the exact solution to the SRS problem, but may prove unusable for application in real-time environment due to large computation times for moderate sized problems. We next propose a second algorithm that uses heuristics to restrict the search space for the DP based algorithm. A third algorithm based on a combination of insertion and local search (ILS) heuristics is then presented. Simulation conducted for the east side of Dallas/Fort Worth International Airport allows comparison of the three proposed algorithms and indicates that the ILS algorithm performs favorably in its ability to find efficient solutions and its computation times.

safe & surface operations↗

DOE OSTI2020

Cooperative Routing for an Air–Ground Vehicle Team—Exact Algorithm, Transformation Method, and Heuristics

This paper considers a cooperative vehicle routing problem for an intelligence, surveillance, and reconnaissance mission in the presence of communication constraints between the vehicles. The proposed framework uses a ground vehicle and an unmanned aerial vehicle (UAV) that travel cooperatively and visit a set of targets while satisfying the communication constraints. The problem is formulated as a mixed-integer linear program, and a branch-and-cut algorithm is developed to solve the problem to optimality. Furthermore, a transformation method and a heuristic are also developed for the problem. The effectiveness of all the algorithms is corroborated through extensive computational experiments on several randomly generated instances. Furthermore, this paper is motivated by an intelligence, surveillance, and reconnaissance mission involving a single unmanned aerial vehicle (UAV) and a ground vehicle, where the vehicles must coordinate their activity in the presence of communication constraints. The combination of a small UAV and a ground vehicle is an ideal platform for such missions, since small UAVs can fly at low altitudes and can avoid obstacles or threats that would be problematic for the ground vehicle alone. This paper addresses the coordinated routing problem involving these two vehicles and presents an algorithm to obtain an optimal solution for this problem, fast heuristics to obtain good feasible solutions, and also a transformation method to transform any instance of this cooperative vehicle routing problem to an instance of the one-in-a-set traveling salesman problem.

33 ADVANCED PROPULSION SYSTEMS↗

DOE OSTI2020

The Heuristic Dynamic Programming Approach in Boost Converters

In this study, a heuristic dynamic programming controller is proposed to control a boost converter. Conventional controllers such as proportional-integral-derivative (PID) or proportional-integral (PI) are designed based on the linearized small-signal model near the operating point. Therefore, the performance of the controller during the start-up, the load change, or the input voltage variation is not optimal since the system model changes by varying the operating point. The heuristic dynamic programming controller optimally controls the boost converter by following the approximate dynamic programming. The advantage of the HDP is that the neural network-based characteristic of the proposed controller enables boost converters to easily cope with large disturbances. An HDP with a well-trained critic and action networks can perform as an optimal controller for the boost converter. To compare the effectiveness of the traditional PI-based and the HDP boost converter, the simulation results are provided.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2017

Analysis of albedo versus cloud fraction relationships in liquid water clouds using heuristic models and large eddy simulation: ALBEDO VERSUS CLOUD FRACTION RELATIONSHIPS

The relationship between the albedo of a cloudy scene $A$ and cloud fraction f c is studied with the aid of heuristic models of stratocumulus and cumulus clouds. Existing work has shown that scene albedo increases monotonically with increasing cloud fraction but that the relationship varies from linear to superlinear. The reasons for these differences in functional dependence are traced to the relationship between cloud deepening and cloud widening. When clouds deepen with no significant increase in f c (e.g., in solid stratocumulus), the relationship between$A$ and f c is linear.When clouds widen as they deepen, as in cumulus cloud fields, the relationship is superlinear. A simple heuristic model of a cumulus cloud field with a power law size distribution shows that the superlinear $A$-f c behavior is traced out either through random variation in cloud size distribution parameters or as the cloud field oscillates between a relative abundance of small clouds (steep slopes on a log-log plot) and a relative abundance of large clouds (flat slopes). Oscillations of this kind manifest in large eddy simulation of trade wind cumulus where the slope and intercept of the power law fit to the cloud size distribution are highly correlated. Further analysis of the large eddy model-generated cloud fields suggests that cumulus clouds grow larger and deeper as their underlying plumes aggregate; this is followed by breakup of large plumes and a tendency to smaller clouds. The cloud and thermal size distributions oscillate back and forth approximately in unison.

54 ENVIRONMENTAL SCIENCES↗

DOE OSTI2019

Physical Interpretation of Strict Solutions of Diffraction Problems by Heuristic Relations

We propose a new approach to construct heuristic relations describing solutions of diffraction problems. Those relations are based on physical principles and allow one to interpret mathematically strict solutions. Since the heuristic relations possess high performance and accuracy, they can also be used along with any strict approach or experimental results for a significant improvement of efficiency of solutions of practical problems related to applications of the diffraction theory.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Exact and heuristic algorithms for minimizing Tardy/Lost penalties on a single-machine scheduling problem

This paper addresses minimizing Tardy/Lost penalties with common due dates on a single machine. According to this penalty criterion, if tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. The problem is formulated as an integer programming model, and a heuristic algorithm is constructed. Then, using the proposed dominance rules and lower bounds, we develop two dynamic programming algorithms as well as a branch and bound. Experimental results show that the heuristic algorithm has an average optimality gap less than 2 % in all problem sizes. Instances up to 250 jobs with low variety of process times are optimally solved and for high process time varieties, the algorithms solved all instances up to 75 jobs.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Intersecting heuristic adaptive strategies, building design and energy saving intentions when facing discomfort environment: A cross-country analysis

Occupants' adaptive strategies play an important role in the energy consumption of office buildings. Previous research has mostly focused on the adaptive strategies triggered by occupants' indoor discomfort; however, it is crucial to understand if specific adaptive strategies are linked to occupants' energy-saving intentions. This study explores the relationships among employees’ heuristic decision-making in their first choice of adaptive strategies (technological solutions or personal adjustments) when facing extreme discomfort conditions, and their energy-saving intentions, then links these patterns with building design, workplace contextual factors, and demographics. A cross-sectional survey was collected among university employees from China, Brazil, Italy, Poland, Switzerland, and the US. Our results demonstrated that the accessibility to indoor environmental controls (IECs) and office type are the significant factors for adaptive strategies. There was a positive relationship between the number of IEC features and the percentage of employees choosing a technological solution. When feeling too hot, occupants in private offices are more likely to adopt a technological solution, whereas occupants in cubicles are more likely to choose a personal adjustment. Occupants with energy-saving intentions are less likely to choose thermostat adjustments or use portable devices as adaptive strategies than their counterparts. Lastly, the cluster analysis suggests females were more likely to use adaptive strategies for energy-saving purposes than males. The majority of occupants would turn on/off lighting to save energy. The study provides the contributions in the connection between the heuristic decision-making process and energy-saving intentions and recommendations on design strategies for building architects, engineers, and managers.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2025

Clifford Circuit-Based Heuristic Optimization of Fermion-To-Qubit Mappings

Simulation of interacting Fermionic Hamiltonians is one of the most promising applications of quantum computers. However, the feasibility of analyzing Fermionic systems with a quantum computer hinges on the efficiency of Fermion-to-qubit mappings that encode nonlocal Fermionic degrees of freedom in local qubit degrees of freedom. While recent studies have highlighted the importance of designing Fermion-to-qubit mappings that are tailored to specific problem Hamiltonians, the methods proposed so far either are restricted to a narrow class of mappings or they use computationally expensive and unscalable brute-force search algorithms. Here, in this work, we address this challenge by designing a heuristic numerical optimization framework for Fermion-to-qubit mappings. To this end, we first translate the Fermion-to-qubit mapping problem to a Clifford circuit optimization problem and then use simulated annealing to optimize the average Pauli weight of the problem Hamiltonian. For all Fermionic Hamiltonians we have considered, the numerically optimized mappings outperform their conventional counterparts, including ternary-tree-based mappings that are known to be optimal for single creation and annihilation operators. We find that our optimized mappings yield between 15% and 40% improvements on the average Pauli weight when the simulation Hamiltonian has an intermediate level of complexity. Most remarkably, the optimized mappings improve the average Pauli weight for 6 × 6 nearest-neighbor hopping and Hubbard models by more than 40% and 20%, respectively. Surprisingly, we also find specific interaction Hamiltonians for which the optimized mapping outperforms any ternary-tree-based mapping. Our results establish heuristic numerical optimization as an effective method for obtaining mappings tailored for specific Fermionic Hamiltonian.

Hamiltonians↗

DOE OSTI2019

A heuristic classification of woody plants based on contrasting shade and drought strategies

Woody plants vary in their adaptations to drought and shade. For a better prediction of vegetation responses to drought and shade within dynamic global vegetation models, it is critical to group species into functional types with similar adaptations. One of the key challenges is that the adaptations are generally determined by a large number of plant traits that may not be available for a large number of species. In this study, we present two heuristic woody plant groups that were separated using cluster analysis in a three-dimensional trait–environment space based on three key metrics for each species: mean xylem embolism resistance, shade tolerance and habitat aridity. The two heuristic groups separate these species into tolerators and avoiders. Furthermore, the tolerators either rely on their high embolism resistance to tolerate drought in arid habitats (e.g., Juniperus and Prunus ) or rely on high shade tolerance to withstand shaded conditions in wet habitats (e.g., Picea , Abies and Acer ). In contrast, all avoiders have low embolism resistance and low shade tolerance. In arid habitats, avoiders tend to minimize catastrophic embolism (e.g., most Pinus species) while in wet habitats, they may survive despite low shade tolerance (e.g., Betula , Populus , Alnus and Salix ). Because our approach links traits to the environmental conditions, we expect it could be a promising framework for predicting changes in species composition, and therefore ecosystem function, under changing environmental conditions.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2015

Visualization for Hyper-Heuristics: Front-End Graphical User Interface

Modern society is faced with ever more complex problems, many of which can be formulated as generate-and-test optimization problems. General-purpose optimization algorithms are not well suited for real-world scenarios where many instances of the same problem class need to be repeatedly and efficiently solved because they are not targeted to a particular scenario. Hyper-heuristics automate the design of algorithms to create a custom algorithm for a particular scenario. While such automated design has great advantages, it can often be difficult to understand exactly how a design was derived and why it should be trusted. This project aims to address these issues of usability by creating an easy-to-use graphical user interface (GUI) for hyper-heuristics to support practitioners, as well as scientific visualization of the produced automated designs. My contributions to this project are exhibited in the user-facing portion of the developed system and the detailed scientific visualizations created from back-end data.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

The research on meta-job scheduling heuristics in heterogeneous environments

As the core of rational utilization of computing resources, the scheduling algorithm has gained the interest of many researchers. Aimed at meta-job scheduling in heterogeneous environments, this paper puts forward three algorithms: the meta-job scheduling algorithm based on deviation (MaxD-min heuristic), the meta-job scheduling algorithm based on relative deviation (MaxRD-min heuristic), and the Cordwood algorithm (CA). The former two Algorithm are improvements of the classic Min-min algorithm. The latter CA algorithm is a new method that tries to place each building block on the tray with minimal amount of Sufferage. In conclusion, the result of experimenting shows that the three algorithms, in comparison to Min-Min and Max-Min algorithm, can effectively reduce the total span of scheduling (makespan).

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1972

Reasoning by analogy as an aid to heuristic theorem proving.

When heuristic problem-solving programs are faced with large data bases that contain numbers of facts far in excess of those needed to solve any particular problem, their performance rapidly deteriorates. In this paper, the correspondence between a new unsolved problem and a previously solved analogous problem is computed and invoked to tailor large data bases to manageable sizes. This paper outlines the design of an algorithm for generating and exploiting analogies between theorems posed to a resolution-logic system. These algorithms are believed to be the first computationally feasible development of reasoning by analogy to be applied to heuristic theorem proving.

Kling, R. E.↗