Search NASA⌕ Search

SEARCH · Search NASA

Results for “problem solving complexity”

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 559 records · Page 31

Human controller modeling in environments that include non-control tasks

In complex environments where the human operator is a supervisor, he must allocate his attention between different kinds of tasks for optimum overall performance. When a portion of the future reference trajectory for the control task is available for preview, scheduling various activities is possible. A model has been developed for this situation using dynamic programming to solve an optimal control problem. An experiment was conducted where subjects controlled an airplane symbol over a map, shown a fixed distance into the future. Discrete, non-control tasks were introduced as number entry tasks. Results from the model are compared with experimental results.

Govindaraj, T.↗

A model of asynchronous iterative algorithms for solving large, sparse, linear systems

Solving large, sparse, linear systems of equations is one of the fundamental problems in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. This model is then analyzed to determine the expected intertask data transfer and task computational complexity as functions of the number of tasks. Based on the analysis, recommendations for task partitioning are made. These recommendations are a function of the sparseness of the linear system, its structure (i.e., randomly sparse or banded), and dimension.

Reed, D. A.↗

Comments on the "Byzantine Self-Stabilizing Pulse Synchronization" Protocol: Counter-examples

Embedded distributed systems have become an integral part of many safety-critical applications. There have been many attempts to solve the self-stabilization problem of clocks across a distributed system. An analysis of one such protocol called the Byzantine Self-Stabilizing Pulse Synchronization (BSS-Pulse-Synch) protocol from a paper entitled "Linear Time Byzantine Self-Stabilizing Clock Synchronization" by Daliot, et al., is presented in this report. This report also includes a discussion of the complexity and pitfalls of designing self-stabilizing protocols and provides counter-examples for the claims of the above protocol.

Malekpour, Mahyar R.↗

Animated computer graphics models of space and earth sciences data generated via the massively parallel processor

The capability was developed of rapidly producing visual representations of large, complex, multi-dimensional space and earth sciences data sets via the implementation of computer graphics modeling techniques on the Massively Parallel Processor (MPP) by employing techniques recently developed for typically non-scientific applications. Such capabilities can provide a new and valuable tool for the understanding of complex scientific data, and a new application of parallel computing via the MPP. A prototype system with such capabilities was developed and integrated into the National Space Science Data Center's (NSSDC) Pilot Climate Data System (PCDS) data-independent environment for computer graphics data display to provide easy access to users. While developing these capabilities, several problems had to be solved independently of the actual use of the MPP, all of which are outlined.

Treinish, Lloyd A.↗

A direct algorithm for solution of incompressible three-dimensional unsteady Navier-Stokes equations

A direct, implicit, numerical solution algorithm, with second-order accuracy in space and time, is constructed for the three-dimensional unsteady incompressible Navier-Stokes equations formulated in terms of velocity and vorticity, using generalized orthogonal coordinates to achieve the accurate solution of complex viscous flow configurations. A numerically stable, efficient, direct inversion procedure is developed for the computationally intensive divergence-curl elliptic velocity problem. This overdetermined partial differential operator is first formulated as a uniquely determined, nonsingular matrix-vector problem; this aspect of the procedure is a unique feature of the present analysis. The three-dimensional vorticity-transport equation is solved by a modified factorization technique which completely eliminates the need for any block-matrix inversions and only scalar tridiagonal matrices need to be inverted. The method is applied to the test problem of the three-dimensional flow within a shear-driven cubical box. Coherent streamwise vortex structures are observed within the steady-state flow at Re = 100.

Osswald, G. A.↗

Plants and men in space - A new field in plant physiology

Results are presented on a comparison of nutritional values of and human psychological responses to algae and of higher plants considered for growth as food on long-term missions in space, together with the technological complexities of growing these plants. The comparison shows the advantages of higher plants, with results suggesting that a high level of material recycling can be obtained. It is noted that the issue of space gravity may be not a major problem for plants because of the possibility that phototropism can provide an alternative sense of direction. Problems of waste recycling can be solved in association with plant cultivation, and a high degree of autonomy of food production can be obtained.

Andre, M.↗

A multilayer perceptron solution to the match phase problem in rule-based artificial intelligence systems

In rule-based AI planning, expert, and learning systems, it is often the case that the left-hand-sides of the rules must be repeatedly compared to the contents of some 'working memory'. The traditional approach to solve such a 'match phase problem' for production systems is to use the Rete Match Algorithm. Here, a new technique using a multilayer perceptron, a particular artificial neural network model, is presented to solve the match phase problem for rule-based AI systems. A syntax for premise formulas (i.e., the left-hand-sides of the rules) is defined, and working memory is specified. From this, it is shown how to construct a multilayer perceptron that finds all of the rules which can be executed for the current situation in working memory. The complexity of the constructed multilayer perceptron is derived in terms of the maximum number of nodes and the required number of layers. A method for reducing the number of layers to at most three is also presented.

Sartori, Michael A.↗

Complex generalized minimal residual algorithm for iterative solution of quantum-mechanical reactive scattering equations

Complex dense matrices corresponding to the D + H2 and O + HD reactions were solved using a complex generalized minimal residual (GMRes) algorithm described by Saad and Schultz (1986) and Saad (1990). To provide a test case with a different structure, the H + H2 system was also considered. It is shown that the computational effort for solutions with the GMRes algorithm depends on the dimension of the linear system, the total energy of the scattering problem, and the accuracy criterion. In several cases with dimensions in the range 1110-5632, the GMRes algorithm outperformed the LAPACK direct solver, with speedups for the linear equation solution as large as a factor of 23.

Chatfield, David C.↗

Newton modified barrier method in constrained optimization

In this paper, we develop and investigate the Newton method for solving constrained (non-smooth) optimization problems. This approach is based on the modified barrier functions (MBF) theory and on the global converging step-size version of the Newton method for smooth unconstrained optimization. Due to the excellent properties of the MBF near primal-dual solution, the Newton modified barrier method (NMBM) has a better rate of convergence, better complexity bound, and is much more stable in the final stage of the computational process than the methods which are based on the classical barrier functions (CBF).

Polyak, R.↗

Algorithms for Performance, Dependability, and Performability Evaluation using Stochastic Activity Networks

Modeling tools and technologies are important for aerospace development. At the University of Illinois, we have worked on advancing the state of the art in modeling by Markov reward models in two important areas: reducing the memory necessary to numerically solve systems represented as stochastic activity networks and other stochastic Petri net extensions while still obtaining solutions in a reasonable amount of time, and finding numerically stable and memory-efficient methods to solve for the reward accumulated during a finite mission time. A long standing problem when modeling with high level formalisms such as stochastic activity networks is the so-called state space explosion, where the number of states increases exponentially with size of the high level model. Thus, the corresponding Markov model becomes prohibitively large and solution is constrained by the the size of primary memory. To reduce the memory necessary to numerically solve complex systems, we propose new methods that can tolerate such large state spaces that do not require any special structure in the model (as many other techniques do). First, we develop methods that generate row and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix, permitting us to cache portions of the matrix and hence reduce the solution time. Finally, we develop a new memory and computationally efficient technique for Gauss-Seidel based solvers that avoids the need for generating rows of A in order to solve Ax = b. This is a significant performance improvement for on-the-fly methods as well as other recent solution techniques based on Kronecker operators. Taken together, these new results show that one can solve very large models without any special structure.

Deavours, Daniel D.↗

Lead-Lag Control for Helicopter Vibration and Noise Reduction

As a helicopter transitions from hover to forward flight, the main rotor blades experience an asymmetry in flow field around the azimuth, with the blade section tangential velocities increasing on the advancing side and decreasing on the retreating side. To compensate for the reduced dynamic pressure on the retreating side, the blade pitch angles over this part of the rotor disk are increased. Eventually, a high enough forward speed is attained to produce compressibility effects on the advancing side of the rotor disk and stall on the retreating side. The onset of these two phenomena drastically increases the rotor vibratory loads and power requirements, thereby effectively establishing a limit on the maximum achievable forward speed. The alleviation of compressibility and stall (and the associated decrease in vibratory loads and power) would potentially result in an increased maximum forward speed. In the past, several methods have been examined and implemented to reduce the vibratory hub loads. Some of these methods are aimed specifically at alleviating vibration at very high flight speeds and increasing the maximum flight speed, while others focus on vibration reduction within the conventional flight envelope. Among the later are several types passive as well as active schemes. Passive schemes include a variety of vibration absorbers such as mechanical springs, pendulums, and bifilar absorbers. These mechanism are easy to design and maintain, but incur significant weight and drag penalties. Among the popular active control schemes in consideration are Higher Harmonic Control (HHC) and Individual Blade Control (IBC). HHC uses a conventional swash plate to generate a multi-cyclic pitch input to the blade. This requires actuators capable of sufficiently high power and bandwidth, increasing the cost and weight of the aircraft. IBC places actuators in the rotating reference frame, requiring the use of slip rings capable of transferring enough power to the actuators. Both schemes cause an increase in pitch link loads. Trailing Edge Flap (TEF) deployment can also used to generate unsteady aerodynamic forces and moments that counter the original vibratory loads, and thereby reduce rotor vibrations. While the vibrations absorbers, HHC, IBC, and TEF concepts discussed above attempt to reduce the vibratory loads, they do not specifically address the phenomena causing the vibrations at high advance ratios. One passive method that attempts to directly alleviate compressibility and stall, instead of reducing the ensuing vibrations, is the use of advanced tip designs. Taper, sweep, anhedral, and the manipulation of other geometric properties of the blade tips can reduce the severity of stall and compressibility effects , as well as reduce rotor power. A completely different approach to solve these problems is the tiltrotor configuration. As the forward velocity of the aircraft increases, the rotors, in this case, are tilted forward until they are perpendicular to the flow and act as propellers. This eliminates the edgewise flow encountered by conventional rotors and circumvents all the problems associated with flow asymmetry. However, the success involves a tremendous increase in cost and complexity of the aircraft. Another possible approach that has been proposed for the alleviation of vibratory loads at high forward flight speeds involves the use of controlled lead-lag motions to reduce the asymmetry in flow. A correctly phased 1/rev controlled lag motion could be introduced such that it produces a backward velocity on the advancing side and a forward velocity on the retreating side, to delay compressibility effects and stall to a higher advance ratio. Using a large enough lead-lag amplitude, the tip velocities could be reduced to levels encountered in hover. This concept was examined by two groups in the 1950's and early 1960's. In the United States, the Research Labs Division of United Aircraft developed a large lead-lag motion rotor, meant to achieve lag motion amplitudes up to 45 degrees. In order to reduce the required actuation force, the blade hinges were moved to 40% of the blade radius to increase the rotating lag frequency to approximately 1/rev. The blade hinges were redesigned to produce a flap-lag coupling so the large flapwise aerodynamic loads could be exploited to actuate the blades in the lag direction. A wind tunnel test of this rotor concept revealed actuation and blade motion scheduling problems. The project was eventually discontinued due to these problems and high blade stresses. Around the same time, at Boelkow in Germany, a similar lead-lag rotor program was conducted under the leadership of Hans Derschmidt. Here, too, the blade hinges were moved outboard to 34% radius to reduce the actuation loads. The main difference between this and the United Aircraft program was the use of a mechanical actuation scheme with maximum lead-lag motions of 400. This program was also discontinued for unclear reasons. The present study is directed toward conducting a comprehensive analytical examination to evaluate the effectiveness of controlled lead-lag motions in reducing vibratory hub loads and increasing maximum flight speed. Since both previous studies on this subject were purely experimental, only a limited data set and physical understanding of the problem was obtained. With the currently available analytical models and computational resources, the present effort is geared toward developing an in-depth physical understanding of the precise underlying mechanisms by which vibration reduction may be achieved. Additionally, in recognition of the fact that large amplitude lead-lag motions would - (i) be difficult to implement, and (ii) produce very large blade stresses; the present study examines the potential of only moderate-to-small lead-lag motions for reduction of vibratory hub loads. Using such an approach, the emphasis is not on eliminating the periodic variations in tangential velocity at the blade tip, but at best reducing these variations slightly so that compressibility and stall are delayed to slightly higher advance ratios. This study was conducted in two steps. In the first step, a hingeless helicopter rotor was modeled using rigid blades undergoing flap-lag-torsion rotations about spring restrained hinges and bearings. This model was then modified by separating the lead-lag degree of freedom into two components, a free and a prescribed motion. Using this model, a parametric study of the effect of phase and amplitude of a prescribed lead-lag motion on hub vibration was conducted. The data gathered was analyzed to obtain an understanding of the basic physics of the problem and show the capability of this method to reduce vibration and expand the flight envelope. In the second half of the study, the similar analysis was conducted using an elastic blade model to confirm the effects predicted by the simpler model.

Gandhi, Farhan↗

Optimal Planning and Problem-Solving

CTAEMS MDP Optimal Planner is a problem-solving software designed to command a single spacecraft/rover, or a team of spacecraft/rovers, to perform the best action possible at all times according to an abstract model of the spacecraft/rover and its environment. It also may be useful in solving logistical problems encountered in commercial applications such as shipping and manufacturing. The planner reasons around uncertainty according to specified probabilities of outcomes using a plan hierarchy to avoid exploring certain kinds of suboptimal actions. Also, planned actions are calculated as the state-action space is expanded, rather than afterward, to reduce by an order of magnitude the processing time and memory used. The software solves planning problems with actions that can execute concurrently, that have uncertain duration and quality, and that have functional dependencies on others that affect quality. These problems are modeled in a hierarchical planning language called C_TAEMS, a derivative of the TAEMS language for specifying domains for the DARPA Coordinators program. In realistic environments, actions often have uncertain outcomes and can have complex relationships with other tasks. The planner approaches problems by considering all possible actions that may be taken from any state reachable from a given, initial state, and from within the constraints of a given task hierarchy that specifies what tasks may be performed by which team member.

Clemet, Bradley↗

Observation Scheduling System

Software has been designed to schedule remote sensing with the Earth Observing One spacecraft. The software attempts to satisfy as many observation requests as possible considering each against spacecraft operation constraints such as data volume, thermal, pointing maneuvers, and others. More complex constraints such as temperature are approximated to enable efficient reasoning while keeping the spacecraft within safe limits. Other constraints are checked using an external software library. For example, an attitude control library is used to determine the feasibility of maneuvering between pairs of observations. This innovation can deal with a wide range of spacecraft constraints and solve large scale scheduling problems like hundreds of observations and thousands of combinations of observation sequences.

Chien, Steve A.↗

NASA Goddard Giovanni Support for YOTC

The fundamental challenges to overcoming our shortcomings in understanding and modeling/predicting tropical convection have been twofold: I) the need to represent the broad range of scales applicable to the tropical organization problem (i.e. cumulus to planetary), and II) the lack of observations that adequately and simultaneously characterize this broad range of scales and that also provide three-dimensional information on thermodynamic, radiative and dynamical interactions, including cloud microphysical processes. In regards to the second challenge, it should be stressed that this problem will not be solved through the production and examination of one or a few high quality long-term records of fundamental quantities (e.g., SST, water vapor, cloud fraction). Rather, an alternative and more comprehensive paradigm is needed, one that integrates the multitude of applicable resources and measures of tropical convection in a manner that that can be better utilized by the diagnostic, modeling and forecasting communities to more completely and coherently focus on the problem.Because the goal of YOTC involves examining a scientifically complex, multi-scale process , rather than documenting the characteristics of a single parameter (e.g., SST, cloud cover), YOTC has an IOP perspective that targets a period, May 2008 April 2010, long enough to encompass many cases of tropical convection activity in many of its most challenging yet influential forms. This includes mesoscale and synoptic variability, easterly waves and hurricanes, convectively coupled waves, the MJO and the culmination of these in terms of the monsoon, their interactions with the extra-tropics, and mean characteristics such as tropical-to-subtropical transitions. The YOTC time period and length are driven in part by the following: 1) keeping the multi-sensor/multi-platform and model-analyses data sets and associated infrastructure manageable, 2) facilitating a focused effort by the research and operational communities on a specific scientific problem, and 3) capitalizing on the recent key additions to the armada of satellites (e.g., CloudSat and CALIPSO). The proposed dissemination framework for the YOTC satellite data archive is based on the Giovanni system. Giovanni is a web-based application developed by the NASA Goddard Earth Science (GES) Data and Information Service Center (DISC) that provides a simple and intuitive way to visualize, analyze, and access/download vast amounts of Earth science remote sensing data. A prototype YOTC Giovanni System (hereafter YOTC-GS) is in the process of being developed. YOTC-GS will provide access to level 2 (i.e. swath level data) and/or level 3 (i.e. gridded/mapped data) forms of satellite data, the choice or both depending on what is appropriate and relevant. The former is needed and better suited for detailed process examination, exploiting the highest temporal-spatial resolutions available and comparison to regional cloud-system resolving model / cloud resolving model (CSRM/CRM) model output. The latter is needed and more well suited for examination of phenomena, conditions and processes on large to global scales, and for comparisons to global model analyses, prediction and simulation output.

Ostrenga, Dana↗

Rapid Design of Gravity Assist Trajectories

Several International Solar Terrestrial Physics (ISTP) missions require the design of complex gravity assisted trajectories in order to investigate the interaction of the solar wind with the Earth's magnetic field. These trajectories present a formidable trajectory design and optimization problem. The philosophy and methodology that enable an analyst to design and analyse such trajectories are discussed. The so called 'floating end point' targeting, which allows the inherently nonlinear multiple body problem to be solved with simple linear techniques, is described. The combination of floating end point targeting with analytic approximations with a Newton method targeter to achieve trajectory design goals quickly, even for the very sensitive double lunar swingby trajectories used by the ISTP missions, is demonstrated. A multiconic orbit integration scheme allows fast and accurate orbit propagation. A prototype software tool, Swingby, built for trajectory design and launch window analysis, is described.

Carrico, J.↗

Golden Ratio Versus Pi as Random Sequence Sources for Monte Carlo Integration

We discuss here the relative merits of these numbers as possible random sequence sources. The quality of these sequences is not judged directly based on the outcome of all known tests for the randomness of a sequence. Instead, it is determined implicitly by the accuracy of the Monte Carlo integration in a statistical sense. Since our main motive of using a random sequence is to solve real world problems, it is more desirable if we compare the quality of the sequences based on their performances for these problems in terms of quality/accuracy of the output. We also compare these sources against those generated by a popular pseudo-random generator, viz., the Matlab rand and the quasi-random generator ha/ton both in terms of error and time complexity. Our study demonstrates that consecutive blocks of digits of each of these numbers produce a good random sequence source. It is observed that randomly chosen blocks of digits do not have any remarkable advantage over consecutive blocks for the accuracy of the Monte Carlo integration. Also, it reveals that pi is a better source of a random sequence than theta when the accuracy of the integration is concerned.

Sen, S. K.↗

Modeling the human controller in environments that include continuous and discrete tasks

In complex environments where the human operator is a supervisor, he must allocate his attention between different kinds of tasks for satisfactory overall performance. When a portion of the future reference trajectory for a continuous control task is available for preview, scheduling various other discrete activities is possible. A model has been developed for this situation using dynamic programming to solve an optimal control problem. An experiment was conducted where subjects controlled an airplane symbol over a map, shown a fixed distance into the future. Discrete tasks were introduced as data entry tasks. Results showed that the model compared favorably with experimental results.

Govindaraj, T.↗

A solution of Mx(double dot) + Cx(dot) + Kx = 0 applicable to the design of active dampers

A solution is presented for the equations of motion for the damped linear oscillator, Mx(double dot) + Cx(dot) + Kx = 0. The algorithm solves a transformed set of equations in terms of the modal variables of the undamped system and, at the same time, solves the adjoint equation of the transformed problem. The adjoint solution is normalized to give the inverse of the solution matrix of the transformed problem. The normalized inverse is useful in design for direct computation of sensitivity derivatives of damping ratios with respect to damping rates. The algorithm is programmed to reduce storage requirements by a factor of three-fourths compared to standard complex eigenvalue subroutines. A numerical example is included.

Thurston, G. A.↗