Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph 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.

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

At least 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
NASA NTRS2009

Necessary and Sufficient Conditions for Attitude Estimation in Fractionated Spacecraft Systems

This paper addresses the problem of attitude estimation in fractionated spacecraft clusters. Each module in the cluster may have either a star-tracker, a relative attitude sensor, or both. Using results in nonlinear ob- servability theory, we provide graph-theoretic sufficient conditions for the attitude of every module to be observable. In particular we show that the attitude of every module in the cluster can be observed if every module has either a star tracker with non-collinear stars, or there is a path through the sensing network from a module with a star tracker to the module without a star tracker, and each of the relative measurements along the path has either multiple non-collinear beacons or a single beacon that is not parallel to the rotation vector of the target module.

Blackmore, Lars↗
NASA NTRS1965

Notes on System Theory, Volume VII

System theory - matrices, feedback control system, network synthesis, set theory, stability, shift registers, coding, theorem proving, polynomial roots, channels, and signal flow graphs

FEEDBACK CONTROL SYSTEM↗
NASA NTRS1987

Roles of initial condition and vortex pairing in jet noise

Sound generation by vortex pairing in circular and elliptic cold-air jets at Mach 0.15-0.35 is investigated experimentally, with a focus on the effects of initial conditions. The results are presented in graphs and interpreted using the theory of vortex sound proposed by Moehring (1978) and vortex-filament models of jet coherent structure. Tripping the nozzle boundary layer is shown to (1) preempt formation of shear-layer vortices, (2) remove the sound they produce in later pairing, and (3) increase the diffusion of coherent vorticity in the vortex rings. Hence pairing noise should not be significant in practical jets, which are initially turbulent.

Bridges, J. E.↗
NASA NTRSDate not supplied

Methods for Determining Subsets of High Impact, Probabilistically Dependent Medical Conditions Represented in a Directed Graph

One of the longest standing questions in network theory is how a component influences other parts in the system, and how that role is affected when restricting the navigation through the network. The Katz score, one of many centrality measures created for this purpose, takes into account all possible walks through the network, penalizing each additional step in a walk by a scalar called the Katz parameter. This centrality measure often covers an infinite number of walks with infinite length. In this paper we identify the maximum path length which has influence on the Katz score. We ultimately provide guidance when deciding which Katz parameter to use as it depends on the path length of interest. We show how changing the Katz parameter affects the ranking of the vertices in some synthetic graphs as well as NASA's expert informed network of medical dependencies called the Susceptibility Inference Network (SIN).

Hunter Rehm↗
NASA NTRS2016

The Mathematics of Dispatchability Revisited

Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, the dispatchability property has both theoretical and practical interest. One thing that hampers further work in this area is the underdeveloped theory. The existing definitions are expressed in terms of algorithms, and are less suitable for mathematical proofs. In this paper, we develop a new formal theory of dispatchability in terms of execution sequences. We exploit this to prove a characterization of dispatchability involving the structural properties of the STN graph. This facilitates the potential application of the theory to uncertainty reasoning.

control↗
NASA NTRS2016

The Mathematics of Dispatchability, Revisited

Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently, it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, dispatchability has considerable theoretical as well as practical significance. One thing that hampers further work in this area is the underdeveloped theory. Moreover, the existing foundation is inadequate in certain respects. In this paper, we develop a new mathematical theory of dispatchability and its relationship to execution. We also provide several characterizations of dispatchability, including characterizations in terms of the structural properties of the STN graph. This facilitates the potential application of the theory to other areas.

mathematical models↗
NASA NTRS1989

Diffraction of impulsive sounds by a curved obstruction - A time-domain study

The diffraction of spark-discharge-produced sound waves produced by a half circular cylinder covered with absorbing material is investigated theoretically and experimentally. The test bench setup and the measurement instrumentation and procedure are described; the derivation of an analytical model on the basis of the matched asymptotic expansion theory of Pierce (1981) is outlined; and the results are compared in graphs. Good general agreement is obtained, except in the deep shadow of the obstacle, where the theory underpredicts the magnitude of the received pulse. This discrepancy is tentatively attributed to the creeping-wave mechanism described by Pierce.

Berthelot, Yves H.↗
NASA NTRS1994

On k-ary n-cubes: Theory and applications

Many parallel processing networks can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and toruses. In this paper, combinatorial properties of k-ary n-cubes are explored. In particular, the problem of characterizing the subgraph of a given number of nodes with the maximum edge count is studied. These theoretical results are then used to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions.

Mao, Weizhen↗
NASA NTRS1984

Reconnection at the earth's magnetopause - Magnetic field observations and flux transfer events

Theoretical models of plasma acceleration by magnetic-field-line reconnection at the earth magnetopause and the high-resolution three-dimensional plasma measurements obtained with the ISEE satellites are compared and illustrated with diagrams, graphs, drawings, and histograms. The history of reconnection theory and the results of early satellite observations are summarized; the thickness of the magnetopause current layer is discussed; problems in analyzing the polarization of current-layer rotation are considered; and the flux-transfer events responsible for periods of patchy reconnection are characterized in detail. The need for further observations and refinements of the theory to explain the initiation of reconnection and identify the mechanism determining whether it is patchy or steady-state is indicated.

Russell, C. T.↗
NASA NTRS1993

Resource utilization model for the algorithm to architecture mapping model

The analytical model for resource utilization and the variable node time and conditional node model for the enhanced ATAMM model for a real-time data flow architecture are presented in this research. The Algorithm To Architecture Mapping Model, ATAMM, is a Petri net based graph theoretic model developed at Old Dominion University, and is capable of modeling the execution of large-grained algorithms on a real-time data flow architecture. Using the resource utilization model, the resource envelope may be obtained directly from a given graph and, consequently, the maximum number of required resources may be evaluated. The node timing diagram for one iteration period may be obtained using the analytical resource envelope. The variable node time model, which describes the change in resource requirement for the execution of an algorithm under node time variation, is useful to expand the applicability of the ATAMM model to heterogeneous architectures. The model also describes a method of detecting the presence of resource limited mode and its subsequent prevention. Graphs with conditional nodes are shown to be reduced to equivalent graphs with time varying nodes and, subsequently, may be analyzed using the variable node time model to determine resource requirements. Case studies are performed on three graphs for the illustration of applicability of the analytical theories.

Stoughton, John W.↗
NASA NTRS1991

An overview of the essential differences and similarities of system identification techniques

Information is given in the form of outlines, graphs, tables and charts. Topics include system identification, Bayesian statistical decision theory, Maximum Likelihood Estimation, identification methods, structural mode identification using a stochastic realization algorithm, and identification results regarding membrane simulations and X-29 flutter flight test data.

Mehra, Raman K.↗
NASA NTRSDate not supplied

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry. Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space. These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing. We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.

Delay Tolerant Networking↗
NASA NTRSDate not supplied

Toward Time Synchronization in Delay Tolerant Network based Solar System Internetworking

The expanding presence in space will place an increased dependency on networked communications– a scalable communications infrastructure; that is, the Solar System Internet (SSI). Upcoming developments towards a SSI include NASA’s upcoming LunaNet, or lunar Internet, which provides multi-hop multi-path communications using Delay Tolerant Networking (DTN). DTN has been an active area of research and development, particularly in routing, security, and optimization. DTNs are marked by mobility, disconnection, and a wide variance of latencies (propagation and processing delays). In this paper, we outline progress towards a theory of time synchronization across such a network. An underlying assumption of DTN is that the network is time synchronized already, rather than synchronization being provided as a service. While this is necessary for schedule-based routing, which is necessarily prevalent in DTNs, it is so deeply ingrained as to be built into the primary unit of data in DTNs– the bundle. Indeed, a bundle’s creation timestamp and its time to live (called the lifetime) are based on time, and there are special recommendations for systems that lack accurate clocks. The assumption of time synchronization makes sense when limiting considerations to smaller-scale and more traditional space communication. However, just as end-to-end connectivity cannot be guaranteed in DTNs, neither can access to a reference or authoritative clock. In this more general case, it might be necessary to synchronize over time-varying meshes, and perhaps even to consider relativistic effects. Moreover, by imposing synchronization restrictions in order to sustain a network, the effectiveness of the network to achieve scalability will be necessarily muted. To work towards a time synchronization theory for DTNs, we build upon past successes in modeling DTNs using time-varying graphs and sheaves. This includes error and limitation estimation, which allows one to define domains over which schedule-based routing is possible, up to some threshold sensitivity. Despite the theoretical nature of these results, the approaches taken are also algorithmic, and hence lend themselves to practical implementations. The paper concludes with comparisons of the various methods along with suggestions for future work.

Delay Tolerant Networking↗
NASA NTRS1990

A VLSI decomposition of the deBruijn graph

A new Viterbi decoder for convolutional codes with constraint lengths up to 15, called the Big Viterbi Decoder, is under development for the Deep Space Network. It will be demonstrated by decoding data from the Galileo spacecraft, which has a rate 1/4, constraint-length 15 convolutional encoder on board. Here, the mathematical theory underlying the design of the very-large-scale-integrated (VLSI) chips that are being used to build this decoder is explained. The deBruijn graph B sub n describes the topology of a fully parallel, rate 1/v, constraint length n+2 Viterbi decoder, and it is shown that B sub n can be built by appropriately wiring together (i.e., connecting together with extra edges) many isomorphic copies of a fixed graph called a B sub n building block. The efficiency of such a building block is defined as the fraction of the edges in B sub n that are present in the copies of the building block. It is shown, among other things, that for any alpha less than 1, there exists a graph G which is a B sub n building block of efficiency greater than alpha for all sufficiently large n. These results are illustrated by describing a special hierarchical family of deBruijn building blocks, which has led to the design of the gate-array chips being used in the Big Viterbi Decoder.

Collins, O.↗
NASA NTRS1989

A simple element for aeroelastic analysis of undamaged and damaged wings

The effects of material damage on the aeroelastic response of an anisotropic composite wing are investigated analytically. The wing is modeled as a Timoshenko beam of arbitrary cross section, applying a 24-DOF one-dimensional beam element and Cartesian coordinates. The formulations for the element stiffness matrix, the strain-displacement relations, the box-beam constitutive relations, the contributions of stringers and web, and the warping correction factor are outlined; the application of strip theory in deriving the aerodynamic model is briefly explained; and numerical results are presented in extensive graphs. It is shown that asymmetry and damage can induce bending-stretching coupling phenomena and thereby affect the stability of the aircraft either positively or negatively. The need to take such effects into account in the design of advanced composite wings is stressed.

Kapania, Rakesh K.↗
NASA NTRS2003

Strength Differential Measured in Inconel 718: Effects of Hydrostatic Pressure Studied

Aeropropulsion components, such as disks, blades, and shafts, are commonly subjected to multiaxial stress states at elevated temperatures. Experimental results from loadings as complex as those experienced in service are needed to help guide the development of accurate viscoplastic, multiaxial deformation models that can be used to improve the design of these components. During a recent study on multiaxial deformation (ref. 1) on a common aerospace material, Inconel 718, it was shown that the material in the aged state exhibits a strength differential effect (SDE), whereby the uniaxial compressive yield and subsequent flow behavior are significantly higher than those in uniaxial tension. Thus, this material cannot be described by a standard von Mises yield formulation. There have been other formulations postulated (ref. 2) that involve other combinations of the stress invariants, including the effect of hydrostatic stress. The question remained as to which invariants are necessary in the flow model. To capture the physical mechanisms occurring during deformation and reflect them in the plasticity formulation, researchers examined the flow of Inconel 718 under various amounts of hydrostatic stress to determine whether or not hydrostatic stress is needed in the formulation. Under NASA Grant NCC3-464, monitored by the NASA Glenn Research Center, a series of tensile tests were conducted at Case Western Reserve University on aged (precipitation hardened) Inconel 718 at 650 C and with superimposed hydrostatic pressure. Dogbone shaped tensile specimens (3-mm-diameter gauge by 16-mm gauge length) and cylindrical compression specimens (3-mm-diameter gauge by 6-mm gauge length) were strain gauged and loaded in a high-pressure testing apparatus. Hydrostatic pressures were obtained with argon and ranged from 210 to 630 MPa. The aged Inconel 718 showed a pronounced difference in the tension and compression yield strength (i.e., an SDE), as previously observed. Also, there were no significant effects of hydrostatic pressure on either the tensile and compressive yield strength (see the graph) or on the magnitude of the SDE. This behavior is not consistent with the pressure-dependent theory of the SDE, which postulates that the SDE is associated with pressure-dependent and/or internal friction dependent deformation associated with non-Schmid effects at the crystal level (refs. 3 and 4). Flow in Inconel 718 appears to be independent of hydrostatic pressure, suggesting that this invariant may be removed from the phenomenological constitutive model. As part of an ongoing effort to develop advanced constitutive models, Glenn s Life Prediction Branch coordinated this work with that of research on the multiaxial deformation behavior of Inconel 718 being conducted at Pennsylvania State University under NASA Grant NCC597.

Lewandowski, John J.↗
NASA NTRS2022

Multi-Agent Control Approach to the Stability of Linear Deployable Systems

Collisions and undesired dynamic responses may occur during the expansion phase of deployable elements on a spacecraft. This problem is more pronounced in large and complex deployable elements where characterization of transient dynamics using testing and simulation can be challenging. This paper introduces a multi-agent control theory approach to address the problem of collisions and transient behavior in deployable lattice systems. We introduce the graph theoretic and relative error vector-based state-space structures to represent the geometry of a lattice-based deploy system. We show that under the assumption of almost-strict dissipativity, the closed-loop feedback gains of the relative error dynamics are the spring and damper constants in the structure. Moreover, we introduce the control perspective of shaping transient dynamics using eigenstructure assignment and balanced coordinate transformation.

Pablos, Juan L. de↗