Search NASA⌕ Search

SEARCH · Search NASA

Results for “Search algorithm”

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 451 records · Page 25
All sourcesNASA NTRSDOE OSTI
NASA NTRS1989

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗
NASA NTRS2010

Graph-Based Path-Planning for Titan Balloons

A document describes a graph-based path-planning algorithm for balloons with vertical control authority and little or no horizontal control authority. The balloons are designed to explore celestial bodies with atmospheres, such as Titan, a moon of Saturn. The algorithm discussed enables the balloon to achieve horizontal motion using the local horizontal winds. The approach is novel because it enables the balloons to use arbitrary wind field models. This is in contrast to prior approaches that used highly simplified wind field models, such as linear, or binary, winds. This new approach works by discretizing the space in which the balloon operates, and representing the possible states of the balloon as a graph whose arcs represent the time taken to move from one node to another. The approach works with arbitrary wind fields, by looking up the wind strength and direction at every node in the graph from an arbitrary wind model. Having generated the graph, search techniques such as Dijkstra s algorithm are then used to find the set of vertical actuation commands that takes the balloon from the start to the goal in minimum time. In addition, the set of reachable locations on the moon or planet can be determined.

Blackmore, Lars James↗
NASA NTRS2016

Heuristics for Relevancy Ranking of Earth Dataset Search Results

As the Variety of Earth science datasets increases, science researchers find it more challenging to discover and select the datasets that best fit their needs. The most common way of search providers to address this problem is to rank the datasets returned for a query by their likely relevance to the user. Large web page search engines typically use text matching supplemented with reverse link counts, semantic annotations and user intent modeling. However, this produces uneven results when applied to dataset metadata records simply externalized as a web page. Fortunately, data and search provides have decades of experience in serving data user communities, allowing them to form heuristics that leverage the structure in the metadata together with knowledge about the user community. Some of these heuristics include specific ways of matching the user input to the essential measurements in the dataset and determining overlaps of time range and spatial areas. Heuristics based on the novelty of the datasets can prioritize later, better versions of data over similar predecessors. And knowledge of how different user types and communities use data can be brought to bear in cases where characteristics of the user (discipline, expertise) or their intent (applications, research) can be divined. The Earth Observing System Data and Information System has begun implementing some of these heuristics in the relevancy algorithm of its Common Metadata Repository search engine.

science data management↗
NASA NTRS2017

Relevancy Ranking of Satellite Dataset Search Results

As the Variety of Earth science datasets increases, science researchers find it more challenging to discover and select the datasets that best fit their needs. The most common way of search providers to address this problem is to rank the datasets returned for a query by their likely relevance to the user. Large web page search engines typically use text matching supplemented with reverse link counts, semantic annotations and user intent modeling. However, this produces uneven results when applied to dataset metadata records simply externalized as a web page. Fortunately, data and search provides have decades of experience in serving data user communities, allowing them to form heuristics that leverage the structure in the metadata together with knowledge about the user community. Some of these heuristics include specific ways of matching the user input to the essential measurements in the dataset and determining overlaps of time range and spatial areas. Heuristics based on the novelty of the datasets can prioritize later, better versions of data over similar predecessors. And knowledge of how different user types and communities use data can be brought to bear in cases where characteristics of the user (discipline, expertise) or their intent (applications, research) can be divined. The Earth Observing System Data and Information System has begun implementing some of these heuristics in the relevancy algorithm of its Common Metadata Repository search engine.

science data management↗
NASA NTRS1981

Contextual classification of multispectral image data

A general method is presented for exploiting both spatial and spectral information when classifying multispectral image data. This statistical classification algorithm utilizes the tendency of certain ground cover classes to be more likely to occur in some contexts than others. The theoretical model assumes the two-dimensional array of random observations and a 0-1 loss function, a distribution of the p-context array that is spatially invariant, and class-conditional independence for the observations. The problems that prevent the immediate use of this context classifier are the need for a generally applicable method for making adequate estimates of the context distribution and a reduction in the computational intensivity of the classifier. The former problem is being approached by a method that raises the relative frequency value for each class configuration to a power and uses the result as the context distribution estimate. The second is being approached by searching for a less computationally intensive algorithm.

Tilton, J. C.↗
NASA NTRS2010

Physics-Based Methods of Failure Analysis and Diagnostics in Human Space Flight

The Integrated Health Management (IHM) for the future aerospace systems requires to interface models of multiple subsystems in an efficient and accurate information environment at the earlier stages of system design. The complexity of modern aeronautic and aircraft systems (including e.g. the power distribution, flight control, solid and liquid motors) dictates employment of hybrid models and high-level reasoners for analysing mixed continuous and discrete information flow involving multiple modes of operation in uncertain environments, unknown state variables, heterogeneous software and hardware components. To provide the information link between key design/performance parameters and high-level reasoners we rely on development of multi-physics performance models, distributed sensors networks, and fault diagnostic and prognostic (FD&P) technologies in close collaboration with system designers. The main challenges of our research are related to the in-flight assessment of the structural stability, engine performance, and trajectory control. The main goal is to develop an intelligent IHM that not only enhances components and system reliability, but also provides a post-flight feedback helping to optimize design of the next generation of aerospace systems. Our efforts are concentrated on several directions of the research. One of the key components of our strategy is an innovative approach to the diagnostics/prognostics based on the real time dynamical inference (DI) technologies extended to encompass hybrid systems with hidden state trajectories. The major investments are into the multiphysics performance modelling that provides an access of the FD&P technologies to the main performance parameters of e.g. solid and liquid rocket motors and composite materials of the nozzle and case. Some of the recent results of our research are discussed in this chapter. We begin by introducing the problem of dynamical inference of stochastic nonlinear models and reviewing earlier results. Next, we present our analytical approach to the solution of this problem based on the path integral formulation. The resulting algorithm does not require an extensive global search for the model parameters, provides optimal compensation for the effects of dynamical noise, and is robust for a broad range of dynamical models. In the following Section the strengths of the algorithm are illustrated illustrated by inferring the parameters of the stochastic Lorenz system and comparing the results with those of earlier research. Next, we discuss a number of recent results in application to the development of the IHM for aerospace system. Firstly, we apply dynamical inference approach to a solution of classical three tank problems with mixed unknown continuous and binary parameters. The problem is considered in the context of ground support system for filling fuel tanks of liquid rocket motors. It is shown that the DI algorithm is well suited for successful solution of a hybrid version of this benchmark problem even in the presence of additional periodic and stochastic perturbation of unknown strength. Secondly, we illustrate our approach by its application to an analysis of the nozzle fault in a solid rocket motor (SRM). The internal ballistics of the SRM is modelled as a set of one-dimensional partial differential equations coupled to the dynamics of the propellant regression. In this example we are specifically focussed on the inference of discrete and continuous parameters of the nozzle blocking fault and on the possibility of an application of the DI algorithm to reducing the probability of "misses" of an on-board FD&P for SRM. In the next section re-contact problem caused by first stage/upper stage separation failure is discussed. The reaction forces imposed on the nozzle of the upper stage during the re-contact and their connection to the nozzle damage and to the thrust vector control (TVC) signal are obtained. It is shown that transient impact induced torquean be modelled as a response of an effective damped oscillator. A possible application of the DI algorithm to the inference of damage parameters and predicting fault dynamics ahead of time using the actuator signal is discussed. Finally, we formulate Bayesian inferential framework for development of the IHM system for in-flight structural health monitoring (SHM) of composite materials. We consider the signal generated by piezoelectric actuator mounted on composite structure generating elastic waves in it. The signal received by the sensor is than compared with the baseline signal. The possibility of damage inference is discussed in the context of development of the SHM.

Smelyanskiy, Vadim N.↗
NASA NTRS1993

The potential of genetic algorithms for conceptual design of rotor systems

The capabilities of genetic algorithms as a non-calculus based, global search method make them potentially useful in the conceptual design of rotor systems. Coupling reasonably simple analysis tools to the genetic algorithm was accomplished, and the resulting program was used to generate designs for rotor systems to match requirements similar to those of both an existing helicopter and a proposed helicopter design. This provides a comparison with the existing design and also provides insight into the potential of genetic algorithms in design of new rotors.

Crossley, William A.↗
NASA NTRS2004

Cooperative Lander-Surface/Aerial Microflyer Missions for Mars Exploration

Concepts are being investigated for exploratory missions to Mars based on Bioinspired Engineering of Exploration Systems (BEES), which is a guiding principle of this effort to develop biomorphic explorers. The novelty lies in the use of a robust telecom architecture for mission data return, utilizing multiple local relays (including the lander itself as a local relay and the explorers in the dual role of a local relay) to enable ranges ~10 to 1,000 km and downlink of color imagery. As illustrated in Figure 1, multiple microflyers that can be both surface or aerially launched are envisioned in shepherding, metamorphic, and imaging roles. These microflyers imbibe key bio-inspired principles in their flight control, navigation, and visual search operations. Honey-bee inspired algorithms utilizing visual cues to perform autonomous navigation operations such as terrain following will be utilized. The instrument suite will consist of a panoramic imager and polarization imager specifically optimized to detect ice and water. For microflyers, particularly at small sizes, bio-inspired solutions appear to offer better alternate solutions than conventional engineered approaches. This investigation addresses a wide range of interrelated issues, including desired scientific data, sizes, rates, and communication ranges that can be accomplished in alternative mission scenarios. The mission illustrated in Figure 1 offers the most robust telecom architecture and the longest range for exploration with two landers being available as main local relays in addition to an ephemeral aerial probe local relay. The shepherding or metamorphic plane are in their dual role as local relays and image data collection/storage nodes. Appropriate placement of the landing site for the scout lander with respect to the main mission lander can allow coverage of extremely large ranges and enable exhaustive survey of the area of interest. In particular, this mission could help with the path planning and risk mitigation in the traverse of the long-distance surface explorer/rover. The basic requirements of design and operation of BEES to implement the scenarios are discussed. Terrestrial applications of such concepts include distributed aerial/surface measurements of meteorological events, i.e., storm watch, seismic monitoring, reconnaissance, biological chemical sensing, search and rescue, surveillance, autonomous security/ protection agents, and/or delivery and lateral distribution of agents (sensors, surface/subsurface crawlers, clean-up agents). Figure 2 illustrates an Earth demonstration that is in development, and its implementation will illustrate the value of these biomorphic mission concepts.

Thakoor, Sarita↗
NASA NTRS1983

SETI Pulse Detection Algorithm: Analysis of False-alarm Rates

Some earlier work by the Search for Extraterrestrial Intelligence (SETI) Science Working Group (SWG) on the derivation of spectrum analyzer thresholds for a pulse detection algorithm based on an analysis of false alarm rates is extended. The algorithm previously analyzed was intended to detect a finite sequence of i periodically spaced pulses that did not necessarily occupy the entire observation interval. This algorithm would recognize the presence of such a signal only if all i-received pulse powers exceeded a threshold T(i): these thresholds were selected to achieve a desired false alarm rate, independent of i. To simplify the analysis, it was assumed that the pulses were synchronous with the spectrum sample times. This analysis extends the earlier effort to include infinite and/or asynchronous pulse trains. Furthermore, to decrease the possibility of missing an extraterrestrial intelligence signal, the algorithm was modified to detect a pulse train even if some of the received pulse powers fall below the threshold. The analysis employs geometrical arguments that make it conceptually easy to incorporate boundary conditions imposed on the derivation of the false alarm rates. While the exact results can be somewhat complex, simple closed form approximations are derived that produce a negligible loss of accuracy.

Levitt, B. K.↗
NASA NTRS1977

An asymptotic analysis of a general class of signal detection algorithms

For applications to the problem of radio frequency interference identification, or in the search for extraterrestrial intelligence, it is important to have a basic understanding of signal detection algorithms. A general technique for assessing the asymptotic sensitivity of a broad class of signal detection algorithms is given. In these algorithms, the decision is based on the value of X sub 1 + X sub 2...+ X sub n where the X sub 1's are obtained by sampling and preliminary processing of a physical process.

Mceliece, R. J.↗
NASA NTRS1987

An adaptive algorithm for motion compensated color image coding

This paper presents an adaptive algorithm for motion compensated color image coding. The algorithm can be used for video teleconferencing or broadcast signals. Activity segmentation is used to reduce the bit rate and a variable stage search is conducted to save computations. The adaptive algorithm is compared with the nonadaptive algorithm and it is shown that with approximately 60 percent savings in computing the motion vector and 33 percent additional compression, the performance of the adaptive algorithm is similar to the nonadaptive algorithm. The adaptive algorithm results also show improvement of up to 1 bit/pel over interframe DPCM coding with nonuniform quantization. The test pictures used for this study were recorded directly from broadcast video in color.

Kwatra, Subhash C.↗
DOE OSTI2024

Constitutive model development of aluminum alloy 1100 for elevated temperature forming process

Commercially pure aluminum alloy, AA1100, presents good electrical and thermal conductivity, high formability, and low cost. Those favorable characteristics have the potential to enable bipolar plates with improved economics and enhanced performance compared to current stainless steel bipolar plates for proton exchange membrane fuel cells. An accurate constitutive model is essential to develop and optimize processing parameters and effectively control the forming process. Here, the objective of this work is to develop a constitutive model of AA1100 that is able to simulate stress-strain relation, formed geometry, and predict the onset of fracture strain to avoid forming failure. Initially, a set of tensile tests at temperature between 300 and 500°C and strain rate between 0.005 and 1.0/s were conducted to examine the deformation behavior. Then, a set of damage-based unified visco-plastic constitutive equations is proposed and calibrated based on the results of stress-strain data. A genetic algorithm optimization method is applied to search for best fitting material constants in constitutive equations. The proposed model shows good predictability of both the stress-strain relation and fracture strain at low strain rate and high temperature conditions. The accuracy of proposed model is also evaluated statistically. A comparison of the proposed model with three popular models (Arrhenius-type mode, Johnson-Cook model and Zerilli-Armstrong model) was made. The proposed model shows the best experimental agreement with correlation coefficient of 0.96 in contrast to 0.25, 0.38 and 0.75 for the popular models, respectively. The proposed model can help to optimize the elevated temperature forming process and guide die design to enable optimal geometric features in the formed components.

08 HYDROGEN↗
NASA NTRS1975

Panel flutter optimization by gradient projection

A gradient projection optimal control algorithm incorporating conjugate gradient directions of search is described and applied to several minimum weight panel design problems subject to a flutter speed constraint. New numerical solutions are obtained for both simply-supported and clamped homogeneous panels of infinite span for various levels of inplane loading and minimum thickness. The minimum thickness inequality constraint is enforced by a simple transformation of variables.

Pierson, B. L.↗
NASA NTRS1990

A search for novae in M 31 globular clusters

By combining a local sky-fitting algorithm with a Fourier point-spread-function matching technique, nova outbursts have been searched for inside 54 of the globular clusters contained on the Ciardullo et al. (1987 and 1990) H-alpha survey frames of M 31. Over a mean effective survey time of about 2.0 years, no cluster exhibited a magnitude increase indicative of a nova explosion. If the cataclysmic variables (CVs) contained within globular clusters are similar to those found in the field, then these data imply that the overdensity of CVs within globulars is at least several times less than that of the high-luminosity X-ray sources. If tidal capture is responsible for the high density of hard binaries within globulars, then the probability of capturing condensed objects inside globular clusters may depend strongly on the mass of the remnant.

Ciardullo, Robin↗
NASA NTRS1992

Minimum-exposure near-terrain flight trajectories for rotorcraft

The paper presents methodologies for constructing optimal trajectories for rotorcraft executing nap-of-the-earth flight over known terrain. Unlike the standard techniques, the present approaches require only a one-dimensional numerical search for determining optimal trajectories. Numerical algorithms are developed using two kinematic vehicle models in conjunction with optimal control theory.

Menon, P. K. A.↗
NASA NTRS2002

Asteroseismology from Space: The Delta Scuti Star Theta(sup 2) Tauri Monitored by the WIRE Satellite

The bright variable star (theta)(sup 2) Tau was monitored with the star camera on the Wide-Field Infrared Explorer satellite. Twelve independent frequencies were detected down to the 0.5 mmag amplitude level. Their reality was investigated by searching for them using two different algorithms and by some internal checks: both procedures strengthened our confidence in the results. All the frequencies are in the range 10.8 - 14.6 cd(exp -1). The histogram of the frequency spacings shows that 81% are below 1.8 d; rotation may thus play a role in the mode excitation. The fundamental radial mode is not observed, although it is expected to occur in a region where the noise level is very low (55 (micro)mag). The rms (root mean square) residual is about two times lower than that usually obtained from successful groundbased multisite campaigns. The comparison of the results of previous campaigns with the new ones establishes the amplitude variability of some modes.

Poretti, E.↗
NASA NTRS2003

Interleaved Observation Execution and Rescheduling on Earth Observing Systems

Observation scheduling for Earth orbiting satellites solves the following problem: given a set of requests for images of the Earth, a set of instruments for acquiring those images distributed on a collecting of orbiting satellites, and a set of temporal and resource constraints, generate a set of assignments of instruments and viewing times to those requests that satisfy those constraints. Observation scheduling is often construed as a constrained optimization problem with the objective of maximizing the overall utility of the science data acquired. The utility of an image is typically based on the intrinsic importance of acquiring it (for example, its importance in meeting a mission or science campaign objective) as well as the expected value of the data given current viewing conditions (for example, if the image is occluded by clouds, its value is usually diminished). Currently, science observation scheduling for Earth Observing Systems is done on the ground, for periods covering a day or more. Schedules are uplinked to the satellites and are executed rigorously. An alternative to this scenario is to do some of the decision-making about what images are to be acquired on-board. The principal argument for this capability is that the desirability of making an observation can change dynamically, because of changes in meteorological conditions (e.g. cloud cover), unforeseen events such as fires, floods, or volcanic eruptions, or un-expected changes in satellite or ground station capability. Furthermore, since satellites can only communicate with the ground between 5% to 10% of the time, it may be infeasible to make the desired changes to the schedule on the ground, and uplink the revisions in time for the on-board system to execute them. Examples of scenarios that motivate an on-board capability for revising schedules include the following. First, if a desired visual scene is completely obscured by clouds, then there is little point in taking it. In this case, satellite resources, such as power and storage space can be better utilized taking another image that is higher quality. Second, if an unexpected but important event occurs (such as a fire, flood, or volcanic eruption), there may be good reason to take images of it, instead of expending satellite resources on some of the lower priority scheduled observations. Finally, if there is unexpected loss of capability, it may be impossible to carry out the schedule of planned observations. For example, if a ground station goes down temporarily, a satellite may not be able to free up enough storage space to continue with the remaining schedule of observations. This paper describes an approach for interleaving execution of observation schedules with dynamic schedule revision based on changes to the expected utility of the acquired images. We describe the problem in detail, formulate an algorithm for interleaving schedule revision and execution, and discuss refinements to the algorithm based on the need for search efficiency. We summarize with a brief discussion of the tests performed on the system.

Khatib, Lina↗
NASA NTRS2002

Asteroseismology from Space: The Delta Scuti Star Theta(sup 2) Tauri Monitored by the WIRE Satellite

The bright variable star theta(sup 2) Tau was monitored with the star camera on the Wide-Field Infrared Explorer satellite. Twelve independent frequencies were detected down to the 0.5 mmag amplitude level. Their reality was investigated by searching for them using two different algorithms and by some internal checks: both procedures strengthened our confidence in the results. All the frequencies are in the range 10.8-14.6 cd(exp -1). The histogram of the frequency spacings shows that 81% are below 1.8 d; rotation may thus play a role in the mode excitation. The fundamental radial mode is not observed, although it is expected to occur in a region where the noise level is very low (55 mu mag). The rms residual is about two times lower than that usually obtained from successful groundbased multisite campaigns. The comparison of the results of previous campaigns with the new ones establishes the amplitude variability of some modes.

Poretti, E.↗