Engineering Papers⌕ Search

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.

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

At least 289 records · Page 16
All sourcesNASA NTRSDOE OSTI
NASA NTRS1973

Properties of heuristic search strategies

A directed graph is used to model the search space of a state space representation with single input operators, an AND/OR is used for problem reduction representations, and a theorem proving graph is used for state space representations with multiple input operators. These three graph models and heuristic strategies for searching them are surveyed. The completeness, admissibility, and optimality properties of search strategies which use the evaluation function f = (1 - omega)g = omega(h) are presented and interpreted using a representation of the search process in the plane. The use of multiple output operators to imply dependent successors, and thus obtain a formalism which includes all three types of representations, is discussed.

Vanderbrug, G. J.↗
NASA NTRS1976

An analysis of the errors associated with the determination of atmospheric temperature from atmospheric pressure and density data

A graph was developed for relating delta T/T, the relative uncertainty in atmospheric temperature T, to delta p/p, the relative uncertainty in the atmospheric pressure p, for situations, when T is derived from the slope of the pressure-height profile. A similar graph relates delta T/T to delta roh/rho, the relative uncertainty in the atmospheric density rho, for those cases when T is derived from the downward integration of the density-height profile. A comparison of these two graphs shows that for equal uncertainties in the respective basic parameters, p or rho, smaller uncertainties in the derived temperatures are associated with density-height rather than with pressure-height data. The value of delta T/T is seen to depend not only upon delta p or delta rho, and to a small extent upon the value of T or the related scale height H, but also upon the inverse of delta h, the height increment between successive observations of p or rho. In the case of pressure-height data, delta T/T is dominated by 1/delta h for all values of delta h; for density-height data, delta T/T is dominated by delta rho/rho for delta h smaller than about 5 km. In the case of T derived from density-height data, this inverse relationship between delta T/T and delta h applies only for large values of delta h, that is, for delta h 35 km. No limit exists in the fineness of usable height resolution of T which may be derived from densities, while a fine height resolution in pressure-height data leads to temperature with unacceptably large uncertainties.

Minzner, R. A.↗
NASA NTRS1979

Review and revocation of access privileges distributed through capabilities

The problems of review and revocation of access privileges are presented in the context of the systems that use capabilities for the long-term distribution of access privileges. The approach to solve these two problems requires that a capability propagation graph be maintained in memory spaces associated with subjects (e.g., domains, processes, etc.) that make copies of the respective capability; the graph remains inaccessible to those subjects, however. Parallel processes of the operating system update the graph as the system runs. It is noted that the most important application of the above mechanisms may prove to be the possibility of implementing a capability-based system in which the capability representation is short.

Gligor, V. D.↗
NASA NTRS1980

On deadlock detection in distributed systems

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in a previous study Menasce and Muntz (1979). In this paper, it is shown that the distributed protocol is incorrect, and possible remedies are presented. However, the distributed protocol remains impractical because 'condensations' of 'transaction-wait-for' graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol.

Gligor, V. D.↗
NASA NTRS1984

Augmenting computer networks

Three methods of augmenting computer networks by adding at most one link per processor are discussed: (1) A tree of N nodes may be augmented such that the resulting graph has diameter no greater than 4log sub 2((N+2)/3)-2. Thi O(N(3)) algorithm can be applied to any spanning tree of a connected graph to reduce the diameter of that graph to O(log N); (2) Given a binary tree T and a chain C of N nodes each, C may be augmented to produce C so that T is a subgraph of C. This algorithm is O(N) and may be used to produce augmented chains or rings that have diameter no greater than 2log sub 2((N+2)/3) and are planar; (3) Any rectangular two-dimensional 4 (8) nearest neighbor array of size N = 2(k) may be augmented so that it can emulate a single step shuffle-exchange network of size N/2 in 3(t) time steps.

Bokhari, S. H.↗
NASA NTRS1988

A machine vision identification technique from range images

An orientation-independent identification technique from three-dimensional surface maps or range images is developed. Given the range image of an object, it is decomposed into orientation-independent patches using the sign of Gaussian curvature. A relational graph is then set up such that a node represents a patch and an edge represents the adjacency of two patches. The identification of the object is achieved by matching its graph representation to a number of model graphs. The matching is performed by employing the best-first search strategy. Examples of real range images show the merit of the technique.

Kehtarnavaz, N.↗
NASA NTRS1990

Spatial scales of cirrus cloud properties

Research in studying the spatial scales of the cirrus, used data collected during the flight legs of the NCAR Sabreliner aircraft on four days during the FIRE Cirrus IFO to study the spatial scales of the cirrus, and will concentrate on the scales of horizontal wind. The spatial scales of the cloud features can be described by power spectra (or spectral density graphs) and cumulative variance graphs. The cumulative variance graphs were created by first using a Fast Fourier Transform (FFT) to create variance spectra. The variances were then summed in a cumulative fashion from the largest scalelengths (wavelengths) to the smallest. No detrending was done to the original data, and no smoothing or averaging was done to the spectral points. All the spectral points were included. This means that the values of the first five to ten spectral points of the large scalelengths should only be considered to be qualitatively correct. The cumulative variance at smaller scalelengths should be correct because a more accurate representation of the variance at the larger scalelengths should only redistribute the energy amongst the larger scalelengths.

Hein, Paul F.↗
NASA NTRS1990

Using minimal spanning trees to compare the reliability of network topologies

Graph theoretic methods are applied to compute the reliability for several types of networks of moderate size. The graph theory methods used are minimal spanning trees for networks with bi-directional links and the related concept of strongly connected directed graphs for networks with uni-directional links. A comparison is conducted of ring networks and braided networks. The case is covered where just the links fail and the case where both links and nodes fail. Two different failure modes for the links are considered. For one failure mode, the link no longer carries messages. For the other failure mode, the link delivers incorrect messages. There is a description and comparison of link-redundancy versus path-redundancy as methods to achieve reliability. All the computations are carried out by means of a fault tree program.

Leister, Karen J.↗
NASA NTRS1990

Quantifying fault recovery in multiprocessor systems

Various aspects of reliable computing are formalized and quantified with emphasis on efficient fault recovery. The mathematical model which proves to be most appropriate is provided by the theory of graphs. New measures for fault recovery are developed and the value of elements of the fault recovery vector are observed to depend not only on the computation graph H and the architecture graph G, but also on the specific location of a fault. In the examples, a hypercube is chosen as a representative of parallel computer architecture, and a pipeline as a typical configuration for program execution. Dependability qualities of such a system is defined with or without a fault. These qualities are determined by the resiliency triple defined by three parameters: multiplicity, robustness, and configurability. Parameters for measuring the recovery effectiveness are also introduced in terms of distance, time, and the number of new, used, and moved nodes and edges.

Malek, Miroslaw↗
NASA NTRS1991

Robust fault diagnosis of physical systems in operation

Ideas are presented and demonstrated for improved robustness in diagnostic problem solving of complex physical systems in operation, or operative diagnosis. The first idea is that graceful degradation can be viewed as reasoning at higher levels of abstraction whenever the more detailed levels proved to be incomplete or inadequate. A form of abstraction is defined that applies this view to the problem of diagnosis. In this form of abstraction, named status abstraction, two levels are defined. The lower level of abstraction corresponds to the level of detail at which most current knowledge-based diagnosis systems reason. At the higher level, a graph representation is presented that describes the real-world physical system. An incremental, constructive approach to manipulating this graph representation is demonstrated that supports certain characteristics of operative diagnosis. The suitability of this constructive approach is shown for diagnosing fault propagation behavior over time, and for sometimes diagnosing systems with feedback. A way is shown to represent different semantics in the same type of graph representation to characterize different types of fault propagation behavior. An approach is demonstrated that threats these different behaviors as different fault classes, and the approach moves to other classes when previous classes fail to generate suitable hypotheses. These ideas are implemented in a computer program named Draphys (Diagnostic Reasoning About Physical Systems) and demonstrated for the domain of inflight aircraft subsystems, specifically a propulsion system (containing two turbofan systems and a fuel system) and hydraulic subsystem.

Abbott, Kathy Hamilton↗
NASA NTRS1990

Mapping unstructured grid problems to the connection machine

We present a highly parallel graph mapping technique that enables one to solve unstructured grid problems on massively parallel computers. Many implicit and explicit methods for solving discretizated partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The time spent communicating can limit the high performance promised by massively parallel computing. To eliminate this bottleneck, we map the graph of the irregular problem to the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. We show that, in comparison to a naive assignment of processors, our heuristic mapping algorithm significantly reduces the communication time on the Connection Machine, CM-2.

Hammond, Steven W.↗
NASA NTRS1990

Assembly planning based on subassembly extraction

A method is presented for the automatic determination of assembly partial orders from a liaison graph representation of an assembly through the extraction of preferred subassemblies. In particular, the authors show how to select a set of tentative subassemblies by decomposing a liaison graph into a set of subgraphs based on feasibility and difficulty of disassembly, how to evaluate each of the tentative subassemblies in terms of assembly cost using the subassembly selection indices, and how to construct a hierarchical partial order graph (HPOG) as an assembly plan. The method provides an approach to assembly planning by identifying spatial parallelism in assembly as a means of constructing temporal relationships among assembly operations and solves the problem of finding a cost-effective assembly plan in a flexible environment. A case study of the assembly planning of a mechanical assembly is presented.

Lee, Sukhan↗
NASA NTRS1992

Planning Assembly Of Large Truss Structures In Outer Space

Report dicusses developmental algorithm used in systematic planning of sequences of operations in which large truss structures assembled in outer space. Assembly sequence represented by directed graph called "assembly graph", in which each arc represents joining of two parts or subassemblies. Algorithm generates assembly graph, working backward from state of complete assembly to initial state, in which all parts disassembled. Working backward more efficient than working forward because it avoids intermediate dead ends.

De Mello, Luiz S. Homem↗
NASA NTRS1991

Application of machine learning and expert systems to Statistical Process Control (SPC) chart interpretation

Statistical Process Control (SPC) charts are one of several tools used in quality control. Other tools include flow charts, histograms, cause and effect diagrams, check sheets, Pareto diagrams, graphs, and scatter diagrams. A control chart is simply a graph which indicates process variation over time. The purpose of drawing a control chart is to detect any changes in the process signalled by abnormal points or patterns on the graph. The Artificial Intelligence Support Center (AISC) of the Acquisition Logistics Division has developed a hybrid machine learning expert system prototype which automates the process of constructing and interpreting control charts.

Shewhart, Mark↗
NASA NTRS1992

Evaluation of force-torque displays for use with space station telerobotic activities

Recent experiments which addressed Space Station remote manipulation tasks found that tactile force feedback (reflecting forces and torques encountered at the end-effector through the manipulator hand controller) does not improve performance significantly. Subjective response from astronaut and non-astronaut test subjects indicated that force information, provided visually, could be useful. No research exists which specifically investigates methods of presenting force-torque information visually. This experiment was designed to evaluate seven different visual force-torque displays which were found in an informal telephone survey. The displays were prototyped in the HyperCard programming environment. In a within-subjects experiment, 14 subjects nullified forces and torques presented statically, using response buttons located at the bottom of the screen. Dependent measures included questionnaire data, errors, and response time. Subjective data generally demonstrate that subjects rated variations of pseudo-perspective displays consistently better than bar graph and digital displays. Subjects commented that the bar graph and digital displays could be used, but were not compatible with using hand controllers. Quantitative data show similar trends to the subjective data, except that the bar graph and digital displays both provided good performance, perhaps do to the mapping of response buttons to display elements. Results indicate that for this set of displays, the pseudo-perspective displays generally represent a more intuitive format for presenting force-torque information.

Hendrich, Robert C.↗
NASA NTRS1990

Solving unstructured grid problems on massively parallel computers

A highly parallel graph mapping technique that enables one to efficiently solve unstructured grid problems on massively parallel computers is presented. Many implicit and explicit methods for solving discretized partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The cost of this communication can negate the high performance promised by massively parallel computing. To eliminate this bottleneck, the graph of the irregular problem is mapped into the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. It is shown that using the heuristic mapping algorithm significantly reduces the communication time compared to a naive assignment of processes to processors.

Hammond, Steven W.↗
NASA NTRS1990

Assembly, disassembly and repair of large truss structures in space

This paper addresses the problem of planning assembly, disassembly and repair sequences for large truss structures in space. First, the AND/OR graph representation scheme for mechanical assemblies is reviewed and extended to truss structures. The assembly, disassembly and repair sequence planning problem is then formulated as a graph search problem using assembly's AND/OR graph and appropriate cost functions. The general search problem, which is known to be exponential, is simplified by taking advantage of the symmetries that exist in truss structures. General cost functions for truss assembly are discussed.

Desai, Rajiv S.↗
NASA NTRS1989

Generation of precedence relations for mechanical assemblies

Planning of assembly sequences is essential to the manufacturing system design process. Several methodologies have been proposed to represent all the feasible assembly sequences. In this thesis, three algorithms are presented to generate three sets of precedence relations based on all the infeasible assembly tasks, all the infeasible assembly states, and all the feasible assembly sequences, respectively. The equivalence of the resulting sets of precedence relations to the AND/OR graph is established. A new property, the real time property, of a representation of assembly sequences is defined and discussed. A representation of assembly sequences is said to have the real time property, if it is possible to generate the next assembly task by testing locally in the representation, and it will guarantee that the generated assembly task will not lead the assembly sequence to a dead end situation, in which no feasible assembly task can be performed any more. It is shown that the correctness and completeness of one representation can not guarantee the real time property of the representation. It is proven that the directed graph representation and the set of precedence relations based on all the infeasible assembly states have the real time property, while the AND/OR graph representation and the set of precedence relations based on all the infeasible assembly tasks do not have the real time property. Finally in the thesis, the PLEIDEAS system, a PLanning Environment for Integrated DEsign of Assembly Systems, is described and illustrated by an example.

Zhang, Hui↗