SEARCH · Engineering Papers

Results for “complex systems theory”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

501 records · Page 28

All sources NASA NTRS DOE OSTI

NASA NTRS2003

Subgrid Scale Modeling in Solar Convection Simulations using the ASH Code

The turbulent solar convection zone has remained one of the most challenging and important subjects in physics. Understanding the complex dynamics in the solar con- vection zone is crucial for gaining insight into the solar dynamo problem. Many solar observatories have generated revealing data with great details of large scale motions in the solar convection zone. For example, a strong di erential rotation is observed: the angular rotation is observed to be faster at the equator than near the poles not only near the solar surface, but also deep in the convection zone. On the other hand, due to the wide range of dynamical scales of turbulence in the solar convection zone, both theory and simulation have limited success. Thus, cutting edge solar models and numerical simulations of the solar convection zone have focused more narrowly on a few key features of the solar convection zone, such as the time-averaged di erential rotation. For example, Brun & Toomre (2002) report computational finding of differential rotation in an anelastic model for solar convection. A critical shortcoming in this model is that the viscous dissipation is based on application of mixing length theory to stellar dynamics with some ad hoc parameter tuning. The goal of our work is to implement the subgrid scale model developed at CTR into the solar simulation code and examine how the differential rotation will be a affected as a result. Specifically, we implement a Smagorinsky-Lilly subgrid scale model into the ASH (anelastic spherical harmonic) code developed over the years by various authors. This paper is organized as follows. In x2 we briefly formulate the anelastic system that describes the solar convection. In x3 we formulate the Smagorinsky-Lilly subgrid scale model for unstably stratifed convection. We then present some preliminary results in x4, where we also provide some conclusions and future directions.

Young, Y.-N.↗

NASA NTRS1999

Sonic Boom Prediction and Minimization of the Douglas Reference OPT5 Configuration

Conventional CFD methods and grids do not yield adequate resolution of the complex shock flow pattern generated by a real aircraft geometry. As a result, a unique grid topology and supersonic flow solver was developed at Northrop Grumman based on the characteristic behavior of supersonic wave patterns emanating from the aircraft. Using this approach, it was possible to compute flow fields with adequate resolution several body lengths below the aircraft. In this region, three-dimensional effects are diminished and conventional two-dimensional modified linear theory (MLT) can be applied to estimate ground pressure signatures or sonic booms. To accommodate real aircraft geometries and alleviate the burdensome grid generation task, an implicit marching multi-block, multi-grid finite-volume Euler code was developed as the basis for the sonic boom prediction methodology. The Thomas two-dimensional extrapolation method is built into the Euler code so that ground signatures can be obtained quickly and efficiently with minimum computational effort suitable to the aircraft design environment. The loudness levels of these signatures can then be determined using a NASA generated noise code. Since the Euler code is a three-dimensional flow field solver, the complete circumferential region below the aircraft is computed. The extrapolation of all this field data from a cylinder of constant radius leads to the definition of the entire boom corridor occurring directly below and off to the side of the aircraft's flight path yielding an estimate for the entire noise "annoyance" corridor in miles as well as its magnitude. An automated multidisciplinary sonic boom design optimization software system was developed during the latter part of HSR Phase 1. Using this system, it was found that sonic boom signatures could be reduced through optimization of a variety of geometric aircraft parameters. This system uses a gradient based nonlinear optimizer as the driver in conjunction with a computationally efficient Euler CFD solver (NIIM3DSB) for computing the three-dimensional near-field characteristics of the aircraft. The intent of the design system is to identify and optimize geometric design variables that have a beneficial impact on the ground sonic boom. The system uses a simple wave drag data format to specify the aircraft geometry. The geometry is internally enhanced and analytic methods are used to generate marching grids suitable for the multi-block Euler solver. The Thomas extrapolation method is integrated into this system, and hence, the aircraft's centerline ground sonic boom signature is also automatically computed for a specified cruise altitude and yields the parameters necessary to evaluate the design function. The entire design system has been automated since the gradient based optimization software requires many flow analyses in order to obtain the required sensitivity derivatives for each design variable in order to converge on an optimal solution. Hence, once the problem is defined which includes defining the objective function and geometric and aerodynamic constraints, the system will automatically regenerate the perturbed geometry, the necessary grids, the Euler solution, and finally the ground sonic boom signature at the request of the optimizer.

Siclari, Michael J.↗

NASA NTRS1997

Reduced Navier Stokes Relaxation Procedures for Internal Flows

In spite of significant advancement in the field of high speed computing, flow calculations involving complex geometries and/or flow behavior still require large amounts of CPU time and memory. In order to predict such flows without sacrificing grid convergence and accuracy, adaptive gridding techniques that provide optimal resolution are highly desirable. The present work combines multigrid techniques and domain decomposition concepts to provide local, solution adaptive, grid refinement. Several viscous compressible and incompressible, two and three-dimensional, flows with strong inviscid interaction and/or axial flow reversal, are considered with a segmented multigrid domain decomposition (SMGDD) procedure for which uniform meshes result in each domain. A pressure-based form of flux-vector splitting is applied to the Navier-Stokes equations, which are represented by an implicit lowest-order reduced Navier-Stokes (RNS) system and a purely diffusive, higher-order, deferred-corrector. A trapezoidal or box-like form of discretization insures that all mass conservation properties are satisfied at interfacial and outflow boundaries, even for this primitive-variable non-staggered grid computation. The SMGDD technique presented herein has previously been applied for incompressible two dimensional flows. The present work offers improvement in the gridding strategy, by allowing for disjoint subdomains that provide optimal resolution of disparate flow features. It also extends the SMGDD technique to three dimensional compressible flows. Laminar and turbulent flow in a backward facing step channel is considered; although the procedure is applicable to more severe geometries. The standard K-epsilon model is applied for turbulence closure. For Re greater than 400, differences between two-dimensional theory and experiment are resolved through a three dimensional simulation, which confirms the experimentally observed three dimensionality of the recirculation patterns on the upper and lower surfaces.

Rubin, Stanley G.↗

NASA NTRSDate not supplied

Monitoring Airspace Complexity and Determining Contributing Factors

The national airspace has evolved over many years to accommodate increased traffic demand [1] while simultaneously maintaining one of the safest forms of transportation [2], [3]. One of the reasons for this success is the ability of the system and the operators to adapt and accommodate to situations that routinely disrupt optimal operations. These situations may include: adverse weather, delays, early arrivals, equipment outages, and other factors that are outside the operators ability to control. These factors can lead to states where automation is unable to properly handle these issues and therefore air traffic controllers and pilots have to intervene, ultimately increasing communication between operators resulting in higher workload. As controller workload increases to handle sub-optimal operating conditions this can be viewed as an increase in complexity. The reasoning for this is because humans are now required to make tactical decisions in response to external factors, resulting in a departure from the strategic plan where operations would be more efficiently managed. Human operators control airspace complexity under rigid regulations that are constantly changing. The airspace is divided into sectors and the number of aircraft assigned to each controller is limited for safe handling. There has been past work that devised airspace complexity metrics in commercial aviation and related these metrics to controller workload (e.g., [4],[5]). The upper bounds on the system load are pre-determined. Such bounds on complexity make for a safe system, but the system cannot scale and adapt to autonomous, dense, and heterogeneous traffic, including the many types of Unmanned Aerial Vehicles (UAVs) envisioned to be added to the operations. We hypothesize that, as traffic density and heterogeneity grow, and other key metrics change, there will be phase transitions at which the way traffic should be managed changes significantly [6]. We offer a method for in-time detection of contributing factors that lead to phase transitions, characterized by increased complexity. To the best of our knowledge, there is no tool similar to our proposed effort that identifies such contributing factors or precursor patterns. To define the scope we are proposing to measure complexity from the viewpoint of the Terminal Radar Approach Control Facilities (TRACON) controller’s perspective. In particular we are analyzing arrivals into KSFO. With safety as the top concern for airspace operators, it is important to recognize that as density and heterogeneity grow, the focus of the system will change. Times of the day when the airspace has low density and heterogeneity, the flights will follow more efficient paths where the aircraft move on established routes that are more or less directly to the destination. However, when density and heterogeneity increases, the system will begin changing focus to avoiding conflicts and collisions and route the flights in a more flexible way. Higher flexibility requires more communication and coordination between controllers and pilots which the current automation is unable to handle. This paper proposes a novel approach that monitors airspace complexity at multiple scales, uses a Machine Learning-based tool that predicts when operations will transition to a regime of greater complexity, and identifies actions that can reduce the complexity while still maintaining efficient and safe operations. We demonstrate our proposed approach using data from multiple complementary sources. This includes, but is not limited to: historical aircraft surveillance data from NASA’s Sherlock Data Warehouse [7], METAR weather data, and airport configuration data from Aviation System Performance Metrics (ASPM). The surveillance data flight paths are sampled at a variable sample rate — increasing as the aircraft approaches the airport. This is due to how Sherlock manages flight track stitching between different radar facilities which have different sampling rates. The weather and performance data are logged at defined intervals throughout the day at a courser refresh rate. In addition to the logged data and metrics, we leverage pre-defined Standard Terminal Arrival Routes (STARs) procedures to characterize the path of each flight. Each flight files for one of these routes in the flight plan well before entering the terminal airspace, and approximately follows the route until it leaves the STAR, typically on the final fix of a runway transition. However, most flights do not always fly the full STAR procedure to completion [8], but the majority do adhere to the fixes within the common route of the procedure. Our approach leverages fixes in the common route of each of the STARs to build a reference path to the airport. This allows us to characterize the flight paths in what we are defining as the “maneuvering area” (the airspace between the STAR and before the flight is lined up on the runway’s final approach) to determine how off nominal the flights are to calculate its complexity score. Determining airspace complexity is a concept that does not have a concrete answer. In designing this metric, we consider what increases the workload for the air traffic controllers. Consequently more specialized vectoring maneuvers results in higher workload. Accordingly, we start with a theory: each flight has a direct path it takes from the STAR’s common route to the final approach’s outer marker fix for the flight’s landing runway. It is important to note that the direct path is only used as a reference. If the majority of the flights have a large consistent offset as compared to other routes it does not necessarily mean that those flights have higher complexity. We are merely building a distribution based on this direct path for that particular STAR and runway pair to determine the normal mode of operations for that route. Flights that are in the upper tail of these distributions will result in higher complexity scores and flights that fly in the median will represent the normal mode of operations and therefore will have lower complexity scores. Since flights following each STAR route take different paths to the airport, we have a different distribution for each STAR route and therefore can model these distributions to compute a complexity score from their respective normalized distributions. To evaluate the effectiveness of our proposed airspace complexity metric we will compare against an established approach based on trajectory clustering [9]. This unsupervised learning technique consists of the following steps: (1) identify the general maneuvering areas (waypoints) by performing $\kappa$-means or DBSCAN clustering on locations where aircraft frequently turn based on the surveillance radar track data, (2) map flight trajectories onto sequences of waypoints, and (3) cluster the sequences based on their common subsequences. From a high-level perspective, this baseline model learns nominal operations in the airspace through the sequence of waypoints that are representative of where aircraft change direction and defines deviations from the nominal operations as “complex.” Therefore, more deviations from the nominal operations correspond to higher complexity values. For our validation, we re-implemented this technique and tune model hyper-parameters to correctly detect waypoints for the arrival traffic into the San Francisco bay area. We will compute the complexity measure over a one-year period using our proposed technique as well as the baseline. Our validation will be based on each technique’s ability to detect a set of undesirable outcomes (e.g., go-arounds, holding patterns, average time in the airspace, etc.). Since our current complexity metric is derived from the offset from the direct reference path, it’s important to understand what causes these offsets. In many of the flights with high offset distance, flights performing holding patterns and S turns can be observed. These maneuvering tactics are utilized to add distance between the aircraft and the destination runway to prevent multiple flights from having conflicting arrival times. In order to predict a rise in complexity (or the precursor to complexity), it’s necessary to be able to identify these potential conflicts (which in turn, result in higher offsets). To do this, we define a “representative flight” for each STAR route and runway pair. This flight is approximately the path the flight would take if there was a clear path with no other flights in the airspace — including the time remaining to the airport. We first identify the flights for a given STAR runway pair using the offset to the reference path distributions that fall between the 44-55 percentiles. This yields the flights that conform to the most normal mode of operation. Each of these flights is partitioned based on the percent complete from the entry point into the maneuvering areas from 0\% – 100\% complete. Then for each percent “bin”, we take the median value of the flight’s latitude/longitude coordinates, airspeed, and (non causal) time remaining to the airport to construct a lookup table for each percent complete bin on a given route. As a flight enters the maneuvering area, we can find the estimated arrival time of a flight to the airport by finding the closest point to the representative path’s percent complete bin (relative to the flight’s current position at any snapshot in the airspace) and therefore retrieve the corresponding remaining time left on the “representative path”. We assume that the flight will follow the representative path to completion when deriving these estimates. We can then compare these estimated arrival times against other flights for the same snapshot in time to identify potential conflicts. If more flights are estimated to arrive within a tolerance window than there are runways available, then we have a potential conflict. We can use this derived measure along with other factors expected to add disruption to the operation such as weather and runway configuration changes as an input to machine learning tools to detect precursors that increases in our complexity measure. This novel method will assist in uncovering insights into the contributing factors that lead to increased complexity that may allow for in-time responses to avoid reaching a high complexity state in the airspace.

complexity↗

NASA NTRS1962

Empire. a study of early manned interplanetary missions final report, may 26 - nov. 25, 1962

This report summarizes the investigations and results of the EMPIRE Study Program undertaken by Aeronutronic Division of Ford Motor Company for the Future Projects Office, Marshall Space Flight Center, under Contract NAS8-5025. The dual planet flyby missions of the Crocco and Symmetric trajectory classes are discussed. The Crocco mission with an August 1971 launch window requires an interplanetary injection velocity increment of i0.i km/sec, has a return velocity of 13.5 km/sec, and takes approximately 400 days. The Symmetric mission with a July 1970 launch window has an injection velocity increment of 5.3 km/sec, a return velocity of 15.8 km/sec, and takes approximately 630 days. Additional results of the trajectory studies and abort trajectories are reported. The guidance and navigation subsystem, midcourse corrections, and planetary approach corrections are discussed. A detailed analysis of the reentry phase of EMPIRE includes consideration of an Apollo-type, a Drag Brake, and a lifting-type reentry vehicle to return the six-man crew at mission completion or in an aborted condition. The High L/D reentry vehicle is used in the missions considered. The various technological areas required for design criteria are developed and several spacecraft designs are considered. The all chemical propulsion Crocco system is discarded due to weight, complexity, and cost. The nuclear injected Crocco is treated in a similar manner. The lower energy injection for the Symmetric Mission leads to the feasibility of a nuclear injected vehicle with an Earth orbit weight of about 180,000 kilograms (400,000 pounds) before interplanetary transit. In addition, two chemical symmetric vehicles are treated. Conservative radiation exposures are derived, for the 630 day mission, of less than 200 REM and a polyethelene radiation shelter is designed. Scientific aspects of the missions are discussed. Mission Success Probabilities are presented for the various missions considered and for Saturn C-5, Nova, and Super-Nova Earth launch vehicles in light of possible development. The need for acceleration of nuclear rocket engine developments and auxiliary power developments is indicated. Definition of a larger nuclear engine of the order of 200,000 pounds thrust and about 800 seconds burning time or 50,000 pound thrust and 3600 seconds burning time is indicated for the Symmetric Mission in 1970 (energy requirements are higher in 1972 and for later launch due to the less favorable position of Mars)_ Immediate development of this advanced nuclear propulsion capability is recommended. A Development Plan and Funding Schedule is given for the 1970 launch window pinpointing the critical development areas and indicating a total program cost of $12.6 billion independent of other programmed R&D costs. In conclusion, technological feasibility for an early manned dual planet Mars-Venus flyby is believed to be demonstrated in this study. Several areas of accelerated development and experimental confirmation of theory are pinpointed. The necessary funding and development of Nova or orbital operations capability with Saturn C-5's is required. The 1970 launch window appears to offer the least expensive Symmetric Mission for several years into the 1980's.

F. P. Dixon↗

NASA NTRS2021

Transition Analysis for Isolated Trips on BOLT-II Wind-Tunnel and Flight Configuration

The BOLT-II configuration designed for an upcoming flight experiment exemplifies the complexities of hypersonic boundary layer transition in the presence of multiple and potentially interacting instability mechanisms. The present paper is related to the NASA-led roughness experiment on the secondary side of the BOLT-II configuration. First, computations are performed to aid mean-flow based correlations for the transition measurements acquired during an experimental campaign in the Ludwieg Tube facility at the United States Air Force Academy. To that end, both laminar and turbulent flow computations are performed for selected conditions of the experiment with a 1:3 scale model of the slightly shorter BOLT configuration. The variation in well-known correlation parameters for transition due to isolated roughness elements with respect to element position, height, and flow Reynolds number is delineated. Furthermore, the wake instability theory is used to examine the amplification of unstable disturbances behind the centerline trip at the design conditions of the BOLT-II flight experiment and for its dynamically scaled version on the 1:3 scale model of the wind tunnel experiment. To our knowledge, this study represents the first analysis of the wake instabilities in the presence of a prominent entropy layer outside the boundary layer. At the nominal flight design condition of Re ∞ ) = 5.44 and Re ∞ = 2.5 x 10 6 /m, a diamond planform (“pizza-box”) trip with k/δ = 0.70 and planform-halfwidth-to-height ratio of b/k = 3.0 at X/L = 0.254 induces a strong distortion of the boundary-layer flow in the vicinity of the symmetry plane, such that the wake structure includes a centerline streak produced by the flow retardation behind the trip along with multiple additional, prominent vorticity structures representing the necklace vortex system. Stability results reveal that each of these streaks can support a strong amplification of wake instabilities within a frequency band of 95 kHz–255 kHz, with a peak N-factor of greater than 15 beyond X/L ≈ 0.42. The dynamically scaled wind tunnel configuration with Re ∞ = 20.25 x 10 6 /m is also found to support N > 15 at similar axial stations.

BOLT↗

NASA NTRS2021

Transition Analysis for Isolated Trips on BOLT-II Wind-Tunnel and Flight Configuration

BOLT↗

NASA NTRS1992

CELSS system control: issues, methods, and directions

In the general control perspective, the CELSS concept implies a very complex system and presents challenges at every level. These challenges are generated by: (1) the prospect that the system will be inherently unstable, (2) the prospective difficulty of establishing an adequate mathematical model of the system for the purpose of control law synthesis (dimensionality is high, and the dynamics and interactive processes of some of the subsystems are not understood well), (3) assuring control law robustness (assuring that the resulting control law(s) will be effective over the domain of the specified uncertainties), (4) hardware realization of the control law, (5) hardware system robustness ("fault tolerance") and (6) achieving the logistics of the automation (or "management") aspects of the problem. A suggested organization of the problem, a sketch of the issues related to perceived difficulties, a commentary/evaluation of the issues, a review of methods available to address the issues, and a suggested strategy to address the broad CELSS systems control problem are presented.

NASA Center ARC↗

NASA NTRS1990

GRID2D/3D: A computer program for generating grid systems in complex-shaped two- and three-dimensional spatial domains. Part 2: User's manual and program listing

An efficient computer program, called GRID2D/3D, was developed to generate single and composite grid systems within geometrically complex two- and three-dimensional (2- and 3-D) spatial domains that can deform with time. GRID2D/3D generates single grid systems by using algebraic grid generation methods based on transfinite interpolation in which the distribution of grid points within the spatial domain is controlled by stretching functions. All single grid systems generated by GRID2D/3D can have grid lines that are continuous and differentiable everywhere up to the second-order. Also, grid lines can intersect boundaries of the spatial domain orthogonally. GRID2D/3D generates composite grid systems by patching together two or more single grid systems. The patching can be discontinuous or continuous. For continuous composite grid systems, the grid lines are continuous and differentiable everywhere up to the second-order except at interfaces where different single grid systems meet. At interfaces where different single grid systems meet, the grid lines are only differentiable up to the first-order. For 2-D spatial domains, the boundary curves are described by using either cubic or tension spline interpolation. For 3-D spatial domains, the boundary surfaces are described by using either linear Coon's interpolation, bi-hyperbolic spline interpolation, or a new technique referred to as 3-D bi-directional Hermite interpolation. Since grid systems generated by algebraic methods can have grid lines that overlap one another, GRID2D/3D contains a graphics package for evaluating the grid systems generated. With the graphics package, the user can generate grid systems in an interactive manner with the grid generation part of GRID2D/3D. GRID2D/3D is written in FORTRAN 77 and can be run on any IBM PC, XT, or AT compatible computer. In order to use GRID2D/3D on workstations or mainframe computers, some minor modifications must be made in the graphics part of the program; no modifications are needed in the grid generation part of the program. The theory and method used in GRID2D/3D is described.

Bailey, R. T.↗

NASA NTRS1995

The AAMP5/AAMP-FV project

This presentation describes a project, formal verification of the microcode in the AAMP5 microprocessor, conducted to explore how formal techniques for specification and verification could be introduced into an industrial process. Sponsored by the Systems Validation Branch of NASA Langley and by Collins Commercial Avionics, a division of Rockwell International, it was conducted by Collins and the SRI International Computer Science Laboratory. The project consisted of specifying in the PVS language developed by SRI a portion of a Rockwell proprietary microprocessor, the AAMP5, at both the instruction set and register-transfer levels and using the PVS theorem prover to prove the microcode correct for a representative subset of instructions. While this presentation includes a brief technical overview, its emphasis is on the lessons learned in using PVS for an example of this size and the implications for using formal methods in an industrial setting. The central result of this project was to demonstrate the feasibility of formally specifying a commercial microprocessor and the use of mechanical proofs of correctness to verify microcode. This is particularly significant since the AAMP5 was not designed for formal verification, but to provide a more than three fold performance improvement, by pipelining instruction execution, while remaining object code compatible with the earlier AAMP2. As a consequence, the AAMP5 is one of the most complex microprocessors to which formal methods have been applied. Another key result was the discovery of both actual and seeded errors. Two actual microcode errors were discovered and corrected during development of the formal specification, illustrating the value of simply creating a precise specification. Two seeded errors were systematically uncovered while doing correctness proofs. One of these was an actual error that had been discovered after first fabrication but left in the microcode provided to SRI. The other error was designed to be unlikely to be detected by walkthroughs, testing, or simulation. Several other results emerged during the project, including the ease with which practicing engineers became comfortable with PVS, the need for libraries of general purpose theories, the usefulness of formal specification in revealing errors, the natural fit between formal specification and inspections, the difficulty of selecting the best style of specification for a new problem domain, the high level of assurance provided by proofs of correctness, and the need to engineer proof strategies for reuse.

Miller, Steven P.↗

NASA NTRS1994

Infinite possibilities: Computational structures technology

Computational Fluid Dynamics (or CFD) methods are very familiar to the research community. Even the general public has had some exposure to CFD images, primarily through the news media. However, very little attention has been paid to CST--Computational Structures Technology. Yet, no important design can be completed without it. During the first half of this century, researchers only dreamed of designing and building structures on a computer. Today their dreams have become practical realities as computational methods are used in all phases of design, fabrication and testing of engineering systems. Increasingly complex structures can now be built in even shorter periods of time. Over the past four decades, computer technology has been developing, and early finite element methods have grown from small in-house programs to numerous commercial software programs. When coupled with advanced computing systems, they help engineers make dramatic leaps in designing and testing concepts. The goals of CST include: predicting how a structure will behave under actual operating conditions; designing and complementing other experiments conducted on a structure; investigating microstructural damage or chaotic, unpredictable behavior; helping material developers in improving material systems; and being a useful tool in design systems optimization and sensitivity techniques. Applying CST to a structure problem requires five steps: (1) observe the specific problem; (2) develop a computational model for numerical simulation; (3) develop and assemble software and hardware for running the codes; (4) post-process and interpret the results; and (5) use the model to analyze and design the actual structure. Researchers in both industry and academia continue to make significant contributions to advance this technology with improvements in software, collaborative computing environments and supercomputing systems. As these environments and systems evolve, computational structures technology will evolve. By using CST in the design and operation of future structures systems, engineers will have a better understanding of how a system responds and lasts, more cost-effective methods of designing and testing models, and improved productivity. For informational and educational purposes, a videotape is being produced using both static and dynamic images from research institutions, software and hardware companies, private individuals, and historical photographs and drawings. The extensive number of CST resources indicates its widespread use. Applications run the gamut from simpler university-simulated problems to those requiring solutions on supercomputers. In some cases, an image or an animation will be mapped onto the actual structure to show the relevance of the computer model to the structure. Transferring the digital files to videotape presents a number of problems related to maintaining the quality of the original image, while still producing a broadcast quality videotape. Since researchers normally do not create a computer image using traditional composition theories or video production requirements, often the image loses some of its original digital quality and impact when transferred to videotape. Although many CST images are currently available, those that are edited into the final project must meet two important criteria: they must complement the narration, and they must be broadcast quality when recorded on videotape.

Beam, Sherilee F.↗

NASA NTRS2010

Hidden Statistics Approach to Quantum Simulations

Recent advances in quantum information theory have inspired an explosion of interest in new quantum algorithms for solving hard computational (quantum and non-quantum) problems. The basic principle of quantum computation is that the quantum properties can be used to represent structure data, and that quantum mechanisms can be devised and built to perform operations with this data. Three basic non-classical properties of quantum mechanics superposition, entanglement, and direct-product decomposability were main reasons for optimism about capabilities of quantum computers that promised simultaneous processing of large massifs of highly correlated data. Unfortunately, these advantages of quantum mechanics came with a high price. One major problem is keeping the components of the computer in a coherent state, as the slightest interaction with the external world would cause the system to decohere. That is why the hardware implementation of a quantum computer is still unsolved. The basic idea of this work is to create a new kind of dynamical system that would preserve the main three properties of quantum physics superposition, entanglement, and direct-product decomposability while allowing one to measure its state variables using classical methods. In other words, such a system would reinforce the advantages and minimize limitations of both quantum and classical aspects. Based upon a concept of hidden statistics, a new kind of dynamical system for simulation of Schroedinger equation is proposed. The system represents a modified Madelung version of Schroedinger equation. It preserves superposition, entanglement, and direct-product decomposability while allowing one to measure its state variables using classical methods. Such an optimal combination of characteristics is a perfect match for simulating quantum systems. The model includes a transitional component of quantum potential (that has been overlooked in previous treatment of the Madelung equation). The role of the transitional potential is to provide a jump from a deterministic state to a random state with prescribed probability density. This jump is triggered by blowup instability due to violation of Lipschitz condition generated by the quantum potential. As a result, the dynamics attains quantum properties on a classical scale. The model can be implemented physically as an analog VLSI-based (very-large-scale integration-based) computer, or numerically on a digital computer. This work opens a way of developing fundamentally new algorithms for quantum simulations of exponentially complex problems that expand NASA capabilities in conducting space activities. It has been illustrated that the complexity of simulations of particle interaction can be reduced from an exponential one to a polynomial one.

Zak, Michail↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Monte Carlo Tree Search Approach

Numerous unmanned aircraft systems operating at low altitudes to deliver goods and services may one day become ubiquitous in our cities. In the Unmanned Aircraft Systems (UAS) Traffic Management (UTM) framework, such a concept is envisioned, where aerial vehicles operate beyond visual line of sight (BVLOS) within specifically reserved and time stamped “corridors” in the airspace. For example, these corridors or operational intent volumes can connect an aerial vehicle’s origin site to its destination site for package delivery operations. There may also be more than one corridor available for an aerial vehicle to choose from and often different corridors may intersect with one another. Thus, it is imperative to ensure flight trajectories belonging to different aerial vehicles are not in conflict. Per the UTM CONOPs, we assume that a vehicle almost always stays inside its corridor or operational volume. This work provides a framework for strategic deconfliction of UTM or package delivery drones, where we schedule the departure time of all vehicles subject to various temporal constraints (including the corridor deconfliction at the intersections). We present the “multi-route weighted package delivery problem” which serves as an exemplifying model for strategic deconfliction in UTM. In the multi-route weighted package delivery problem, a graph network is given which consists of a set of depots (source) and drop-off (destination) nodes, with multiple routes (defined as a sequence of waypoints) connecting the depots to drop-off nodes. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is for a known set of aerial vehicles to depart from the depots, choose a route and take off time, while avoiding conflicts with other aerial vehicles, and minimizing both risk and distance traveled. We provide a mixed integer linear programming (MILP) formulation of the problem, as well as a heuristic solution based on Monte Carlo Tree Search (MCTS) – a method used in game theory and artificial intelligence – to overcome limitations inherent to optimal solvers. Computational results show the advantages of using MCTS over the MILP formulation; the former can provide a sub-optimal solution quickly, and may sometimes even reach an optimal solution, whereas the latter may not even produce a solution in reasonable time. Furthermore, results from both the MILP formulation and MCTS methods were validated using a preliminary agent-based simulator implementing the UTM concept of operations. Thus, the MCTS method can be seen as a scalable solution to the complex multi-route weighted package delivery problem and may possibly be extended to similar complex optimization problems.

Kenny Chour↗

NASA NTRS2013

Regression Verification Using Impact Summaries

Regression verification techniques are used to prove equivalence of syntactically similar programs. Checking equivalence of large programs, however, can be computationally expensive. Existing regression verification techniques rely on abstraction and decomposition techniques to reduce the computational effort of checking equivalence of the entire program. These techniques are sound but not complete. In this work, we propose a novel approach to improve scalability of regression verification by classifying the program behaviors generated during symbolic execution as either impacted or unimpacted. Our technique uses a combination of static analysis and symbolic execution to generate summaries of impacted program behaviors. The impact summaries are then checked for equivalence using an o-the-shelf decision procedure. We prove that our approach is both sound and complete for sequential programs, with respect to the depth bound of symbolic execution. Our evaluation on a set of sequential C artifacts shows that reducing the size of the summaries can help reduce the cost of software equivalence checking. Various reduction, abstraction, and compositional techniques have been developed to help scale software verification techniques to industrial-sized systems. Although such techniques have greatly increased the size and complexity of systems that can be checked, analysis of large software systems remains costly. Regression analysis techniques, e.g., regression testing [16], regression model checking [22], and regression verification [19], restrict the scope of the analysis by leveraging the differences between program versions. These techniques are based on the idea that if code is checked early in development, then subsequent versions can be checked against a prior (checked) version, leveraging the results of the previous analysis to reduce analysis cost of the current version. Regression verification addresses the problem of proving equivalence of closely related program versions [19]. These techniques compare two programs with a large degree of syntactic similarity to prove that portions of one program version are equivalent to the other. Regression verification can be used for guaranteeing backward compatibility, and for showing behavioral equivalence in programs with syntactic differences, e.g., when a program is refactored to improve its performance, maintainability, or readability. Existing regression verification techniques leverage similarities between program versions by using abstraction and decomposition techniques to improve scalability of the analysis [10, 12, 19]. The abstractions and decomposition in the these techniques, e.g., summaries of unchanged code [12] or semantically equivalent methods [19], compute an over-approximation of the program behaviors. The equivalence checking results of these techniques are sound but not complete-they may characterize programs as not functionally equivalent when, in fact, they are equivalent. In this work we describe a novel approach that leverages the impact of the differences between two programs for scaling regression verification. We partition program behaviors of each version into (a) behaviors impacted by the changes and (b) behaviors not impacted (unimpacted) by the changes. Only the impacted program behaviors are used during equivalence checking. We then prove that checking equivalence of the impacted program behaviors is equivalent to checking equivalence of all program behaviors for a given depth bound. In this work we use symbolic execution to generate the program behaviors and leverage control- and data-dependence information to facilitate the partitioning of program behaviors. The impacted program behaviors are termed as impact summaries. The dependence analyses that facilitate the generation of the impact summaries, we believe, could be used in conjunction with other abstraction and decomposition based approaches, [10, 12], as a complementary reduction technique. An evaluation of our regression verification technique shows that our approach is capable of leveraging similarities between program versions to reduce the size of the queries and the time required to check for logical equivalence. The main contributions of this work are: - A regression verification technique to generate impact summaries that can be checked for functional equivalence using an off-the-shelf decision procedure. - A proof that our approach is sound and complete with respect to the depth bound of symbolic execution. - An implementation of our technique using the LLVMcompiler infrastructure, the klee Symbolic Virtual Machine [4], and a variety of Satisfiability Modulo Theory (SMT) solvers, e.g., STP [7] and Z3 [6]. - An empirical evaluation on a set of C artifacts which shows that the use of impact summaries can reduce the cost of regression verification.

Backes, John↗

NASA NTRS1999

Simulating the Formation of Lunar Floor-Fracture Craters Using Elastoviscoplastic Relaxation

Lunar floor-fracture craters formed during the height of mare basalt emplacement. Due to a general temporal and spatial relation with the maria, these craters, numbering some 200, may be diagnostic of the thermal structure of the crust during this time. As the name suggests, these craters exhibit brittle failure, generally limited to the central floor region. That, and a shallower depth than fresh lunar craters, has led to two main theories as to their formation: laccolith emplacement under the crater and viscous relaxation. The implications of each model for the state of the Moon's crust during this time are quite different, so the viability of each model must be checked. Laccolith emplacement has been treated elsewhere. However, previous attempts to study the relaxation of the craters have assumed only a uniform, Newtonian viscous response of the near surface to the topographic driving forces, and simply postulated that the fractures resulted from tensile stresses associated with floor uplift. Here, we use a more sophisticated rheological model that includes not only non-Newtonian viscous behavior (i.e., the viscosity is stress-dependent), but also incorporates elastic behavior and a plastic component to the rheology to directly simulate the formation of the floor fractures. The results of our simulations show that while elastoviscoplastic relaxation is potentially viable for larger floor-fracture craters, it is not viable for craters with diameters < or = 60 km, the size of the majority of floor-fracture craters. We employ the finite element method, a numerical technique well suited for boundary-value problems, via the commercially available MARC software package. To test the viability of topographic relaxation, our goal is to prepare the simulations as to maximize the amount of relaxation. We take advantage of the natural axisymmetry of craters, simulating one radial plane. Initial shapes are based on data for fresh craters from Pike. To simplify implementation, a fourth order polynomial is used for the basin, while a third order inverse function is used for the rim. This form closely approximates the long-wavelength behavior of complex craters, while ignoring higher-frequency topography, save the rim. This approximation is appropriate because crater relaxation is strongly controlled by long-wavelength topography. Loading is accomplished assuming a uniform gravity field (1.62 m/s-square) and a uniform density of 2900 kg/cubic m. The initial stress state is set to be hydrostatic, with an additional pressure term to account for any overlying topography. This additional pressure term is tapered exponentially with depth. While the simulations quickly settle on a preferred stress state, and while the final solution is fairly insensitive to the choice of the e-folding depth of the taper, selecting an e-folding depth close to the diameter of the crater sets the initial stress state near the preferred state. We assume a diuranally averaged surface temperature of -20 C, and allow temperature to increase with depth at a rate of 50 K//km. Assuming a thermal conductivity of 2 W/in/K, this gradient translates to a heat flow of 100mW/square m, an extremely high value for the Moon. Temperature, of course, will not increase without bound. To maximize relaxation, we allow our temperature profile to increase linearly until it reaches the solidus (assumed to be 1200C) at a depth of 24.4 km, at which point it is kept constant. The presence of melt will drop the bulk viscosity; however, we have no rheological control for partial melts. Therefore, we make no attempt to simulate this situation. Elastoviscoplastic rheological model. In general, geologic materials can behave in three main ways: elastically, viscously (via solid-state creep), and brittly (plasticity is a continuum approach to simulate this phenomenon). We combine these three deformation mechanisms in an extended Maxwell solid, where the total strain can be broken down into a simple summation of the elastic, creep, and plastic strains. In relaxation phenomena in general, the system takes advantage of any means possible to eliminate deviatoric stresses by relaxing away the topography. Previous analyses have only modeled the viscous response. Comparatively, the elastic response in our model can augment the relaxation, to a point. This effect decreases as the elastic response becomes stiffer; indeed, in the limit of infinite elastic Young's modulus (and with no plasticity), the solution converges on the purely viscous solution. Igneous rocks common to the lunar near-surface have Young's modulii in the range of 10-100 GPa. To maximize relaxation, we use a Young's modulus of 10 GPa. (There is negligible sensitivity to the other elastic modulus, the Poisson's ratio; we use 0.25.) For the viscous response, we use a flow law for steady-state creep in thoroughly dried Columbia diabase, because the high plagioclase (about 70 vol%) and orthopyroxene (about 17 vol%) content is similar to the composition of the lunar highland crust as described by remote sensing and sample studies: noritic anorthosite. This flow law is highly non-Newtonian, i.e., the viscosity is highly stress dependent. That, and the variability with temperature, stands in strong contrast to previous examinations of lunar floor-fracture crater relaxation. To model discrete, brittle faulting, we assume "Byerlee's rule," a standard geodynamical technique. We implement this "rule" with an-angle of internal friction of about 40 deg, and a higher-than-normal cohesion of about 3.2 MPa (to approximate the breaking of unfractured rock). The actual behavior of geologic materials is more complex than in our rheological model, so the uncertainties in the plasticity do not represent the state-of-the-art error. Additional information is contained in the original.

Dombard, A. J.↗