SEARCH · Engineering Papers

Results for “GRAPH”

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.

At least 595 records · Page 33

All sources NASA NTRS DOE OSTI

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

Validation and verification of expert systems using evidence flow graphs

This paper describes an ongoing investigation into the use of evidence flow graph techniques for performing V&V of expert systems. This method involves translating a rule-base into an evidence flow graph, a representation originally developed for real-time intelligent systems in distributed environments, and then running simulations of the evidence flow graph. Certain errors can be found during the translation process. The simulations can detect output sensitivity to rule firing order, to order of presentation of inputs, and to small changes in input values.

Becker, Lee A.↗

NASA NTRS1990

TIGRE: Combinator graph reduction on the RTX 2000

An efficient evaluation technique is examined for lazy functional programs based on combinator graph reduction. Graph reduction is widely believed to be slow and inefficient, but an abstract machine called the Threaded Interpretive Graph Reduction Engine (TIGRE) achieves a substantial speedup over previous reduction techniques. The runtime system of TIGRE is a threaded system that permits self-modifying program execution with compiler-guaranteed safety. This paper describes an implementation of TIGRE in Forth for the Harris RTX 2000 stack processor.

Koopman, Philip, Jr.↗

NASA NTRS1953

Method and graphs for the evaluation of air-induction systems

Graphs have been developed for rapid evaluation of air-induction systems from considerations of their aerodynamic-performance parameters in combination with power-plant characteristics. The graphs cover the range of supersonic Mach numbers to 3.0. Examples are presented for an air-induction system and engine combination of two Mach numbers and two altitudes in order to illustrate the method and application of the graphs. The examples show that jet-engine characteristics impose restrictions on the use of fixed inlets if the maximum net thrusts are to be realized at all flight conditions. (author)

Brajnikoff, George B↗

NASA NTRS2004

Plan-graph Based Heuristics for Conformant Probabilistic Planning

In this paper, we introduce plan-graph based heuristics to solve a variation of the conformant probabilistic planning (CPP) problem. In many real-world problems, it is the case that the sensors are unreliable or take too many resources to provide knowledge about the environment. These domains are better modeled as conformant planning problems. POMDP based techniques are currently the most successful approach for solving CPP but have the limitation of state- space explosion. Recent advances in deterministic and conformant planning have shown that plan-graphs can be used to enhance the performance significantly. We show that this enhancement can also be translated to CPP. We describe our process for developing the plan-graph heuristics and estimating the probability of a partial plan. We compare the performance of our planner PVHPOP when used with different heuristics. We also perform a comparison with a POMDP solver to show over a order of magnitude improvement in performance.

Ramakrishnan, Salesh↗

NASA NTRS2012

Interactive Web Graphs with Fewer Restrictions

There is growing popularity for interactive, statistical web graphs and programs to generate them. However, it seems that these programs tend to be somewhat restricted in which web browsers and statistical software are supported. For example, the software might use SVG (e.g., Protovis, gridSVG) or HTML canvas, both of which exclude most versions of Internet Explorer, or the software might be made specifically for R (gridSVG, CRanvas), thus excluding users of other stats software. There are more general tools (d3, Rapha lJS) which are compatible with most browsers, but using one of these to make statistical graphs requires more coding than is probably desired, and requires learning a new tool. This talk will present a method for making interactive web graphs, which, by design, attempts to support as many browsers and as many statistical programs as possible, while also aiming to be relatively easy to use and relatively easy to extend.

Fiedler, James↗

NASA NTRS2013

Enhanced Contact Graph Routing (ECGR) MACHETE Simulation Model

Contact Graph Routing (CGR) for Delay/Disruption Tolerant Networking (DTN) space-based networks makes use of the predictable nature of node contacts to make real-time routing decisions given unpredictable traffic patterns. The contact graph will have been disseminated to all nodes before the start of route computation. CGR was designed for space-based networking environments where future contact plans are known or are independently computable (e.g., using known orbital dynamics). For each data item (known as a bundle in DTN), a node independently performs route selection by examining possible paths to the destination. Route computation could conceivably run thousands of times a second, so computational load is important. This work refers to the simulation software model of Enhanced Contact Graph Routing (ECGR) for DTN Bundle Protocol in JPL's MACHETE simulation tool. The simulation model was used for performance analysis of CGR and led to several performance enhancements. The simulation model was used to demonstrate the improvements of ECGR over CGR as well as other routing methods in space network scenarios. ECGR moved to using earliest arrival time because it is a global monotonically increasing metric that guarantees the safety properties needed for the solution's correctness since route re-computation occurs at each node to accommodate unpredicted changes (e.g., traffic pattern, link quality). Furthermore, using earliest arrival time enabled the use of the standard Dijkstra algorithm for path selection. The Dijkstra algorithm for path selection has a well-known inexpensive computational cost. These enhancements have been integrated into the open source CGR implementation. The ECGR model is also useful for route metric experimentation and comparisons with other DTN routing protocols particularly when combined with MACHETE's space networking models and Delay Tolerant Link State Routing (DTLSR) model.

Segui, John S.↗

NASA NTRS2013

Contact Graph Routing Enhancements Developed in ION for DTN

The Interplanetary Overlay Network (ION) software suite is an open-source, flight-ready implementation of networking protocols including the Delay/Disruption Tolerant Networking (DTN) Bundle Protocol (BP), the CCSDS (Consultative Committee for Space Data Systems) File Delivery Protocol (CFDP), and many others including the Contact Graph Routing (CGR) DTN routing system. While DTN offers the capability to tolerate disruption and long signal propagation delays in transmission, without an appropriate routing protocol, no data can be delivered. CGR was built for space exploration networks with scheduled communication opportunities (typically based on trajectories and orbits), represented as a contact graph. Since CGR uses knowledge of future connectivity, the contact graph can grow rather large, and so efficient processing is desired. These enhancements allow CGR to scale to predicted NASA space network complexities and beyond. This software improves upon CGR by adopting an earliest-arrival-time cost metric and using the Dijkstra path selection algorithm. Moving to Dijkstra path selection also enables construction of an earliest- arrival-time tree for multicast routing. The enhancements have been rolled into ION 3.0 available on sourceforge.net.

Segui, John S.↗

NASA NTRS2009

Decomposition Algorithm for Global Reachability Analysis on a Time-Varying Graph with an Application to Planetary Exploration

Hot air (Montgolfiere) balloons represent a promising vehicle system for possible future exploration of planets and moons with thick atmospheres such as Venus and Titan. To go to a desired location, this vehicle can primarily use the horizontal wind that varies with altitude, with a small help of its own actuation. A main challenge is how to plan such trajectory in a highly nonlinear and time-varying wind field. This paper poses this trajectory planning as a graph search on the space-time grid and addresses its computational aspects. When capturing various time scales involved in the wind field over the duration of long exploration mission, the size of the graph becomes excessively large. We show that the adjacency matrix of the graph is block-triangular, and by exploiting this structure, we decompose the large planning problem into several smaller subproblems, whose memory requirement stays almost constant as the problem size grows. The approach is demonstrated on a global reachability analysis of a possible Titan mission scenario.

Dijkstra's algorithm↗

NASA NTRS2018

Modeling Principles Using the Relation Between Lagrange Multipliers and Bond Graphs

Final document is attached. Modeling dynamic systems by bond graphs has become state of the art technology since hundreds of researchers around the world have incorporated the technology in many fields of engineering and science. The legacy of its invertor Prof. Henry Paynter at MIT in 1959 is now a fundamental and practical technique to understand reality by building computer models. This paper addresses a particular aspect of this technology when modeling of mechanical systems require relaxation of constraints by means of Lagrange principles. Lagrange's equations are a useful means of describing and solving systems with kinematic constraints. Lagrange multipliers are variables used in equations to find the extremes of multivariate functions. Here we explore the relation of Lagrange multipliers to solve modeling difficulties of a space vehicle with equations with dependent derivatives. Lagrange multipliers were used in conjunction with bond graphs to simulate a system where joints of kinematic linkages produce dependent derivatives. NASA's Morpheus Project lunar lander was used as a case study. The Morpheus Project is a terrestrial test vehicle designed to fly the terminal descent trajectory of a lunar lander to advance the Autonomous Landing Hazard Avoidance Technology (ALHAT). An objective of this study is to apply the modeling approach herein to capture the dynamic movement of the lander as the propellant is sloshed and consumed. This paper expands further the analysis presented by (Granda, J J. Nguyen, L, Carlson, T, Sahragard-Monfared, G., Fornalski, E., Brocker 2016). Using an automated approach bond graph models of state space equations were generated using the Computer Aided Modeling Program (CAMPG). Integral causality models and derivative causality models were considered in order to find the simpler solution for the mathematical dependencies produced in modeling this vehicle.

Granda, Jose J.↗

NASA NTRSDate not supplied

Development of a Knowledge Graph for Dataset Discovery and Identification at a NASA Data Center

The NASA Goddard Earth Sciences Data and Information Services Center (GES DISC) archives and distributes hundreds of Earth Science data collections to the public. These collections are used in research, resulting in the publication of thousands of scientific papers each year. As new users come to GES DISC for data, it is important for them to understand how prior research used the data. To help researchers, a knowledge graph (KG) was designed and implemented to connect publication citations with dataset metadata. The relationships created in the graph have the potential to allow the Web applications that utilize this information to directly connect the publication to the GES DISC datasets and services. These relationships are demonstrated using a web application prototype. In addition, the graph can also make connections between publications, datasets, and measurements based on the mentions of datasets and their attributes in the publications. To demonstrate this capability, a web application was created that takes the excerpt from the publication and returns a most likely dataset and measurement pairing, ranking the results based on how often these datasets and measurements were used in prior publications.

Nathaniel Crosby↗

DOE OSTI2013

A heterogeneous graph-based recommendation simulator

Heterogeneous graph-based recommendation frameworks have flexibility in that they can incorporate various recommendation algorithms and various kinds of information to produce better results. In this demonstration, we present a heterogeneous graph-based recommendation simulator which enables participants to experience the flexibility of a heterogeneous graph-based recommendation method. With our system, participants can simulate various recommendation semantics by expressing the semantics via meaningful paths like User Movie User Movie. The simulator then returns the recommendation results on the fly based on the user-customized semantics using a fast Monte Carlo algorithm.

Yeonchan, Ahn↗

DOE OSTI2015

Dynamic graph system for a semantic database

A method and system in a computer system for dynamically providing a graphical representation of a data store of entries via a matrix interface is disclosed. A dynamic graph system provides a matrix interface that exposes to an application program a graphical representation of data stored in a data store such as a semantic database storing triples. To the application program, the matrix interface represents the graph as a sparse adjacency matrix that is stored in compressed form. Each entry of the data store is considered to represent a link between nodes of the graph. Each entry has a first field and a second field identifying the nodes connected by the link and a third field with a value for the link that connects the identified nodes. The first, second, and third fields represent the rows, column, and elements of the adjacency matrix.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2015

Graph modeling systems and methods

An apparatus and a method for vulnerability and reliability modeling are provided. The method generally includes constructing a graph model of a physical network using a computer, the graph model including a plurality of terminating vertices to represent nodes in the physical network, a plurality of edges to represent transmission paths in the physical network, and a non-terminating vertex to represent a non-nodal vulnerability along a transmission path in the physical network. The method additionally includes evaluating the vulnerability and reliability of the physical network using the constructed graph model, wherein the vulnerability and reliability evaluation includes a determination of whether each terminating and non-terminating vertex represents a critical point of failure. The method can be utilized to evaluate wide variety of networks, including power grid infrastructures, communication network topologies, and fluid distribution systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2014

Recursive Feature Extraction in Graphs

ReFeX extracts recursive topological features from graph data. The input is a graph as a csv file and the output is a csv file containing feature values for each node in the graph. The features are based on topological counts in the neighborhoods of each nodes, as well as recursive summaries of neighbors' features.

Source record↗

DOE OSTI2016

Dynamic graph system for a semantic database

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2016

GraphMeta: Managing HPC Rich Metadata in Graphs

High-performance computing (HPC) systems face increasingly critical metadata management challenges, especially in the approaching exascale era. These challenges arise not only from exploding metadata volumes, but also from increasingly diverse metadata, which contains data provenance and arbitrary user-defined attributes in addition to traditional POSIX metadata. This ‘rich’ metadata is becoming critical to supporting advanced data management functionality such as data auditing and validation. In our prior work, we identified a graph-based model as a promising solution to uniformly manage HPC rich metadata due to its flexibility and generality. However, at the same time, graph-based HPC rich metadata anagement also introduces significant challenges to the underlying infrastructure. In this study, we first identify the challenges on the underlying infrastructure to support scalable, high-performance rich metadata management. Based on that, we introduce GraphMeta, a graphbased engine designed for this use case. It achieves performance scalability by introducing a new graph partitioning algorithm and a write-optimal storage engine. We evaluate GraphMeta under both synthetic and real HPC metadata workloads, compare it with other approaches, and demonstrate its advantages in terms of efficiency and usability for rich metadata management in HPC systems.

Dai, Dong↗

DOE OSTI2017

NOUS: A Knowledge Graph Management System

Knowledge graphs represent information as entities and relationships between them. For tasks such as natural language question answering or automated analysis of text, a knowledge graph provides valuable context to establish the specific type of entities being discussed. It allow us to derive better context about newly arriving information and leads to intelligent reasoning capabilities. We address two primary needs: A) Automated construction of knowledge graphs is a technically challenging, expensive process; and B) The ability to synthesize new information by monitoring newly emerging knowledge is a transformational capability that does not exist in state of the art systems.

Source record↗