Search NASA⌕ Search

SEARCH · Search NASA

Results for “Heuristic Evaluation”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
NASA NTRS2011

Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a ppro~imate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.

Kaplan, Sezgin↗
NASA NTRS1990

A model for a space shuttle safing and failure-detection expert

The safing and failure-detection expert (SAFE) is a prototype for a malfunction detection, diagnosis, and safing system for the atmospheric revitalization subsystem (ARS) in the Space Shuttle orbiter. SAFE, whose knowledge was extracted from expert-provided heuristics and documented procedures, automatically manages all phases of failure handling: detection, diagnosis, testing procedures, and recovery instructions. The SAFE architecture allows it to handle correctly sensor failures and multiple malfunctions. Since SAFE is highly interactive, it was used as a test bed for the evaluation of various advanced human-computer interface (HCI) techniques. The use of such expert systems in the next generation of space vehicles would increase their reliability and autonomy to levels not achievable before.

Zeilingold, Daphna↗
NASA NTRS1991

Two criteria for the selection of assembly plans - Maximizing the flexibility of sequencing the assembly tasks and minimizing the assembly time through parallel execution of assembly tasks

The authors introduce two criteria for the evaluation and selection of assembly plans. The first criterion is to maximize the number of different sequences in which the assembly tasks can be executed. The second criterion is to minimize the total assembly time through simultaneous execution of assembly tasks. An algorithm that performs a heuristic search for the best assembly plan over the AND/OR graph representation of assembly plans is discussed. Admissible heuristics for each of the two criteria introduced are presented. Some implementation issues that affect the computational efficiency are addressed.

Homem De Mello, Luiz S.↗
NASA NTRS2003

Benchmark and Framework for Encouraging Research on Multi-Threaded Testing Tools

A problem that has been getting prominence in testing is that of looking for intermittent bugs. Multi-threaded code is becoming very common, mostly on the server side. As there is no silver bullet solution, research focuses on a variety of partial solutions. In this paper (invited by PADTAD 2003) we outline a proposed project to facilitate research. The project goals are as follows. The first goal is to create a benchmark that can be used to evaluate different solutions. The benchmark, apart from containing programs with documented bugs, will include other artifacts, such as traces, that are useful for evaluating some of the technologies. The second goal is to create a set of tools with open API s that can be used to check ideas without building a large system. For example an instrumentor will be available, that could be used to test temporal noise making heuristics. The third goal is to create a focus for the research in this area around which a community of people who try to solve similar problems with different techniques, could congregate.

Havelund, Klaus↗
NASA NTRS1990

Parallel simulated annealing algorithms for cell placement on hypercube multiprocessors

Two parallel algorithms for standard cell placement using simulated annealing are developed to run on distributed-memory message-passing hypercube multiprocessors. The cells can be mapped in a two-dimensional area of a chip onto processors in an n-dimensional hypercube in two ways, such that both small and large cell exchange and displacement moves can be applied. The computation of the cost function in parallel among all the processors in the hypercube is described, along with a distributed data structure that needs to be stored in the hypercube to support the parallel cost evaluation. A novel tree broadcasting strategy is used extensively for updating cell locations in the parallel environment. A dynamic parallel annealing schedule estimates the errors due to interacting parallel moves and adapts the rate of synchronization automatically. Two novel approaches in controlling error in parallel algorithms are described: heuristic cell coloring and adaptive sequence control.

Banerjee, Prithviraj↗
NASA NTRSDate not supplied

Probabilistic Calibration of Expensive Models using Efficiently Trained Surrogates

Calibration of computational models in the presence of uncertainty is often cast as a Bayesian inference problem and solved via sampling methods, e.g., Markov chain Monte Carlo. When the computational model is expensive, this task becomes intractable due to the large number of samples required to accurately estimate the posterior distribution of the calibration parameters. A popular solution to this problem is to use machine learning to develop a faster-to-evaluate, lower-fidelity substitute for the original model to serve as a surrogate while solving the inference problem. Although considered an offline cost, generating training data to construct this surrogate model can still be an expensive task in practice. An active learning algorithm is presented that focuses training on improving surrogate accuracy specifically in and around the bulk of the posterior distribution, as this is where the model is exercised during calibration. Candidate samples are drawn from families of distributions related to an approximation of the posterior. The sample maximizing predictive variance is then selected for evaluation by the original computational model, yielding a label for the training point. Iterating this approach increases efficiency relative to space filling designs (e.g., Latin hypercube sampling) by avoiding low probability points. Practical considerations are discussed, including the benefits of using a sequential Monte Carlo sampling approach, convergence heuristics, and the importance of both exploration and exploitation given that the true posterior is unknown a priori.

uncertainty quantification↗
NASA NTRS1998

PLUM: Parallel Load Balancing for Unstructured Adaptive Meshes

Dynamic mesh adaption on unstructured grids is a powerful tool for computing large-scale problems that require grid modifications to efficiently resolve solution features. Unfortunately, an efficient parallel implementation is difficult to achieve, primarily due to the load imbalance created by the dynamically-changing nonuniform grid. To address this problem, we have developed PLUM, an automatic portable framework for performing adaptive large-scale numerical computations in a message-passing environment. First, we present an efficient parallel implementation of a tetrahedral mesh adaption scheme. Extremely promising parallel performance is achieved for various refinement and coarsening strategies on a realistic-sized domain. Next we describe PLUM, a novel method for dynamically balancing the processor workloads in adaptive grid computations. This research includes interfacing the parallel mesh adaption procedure based on actual flow solutions to a data remapping module, and incorporating an efficient parallel mesh repartitioner. A significant runtime improvement is achieved by observing that data movement for a refinement step should be performed after the edge-marking phase but before the actual subdivision. We also present optimal and heuristic remapping cost metrics that can accurately predict the total overhead for data redistribution. Several experiments are performed to verify the effectiveness of PLUM on sequences of dynamically adapted unstructured grids. Portability is demonstrated by presenting results on the two vastly different architectures of the SP2 and the Origin2OOO. Additionally, we evaluate the performance of five state-of-the-art partitioning algorithms that can be used within PLUM. It is shown that for certain classes of unsteady adaption, globally repartitioning the computational mesh produces higher quality results than diffusive repartitioning schemes. We also demonstrate that a coarse starting mesh produces high quality load balancing, at a fraction of the cost required a fine initial mesh. Results indicate that our parallel load balancing strategy will remain viable on large numbers of processors.

Oliker, Leonid↗
NASA NTRS2024

Automated Detection of Spurious Signals in VLBI Phase Calibration Data

In this memorandum, a set of processing strategies for automatic masking of phase calibration tones is outlined as implemented in the software package PIMA in the task Generate Phase Calibration Mask, or GEPM. The task relies on a robust procedure of cleaning phase calibration data before employing several mathematical strategies designed to selectively identify spurious signals from phase calibration tones. These strategies were derived as more rigorous implementations of heuristics traditionally used by analysts in manually identifying problematic phase calibration data. The task is intended to automate the process of generating a phase calibration mask and in so doing increase the speed and regularity of VLBI analysis. At the outset of the project, a series of goals were identified to evaluate the success of this mask generation. This included the development of an algorithm to identify and mask short-term (defined as less than 10 seconds in length) spurious signals affecting phase calibration data, the development of an algorithm to identify and mask phase calibration tones affected by constant radio-frequency interference, the implementation of a detection scheme for identifying large jumps in phase calibration phase caused by clock breaks, and finally a method of reporting phase calibration health metrics to the user. Processing of over 10 experiments has demonstrated that the final form of the task GEPM as detailed in this technical memorandum satisfies each of these conditions and satisfactorily performs the task of automatic phase calibration data masking, although the wide variety in quality and characteristics of phase calibration data makes a single solution to the problem quite difficult. A series of user inputs have therefore been defined to assist analysts in tailoring automatic masking to specific stations and phase calibration generators. The vast majority of applicable code was written in FORTRAN to increase execution speed and ease of interfacing with the existing code base in PIMA, but a wrapper function in Python was also written to allow for a simpler method of interacting with GEPM and inputting relevant parameters. In addition to this report, thorough documentation was added to the already existing repositories associated with PIMA as a whole.

Geodesy↗
NASA NTRS1989

A Rocket Engine Design Expert System

The overall structure and capabilities of an expert system designed to evaluate rocket engine performance are described. The expert system incorporates a JANNAF standard reference computer code to determine rocket engine performance and a state of the art finite element computer code to calculate the interactions between propellant injection, energy release in the combustion chamber, and regenerative cooling heat transfer. Rule-of-thumb heuristics were incorporated for the H2-O2 coaxial injector design, including a minimum gap size constraint on the total number of injector elements. One dimensional equilibrium chemistry was used in the energy release analysis of the combustion chamber. A 3-D conduction and/or 1-D advection analysis is used to predict heat transfer and coolant channel wall temperature distributions, in addition to coolant temperature and pressure drop. Inputting values to describe the geometry and state properties of the entire system is done directly from the computer keyboard. Graphical display of all output results from the computer code analyses is facilitated by menu selection of up to five dependent variables per plot.

Davidian, Kenneth J.↗
NASA NTRS1995

Experimental evaluation of dynamic data allocation strategies in a distributed database with changing workloads

Traditionally, allocation of data in distributed database management systems has been determined by off-line analysis and optimization. This technique works well for static database access patterns, but is often inadequate for frequently changing workloads. In this paper we address how to dynamically reallocate data for partionable distributed databases with changing access patterns. Rather than complicated and expensive optimization algorithms, a simple heuristic is presented and shown, via an implementation study, to improve system throughput by 30 percent in a local area network based system. Based on artificial wide area network delays, we show that dynamic reallocation can improve system throughput by a factor of two and a half for wide area networks. We also show that individual site load must be taken into consideration when reallocating data, and provide a simple policy that incorporates load in the reallocation decision.

Brunstrom, Anna↗
NASA NTRS1989

A rocket engine design expert system

The overall structure and capabilities of an expert system designed to evaluate rocket engine performance are described. The expert system incorporates a JANNAF standard reference computer code to determine rocket engine performance and a state-of-the-art finite element computer code to calculate the interactions between propellant injection, energy release in the combustion chamber, and regenerative cooling heat transfer. Rule-of-thumb heuristics were incorporated for the hydrogen-oxygen coaxial injector design, including a minimum gap size constraint on the total number of injector elements. One-dimensional equilibrium chemistry was employed in the energy release analysis of the combustion chamber and three-dimensional finite-difference analysis of the regenerative cooling channels was used to calculate the pressure drop along the channels and the coolant temperature as it exits the coolant circuit. Inputting values to describe the geometry and state properties of the entire system is done directly from the computer keyboard. Graphical display of all output results from the computer code analyses is facilitated by menu selection of up to five dependent variables per plot.

Davidian, Kenneth J.↗
NASA NTRS2005

Using Dynamic Simulations and Automated Decision Tools to Design Lunar Habitats

This paper describes the role of transient simulations, heuristic techniques, and closed loop integrated control in designing and sizing habitat life support systems. The integration of these three elements allows for more accurate requirements to be derived in advance of hardware choices. As a test case, we used a typical lunar surface habitat. Large numbers of habitat configurations were rapidly tested and evaluated using automated decision support tools. Through this process, preliminary sizing for habitat life support systems were derived. Our preliminary results show that by using transient simulations and closed loop control , we substantially reduced the system mass required to meet mission goals. This has greater implications for general systems analyses and for life support systems. It is likely that transient models, realtime integrated control, and other analyses capable of capturing the uncertainties of systems can be useful for systems analyses much earlier in the system development life cycle than has previously been considered.

Bell, Scott↗
NASA NTRS1971

An approximate theory of imperfect modeling with application to thermal modeling of spacecraft.

Proposal of a new concept of model testing which makes use of imperfect models and is based on the heuristic argument of representing the error states in a multidimensional Euclidean space when the errors in the modeling parameter are sufficiently small. By a separation of these errors into positive and negative groups, and from a consideration of the error paths in the hyperspaces, it is shown that the global effect of these errors may be evaluated with a good degree of approximation. Conditions under which the procedure would yield satisfactory results are discussed. To test the usefulness of the theory a computer experiment was conducted for the prediction of both transient and steady state thermal behavior of a hypothetical spacecraft using perfect, as well as imperfect, models.

Chao, B. T.↗
NASA NTRS2021

Autonomous Safe Landing Site Detection for a FutureMars Science Helicopter

Future Mars Rotorcrafts require advanced navigation capabilities to enable all terrain access for science investigations with long distance flights that are executed fully autonomously. A critical component is the ability to safely land in hazardous terrain as part of a mission, or triggered by an emergency situation. In this paper, we present an advanced navigation system for continuous on-board terrain reconstruction for the purpose of hazard-free landing site detection for the autonomous navigation of a Mars Science Helicopter - a JPL research concept that investigates the feasibility of flying a multi-kilogram science payload at various Mars science locations, with flight ranges of multiple kilometers per flight. Our approach builds on a visionbased perception system that incorporates an on-board visualinertial state estimator augmented by a laser altimeter (range- VIO), and a structure-from-motion 3D reconstruction approach that uses a single, downward-looking camera to provide dense depth measurements while the vehicle is in motion. Depth measurements are accumulated in a local, robot-centric, multiresolution elevation map that is analyzed by a landing site detector to extract safe landing areas below the rotorcraft, based on a heuristic that includes slope, roughness and the presence of landing hazards. Detected landing sites are prioritized by an on-board autonomy engine that either selects suitable landing sites for immediate landing maneuvers, or can explore a terrain location as part of a mission in order to find a best landing site in a pre-planned area. We demonstrate and evaluate our approach on simulated data and data acquired with a surrogate unmanned aerial system (UAS) executing flights over relevant terrain.

Tzanetos, Teddy↗
NASA NTRS1987

Automatic creation of object hierarchies for ray tracing

Various methods for evaluating generated trees are proposed. The use of the hierarchical extent method of Rubin and Whitted (1980) to find the objects that will be hit by a ray is examined. This method employs tree searching; the construction of a tree of bounding volumes in order to determine the number of objects that will be hit by a ray is discussed. A tree generation algorithm, which uses a heuristic tree search strategy, is described. The effects of shuffling and sorting on the input data are investigated. The cost of inserting an object into the hierarchy during the construction of a tree algorithm is estimated. The steps involved in estimating the number of intersection calculations are presented.

Goldsmith, Jeffrey↗
NASA NTRSDate not supplied

Corridor Design and Analysis for UAM Operations

The Urban Air Mobility (UAM) concept is a part of Advanced Air Mobility (AAM), a joint initiative between the Federal Aviation Administration (FAA), NASA, and industry to develop an air transportation system that uses new electric (i.e., green) air vehicles in geographical areas previously underserved by traditional aviation. Market forecast studies predict that there will be demand for alternate modes of air transportation using electric Vertical Take-off and Landing aircraft. UAM expands transportation networks by introducing short flights to move people and goods around metropolitan areas​. UAM is expected to improve mobility for the public, decongest road traffic, reduce trip time, and decrease strain on existing public transportation networks. Various challenges exist to make the introduction of UAM operations successful in the U.S. National Airspace System (NAS). These include but are not limited to integration with existing airports and airspace, provision of air traffic services (e.g., separation), vehicle design and certification, and community acceptance. The focus of this paper is on integration of UAM operations into the NAS via introduction of new airspace structures. UAM will operate within a regulatory, operational, and technical environment that is incorporated into the NAS​. As per the UAM Concept of Operations (ConOps), the FAA retains regulatory authority and is responsible for establishing operational parameters and maintaining oversight. The FAA’s UAM ConOps describes flights at low altitudes (below 5,000 ft) with minimal disruption to established conventional aircraft traffic and limited voice interactions with the Air Traffic Control (ATC). Early stages of UAM may use existing procedures to safely integrate UAM with conventional flights. This would involve flying under Part 91 Visual Flight Rules (VFR) and using voice for communications. The initial UAM ecosystem will utilize the current infrastructure such as routes, helipads, and ATC services, where practicable. ​A NASA study explored the use of existing helicopter routes in Dallas Fort Worth (DFW) airspace for initial UAM operations with a Letter of Agreement (LOA) that included procedures to request a Class B (controlled airspace) clearance. The research showed that the chosen approach was feasible for near-term, low-demand UAM traffic, but was not scalable. The growth of operations in today’s aviation system has resulted in airspace reorganization and procedures to ensure safety and efficiency as traffic rates increase. One proposed operating innovation that can help with the scalability of UAM is establishing routes and corridors. This may look similar to the Area Navigation (RNAV) procedures used today to streamline operations into busy airports. However, instead of FAA automation systems and ATC managing the flow of traffic, some UAM concepts envision a third-party service provider performing this role as part of the Provider of Services for UAM (PSU) network. The FAA’s UAM ConOps posits that new airspace structures such as UAM corridors include the following design criteria: 1) Minimal impact on existing NAS operations, 2) no or minimal additional ATC services, 3) public interest considerations such as noise, safety, and security, and 4) customer needs. The airspace available in urban environments is limited by the height of buildings, the effect of weather including wind gusts, privacy needs, and a clearance envelope. The new airspace structure would need to be designed around large airports and urban areas where the initial market demand is likely to exist. NASA has started evaluating airspace in the Dallas Fort Worth area to design new airspace structures, keeping the first two design criteria in mind. It is assumed that there will be an on-board pilot-in-command, and the flights will operate under VFR in Visual Meteorological Conditions. Corridors will be required in controlled airspace, whereas UAM operations can fly in uncontrolled Class G and E airspace using current day rules. Keeler et. al identified factors and heuristics for development of routes for UAM operations for integration with airspace close to large airports such as Dallas Fort Worth and Dallas Love Field. This paper describes the heuristics applied to define the corridors, analyzes them with respect to legacy traffic and presents key results.

Urban Air Mobility↗
NASA NTRS2020

Tactical Separation and Safety Alerting System for Terminal Airspace

Provision of tactical alerts to aid air traffic controllers in providing separation assurance in terminal airspace is hindered by the complexity of the airspace, its operations, and flight procedures. A prototype automation system is studied that provides controllers with both separation and safety alerts based on or derived from the separation standard for terminal airspace. The system models flight trajectories heuristically, with use of merged intent information from readily available sources: area navigation departure procedures, flight-plan routes, and arrival nominal interior routes used in terminal automation systems. Flight vertical intent is modeled according to standard procedural restrictions except when superseded by controller-issued altitude clearances. Importantly, flight trajectories are modeled for all aircraft, including those conducting visual approaches. New safety-alert thresholds for aircraft conducting visual approaches are studied. Performance of the system is evaluated through fast-time playback of recorded air traffic data from high-fidelity Human-In-The-Loop simulations and real-world operations in two Terminal Radar Approach Control facilities. The prototype system is found to produce a false-alert rate of 8% for separation alerts. The number and validity of safety alerts are studied by comparing with the current Conflict Alert system, showing that the false alerts of Conflict Alert are at 85% and they are avoided in the prototype system.

Air Traffic Management↗
NASA NTRS2006

Towards a Compositional SPIN

This paper discusses our initial experience with introducing automated assume-guarantee verification based on learning in the SPIN tool. We believe that compositional verification techniques such as assume-guarantee reasoning could complement the state-reduction techniques that SPIN already supports, thus increasing the size of systems that SPIN can handle. We present a "light-weight" approach to evaluating the benefits of learning-based assume-guarantee reasoning in the context of SPIN: we turn our previous implementation of learning for the LTSA tool into a main program that externally invokes SPIN to provide the model checking-related answers. Despite its performance overheads (which mandate a future implementation within SPIN itself), this approach provides accurate information about the savings in memory. We have experimented with several versions of learning-based assume guarantee reasoning, including a novel heuristic introduced here for generating component assumptions when their environment is unavailable. We illustrate the benefits of learning-based assume-guarantee reasoning in SPIN through the example of a resource arbiter for a spacecraft. Keywords: assume-guarantee reasoning, model checking, learning.

Pasareanu, Corina S.↗