Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 487 records · Page 27

Spline-Based Smoothing of Airfoil Curvatures

Constrained fitting for airfoil curvature smoothing (CFACS) is a splinebased method of interpolating airfoil surface coordinates (and, concomitantly, airfoil thicknesses) between specified discrete design points so as to obtain smoothing of surface-curvature profiles in addition to basic smoothing of surfaces. CFACS was developed in recognition of the fact that the performance of a transonic airfoil is directly related to both the curvature profile and the smoothness of the airfoil surface. Older methods of interpolation of airfoil surfaces involve various compromises between smoothing of surfaces and exact fitting of surfaces to specified discrete design points. While some of the older methods take curvature profiles into account, they nevertheless sometimes yield unfavorable results, including curvature oscillations near end points and substantial deviations from desired leading-edge shapes. In CFACS as in most of the older methods, one seeks a compromise between smoothing and exact fitting. Unlike in the older methods, the airfoil surface is modified as little as possible from its original specified form and, instead, is smoothed in such a way that the curvature profile becomes a smooth fit of the curvature profile of the original airfoil specification. CFACS involves a combination of rigorous mathematical modeling and knowledge-based heuristics. Rigorous mathematical formulation provides assurance of removal of undesirable curvature oscillations with minimum modification of the airfoil geometry. Knowledge-based heuristics bridge the gap between theory and designers best practices. In CFACS, one of the measures of the deviation of an airfoil surface from smoothness is the sum of squares of the jumps in the third derivatives of a cubicspline interpolation of the airfoil data. This measure is incorporated into a formulation for minimizing an overall deviation- from-smoothness measure of the airfoil data within a specified fitting error tolerance. CFACS has been extensively tested on a number of supercritical airfoil data sets generated by inverse design and optimization computer programs. All of the smoothing results show that CFACS is able to generate unbiased smooth fits of curvature profiles, trading small modifications of geometry for increasing curvature smoothness by eliminating curvature oscillations and bumps (see figure).

Li, W.↗

Improving the Estimates of International Space Station (ISS) Induced K-Factor Failure Rates for On-Orbit Replacement Unit (ORU) Supportability Analyses

This is a case study on revised estimates of induced failure for International Space Station (ISS) on-orbit replacement units (ORUs). We devise a heuristic to leverage operational experience data by aggregating ORU, associated function (vehicle sub -system), and vehicle effective' k-factors using actual failure experience. With this input, we determine a significant failure threshold and minimize the difference between the actual and predicted failure rates. We conclude with a discussion on both qualitative and quantitative improvements the heuristic methods and potential benefits to ISS supportability engineering analysis.

Anderson, Leif F.↗

Massively Parallel Dantzig-Wolfe Decomposition Applied to Traffic Flow Scheduling

Optimal scheduling of air traffic over the entire National Airspace System is a computationally difficult task. To speed computation, Dantzig-Wolfe decomposition is applied to a known linear integer programming approach for assigning delays to flights. The optimization model is proven to have the block-angular structure necessary for Dantzig-Wolfe decomposition. The subproblems for this decomposition are solved in parallel via independent computation threads. Experimental evidence suggests that as the number of subproblems/threads increases (and their respective sizes decrease), the solution quality, convergence, and runtime improve. A demonstration of this is provided by using one flight per subproblem, which is the finest possible decomposition. This results in thousands of subproblems and associated computation threads. This massively parallel approach is compared to one with few threads and to standard (non-decomposed) approaches in terms of solution quality and runtime. Since this method generally provides a non-integral (relaxed) solution to the original optimization problem, two heuristics are developed to generate an integral solution. Dantzig-Wolfe followed by these heuristics can provide a near-optimal (sometimes optimal) solution to the original problem hundreds of times faster than standard (non-decomposed) approaches. In addition, when massive decomposition is employed, the solution is shown to be more likely integral, which obviates the need for an integerization step. These results indicate that nationwide, real-time, high fidelity, optimal traffic flow scheduling is achievable for (at least) 3 hour planning horizons.

Rios, Joseph Lucio↗

Configuring Airspace Sectors with Approximate Dynamic Programming

In response to changing traffic and staffing conditions, supervisors dynamically configure airspace sectors by assigning them to control positions. A finite horizon airspace sector configuration problem models this supervisor decision. The problem is to select an airspace configuration at each time step while considering a workload cost, a reconfiguration cost, and a constraint on the number of control positions at each time step. Three algorithms for this problem are proposed and evaluated: a myopic heuristic, an exact dynamic programming algorithm, and a rollouts approximate dynamic programming algorithm. On problem instances from current operations with only dozens of possible configurations, an exact dynamic programming solution gives the optimal cost value. The rollouts algorithm achieves costs within 2% of optimal for these instances, on average. For larger problem instances that are representative of future operations and have thousands of possible configurations, excessive computation time prohibits the use of exact dynamic programming. On such problem instances, the rollouts algorithm reduces the cost achieved by the heuristic by more than 15% on average with an acceptable computation time.

Bloem, Michael↗

Integrated Traffic Flow Management Decision Making

A generalized approach is proposed to support integrated traffic flow management decision making studies at both the U.S. national and regional levels. It can consider tradeoffs between alternative optimization and heuristic based models, strategic versus tactical flight controls, and system versus fleet preferences. Preliminary testing was accomplished by implementing thirteen unique traffic flow management models, which included all of the key components of the system and conducting 85, six-hour fast-time simulation experiments. These experiments considered variations in the strategic planning look-ahead times, the replanning intervals, and the types of traffic flow management control strategies. Initial testing indicates that longer strategic planning look-ahead times and re-planning intervals result in steadily decreasing levels of sector congestion for a fixed delay level. This applies when accurate estimates of the air traffic demand, airport capacities and airspace capacities are available. In general, the distribution of the delays amongst the users was found to be most equitable when scheduling flights using a heuristic scheduling algorithm, such as ration-by-distance. On the other hand, equity was the worst when using scheduling algorithms that took into account the number of seats aboard each flight. Though the scheduling algorithms were effective at alleviating sector congestion, the tactical rerouting algorithm was the primary control for avoiding en route weather hazards. Finally, the modeled levels of sector congestion, the number of weather incursions, and the total system delays, were found to be in fair agreement with the values that were operationally observed on both good and bad weather days.

Grabbe, Shon R.↗

Centralized Planning for Multiple Exploratory Robots

A computer program automatically generates plans for a group of robotic vehicles (rovers) engaged in geological exploration of terrain. The program rapidly generates multiple command sequences that can be executed simultaneously by the rovers. Starting from a set of high-level goals, the program creates a sequence of commands for each rover while respecting hardware constraints and limitations on resources of each rover and of hardware (e.g., a radio communication terminal) shared by all the rovers. First, a separate model of each rover is loaded into a centralized planning subprogram. The centralized planning software uses the models of the rovers plus an iterative repair algorithm to resolve conflicts posed by demands for resources and by constraints associated with the all the rovers and the shared hardware. During repair, heuristics are used to make planning decisions that will result in solutions that will be better and will be found faster than would otherwise be possible. In particular, techniques from prior solutions of the multiple-traveling- salesmen problem are used as heuristics to generate plans in which the paths taken by the rovers to assigned scientific targets are shorter than they would otherwise be.

Estlin, Tara↗

Navigating a Mobile Robot Across Terrain Using Fuzzy Logic

A strategy for autonomous navigation of a robotic vehicle across hazardous terrain involves the use of a measure of traversability of terrain within a fuzzy-logic conceptual framework. This navigation strategy requires no a priori information about the environment. Fuzzy logic was selected as a basic element of this strategy because it provides a formal methodology for representing and implementing a human driver s heuristic knowledge and operational experience. Within a fuzzy-logic framework, the attributes of human reasoning and decision- making can be formulated by simple IF (antecedent), THEN (consequent) rules coupled with easily understandable and natural linguistic representations. The linguistic values in the rule antecedents convey the imprecision associated with measurements taken by sensors onboard a mobile robot, while the linguistic values in the rule consequents represent the vagueness inherent in the reasoning processes to generate the control actions. The operational strategies of the human expert driver can be transferred, via fuzzy logic, to a robot-navigation strategy in the form of a set of simple conditional statements composed of linguistic variables. These linguistic variables are defined by fuzzy sets in accordance with user-defined membership functions. The main advantages of a fuzzy navigation strategy lie in the ability to extract heuristic rules from human experience and to obviate the need for an analytical model of the robot navigation process.

Seraji, Homayoun↗

Scope of Various Random Number Generators in Ant System Approach for TSP

Experimented on heuristic, based on an ant system approach for traveling Salesman problem, are several quasi and pseudo-random number generators. This experiment is to explore if any particular generator is most desirable. Such an experiment on large samples has the potential to rank the performance of the generators for the foregoing heuristic. This is just to seek an answer to the controversial performance ranking of the generators in probabilistic/statically sense.

Sen, S. K.↗

Scope of Various Random Number Generators in ant System Approach for TSP

Experimented on heuristic, based on an ant system approach for traveling salesman problem, are several quasi- and pseudo-random number generators. This experiment is to explore if any particular generator is most desirable. Such an experiment on large samples has the potential to rank the performance of the generators for the foregoing heuristic. This is mainly to seek an answer to the controversial issue "which generator is the best in terms of quality of the result (accuracy) as well as cost of producing the result (time/computational complexity) in a probabilistic/statistical sense."

Sen, S. K.↗

Using Generic Data to Establish Dormancy Failure Rates

Many hardware items are dormant prior to being operated. The dormant period might be especially long, for example during missions to the moon or Mars. In missions with long dormant periods the risk incurred during dormancy can exceed the active risk contribution. Probabilistic Risk Assessments (PRAs) need to account for the dormant risk contribution as well as the active contribution. A typical method for calculating a dormant failure rate is to multiply the active failure rate by a constant, the dormancy factor. For example, some practitioners use a heuristic and divide the active failure rate by 30 to obtain an estimate of the dormant failure rate. To obtain a more empirical estimate of the dormancy factor, this paper uses the recently updated database NPRD-2011 [1] to arrive at a set of distributions for the dormancy factor. The resulting dormancy factor distributions are significantly different depending on whether the item is electrical, mechanical, or electro-mechanical. Additionally, this paper will show that using a heuristic constant fails to capture the uncertainty of the possible dormancy factors.

Reistle, Bruce↗

Optimal Integration of Departures and Arrivals in Terminal Airspace

Coordination of operations with spatially and temporally shared resources, such as route segments, fixes, and runways, improves the efficiency of terminal airspace management. Problems in this category are, in general, computationally difficult compared to conventional scheduling problems. This paper presents a fast time algorithm formulation using a non-dominated sorting genetic algorithm (NSGA). It was first applied to a test problem introduced in existing literature. An experiment with a test problem showed that new methods can solve the 20 aircraft problem in fast time with a 65% or 440 second delay reduction using shared departure fixes. In order to test its application in a more realistic and complicated problem, the NSGA algorithm was applied to a problem in LAX terminal airspace, where interactions between 28% of LAX arrivals and 10% of LAX departures are resolved by spatial separation in current operations, which may introduce unnecessary delays. In this work, three types of separations - spatial, temporal, and hybrid separations - were formulated using the new algorithm. The hybrid separation combines both temporal and spatial separations. Results showed that although temporal separation achieved less delay than spatial separation with a small uncertainty buffer, spatial separation outperformed temporal separation when the uncertainty buffer was increased. Hybrid separation introduced much less delay than both spatial and temporal approaches. For a total of 15 interacting departures and arrivals, when compared to spatial separation, the delay reduction of hybrid separation varied between 11% or 3.1 minutes and 64% or 10.7 minutes corresponding to an uncertainty buffer from 0 to 60 seconds. Furthermore, as a comparison with the NSGA algorithm, a First-Come-First-Serve based heuristic method was implemented for the hybrid separation. Experiments showed that the results from the NSGA algorithm have 9% to 42% less delay than the heuristic method with varied uncertainty buffer sizes.

terminal airspace↗

Comparison of Spares Logistics Analysis Techniques for Long Duration Human Spaceflight

As the durations and distances involved in human exploration missions increase, the logistics associated with the repair and maintenance becomes more challenging. Whereas the operation of the International Space Station (ISS) depends upon regular resupply from the Earth, this paradigm may not be feasible for future missions. Longer mission durations result in higher probabilities of component failures as well as higher uncertainty regarding which components may fail, and longer distances from Earth increase the cost of resupply as well as the speed at which the crew can abort to Earth in the event of an emergency. As such, mission development efforts must take into account the logistics requirements associated with maintenance and spares. Accurate prediction of the spare parts demand for a given mission plan and how that demand changes as a result of changes to the system architecture enables full consideration of the lifecycle cost associated with different options. In this paper, we utilize a range of analysis techniques - Monte Carlo, semi-Markov, binomial, and heuristic - to examine the relationship between the mass of spares and probability of loss of function related to the Carbon Dioxide Removal System (CRS) for a notional, simplified mission profile. The Exploration Maintainability Analysis Tool (EMAT), developed at NASA Langley Research Center, is utilized for the Monte Carlo analysis. We discuss the implications of these results and the features and drawbacks of each method. In particular, we identify the limitations of heuristic methods for logistics analysis, and the additional insights provided by more in-depth techniques. We discuss the potential impact of system complexity on each technique, as well as their respective abilities to examine dynamic events. This work is the first step in an effort that will quantitatively examine how well these techniques handle increasingly more complex systems by gradually expanding the system boundary.

Owens, Andrew↗

Source Data Impacts on Epistemic Uncertainty for Launch Vehicle Fault Tree Models

Launch vehicle systems are designed and developed using both heritage and new hardware. Design modifications to the heritage hardware to fit new functional system requirements can impact the applicability of heritage reliability data. Risk estimates for newly designed systems must be developed from generic data sources such as commercially available reliability databases using reliability prediction methodologies, such as those addressed in MIL-HDBK-217F. Failure estimates must be converted from the generic environment to the specific operating environment of the system in which it is used. In addition, some qualification of applicability for the data source to the current system should be made. Characterizing data applicability under these circumstances is crucial to developing model estimations that support confident decisions on design changes and trade studies. This paper will demonstrate a data-source applicability classification method for suggesting epistemic component uncertainty to a target vehicle based on the source and operating environment of the originating data. The source applicability is determined using heuristic guidelines while translation of operating environments is accomplished by applying statistical methods to MIL-HDK-217F tables. The paper will provide one example for assigning environmental factors uncertainty when translating between operating environments for the microelectronic part-type components. The heuristic guidelines will be followed by uncertainty-importance routines to assess the need for more applicable data to reduce model uncertainty.

Al Hassan, Mohammad↗

Reduction of Subjective and Objective System Complexity

Occam's razor is often used in science to define the minimum criteria to establish a physical or philosophical idea or relationship. Albert Einstein is attributed the saying "everything should be made as simple as possible, but not simpler". These heuristic ideas are based on a belief that there is a minimum state or set of states for a given system or phenomena. In looking at system complexity, these heuristics point us to an idea that complexity can be reduced to a minimum. How then, do we approach a reduction in complexity? Complexity has been described as a subjective concept and an objective measure of a system. Subjective complexity is based on human cognitive comprehension of the functions and inter relationships of a system. Subjective complexity is defined by the ability to fully comprehend the system. Simplifying complexity, in a subjective sense, is thus gaining a deeper understanding of the system. As Apple's Jonathon Ive has stated," It's not just minimalism or the absence of clutter. It involves digging through the depth of complexity. To be truly simple, you have to go really deep". Simplicity is not the absence of complexity but a deeper understanding of complexity. Subjective complexity, based on this human comprehension, cannot then be discerned from the sociological concept of ignorance. The inability to comprehend a system can be either a lack of knowledge, an inability to understand the intricacies of a system, or both. Reduction in this sense is based purely on a cognitive ability to understand the system and no system then may be truly complex. From this view, education and experience seem to be the keys to reduction or eliminating complexity. Objective complexity, is the measure of the systems functions and interrelationships which exist independent of human comprehension. Jonathon Ive's statement does not say that complexity is removed, only that the complexity is understood. From this standpoint, reduction of complexity can be approached in finding the optimal or 'best balance' of the system functions and interrelationships. This is achievable following von Bertalanffy's approach of describing systems as a set of equations representing both the system functions and the system interrelationships. Reduction is found based on an objective function defining the system output given variations in the system inputs and the system operating environment. By minimizing the objective function with respect to these inputs and environments, a reduced system can be found. Thus, a reduction of the system complexity is feasible.

Watson, Michael D.↗

A Tactical Scheduler for Surface Metering Under Minimum Departure Interval Restrictions

Minimum Departure Interval (MDI) and Miles-In-Trail (MIT) are common traffic management tools. They both require minimum separation between departures to meet specific traffic conditions. The MDI restriction is a time separation requirement between departures, usually on the same Standard Instrument Departure (SID), whereas the MIT restriction is a distance separation requirement between aircraft, including but not limited to departure flights, to meet specific criteria associated with flight path or destination. At Incheon International Airport (IATA code: ICN) in South Korea, MDIs are imposed on 92% of departure flights. They involve specific criteria including not only having identical SID, but also satisfying other conditions, imposed on the flight path and destination. To address complicated MDI constraints, Korea Aerospace Research Institute (KARI) has been developing and improving a tactical scheduler for surface metering at ICN to provide appropriate target times for pushbacks and takeoffs for departure flights under MDIs. This paper describes the MDI requirements at ICN, the development of a heuristic scheduling algorithm to work with the MDI restrictions, and the performance evaluation of the algorithm through fast-time simulations. The performance evaluation results indicate that the proposed heuristic algorithm can provide the surface metering schedules that comply with the MDI restrictions without significant performance degradation.

DMAN (Departure Management)↗

Optimal Experimental Design With Fast Neural Network Surrogate Models

Designing optimal experiments minimizes the uncertainty of results and maximizes the efficient use of resources. Herein, machine learning surrogate models and the approximate coordinate exchange (ACE) algorithm are used to determine optimum experimental designs over large or arbitrarily restrictive design spaces. Optimal experimental design is particularly salient in materials science where experiments are expensive and material properties must often be inferred indirectly. The proposed framework is demonstrated by finding optimal experiments with which the hidden constituent properties of composite materials can be most efficiently inferred from observable experimental outcomes. The optimum experimental design is given by an information-theoretic criteria, which maximizes the conditional mutual information between the hidden properties and the expected experimental outcomes. To perform tractable optimization a neural network is trained as a surrogate model to mimic a physics based simulation, which can calculate the expected experimental outcome based on a candidate experimental design and sampled constituent properties. The ACE algorithm is used to optimize over large design spaces with many tests and controlled parameters where an exhaustive search would be intractable even with the surrogate model. Using this approach, optimal experimental designs that are consistent with those produced by heuristic knowledge and established best practices are found; then optimal designs in larger design spaces where heuristic knowledge is unavailable are examined.

machine learning↗

Dynamic Spectrum Allocation in Urban Air Transportation System via Deep Reinforcement Learning

The emerging concepts of Urban Air Mobility (UAM) and Advanced Air Mobility (AAM) open a new paradigm for urban air transportation. A big challenge is that these new aerial vehicles will quickly saturate the already crowded aviation spectrum, which is an essential resource to ensure reliable communications for safe operations. In this paper, we consider an air transportation system where multiple aerial vehicles are operated to transport passengers or cargo from different sources to destinations along their pre-defined paths. During the flight, the minimum communication Quality of Service (QoS) requirement must be achieved to ensure flight safety. Our objective is to minimize the average mission completion time by jointly optimizing the velocity selection and spectrum allocation for all aerial vehicles. We formulate the optimization problem as a multi-stage Markov Decision Process (MDP) where the optimization variables are coupled together. A multi-agent Deep Reinforcement Learning (DRL) based solution is proposed where Value Decomposition Networks (VDN) algorithm is utilized to take discrete actions. Additionally, we propose a heuristic greedy algorithm as a baseline solution. Simulation results show that our learning based solution outperforms the heuristic greedy algorithm and another Orthogonal Multiple Access (OMA) solution in minimizing the mission completion time.

Ruixuan Han↗

Dynamic Spectrum Allocation in Urban Air Transportation System via Deep Reinforcement Learning

The emerging concepts of Urban Air Mobility (UAM) and Advanced Air Mobility (AAM) open a new paradigm for urban air transportation. A big challenge is that these new aerial vehicles will quickly saturate the already crowded aviation spectrum, which is an essential resource to ensure reliable communications for safe operations. In this paper, we consider an air transportation system where multiple aerial vehicles are operated to transport passengers or cargo from different sources to destinations along their pre-defined paths. During the flight, the minimum communication Quality of Service (QoS) requirement must be achieved to ensure flight safety. Our objective is to minimize the average mission completion time by jointly optimizing the velocity selection and spectrum allocation for all aerial vehicles. We formulate the optimization problem as a multi-stage Markov Decision Process (MDP) where the optimization variables are coupled together. A multi-agent Deep Reinforcement Learning (DRL) based solution is proposed where Value Decomposition Networks (VDN) algorithm is utilized to take discrete actions. Additionally, we propose a heuristic greedy algorithm as a baseline solution. Simulation results show that our learning based solution outperforms the heuristic greedy algorithm and another Orthogonal Multiple Access (OMA) solution in minimizing the mission completion time.

Ruixuan Han↗