Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Tractable algorithms”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2002

Two Solvers for Tractable Temporal Constraints with Preferences

A number of reasoning problems involving the manipulation of temporal information can naturally be viewed as implicitly inducing an ordering of potential local decisions involving time on the basis of preferences. Soft temporal constraints problems allow to describe in a natural way scenarios where events happen over time and preferences are associated to event distances and durations. In general, solving soft temporal problems require exponential time in the worst case, but there are interesting subclasses of problems which are polynomially solvable. We describe two solvers based on two different approaches for solving the same tractable subclass. For each solver we present the theoretical results it stands on, a description of the algorithm and some experimental results. The random generator used to build the problems on which tests are performed is also described. Finally, we compare the two solvers highlighting the tradeoff between performance and representational power.

Rossi, F.↗
NASA NTRS2011

Multiple-Beam Detection of Fast Transient Radio Sources

A method has been designed for using multiple independent stations to discriminate fast transient radio sources from local anomalies, such as antenna noise or radio frequency interference (RFI). This can improve the sensitivity of incoherent detection for geographically separated stations such as the very long baseline array (VLBA), the future square kilometer array (SKA), or any other coincident observations by multiple separated receivers. The transients are short, broadband pulses of radio energy, often just a few milliseconds long, emitted by a variety of exotic astronomical phenomena. They generally represent rare, high-energy events making them of great scientific value. For RFI-robust adaptive detection of transients, using multiple stations, a family of algorithms has been developed. The technique exploits the fact that the separated stations constitute statistically independent samples of the target. This can be used to adaptively ignore RFI events for superior sensitivity. If the antenna signals are independent and identically distributed (IID), then RFI events are simply outlier data points that can be removed through robust estimation such as a trimmed or Winsorized estimator. The alternative "trimmed" estimator is considered, which excises the strongest n signals from the list of short-beamed intensities. Because local RFI is independent at each antenna, this interference is unlikely to occur at many antennas on the same step. Trimming the strongest signals provides robustness to RFI that can theoretically outperform even the detection performance of the same number of antennas at a single site. This algorithm requires sorting the signals at each time step and dispersion measure, an operation that is computationally tractable for existing array sizes. An alternative uses the various stations to form an ensemble estimate of the conditional density function (CDF) evaluated at each time step. Both methods outperform standard detection strategies on a test sequence of VLBA data, and both are efficient enough for deployment in real-time, online transient detection applications.

Thompson, David R.↗
NASA NTRS1989

Detection of edges using local geometry

Researchers described a new representation, the local geometry, for early visual processing which is motivated by results from biological vision. This representation is richer than is often used in image processing. It extracts more of the local structure available at each pixel in the image by using receptive fields that can be continuously rotated and that go to third order spatial variation. Early visual processing algorithms such as edge detectors and ridge detectors can be written in terms of various local geometries and are computationally tractable. For example, Canny's edge detector has been implemented in terms of a local geometry of order two, and a ridge detector in terms of a local geometry of order three. The edge detector in local geometry was applied to synthetic and real images and it was shown using simple interpolation schemes that sufficient information is available to locate edges with sub-pixel accuracy (to a resolution increase of at least a factor of five). This is reasonable even for noisy images because the local geometry fits a smooth surface - the Taylor series - to the discrete image data. Only local processing was used in the implementation so it can readily be implemented on parallel mesh machines such as the MPP. Researchers expect that other early visual algorithms, such as region growing, inflection point detection, and segmentation can also be implemented in terms of the local geometry and will provide sufficiently rich and robust representations for subsequent visual processing.

Gualtieri, J. A.↗
NASA NTRS2004

Spacecraft Attitude Maneuver Planning Using Genetic Algorithms

A key enabling technology that leads to greater spacecraft autonomy is the capability to autonomously and optimally slew the spacecraft from and to different attitudes while operating under a number of celestial and dynamic constraints. The task of finding an attitude trajectory that meets all the constraints is a formidable one, in particular for orbiting or fly-by spacecraft where the constraints and initial and final conditions are of time-varying nature. This approach for attitude path planning makes full use of a priori constraint knowledge and is computationally tractable enough to be executed onboard a spacecraft. The approach is based on incorporating the constraints into a cost function and using a Genetic Algorithm to iteratively search for and optimize the solution. This results in a directed random search that explores a large part of the solution space while maintaining the knowledge of good solutions from iteration to iteration. A solution obtained this way may be used as is or as an initial solution to initialize additional deterministic optimization algorithms. A number of representative case examples for time-fixed and time-varying conditions yielded search times that are typically on the order of minutes, thus demonstrating the viability of this method. This approach is applicable to all deep space and planet Earth missions requiring greater spacecraft autonomy, and greatly facilitates navigation and science observation planning.

Kornfeld, Richard P.↗
NASA NTRS2003

On-board autonomous attitude maneuver planning for planetary spacecraft using genetic algorithms

A key enabling technology that leads to greater spacecraft autonomy is the capability to autonomously and optimally slew the spacecraft from and to different attitudes while operating under a number of celestial and dynamic constraints. The task of finding an attitude trajectory that meets all the constraints is a formidable one, in particular for orbiting or fly-by spacecraft where the constraints and initial and final conditions are of time-varying nature. This paper presents an approach for attitude path planning that makes full use of a priori constraint knowledge and is computationally tractable enough to be executed on-board a spacecraft. The approach is based on incorporating the constraints into a cost function and using a Genetic Algorithm to iteratively search for and optimize the solution. This results in a directed random search that explores a large part of the solution space while maintaining the knowledge of good solutions from iteration to iteration. A solution obtained this way may be used 'as is' or as an initial solution to initialize additional deterministic optimization algorithms. A number of example simulations are presented including the case examples of a generic Europa Orbiter spacecraft in cruise as well as in orbit around Europa. The search times are typically on the order of minutes, thus demonstrating the viability of the presented approach. The results are applicable to all future deep space missions where greater spacecraft autonomy is required. In addition, onboard autonomous attitude planning greatly facilitates navigation and science observation planning, benefiting thus all missions to planet Earth as well.

genetic algorithm↗
NASA NTRS1999

Fast Quantum Algorithm for Predicting Descriptive Statistics of Stochastic Processes

Stochastic processes are used as a modeling tool in several sub-fields of physics, biology, and finance. Analytic understanding of the long term behavior of such processes is only tractable for very simple types of stochastic processes such as Markovian processes. However, in real world applications more complex stochastic processes often arise. In physics, the complicating factor might be nonlinearities; in biology it might be memory effects; and in finance is might be the non-random intentional behavior of participants in a market. In the absence of analytic insight, one is forced to understand these more complex stochastic processes via numerical simulation techniques. In this paper we present a quantum algorithm for performing such simulations. In particular, we show how a quantum algorithm can predict arbitrary descriptive statistics (moments) of N-step stochastic processes in just O(square root of N) time. That is, the quantum complexity is the square root of the classical complexity for performing such simulations. This is a significant speedup in comparison to the current state of the art.

Williams Colin P.↗
NASA NTRS2011

MODIS Cloud Optical Property Retrieval Uncertainties Derived from Pixel-Level VNIR/SWIR Radiometric Uncertainties

Moderate Resolution Imaging Spectroradiometer (MODIS) retrievals of optical thickness and effective particle radius for liquid water and ice phase clouds employ a well-known VNIR/ SWIR solar reflectance technique. For this type of algorithm, we evaluate the quantitative uncertainty in simultaneous retrievals of these two cloud parameters to pixel-level radiometric calibration estimates and other fundamental (and tractable) error sources.

Platnick, S.↗
NASA NTRS2021

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↗
NASA NTRS1990

A generalized patched-grid algorithm with application to the F-18 forebody with actuated control strake

Analysis of complex configurations using structured grids virtually demands multiple blocks of grids. To facilitate calculations involving multiple blocks, a geneal grid-block patching algorithm based on generalized coordinate inerpolation has been developed. The computational grid may contain as many arbirarily shaped blocks as required to make the grid generation problem tractable and to accurately model the fow features. Results are presented for several test cases as well as for the F-18 forebody control strake. The methodology developed has application to overlapped or embedded grids.

Biedron, R. T.↗
NASA NTRS2012

Validation of Airborne FMCW Radar Measurements of Snow Thickness Over Sea Ice in Antarctica

Antarctic sea ice and its snow cover are integral components of the global climate system, yet many aspects of their vertical dimensions are poorly understood, making their representation in global climate models poor. Remote sensing is the key to monitoring the dynamic nature of sea ice and its snow cover. Reliable and accurate snow thickness data are currently a highly sought after data product. Remotely sensed snow thickness measurements can provide an indication of precipitation levels, predicted to increase with effects of climate change in the polar regions. Airborne techniques provide a means for regional-scale estimation of snow depth and distribution. Accurate regional-scale snow thickness data will also facilitate an increase in the accuracy of sea ice thickness retrieval from satellite altimeter freeboard estimates. The airborne data sets are easier to validate with in situ measurements and are better suited to validating satellite algorithms when compared with in situ techniques. This is primarily due to two factors: better chance of getting coincident in situ and airborne data sets and the tractability of comparison between an in situ data set and the airborne data set averaged over the footprint of the antennas. A 28-GHz frequency modulated continuous wave (FMCW) radar loaned by the Center for Remote Sensing of Ice Sheets to the Australian Antarctic Division is used to measure snow thickness over sea ice in East Antarctica. Provided with the radar design parameters, the expected performance parameters of the radar are summarized. The necessary conditions for unambiguous identification of the airsnow and snowice layers for the radar are presented. Roughnesses of the snow and ice surfaces are found to be dominant determinants in the effectiveness of layer identification for this radar. Finally, this paper presents the first in situ validated snow thickness estimates over sea ice in Antarctica derived from an FMCW radar on a helicopterborne platform.

sea ice↗
NASA NTRS2006

Bayesian Estimation of Precipitation from Satellite Passive Microwave Observations Using Combined Radar-Radiometer Retrievals

Precipitation estimation from satellite passive microwave radiometer observations is a problem that does not have a unique solution that is insensitive to errors in the input data. Traditionally, to make this problem well posed, a priori information derived from physical models or independent, high-quality observations is incorporated into the solution. In the present study, a database of precipitation profiles and associated brightness temperatures is constructed to serve as a priori information in a passive microwave radiometer algorithm. The precipitation profiles are derived from a Tropical Rainfall Measuring Mission (TRMM) combined radar radiometer algorithm, and the brightness temperatures are TRMM Microwave Imager (TMI) observed. Because the observed brightness temperatures are consistent with those derived from a radiative transfer model embedded in the combined algorithm, the precipitation brightness temperature database is considered to be physically consistent. The database examined here is derived from the analysis of a month-long record of TRMM data that yields more than a million profiles of precipitation and associated brightness temperatures. These profiles are clustered into a tractable number of classes based on the local sea surface temperature, a radiometer-based estimate of the echo-top height (the height beyond which the reflectivity drops below 17 dBZ), and brightness temperature principal components. For each class, the mean precipitation profile, brightness temperature principal components, and probability of occurrence are determined. The precipitation brightness temperature database supports a radiometer-only algorithm that incorporates a Bayesian estimation methodology. In the Bayesian framework, precipitation estimates are weighted averages of the mean precipitation values corresponding to the classes in the database, with the weights being determined according to the similarity between the observed brightness temperature principal components and the brightness temperature principal components of the classes. Because the classes are stratified by the sea surface temperature and the echo-top-height estimator, the number of classes that are considered for retrieval is significantly smaller than the total number of classes, making the algorithm computationally efficient. The radiometer-only algorithm is applied to TMI observations, and precipitation estimates are compared with combined TRMM precipitation radar (PR) TMI reference estimates. The TMI-only algorithm, supported by the empirically derived database, produces estimates that are more consistent with the reference values than the precipitation estimates from the version-6 TRMM facility TMI algorithm. Cloud-resolving model simulations are used to assign a latent heating profile to each precipitation profile in the empirically derived database, making it possible to estimate latent heating using the radiometer-only algorithm. Although the evaluation of latent heating estimates in this study is preliminary, because realistic conditional probability distribution functions are attached to latent heating structures in the algorithm s database, a generally positive impact on latent heating estimation from passive microwave observations is expected.

Grecu, Mircea↗
NASA NTRS1994

Land surface temperature measurements from EOS MODIS data

A generalized split-window method for retrieving land-surface temperature (LST) from AVHRR and MODIS data has been developed. Accurate radiative transfer simulations show that the coefficients in the split-window algorithm for LST must depend on the viewing angle, if we are to achieve a LST accuracy of about 1 K for the whole scan swath range (+/-55.4 deg and +/-55 deg from nadir for AVHRR and MODIS, respectively) and for the ranges of surface temperature and atmospheric conditions over land, which are much wider than those over oceans. We obtain these coefficients from regression analysis of radiative transfer simulations, and we analyze sensitivity and error by using results from systematic radiative transfer simulations over wide ranges of surface temperatures and emissivities, and atmospheric water vapor abundance and temperatures. Simulations indicated that as atmospheric column water vapor increases and viewing angle is larger than 45 deg it is necessary to optimize the split-window method by separating the ranges of the atmospheric column water vapor and lower boundary temperature, and the surface temperature into tractable sub-ranges. The atmospheric lower boundary temperature and (vertical) column water vapor values retrieved from HIRS/2 or MODIS atmospheric sounding channels can be used to determine the range where the optimum coefficients of the split-window method are given. This new LST algorithm not only retrieves LST more accurately but also is less sensitive than viewing-angle independent LST algorithms to the uncertainty in the band emissivities of the land-surface in the split-window and to the instrument noise.

Wan, Zhengming↗
NASA NTRS1992

Formal verification of an oral messages algorithm for interactive consistency

The formal specification and verification of an algorithm for Interactive Consistency based on the Oral Messages algorithm for Byzantine Agreement is described. We compare our treatment with that of Bevier and Young, who presented a formal specification and verification for a very similar algorithm. Unlike Bevier and Young, who observed that 'the invariant maintained in the recursive subcases of the algorithm is significantly more complicated than is suggested by the published proof' and who found its formal verification 'a fairly difficult exercise in mechanical theorem proving,' our treatment is very close to the previously published analysis of the algorithm, and our formal specification and verification are straightforward. This example illustrates how delicate choices in the formulation of the problem can have significant impact on the readability of its formal specification and on the tractability of its formal verification.

Rushby, John↗
NASA NTRS2017

LPV Modeling of a Flexible Wing Aircraft Using Modal Alignment and Adaptive Gridding Methods

One of the earliest approaches in gain-scheduling control is the gridding based approach, in which a set of local linear time-invariant models are obtained at various gridded points corresponding to the varying parameters within the flight envelop. In order to ensure smooth and effective Linear Parameter-Varying control, aligning all the flexible modes within each local model and maintaining small number of representative local models over the gridded parameter space are crucial. In addition, since the flexible structural models tend to have large dimensions, a tractable model reduction process is necessary. In this paper, the notion of s-shifted H2- and H Infinity-norm are introduced and used as a metric to measure the model mismatch. A new modal alignment algorithm is developed which utilizes the defined metric for aligning all the local models over the entire gridded parameter space. Furthermore, an Adaptive Grid Step Size Determination algorithm is developed to minimize the number of local models required to represent the gridded parameter space. For model reduction, we propose to utilize the concept of Composite Modal Cost Analysis, through which the collective contribution of each flexible mode is computed and ranked. Therefore, a reduced-order model is constructed by retaining only those modes with significant contribution. The NASA Generic Transport Model operating at various flight speeds is studied for verification purpose, and the analysis and simulation results demonstrate the effectiveness of the proposed modeling approach.

LPV Modeling↗
NASA NTRS1992

Optimization by nonhierarchical asynchronous decomposition

Large scale optimization problems are tractable only if they are somehow decomposed. Hierarchical decompositions are inappropriate for some types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategy for nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two dimensional quadratic programs. The algorithm is carefully analyzed for quadratic programs, and a number of modifications are suggested to improve its robustness.

Shankar, Jayashree↗
NASA NTRS2010

Guidance and Control System for a Satellite Constellation

A distributed guidance and control algorithm was developed for a constellation of satellites. The system repositions satellites as required, regulates satellites to desired orbits, and prevents collisions. 1. Optimal methods are used to compute nominal transfers from orbit to orbit. 2. Satellites are regulated to maintain the desired orbits once the transfers are complete. 3. A simulator is used to predict potential collisions or near-misses. 4. Each satellite computes perturbations to its controls so as to increase any unacceptable distances of nearest approach to other objects. a. The avoidance problem is recast in a distributed and locally-linear form to arrive at a tractable solution. b. Plant matrix values are approximated via simulation at each time step. c. The Linear Quadratic Gaussian (LQG) method is used to compute perturbations to the controls that will result in increased miss distances. 5. Once all danger is passed, the satellites return to their original orbits, all the while avoiding each other as above. 6. The delta-Vs are reasonable. The controller begins maneuvers as soon as practical to minimize delta-V. 7. Despite the inclusion of trajectory simulations within the control loop, the algorithm is sufficiently fast for available satellite computer hardware. 8. The required measurement accuracies are within the capabilities of modern inertial measurement devices and modern positioning devices.

Bryson, Jonathan Lamar↗
NASA NTRS2007

Automated Target Planning for FUSE Using the SOVA Algorithm

The SOVA algorithm was originally developed under the Resilient Systems and Operations Project of the Engineering for Complex Systems Program from NASA s Aerospace Technology Enterprise as a conceptual framework to support real-time autonomous system mission and contingency management. The algorithm and its software implementation were formulated for generic application to autonomous flight vehicle systems, and its efficacy was demonstrated by simulation within the problem domain of Unmanned Aerial Vehicle autonomous flight management. The approach itself is based upon the precept that autonomous decision making for a very complex system can be made tractable by distillation of the system state to a manageable set of strategic objectives (e.g. maintain power margin, maintain mission timeline, and et cetera), which if attended to, will result in a favorable outcome. From any given starting point, the attainability of the end-states resulting from a set of candidate decisions is assessed by propagating a system model forward in time while qualitatively mapping simulated states into margins on strategic objectives using fuzzy inference systems. The expected return value of each candidate decision is evaluated as the product of the assigned value of the end-state with the assessed attainability of the end-state. The candidate decision yielding the highest expected return value is selected for implementation; thus, the approach provides a software framework for intelligent autonomous risk management. The name adopted for the technique incorporates its essential elements: Strategic Objective Valuation and Attainability (SOVA). Maximum value of the approach is realized for systems where human intervention is unavailable in the timeframe within which critical control decisions must be made. The Far Ultraviolet Spectroscopic Explorer (FUSE) satellite, launched in 1999, has been collecting science data for eight years.[1] At its beginning of life, FUSE had six gyros in two IRUs and four reaction wheels. Over time through various failures, the satellite has been left with one reaction wheel on the vehicle skew axis and two gyros. To remain operational, a control scheme has been implemented using the magnetic torque rods and the remaining momentum wheel.[2] As a consequence, there are attitude regions where there is insufficient torque authority to overcome environmental disturbances (e.g. gravity gradient torques). The situation is further complicated by the fact that these attitude regions shift inertially with time as the spacecraft moves through earth s magnetic field during the course of its orbit. Under these conditions, the burden of planning targets and target-to-target slew maneuvers has increased significantly since the beginning of the mission.[3] Individual targets must be selected so that the magnetic field remains roughly aligned with the skew wheel axis to provide enough control authority to the other two orthogonal axes. If the field moves too far away from the skew axis, the lack of control authority allows environmental torques to pull the satellite away from the target and can potentially cause it to tumble. Slew maneuver planning must factor the stability of targets at the beginning and end, and the torque authority at all points along the slew. Due to the time varying magnetic field geometry relative to any two inertial targets, small modifications in slew maneuver timing can make large differences in the achievability of a maneuver.

Heatwole, Scott↗