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 469 records · Page 26

A linguistic geometry for 3D strategic planning

This paper is a new step in the development and application of the Linguistic Geometry. This formal theory is intended to discover the inner properties of human expert heuristics, which have been successful in a certain class of complex control systems, and apply them to different systems. In this paper we investigate heuristics extracted in the form of hierarchical networks of planning paths of autonomous agents. Employing Linguistic Geometry tools the dynamic hierarchy of networks is represented as a hierarchy of formal attribute languages. The main ideas of this methodology are shown in this paper on the new pilot example of the solution of the extremely complex 3D optimization problem of strategic planning for the space combat of autonomous vehicles. This example demonstrates deep and highly selective search in comparison with conventional search algorithms.

Stilman, Boris↗

Spectral energy distributions of the brightest Palomar-Green quasars at intermediate redshifts

We have combined low-dispersion International Ultraviolet Explorer (IUE) spectra with the optical/near-IR spectrophotometry of Neugebauer et al. (1987) in order to study the spectral energy distributions of seven of the brightest Palomar-Green (PG) quasars at intermediate redshifts (Z(sub em) greater than or equal to 0.9 and less than or equal to 1.5). Some of these PG quasars are barely detectable in long IUE exposures, so we have used the Gaussian Extraction (GEX) technique to maximize the signal-to-noise of the IUE data, and we have co-added all spectra available from the IUE archive for each QSO unless the ultraviolet spectra varied significantly from one exposure to the next. We have corrected the spectral energy distributions for Milky Way reddening using the observed neutral hydrogen column densities on each sight line and the gas-to-dust relation recently derived by Diplas & Savage. Six of the seven quasars are detected down to lambda much less than 700 A in the rest frame, and consequently continuum reddening due to dust in the immediate vicinity of the quasar can have a dramatic effect on the spectral energy distributions. In order to explore the possible importance of intrinsic continuum reddening, we have assembled a heuristic extinction curve which extends to lambda much less than 912 A. Using this heuristic extinction curve, we derive reasonable upper limits on the intrinsic E(B-V) for each quasar. We briefly discuss some of the implications of the derived intrinsic continuum reddening limits. We use geometrically thin accretion disk models to derive the black hole masses and accretion rates implied by the spectral energy distributions. Even if we neglect intrinsic reddening, we find that a large fraction of the quasars require super-Eddington accretion rates (which is not consistent with the thin disk assumption). Comparison of the data in this paper to a large body of data from the literature on the accretion disk M(sub BH) - M dot grid calculated by Wandel & Petrosian reveals that our quasars are among the brightest in the sky at 1450 A, and ostensibly suggests that the fraction of quasars which require super-Eddington accretion rates is much smaller than the fraction that we derive from our data alone. However, intrinsic continuum reddening has been ignored in this comparison, and a small amount of intrinsic reddening will push more of the quasars into the super-Eddington regime. We also plot the recent reverberation monitoring results on NGC 5548 and NGC 3783 on the Wandel & Petrosian grid, and we find that these Seyfert galaxies appear to vary along lines of constant M(sub BH). Continuum flux from two of the quasars in our main sample, PG 1338+416 and PG 1630+377, is detected at lambda(sub rest) less than 584 A. These quasars can in principle be used for the He I Gunn-Peterson test, but the S/N of IUE spectra of individual objects is usually too low to place interesting limits on the Gunn-Peterson optical depth. In order to improve the S/N, we have formed a composite spectrum from the spectra of five quasars detected with IUE at lambda(sub rest) less than 584 A, and we have used this composite spectrum to place a tighter limit on tau(sub GP, He I). We briefly discuss intermediate-redshift Lyman limit systems (Z(sub LL) greater than or equal to 0.5 and less than or equal to 1.6) detected in the IUE spectra of five quasars, including lower limits on N(H I) in each Lyman limit system.

Tripp, Todd M.↗

Automating symbolic analysis with CLIPS

Symbolic Analysis is a methodology first applied as an aid in selecting and generating test cases for 'white box' type testing of computer software programs. The feasibility of automating this analysis process has recently been demonstrated through the development of a CLIPS-based prototype tool. Symbolic analysis is based on separating the logic flow diagram of a computer program into its basic elements, and then systematically examining those elements and their relationships to provide a detailed static analysis of the process that those diagrams represent. The basic logic flow diagram elements are flow structure (connections), predicates (decisions), and computations (actions). The symbolic analysis approach supplies a disciplined step-by-step process to identify all executable program paths and produce a truth table that defines the input and output domains for each path identified. The resulting truth table is the tool that allows software test cases to be generated in a comprehensive manner to achieve total program path, input domain, and output domain coverage. Since the manual application of symbolic analysis is extremely labor intensive and is itself error prone, automation of the process is highly desirable. Earlier attempts at automation, utilizing conventional software approaches, had only limited success. This paper briefly describes the automation problems, the symbolic analysis expert's problem solving heuristics, and the implementation of those heuristics as a CLIPS based prototype, and the manual augmentation required. A simple application example is also provided for illustration purposes. The paper concludes with a discussion of implementation experiences, automation limitations, usage experiences, and future development suggestions.

Morris, Keith E.↗

An Integrated Planning Representation Using Macros, Abstractions, and Cases

Planning will be an essential part of future autonomous robots and integrated intelligent systems. This paper focuses on learning problem solving knowledge in planning systems. The system is based on a common representation for macros, abstractions, and cases. Therefore, it is able to exploit both classical and case based techniques. The general operators in a successful plan derivation would be assessed for their potential usefulness, and some stored. The feasibility of this approach was studied through the implementation of a learning system for abstraction. New macros are motivated by trying to improve the operatorset. One heuristic used to improve the operator set is generating operators with more general preconditions than existing ones. This heuristic leads naturally to abstraction hierarchies. This investigation showed promising results on the towers of Hanoi problem. The paper concludes by describing methods for learning other problem solving knowledge. This knowledge can be represented by allowing operators at different levels of abstraction in a refinement.

Baltes, Jacky↗

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↗

Global Load Balancing with Parallel Mesh Adaption on Distributed-Memory Systems

Dynamic mesh adaption on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load imbalance among processors on a parallel machine. This paper describes the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A heuristic remapping algorithm is presented that assigns partitions to processors such that the redistribution cost is minimized. Results indicate that the parallel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors of an SP2 when 35% of the mesh is randomly adapted. For large-scale scientific computations, our load balancing strategy gives almost a sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remapper yields processor assignments that are less than 3% off the optimal solutions but requires only 1% of the computational time.

Biswas, Rupak↗

The Aggregate Representation of Terrestrial Land Covers Within Global Climate Models (GCM)

This project had four initial objectives: (1) to create a realistic coupled surface-atmosphere model to investigate the aggregate description of heterogeneous surfaces; (2) to develop a simple heuristic model of surface-atmosphere interactions; (3) using the above models, to test aggregation rules for a variety of realistic cover and meteorological conditions; and (4) to reconcile biosphere-atmosphere transfer scheme (BATS) land covers with those that can be recognized from space; Our progress in meeting these objectives can be summarized as follows. Objective 1: The first objective was achieved in the first year of the project by coupling the Biosphere-Atmosphere Transfer Scheme (BATS) with a proven two-dimensional model of the atmospheric boundary layer. The resulting model, BATS-ABL, is described in detail in a Masters thesis and reported in a paper in the Journal of Hydrology Objective 2: The potential value of the heuristic model was re-evaluated early in the project and a decision was made to focus subsequent research around modeling studies with the BATS-ABL model. The value of using such coupled surface-atmosphere models in this research area was further confirmed by the success of the Tucson Aggregation Workshop. Objective 3: There was excellent progress in using the BATS-ABL model to test aggregation rules for a variety of realistic covers. The foci of attention have been the site of the First International Satellite Land Surface Climatology Project Field Experiment (FIFE) in Kansas and one of the study sites of the Anglo-Brazilian Amazonian Climate Observational Study (ABRACOS) near the city of Manaus, Amazonas, Brazil. These two sites were selected because of the ready availability of relevant field data to validate and initiate the BATS-ABL model. The results of these tests are given in a Masters thesis, and reported in two papers. Objective 4: Progress far exceeded original expectations not only in reconciling BATS land covers with those that can be recognized from space, but also in then applying remotely-sensed land cover data to map aggregate values of BATS parameters for heterogeneous covers and interpreting these parameters in terms of surface-atmosphere exchanges.

Shuttleworth, W. James↗

Global Load Balancing with Parallel Mesh Adaption on Distributed-Memory Systems

Dynamic mesh adaptation on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load inbalances among processors on a parallel machine. This paper described the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A heuristic remapping algorithm is presented that assigns partitions to processors such that the redistribution coast is minimized. Results indicate that the parallel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors of an SP2 when 35 percent of the mesh is randomly adapted. For large scale scientific computations, our load balancing strategy gives an almost sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remappier yields processor assignments that are less than 3 percent of the optimal solutions, but requires only 1 percent of the computational time.

Biswas, Rupak↗

Noise and Dynamical Pattern Selection in Solidification

The overall goal of this project was to understand in more detail how a pattern-forming system can adjust its spacing. "Pattern-forming systems," in this context, are nonequilibrium contina whose state is determined by experimentally adjustable control parameter. Below some critical value of the control system then has available to it a range of linearly stable, spatially periodic steady states, each characterized by a spacing which can lie anywhere within some band of values. These systems like directional solidification, where the solidification front is planar when the ratio of growth velocity to thermal gradient is below its critical value, but takes on a cellular shape above critical. They also include systems without interfaces, such as Benard convection, where it is the fluid velocity field which changes from zero to something spatially periodic as the control parameter is increased through its critical value. The basic question to be addressed was that of how the system chooses one of its myriad possible spacings when the control parameter is above critical, and in particular the role of noise in the selection process. Previous work on explosive crystallization had suggested that one spacing in the range should be preferred, in the sense that weak noise should eventually drive the system to that spacing. That work had also suggested a heuristic argument for identifying the preferred spacing. The project had three main objectives: to understand in more detail how a pattern-forming system can adjust its spacing; to investigate how noise drives a system to its preferred spacing; and to extend the heuristic argument for a preferred spacing in explosive crystallization to other pattern-forming systems.

Kurtze, Douglas A.↗

Institutional Memory Preservation at NASA Glenn Research Center

In this era of downsizing and deficit reduction, the preservation of institutional memory is a widespread concern for U.S. companies and governmental agencies. The National Aeronautical and Space Administration faces the pending retirement of many of the agency's long-term, senior engineers. NASA has a marvelous long-term history of success, but the agency faces a recurring problem caused by the loss of these engineers' unique knowledge and perspectives on NASA's role in aeronautics and space exploration. The current work describes a knowledge elicitation effort aimed at demonstrating the feasibility of preserving the more personal, heuristic knowledge accumulated over the years by NASA engineers, as contrasted with the "textbook" knowledge of launch vehicles. Work on this project was performed at NASA Glenn Research Center and elsewhere, and focused on launch vehicle systems integration. The initial effort was directed toward an historic view of the Centaur upper stage which is powered by two RL-10 engines. Various experts were consulted, employing a variety of knowledge elicitation techniques, regarding the Centaur and RL-10. Their knowledge is represented in searchable Web-based multimedia presentations. This paper discusses the various approaches to knowledge elicitation and knowledge representation employed, and assesses successes and challenges in trying to perform large-scale knowledge preservation of institutional memory. It is anticipated that strategies for knowledge elicitation and representation that have been developed in this grant will be utilized to elicit knowledge in a variety of domains including the complex heuristics that underly use of simulation software packages such as that being explored in the Expert System Architecture for Rocket Engine Numerical Simulators.

Coffey, J.↗

Decision Making In A High-Tech World: Automation Bias and Countermeasures

Automated decision aids and decision support systems have become essential tools in many high-tech environments. In aviation, for example, flight management systems computers not only fly the aircraft, but also calculate fuel efficient paths, detect and diagnose system malfunctions and abnormalities, and recommend or carry out decisions. Air Traffic Controllers will soon be utilizing decision support tools to help them predict and detect potential conflicts and to generate clearances. Other fields as disparate as nuclear power plants and medical diagnostics are similarly becoming more and more automated. Ideally, the combination of human decision maker and automated decision aid should result in a high-performing team, maximizing the advantages of additional cognitive and observational power in the decision-making process. In reality, however, the presence of these aids often short-circuits the way that even very experienced decision makers have traditionally handled tasks and made decisions, and introduces opportunities for new decision heuristics and biases. Results of recent research investigating the use of automated aids have indicated the presence of automation bias, that is, errors made when decision makers rely on automated cues as a heuristic replacement for vigilant information seeking and processing. Automation commission errors, i.e., errors made when decision makers inappropriately follow an automated directive, or automation omission errors, i.e., errors made when humans fail to take action or notice a problem because an automated aid fails to inform them, can result from this tendency. Evidence of the tendency to make automation-related omission and commission errors has been found in pilot self reports, in studies using pilots in flight simulations, and in non-flight decision making contexts with student samples. Considerable research has found that increasing social accountability can successfully ameliorate a broad array of cognitive biases and resultant errors. To what extent these effects generalize to performance situations is not yet empirically established. The two studies to be presented represent concurrent efforts, with student and professional pilot samples, to determine the effects of accountability pressures on automation bias and on the verification of the accurate functioning of automated aids. Students (Experiment 1) and commercial pilots (Experiment 2) performed simulated flight tasks using automated aids. In both studies, participants who perceived themselves as accountable for their strategies of interaction with the automation were significantly more likely to verify its correctness, and committed significantly fewer automation-related errors than those who did not report this perception.

Mosier, Kathleen L.↗

Optimizing Observation Scheduling Objectives

In this paper, we present an approach that enables the automatic generation of high quality schedules, with respect to a given objective function. The approach involves the combination of two techniques: GenH, which automatically generates a search heuristic specialized to the given problem instance, and HBSS, which employs the generated heuristic as a bias within a stochastic sampling method.

Bresina, John L.↗

Scheduling in the Face of Uncertain Resource Consumption and Utility

We discuss the problem of scheduling tasks that consume a resource with known capacity and where the tasks have varying utility. We consider problems in which the resource consumption and utility of each activity is described by probability distributions. In these circumstances, we would like to find schedules that exceed a lower bound on the expected utility when executed. We first show that while some of these problems are NP-complete, others are only NP-Hard. We then describe various heuristic search algorithms to solve these problems and their drawbacks. Finally, we present empirical results that characterize the behavior of these heuristics over a variety of problem classes.

Koga, Dennis↗

Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact

We compare existing techniques to bound the resource availability of partially ordered events. We first show that, contrary to intuition, two existing techniques, one due to Laborie and one due to Muscettola, are not strictly comparable in terms of the size of the search trees generated under chronological search with a fixed heuristic. We describe a generalization of these techniques called the Flow Balance Constraint to tightly bound the amount of available resource for a set of partially ordered events with piecewise constant resource impact We prove that the new technique generates smaller proof trees under chronological search with a fixed heuristic, at little increase in computational expense. We then show how to construct tighter resource bounds but at increased computational cost.

Frank, Jeremy↗

Iterative pass optimization of sequence data

The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

NASA Discipline Evolutionary Biology↗

Figure Control of Lightweight Optical Structures

The goal of this paper is to demonstrate the use of fuzzy logic controllers in modifying the figure of a piezoceramic bimorph mirror. Non-contact electron actuation technology is used to actively control a bimorph mirror comprised two PZT-5H wafers by varying the electron flux and electron voltages. Due to electron blooming generated by the electron flux, it is difficult to develop an accurate control model for the bimorph mirror through theoretical analysis alone. The non-contact shape control system with electron flux blooming can be approximately described with a heuristic model based on experimental data. Two fuzzy logic feedback controllers are developed to control the shape of the bimorph mirror according to heuristic fuzzy inference rules generated from previous experimental results. Validation of the proposed fuzzy logic controllers is also discussed.

Main, John A.↗

Adaptable Constrained Genetic Programming: Extensions and Applications

An evolutionary algorithm applies evolution-based principles to problem solving. To solve a problem, the user defines the space of potential solutions, the representation space. Sample solutions are encoded in a chromosome-like structure. The algorithm maintains a population of such samples, which undergo simulated evolution by means of mutation, crossover, and survival of the fittest principles. Genetic Programming (GP) uses tree-like chromosomes, providing very rich representation suitable for many problems of interest. GP has been successfully applied to a number of practical problems such as learning Boolean functions and designing hardware circuits. To apply GP to a problem, the user needs to define the actual representation space, by defining the atomic functions and terminals labeling the actual trees. The sufficiency principle requires that the label set be sufficient to build the desired solution trees. The closure principle allows the labels to mix in any arity-consistent manner. To satisfy both principles, the user is often forced to provide a large label set, with ad hoc interpretations or penalties to deal with undesired local contexts. This unfortunately enlarges the actual representation space, and thus usually slows down the search. In the past few years, three different methodologies have been proposed to allow the user to alleviate the closure principle by providing means to define, and to process, constraints on mixing the labels in the trees. Last summer we proposed a new methodology to further alleviate the problem by discovering local heuristics for building quality solution trees. A pilot system was implemented last summer and tested throughout the year. This summer we have implemented a new revision, and produced a User's Manual so that the pilot system can be made available to other practitioners and researchers. We have also designed, and partly implemented, a larger system capable of dealing with much more powerful heuristics.

Janikow, Cezary Z.↗

Kalman Filter Constraint Tuning for Turbofan Engine Health Estimation

Kalman filters are often used to estimate the state variables of a dynamic system. However, in the application of Kalman filters some known signal information is often either ignored or dealt with heuristically. For instance, state variable constraints are often neglected because they do not fit easily into the structure of the Kalman filter. Recently published work has shown a new method for incorporating state variable inequality constraints in the Kalman filter, which has been shown to generally improve the filter s estimation accuracy. However, the incorporation of inequality constraints poses some risk to the estimation accuracy as the Kalman filter is theoretically optimal. This paper proposes a way to tune the filter constraints so that the state estimates follow the unconstrained (theoretically optimal) filter when the confidence in the unconstrained filter is high. When confidence in the unconstrained filter is not so high, then we use our heuristic knowledge to constrain the state estimates. The confidence measure is based on the agreement of measurement residuals with their theoretical values. The algorithm is demonstrated on a linearized simulation of a turbofan engine to estimate engine health.

Simon, Dan↗