Search NASA⌕ Search

SEARCH · Search NASA

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.

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

At least 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

Information Extraction on an Earth Science Knowledge Graphs with Semantic Parsing

Knowledge graphs are an important tool, both for representing knowledge and for retrieving information. Fundamentally, they are semantic networks that represent entities and relationships in the form of nodes and edges. A large corpus of natural language text can bebroken down into discrete entities and relationships to form a useful knowledge graph. Existing research breaks down text into a subject, object, and verb relationship triple. Although this is a useful first step, it loses much of the original contextual information encoded within the text. Our process uses a novel 7-tuple approach, in which elements of sentences are programmatically parsed into seven categories: initiator, impacted, receiver, beneficiary, result, and context. In this presentation, we show a knowledge graph built using this 7-tupleprocessing of an Earth science corpus. We explain the techniques used to create the graph and analyze its information retrieval capability while assessing the accuracy and limitations of the results.

Carson Davis↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques Applied to Contact Graph Routing

Routing in the space internet has to face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this presentation we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. Finally, we propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol.

Yael Kirkpatrick↗
NASA NTRS2022

Directed Acyclic Graph Guidance Documentation

For over a decade, the National Aeronautics and Space Administration (NASA) has tracked and configuration-managed approximately 30 risks to astronaut health and performance that occur before, during and after spaceflight. The Human System Risk Board (HSRB), a Health and Medical Technical Authority (HMTA) Board at NASA Johnson Space Center, is the entity responsible for identifying, assessing, analyzing, and monitoring the official understanding of the risk or risk posture for each of the Human System Risks and determining – based on evaluation of the available evidence – when that risk posture changes. The ultimate purpose of tracking and researching these risks is to find ways to reduce the risk that astronaut crews face during spaceflight. Historically, research, development and operations relevant to one risk have been conducted in isolation from other risks; these individual risk ‘silos’ enabled initial characterization of each specific risk. In spaceflight however, the impact of exposure to risk for astronaut crews is cumulative, and not independent of exposures or other risks, as all the adverse effects of the spaceflight environment begin at launch, continue throughout the duration of the mission and in some cases across the lifetime of the crews. In January of 2020, the HSRB at NASA embarked on a pilot project designed to assess the potential value of causal diagramming as a tool to facilitate understanding these cumulative and interdependent effects as applied within Human System Risk management. This process uses directed acyclic graphs as a means of formalizing a shared mental model of the causal flow of risk among Risk Board stakeholders. Initially this model was to improve communication among those stakeholders, but the potential value exceeds communication alone. Formalization of the process for creating these causal diagrams will enable the creation of a composite risk network that is vetted by members of the NASA community and configuration managed. The causal diagrams are formulated as directed acyclic graphs (DAGs) to function as a type of knowledge graph for reference for the board and its stakeholders. This document outlines the pilot process, the standardized approaches, and guidance for risk custodian teams when creating and updating DAGs as a part of the NASA Human System Risk Management process.

Risk↗
NASA NTRSDate not supplied

Multigraph-based Routing in Delay Tolerant Networks: An Alternative to Contact Graph Routing

Satellites are leaving the realms of niche use, extending our day-to-day networked infrastructure to space – thereby forcing a generalization of network architectures. The Delay Tolerant Networking (DTN) protocol is being developed to give rise to this new Solar System Internet. Predominantly, DTNs in space use globally-distributed contact tables to compute routes. In this paper, we propose and analyze a novel optimized approach for route computations that improves upon traditional approaches. As the general DTN will always include some scheduled links, our new algorithm enables greater scalability and practicality of DTN routing. These contact tables include windows when two nodes can communicate and were classically organized into a contact graph, where the vertices represent contact opportunities. Because the complexity of a contact graph grows with the number of contacts, pathfinding on it does not scale. A new structure using multigraphs with the same data is proposed. We show that a multigraph-based approach, which we call contact multigraph routing, exhibits performance superior to routing based on contact graphs, allowing greater scaling to schedule-based routing. In this paper, the multigraph-based algorithm is detailed and a proof is included showing it outperforms the previous algorithm given the same input. Pseudocode is included, as are simulation results. We conclude with suggested future work.

Delay Tolerant Networking↗
NASA NTRSDate not supplied

Requirement Discovery Using Embedded Knowledge Graph With ChatGPT

The field of Advanced Air Mobility (AAM) is witnessing a transformation with innovations such as electric aircraft and increasingly automated airspace operations. Within AAM, the Urban Air Mobility (UAM) con-cept focuses on providing air-taxi services in densely populated urban areas. This research introduces the utilization of Large Language Models (LLMs), such as OpenAI's GPT-4, to enhance the UAM Requirement discovery process. This study explores two distinct approaches to leverage LLMs in the context of UAM Requirement discovery. The first approach evaluates the LLM's ability to provide responses without relying on additional outside systems, such as a relational or graph database. Instead, a vector store provides relevant information to the LLM based on the user’s question, a process known as Retrieval Augmented Generation (RAG). The second approach integrates the LLM with a graph database. The LLM acts as an intermediary between the user and the graph database, translating user questions into cypher queries for the database and database responses into human-readable answers for the user. Our team implemented and tested both solutions to analyze require-ments within a UAM dataset. This paper will talk about our approaches, implementations, and findings related to both approaches.

systems engineering↗
NASA NTRSDate not supplied

Requirement Discovery Using Embedded Knowledge Graph with ChatGPT

The field of Advanced Air Mobility (AAM) is witnessing a transformation with innovations such as electric aircraft and increasingly automated airspace operations. Within AAM, the Urban Air Mobility (UAM) concept focuses on providing air-taxi services in densely populated urban areas. This research introduces the utilization of Large Language Models (LLMs), such as OpenAI's GPT-4, to enhance the UAM Requirement discovery process. This study explores two distinct approaches to leverage LLMs in the context of UAM Requirement discovery. The first approach evaluates the LLM's ability to provide responses without relying on additional outside systems, such as a relational or graph database. Instead, a vector store provides relevant information to the LLM based on the user’s question, a process known as Retrieval Augmented Generation (RAG). The second approach integrates the LLM with a graph database. The LLM acts as an intermediary between the user and the graph database, translating user questions into cypher queries for the database and database responses into human-readable answers for the user. Our team implemented and tested both solutions to analyze requirements within a UAM dataset. This paper will talk about our approaches, implementations, and findings related to both approaches.

systems engineering↗
NASA NTRSDate not supplied

Requirement Discovery Using Embedded Knowledge Graph With ChatGPT - Poster

The field of Advanced Air Mobility (AAM) is witnessing a transformation with innovations such as electric aircraft and increasingly automated airspace operations. Within AAM, the Urban Air Mobility (UAM) con-cept focuses on providing air-taxi services in densely populated urban areas. This research introduces the utilization of Large Language Models (LLMs), such as OpenAI's GPT-4, to enhance the UAM Requirement discovery process. This study explores two distinct approaches to leverage LLMs in the context of UAM Requirement discovery. The first approach evaluates the LLM's ability to provide responses without relying on additional outside systems, such as a relational or graph database. Instead, a vector store provides relevant information to the LLM based on the user’s question, a process known as Retrieval Augmented Generation (RAG). The second approach integrates the LLM with a graph database. The LLM acts as an intermediary between the user and the graph database, translating user questions into cypher queries for the database and database responses into human-readable answers for the user. Our team implemented and tested both solutions to analyze require-ments within a UAM dataset. This paper will talk about our approaches, implementations, and findings related to both approaches.

systems engineering↗
NASA NTRSDate not supplied

Airspace Research and Development Portfolio Assessment of Urban Air Mobility using Knowledge Graph Data Science

National Aeronautics and Space Administration (NASA) is spearheading an innovative digital engineering approach to integrate, communicate, and facilitate the research of Urban Air Mobility (UAM) operations. The UAM vision is one in which advanced technologies and new operational procedures enable practical and cost-effective air transport as an integrated mode of movement of people and goods throughout metropolitan areas. To safely support UAM operations at scale in the National Airspace System (NAS), NASA’s Air Traffic Management-Exploration (ATM-X) project has been conducting research that evolves the UAM air traffic management system towards a highly automated and operationally flexible system of the future. The complexity of UAM airspace evolution to accommodate the increasing tempo of UAM operations over time is managed through the UAM airspace research roadmap, which is a system engineering approach to the R&D of complex system-of-systems, where system’s interdependencies make it nearly impossible to define requirements for individual elements of the system in isolation. These interdependencies form a knowledge graph (node-link network) with a highly complex structure far beyond the human user’s ability to extract insights for project management’s research portfolio assessment. This study applies advanced data analytics in knowledge graph to the UAM knowledge graph to facilitate the portfolio assessment.

ATM↗
NASA NTRSDate not supplied

Airspace Research and Development Portfolio Assessment of Urban Air Mobility using Knowledge Graph Data Science

National Aeronautics and Space Administration (NASA) is spearheading an innovative digital engineering approach to integrate, communicate, and facilitate the research of Urban Air Mobility (UAM) operations. The UAM vision is one in which advanced technologies and new operational procedures enable practical and cost-effective air transport as an integrated mode of movement of people and goods throughout metropolitan areas. To safely support UAM operations at scale in the National Airspace System (NAS), NASA’s Air Traffic Management-Exploration (ATM-X) project has been conducting research that evolves the UAM air traffic management system towards a highly automated and operationally flexible system of the future. The complexity of UAM airspace evolution to accommodate the increasing tempo of UAM operations over time is managed through the UAM airspace research roadmap, which is a system engineering approach to the R&D of complex system-of-systems, where system’s interdependencies make it nearly impossible to define requirements for individual elements of the system in isolation. These interdependencies form a knowledge graph (node-link network) with a highly complex structure far beyond the human user’s ability to extract insights for project management’s research portfolio assessment. This study applies advanced data analytics in knowledge graph to the UAM knowledge graph to facilitate the portfolio assessment.

ATM↗
NASA NTRSDate not supplied

Graph Representation Learning for Dengue Forecasting

In 2017, the largest recorded dengue outbreak in Sri Lanka’s history occurred. Since then, dengue has continued to threaten national health across Sri Lanka. The development of an effective Early Warning System (EWS) for dengue outbreaks is essential for Sri Lanka’s Ministry of Health to take preventative measures. We propose the use of Graph Neural Networks as EWS. Using earth observational data from NASAs global satellites and dengue incidence data from Sri Lanka s Ministry of Health, we developed a series of traditional and graph representation EWS to forecast Dengue cases across Sri Lanka’s 25 districts between 2013 and 2022. We demonstrate empirically that Graph Neural Networks which incorporate spatiotemporal relations significantly outperform traditional EWS such as Autoregressive Integrated Moving Average (ARIMA), Random Forest, and Long Short-Term Memory (LSTM). Our source code is available on GitHub and will be provided in the final submission.

Graph Neural Networks↗
NASA NTRSDate not supplied

A Knowledge Graph Framework for Organizing Heterogeneous Datasets for Utilization in Classical and Quantum Computing: Current Challenges and Future Directions

"The escalating impact of climate change induced extreme weather events in urban, suburban, and rural environments demands a rethink of how we have been using the single event-based or use-case-based knowledge graph models. The lack of representation in interaction within environmental variables found in literature led to the development of a novel framework that reflects the true nature of the interconnectedness in our environment. We propose an Environmental Interaction Knowledge Graph (EIKG) framework. This general EIKG framework works as the basis for interconnected environmental events by knitting interrelated events such as hurricanes leading to storm surges, which lead to flood events that could cause mudslides, landslides, etc., The cascading nature of one event leading to another related event in the environment requires an adequate understanding of each event using contextual information before conducting any data-driven analytics. This vision paper showcases how the EIKG:floods, EIKG:wildfire EIKG:landslides, etc, can be derived from a base case framework of EIKG as those individual events are interconnected with some common denominator variables. As an example, the precipitation variable is used in the flood case study as well as in the wildfire case study, as excessive precipitation levels lead to floods, and lack of precipitation leads to droughts and wildfires. We identify the precipitation variable as a “common-denominator-variable” in extreme weather events that play a key role in modeling the environment leading to different extreme weather events based on the variability of that variable (varying values where low precipitation leads to drought, and high values lead to floods). We use the insights gained from EIKG to conduct classical and Quantum Machine Learning (QML) based data analysis on the research questions developed. Our preliminary study shows how the Variational Quantum Classifier (VQC) and Quantum Support Vector Classifier (QSVC) are used along with the classical machine learning models to compare the model accuracies. Our study elaborates on how a quantitative analysis uses state-of-the-art machine learning techniques that include implementing both classical and quantum machine learning models and developing the knowledge graph. The EIKG is used to organize heterogeneous datasets and integrate the relations to case-specific extreme weather events such as floods. The study uses datasets such as county-to-country residential mobility data, socioeconomic datasets from the US Census Bureau, climate and weather-related Earth Observational data from NASA, and critical infrastructure data from the Homeland Infrastructure datasets."

Knowledge Graphs, Quantum Computing, Heterogenous ↗
NASA NTRS1972

FGRAAL: FORTRAN extended graph algorithmic language

The FORTRAN version FGRAAL of the graph algorithmic language GRAAL as it has been implemented for the Univac 1108 is described. FBRAAL is an extension of FORTRAN 5 and is intended for describing and implementing graph algorithms of the type primarily arising in applications. The formal description contained in this report represents a supplement to the FORTRAN 5 manual for the Univac 1108 (UP-4060), that is, only the new features of the language are described. Several typical graph algorithms, written in FGRAAL, are included to illustrate various features of the language and to show its applicability.

Basili, V. R.↗
NASA NTRS1972

Topologies on directed graphs

Given a directed graph, a natural topology is defined and relationships between standard topological properties and graph theoretical concepts are studied. In particular, the properties of connectivity and separatedness are investigated. A metric is introduced which is shown to be related to separatedness. The topological notions of continuity and homeomorphism. A class of maps is studied which preserve both graph and topological properties. Applications involving strong maps and contractions are also presented.

Lieberman, R. N.↗
NASA NTRS1987

Graph-Plotting Routine

Plotter routine for IBM PC (AKPLOT) designed for engineers and scientists who use graphs as integral parts of their documentation. Allows user to generate graph and edit its appearance on cathode-ray tube. Graph may undergo many interactive alterations before finally dumped from screen to be plotted by printer. Written in BASIC.

Kantak, Anil V.↗
NASA NTRS1988

Browsing schematics: Query-filtered graphs with context nodes

The early results of a research project to create tools for building interfaces to intelligent systems on the NASA Space Station are reported. One such tool is the Schematic Browser which helps users engaged in engineering problem solving find and select schematics from among a large set. Users query for schematics with certain components, and the Schematic Browser presents a graph whose nodes represent the schematics with those components. The query greatly reduces the number of choices presented to the user, filtering the graph to a manageable size. Users can reformulate and refine the query serially until they locate the schematics of interest. To help users maintain orientation as they navigate a large body of data, the graph also includes nodes that are not matches but provide global and local context for the matching nodes. Context nodes include landmarks, ancestors, siblings, children and previous matches.

Ciccarelli, Eugene C.↗
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.↗