SEARCH · Search NASA

Results for “graph algorithms”

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 55 records · Page 3

All sources NASA NTRS DOE OSTI

NASA NTRS2011

Planning the FUSE Mission Using the SOVA Algorithm

Three documents discuss the Sustainable Objective Valuation and Attainability (SOVA) algorithm and software as used to plan tasks (principally, scientific observations and associated maneuvers) for the Far Ultraviolet Spectroscopic Explorer (FUSE) satellite. SOVA is a means of managing risk in a complex system, based on a concept of computing the expected return value of a candidate ordered set of tasks as a product of pre-assigned task values and assessments of attainability made against qualitatively defined strategic objectives. For the FUSE mission, SOVA autonomously assembles a week-long schedule of target observations and associated maneuvers so as to maximize the expected scientific return value while keeping the satellite stable, managing the angular momentum of spacecraft attitude- control reaction wheels, and striving for other strategic objectives. A six-degree-of-freedom model of the spacecraft is used in simulating the tasks, and the attainability of a task is calculated at each step by use of strategic objectives as defined by use of fuzzy inference systems. SOVA utilizes a variant of a graph-search algorithm known as the A* search algorithm to assemble the tasks into a week-long target schedule, using the expected scientific return value to guide the search.

Lanzi, James↗

NASA NTRS1990

Assembly planning for large truss structures in space

The approach is based on a graph search algorithm. A relational data structure is used to represent a truss structure. There are four types of entities: units, faces, edges, and vertices. There are contain/contained relationships for every pair of entity types, as well as in-contact relationships between faces. A best-first algorithm constitutes the core of the planner. The cost function in the current implementation corresponds to a combination of the rigidity of the intermediate structures and the total distance to be traversed by the agent executing the assembly tasks.

Homem De Mello, L. S.↗

NASA NTRS1991

Validating system-level error recovery for spacecraft

The system-level software onboard a spacecraft is responsible for recovery from communication, thermal, power, and computer-health anomalies that may occur. The recovery must occur without disrupting any critical scientific or engineering activity that is executing at the time of the error. Thus, the error-recovery software may have to execute concurrently with the ongoing acquisition of scientific data or with spacecraft maneuvers. This paper provides a technique by which the rules that constrain the concurrent execution of these processes can be modeled in a graph. An algorithm is described that uses this model to validate that the constraints hold for all concurrent executions of the error-recovery softwave with the softwave that controls the science and engineering events on the spacecraft.

Lutz, Robyn R.↗

NASA NTRS1993

Constraint checking during error recovery

The system-level software onboard a spacecraft is responsible for recovery from communication, power, thermal, and computer-health anomalies that may occur. The recovery must occur without disrupting any critical scientific or engineering activity that is executing at the time of the error. Thus, the error-recovery software may have to execute concurrently with the ongoing acquisition of scientific data or with spacecraft maneuvers. This work provides a technique by which the rules that constrain the concurrent execution of these processes can be modeled in a graph. An algorithm is described that uses this model to validate that the constraints hold for all concurrent executions of the error-recovery software with the software that controls the science and engineering activities of the spacecraft. The results are applicable to a variety of control systems with critical constraints on the timing and ordering of the events they control.

Lutz, Robyn R.↗

NASA NTRS1996

Dataflow Design Tool: User's Manual

The Dataflow Design Tool is a software tool for selecting a multiprocessor scheduling solution for a class of computational problems. The problems of interest are those that can be described with a dataflow graph and are intended to be executed repetitively on a set of identical processors. Typical applications include signal processing and control law problems. The software tool implements graph-search algorithms and analysis techniques based on the dataflow paradigm. Dataflow analyses provided by the software are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool provides performance optimization through the inclusion of artificial precedence constraints among the schedulable tasks. The user interface and tool capabilities are described. Examples are provided to demonstrate the analysis, scheduling, and optimization functions facilitated by the tool.

Jones, Robert L., III↗

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

ATM↗

NASA NTRS2000

JavaGenes: Evolving Graphs with Crossover

Genetic algorithms usually use string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. All runs were executed by cycle-scavagging on networked workstations using the Condor batch processing system. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. The algorithm has greater difficulty with somewhat larger circuits, suggesting that directed graphs (circuits) are more difficult to evolve than undirected graphs (molecules), although necessary differences in the crossover operator may also explain the results. In principle, JavaGenes should be able to evolve other graph-representable systems, such as transportation networks, metabolic pathways, and computer networks. However, large graphs evolve significantly slower than smaller graphs, presumably because the space-of-all-graphs explodes combinatorially with graph size. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, the genotype-phenotype translation step, common in genetic algorithm work, is eliminated.

Globus, Al↗

NASA NTRS1993

A dataflow analysis tool for parallel processing of algorithms

A graph-theoretic design process and software tool is presented for selecting a multiprocessing scheduling solution for a class of computational problems. The problems of interest are those that can be described using a dataflow graph and are intended to be executed repetitively on a set of identical parallel processors. Typical applications include signal processing and control law problems. Graph analysis techniques are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool is shown to facilitate the application of the design process to a given problem.

Jones, Robert L., III↗

NASA NTRS1990

Partitioning sparse matrices with eigenvectors of graphs

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.

Pothen, Alex↗

NASA NTRS1990

Strategies for concurrent processing of complex algorithms in data driven architectures

Performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in data flow architectures are discussed. Applications include real-time implementation of control and signal processing algorithms where performance is required to be highly predictable. The mapping of algorithms onto the specified class of data flow architectures is realized by a marked graph model called algorithm to architecture mapping model (ATAMM). Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of resource (computing element) requirements. A systematic design procedure is described for generating operating conditions for predictable performance both with and without resource constraints. An ATAMM simulator is used to test and validate the performance prediction by the design procedure. Experiments on a three resource testbed provide verification of the ATAMM model and the design procedure.

Som, Sukhamoy↗

NASA NTRS2005

A Constraint-Based Planner for Data Production

This paper presents a graph-based backtracking algorithm designed to support constrain-tbased planning in data production domains. This algorithm performs backtracking at two nested levels: the outer- backtracking following the structure of the planning graph to select planner subgoals and actions to achieve them and the inner-backtracking inside a subproblem associated with a selected action to find action parameter values. We show this algorithm works well in a planner applied to automating data production in an ecological forecasting system. We also discuss how the idea of multi-level backtracking may improve efficiency of solving semi-structured constraint problems.

Pang, Wanlin↗

NASA NTRSDate not supplied

Towards Sheaf Theoretic Analyses for Delay Tolerant Networking

The goal of Delay Tolerant Networking (DTN) is to take a collection of heterogeneous, disparate connections between satellites, space assets, ground stations, and ground infrastructure and bring it together into a cohesive, functioning overlay network. Depending on the systems being considered, one can find links with a one-way light time exceeding minutes (and hours),periodic links which can sometimes be predicted by orbital mechanics, and restrictions based on the variety of capabilities built into these systems. These characteristics preclude traditional network models and routing techniques and have classically led to either rigid routing tables or purely probabilistic models. As the deeper underlying structures remain unknown, development of more DTN-optimized algorithms has lacked the necessary foundation. In a continuation of previous work, the goal of this paper is to identify and study these fundamental structures that exist in delay tolerant networks (DTN), with a focus on space networks. The current routing methodology has been to use contact graph routing (CGR) algorithms. CGR models a series of known contacts as a static graph. For CGR to work, this graph must be globally consistent and must have an accurate picture of the network. Because this is a globally controlled structure, there is little room for flexibility in the event of changes to the network which would naturally occur as the network grows. As a response to the desire for flexibility as the network changes, we introduced the mathematical structure known as sheaves to DTNs last year. The tag-line for sheaves is that they are a mathematically precise way of gluing local data together into unique global data. Thus, sheaves lend extra power to traditional models(and routing algorithms) by taking additional information and merging it, in as consistent a manner as possible, with the representation itself. The clearest example of how Earth-bound networks exhibit behavior that is “sheafy” is link state routers, which build a local-to-global picture of their network by gluing local information together into a global network, exactly as a sheaf would do. For routing within delay tolerant networks to truly exploit this structure, a deeper structure than a graph is required. In this paper, we develop sheaves that can work over directed graphs such as temporal flow networks, we construct a sheaf representation for Dijkstra’s algorithm, and we outline a construction for routing sheaves capable of modeling multicast scenarios. Finally, there is a section of future work suggesting follow-on research.

Robert Short↗

NASA NTRS1985

Mesh-connected processor arrays for the transitive closure problem

The main purpose in this paper is to lay a theoretical foundation for the design of mesh-connected processor arrays for the transitive closure problem. Using a simple path-algebraic formulation of the problem and observing its similarity to certain well-known smoothing problems that occur in digital signal processing, it is shown how to draw upon existing techniques from the signal processing literature to derive regular iterative algorithms for determining the transitive closure of the graph. The regular iterative algorithms that are derived using these considerations, are then analyzed and synthesized on mesh-connected processor arrays. Among the vast number of mesh-connected processor arrays that can be designed using this unified approach, the systolic arrays reported in the literature for this problem are shown to be special cases.

Rao, S. K.↗

NASA NTRS1994

Weighted graph based ordering techniques for preconditioned conjugate gradient methods

We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.

Clift, Simon S.↗

NASA NTRS1992

Robot path planning for space-truss assembly

Construction, repair, and maintenance of space-based structures will require extensive planning of operations in order to effectively carry out these tasks. The path planning algorithm described here is a general approach to generating paths that guarantee collision avoidance for a single chain nonredundant or redundant robot. The algorithm uses a graph search of feasible points in position space, followed by a local potential field method that guarantees collision avoidance among objects, structures, and the robot arm as well as conformance to joint limit constraints. This algorithm is novel in its computation of goal attractive potential fields in Cartesian space, and computation of obstacle repulsive fields in robot joint space. These effects are combined to generate robot motion. Computation is efficiently implemented through the computation of the robot arm Jacobian and not the full inverse arm kinematics. These planning algorithms have been implemented and evaluated using existing space-truss designs, and are being integrated into the RPI-CIRSSE Testbed environment.

Muenger, Rolf↗

NASA NTRS1990

Method for concurrent execution of primitive operations by dynamically assigning operations based upon computational marked graph and availability of data

Computationally complex primitive operations of an algorithm are executed concurrently in a plurality of functional units under the control of an assignment manager. The algorithm is preferably defined as a computationally marked graph contianing data status edges (paths) corresponding to each of the data flow edges. The assignment manager assigns primitive operations to the functional units and monitors completion of the primitive operations to determine data availability using the computational marked graph of the algorithm. All data accessing of the primitive operations is performed by the functional units independently of the assignment manager.

Stoughton, John W.↗

NASA NTRS1994

Graph-Based Dynamic Assignment Of Multiple Processors

Algorithm-to-architecture mapping model (ATAMM) is strategy minimizing time needed to periodically execute graphically described, data-driven application algorithm on multiple data processors. Implemented as operating system managing flow of data and dynamically assigns nodes of graph to processors. Predicts throughput versus number of processors available to execute given application algorithm. Includes rules ensuring application algorithm represented by graph executed periodically without deadlock and in shortest possible repetition time. ATAMM proves useful in maximizing effectiveness of parallel computing systems.

Hayes, Paul J.↗