Approximating properties of linear models for input output descriptions
Pade approximations for linear and dynamic programming using Markov processes and new algorithms
Holzmann, E. G.↗
SEARCH · Search NASA
Results for “dynamic programming 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.
A summary report on system effectiveness and optimization study
Report treats optimization and effectiveness separately. Report illustrates example of dynamic programming solution to system optimization. Computer algorithm has been developed to solve effectiveness problem and is included in report.
Williamson, O. L.↗
Solution of transient optimization problems by using an algorithm based on nonlinear programming
A new algorithm is presented for solution of dynamic optimization problems which are nonlinear in the state variables and linear in the control variables. It is shown that the optimal control is bang-bang. A nominal bang-bang solution is found which satisfies the system equations and constraints, and influence functions are generated which check the optimality of the solution. Nonlinear optimization (gradient search) techniques are used to find the optimal solution. The algorithm is used to find a minimum time acceleration for a turbofan engine.
Teren, F.↗
Parallel processors and nonlinear structural dynamics algorithms and software
A nonlinear structural dynamics finite element program was developed to run on a shared memory multiprocessor with pipeline processors. The program, WHAMS, was used as a framework for this work. The program employs explicit time integration and has the capability to handle both the nonlinear material behavior and large displacement response of 3-D structures. The elasto-plastic material model uses an isotropic strain hardening law which is input as a piecewise linear function. Geometric nonlinearities are handled by a corotational formulation in which a coordinate system is embedded at the integration point of each element. Currently, the program has an element library consisting of a beam element based on Euler-Bernoulli theory and trianglar and quadrilateral plate element based on Mindlin theory.
Belytschko, Ted↗
Computational Workbench for Multibody Dynamics
PyCraft is a computer program that provides an interactive, workbenchlike computing environment for developing and testing algorithms for multibody dynamics. Examples of multibody dynamic systems amenable to analysis with the help of PyCraft include land vehicles, spacecraft, robots, and molecular models. PyCraft is based on the Spatial-Operator- Algebra (SOA) formulation for multibody dynamics. The SOA operators enable construction of simple and compact representations of complex multibody dynamical equations. Within the Py-Craft computational workbench, users can, essentially, use the high-level SOA operator notation to represent the variety of dynamical quantities and algorithms and to perform computations interactively. PyCraft provides a Python-language interface to underlying C++ code. Working with SOA concepts, a user can create and manipulate Python-level operator classes in order to implement and evaluate new dynamical quantities and algorithms. During use of PyCraft, virtually all SOA-based algorithms are available for computational experiments.
Edmonds, Karina↗
Hybrid Differential Dynamic Programming with Stochastic Search
Differential dynamic programming (DDP) has been demonstrated as a viable approach to low-thrust trajectory optimization, namely with the recent success of NASA's Dawn mission. The Dawn trajectory was designed with the DDP-based Static/Dynamic Optimal Control algorithm used in the Mystic software.1 Another recently developed method, Hybrid Differential Dynamic Programming (HDDP),2, 3 is a variant of the standard DDP formulation that leverages both first-order and second-order state transition matrices in addition to nonlinear programming (NLP) techniques. Areas of improvement over standard DDP include constraint handling, convergence properties, continuous dynamics, and multi-phase capability. DDP is a gradient based method and will converge to a solution nearby an initial guess. In this study, monotonic basin hopping (MBH) is employed as a stochastic search method to overcome this limitation, by augmenting the HDDP algorithm for a wider search of the solution space.
Aziz, Jonathan↗
Combined Bernstein Polynomial, Optimal Reciprocal Collision Avoidance, Differential Dynamic Programming for Trajectory Replanning and Collision Avoidance for UAM Vehicles
This paper presents an integration of Differential Dynamic Programming (DDP) with the Optimal Reciprocal Collision Avoidance (ORCA) algorithm as the basis for a new algorithm, titled Combined Bernstein Polynomial Optimal Reciprocal Collision Avoidance DDP (COBRA-DDP), for trajectory replanning and collision avoidance for Urban Air Mobility (UAM) vehicles. State-constrained variants of DDP provide the ability to plan trajectories while avoiding obstacles, but these methods require a large increase in computational time per iteration which hinders the overall speed of the algorithm. ORCA utilizes simplified dynamics to recognize potential collisions along a trajectory and provides an optimal velocity for the avoidance of multiple vehicles. These velocity commands, however, may not result in a dynamically feasible trajectory for DDP to plan around. As such, a Bernstein polynomial curve that considers the general dynamic constraints of the vehicle is generated to approximate a trajectory based on the velocity commands. COBRA-DDP optimizes this suggested trajectory via unconstrained DDP to provide a dynamically feasible trajectory that provides collision avoidance. This new trajectory can be applied to the vehicle or used to warm start the state constrained DDP algorithms to decrease computation time. Its benefits and effectiveness of the algorithm are demonstrated on a UAM Vertical Takeoff and Landing (VTOL) vehicle simulation with highly nonlinear dynamics.
Optimal Reciprocal Collision Avoidance↗
Efficient Parallelization of a Dynamic Unstructured Application on the Tera MTA
The success of parallel computing in solving real-life computationally-intensive problems relies on their efficient mapping and execution on large-scale multiprocessor architectures. Many important applications are both unstructured and dynamic in nature, making their efficient parallel implementation a daunting task. This paper presents the parallelization of a dynamic unstructured mesh adaptation algorithm using three popular programming paradigms on three leading supercomputers. We examine an MPI message-passing implementation on the Cray T3E and the SGI Origin2OOO, a shared-memory implementation using cache coherent nonuniform memory access (CC-NUMA) of the Origin2OOO, and a multi-threaded version on the newly-released Tera Multi-threaded Architecture (MTA). We compare several critical factors of this parallel code development, including runtime, scalability, programmability, and memory overhead. Our overall results demonstrate that multi-threaded systems offer tremendous potential for quickly and efficiently solving some of the most challenging real-life problems on parallel computers.
Oliker, Leonid↗
Trajectory optimization for real-time guidance. I - Time-varying LQR on a parallel processor
A key algorithmic element of a real-time trajectory optimization hardware/software implementation, the quadratic program (QP) solver element, is presented. The purpose of the effort is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter. Many methods of nonlinear programming require the solution of a QP at each iteration. In the trajectory optimization case the QP has a special dynamic programming structure, a LQR-like structure. QP algorithm speed is increased by taking advantage of this special structure and by parallel implementation.
Psiaki, Mark L.↗
Performance of a parallel code for the Euler equations on hypercube computers
The performance of hypercubes were evaluated on a computational fluid dynamics problem and the parallel environment issues were considered that must be addressed, such as algorithm changes, implementation choices, programming effort, and programming environment. The evaluation focuses on a widely used fluid dynamics code, FLO52, which solves the two dimensional steady Euler equations describing flow around the airfoil. The code development experience is described, including interacting with the operating system, utilizing the message-passing communication system, and code modifications necessary to increase parallel efficiency. Results from two hypercube parallel computers (a 16-node iPSC/2, and a 512-node NCUBE/ten) are discussed and compared. In addition, a mathematical model of the execution time was developed as a function of several machine and algorithm parameters. This model accurately predicts the actual run times obtained and is used to explore the performance of the code in interesting but yet physically realizable regions of the parameter space. Based on this model, predictions about future hypercubes are made.
Barszcz, Eric↗
An engineering approach to automatic programming
An exploratory study of the automatic generation and optimization of symbolic programs using DECOM - a prototypical requirement specification model implemented in pure LISP was undertaken. It was concluded, on the basis of this study, that symbolic processing languages such as LISP can support a style of programming based upon formal transformation and dependent upon the expression of constraints in an object-oriented environment. Such languages can represent all aspects of the software generation process (including heuristic algorithms for effecting parallel search) as dynamic processes since data and program are represented in a uniform format.
Rubin, Stuart H.↗
Parallel eigenanalysis of finite element models in a completely connected architecture
A parallel algorithm is presented for the solution of the generalized eigenproblem in linear elastic finite element analysis, (K)(phi) = (M)(phi)(omega), where (K) and (M) are of order N, and (omega) is order of q. The concurrent solution of the eigenproblem is based on the multifrontal/modified subspace method and is achieved in a completely connected parallel architecture in which each processor is allowed to communicate with all other processors. The algorithm was successfully implemented on a tightly coupled multiple-instruction multiple-data parallel processing machine, Cray X-MP. A finite element model is divided into m domains each of which is assumed to process n elements. Each domain is then assigned to a processor or to a logical processor (task) if the number of domains exceeds the number of physical processors. The macrotasking library routines are used in mapping each domain to a user task. Computational speed-up and efficiency are used to determine the effectiveness of the algorithm. The effect of the number of domains, the number of degrees-of-freedom located along the global fronts and the dimension of the subspace on the performance of the algorithm are investigated. A parallel finite element dynamic analysis program, p-feda, is documented and the performance of its subroutines in parallel environment is analyzed.
Akl, F. A.↗
Phi-s correlation and dynamic time warping - Two methods for tracking ice floes in SAR images
The authors present two algorithms for performing shape matching on ice floe boundaries in SAR (synthetic aperture radar) images. These algorithms quickly produce a set of ice motion and rotation vectors that can be used to guide a pixel value correlator. The algorithms match a shape descriptor known as the Phi-s curve. The first algorithm uses normalized correlation to match the Phi-s curves, while the second uses dynamic programming to compute an elastic match that better accommodates ice floe deformation. Some empirical data on the performance of the algorithms on Seasat SAR images are presented.
Mcconnell, Ross↗
Hybrid Differential Dynamic Programming with Stochastic Search
Differential dynamic programming (DDP) has been demonstrated as a viable approach to low-thrust trajectory optimization, namely with the recent success of NASAs Dawn mission. The Dawn trajectory was designed with the DDP-based Static Dynamic Optimal Control algorithm used in the Mystic software. Another recently developed method, Hybrid Differential Dynamic Programming (HDDP) is a variant of the standard DDP formulation that leverages both first-order and second-order state transition matrices in addition to nonlinear programming (NLP) techniques. Areas of improvement over standard DDP include constraint handling, convergence properties, continuous dynamics, and multi-phase capability. DDP is a gradient based method and will converge to a solution nearby an initial guess. In this study, monotonic basin hopping (MBH) is employed as a stochastic search method to overcome this limitation, by augmenting the HDDP algorithm for a wider search of the solution space.
Aziz, Jonathan↗
Study of the dynamics of orbital assemblies including interactions with geometrical appendages
The complete equations for the Unified Flexible Spacecraft Simulation (UFSS) program developed for the NASA/MSFC are presented. This general purpose simulation program is based on an algorithm which utilizes the digital computer to synthesize the dynamic and kinematic equations for a topological tree configuration of N interconnected bodies (the interconnected system of bodies forms no closed loops), the terminal members of which may be flexible. Necessary input quantities to the dynamic subroutine include the mass and inertia properties of each body and the flexible characteristics of each terminal member in addition to the specification, for each body, of those bodies to which it connects. This latter description involves the specification of the number of rotational degrees of freedom at each interconnection along with the associated position vectors defining these connections relative to the mass centers of the bodies involved. These position vectors can be input as time-varying functions if desired, thus affording the capability of studying the effects of time-varying hinge locations. Springs and dampers are assumed to act at each interconnection and structural damping in the flexible terminal members is included in the form of equivalent viscous damping.
Ness, D. J.↗
A simple attitude data filter for three-axis attitude initialization for autonomous ascent of Shuttle-launched spacecraft
A method for accurately initializing spacecraft attitude after release from the Orbiter is described. It is noted that the method is suitable for an autonomous ascent to mission orbit. Test results are given from a FORTRAN simulation of the estimation algorithm using measurement data from a detailed spacecraft dynamics simulation program. The technique here is orbital yaw-gyrocompassing. Attitude is estimated through a Kalman filter, using pitch and roll measurements from an earth sensor, while gyro data provide the system dynamics information. In the tests described, gyro and earth sensor data are generated by an existing control system simulation of earth-search and yaw-gyrocompassing attitude dynamics; they include realistic errors such as delays, random noise and quantization effects. The estimated attitude history is compared with the true attitude history from the simulation program to assess the accuracy and convergence of the filter in the presence of noisy measurements and disturbances, including thruster firings for momentum control. It is noted that since the earth sensor provides direct measurements of pitch and roll, the main criterion of filter performance is yaw accuracy.
Joshi, R. T.↗
Hubble space telescope: Pointing error effects on nonlinear ball joints
The Hubble Space Telescope pointing error produced by optical benches mounted on free ball joints is examined. Spacecraft cable connections are assumed to produce translational and rotational damping and restoring forces which act through the optical bench center of mass. The nonlinear dynamics are modeled and then implemented using an existing computer program for simulating the vehicle dynamics and pointing control system algorithm. Results are presented for the test case which indicate acceptable performance.
Farmer, J. E.↗
A dynamically adaptive multigrid algorithm for the incompressible Navier-Stokes equations: Validation and model problems
An algorithm is described for the solution of the laminar, incompressible Navier-Stokes equations. The basic algorithm is a multigrid based on a robust, box-based smoothing step. Its most important feature is the incorporation of automatic, dynamic mesh refinement. This algorithm supports generalized simple domains. The program is based on a standard staggered-grid formulation of the Navier-Stokes equations for robustness and efficiency. Special grid transfer operators were introduced at grid interfaces in the multigrid algorithm to ensure discrete mass conservation. Results are presented for three models: the driven-cavity, a backward-facing step, and a sudden expansion/contraction.
Thompson, C. P.↗