SEARCH · Search NASA

Results for “tree search”

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 73 records · Page 4

All sources NASA NTRS DOE OSTI

NASA NTRS1987

The mechanisms of temporal inference

The properties of a temporal language are determined by its constituent elements: the temporal objects which it can represent, the attributes of those objects, the relationships between them, the axioms which define the default relationships, and the rules which define the statements that can be formulated. The methods of inference which can be applied to a temporal language are derived in part from a small number of axioms which define the meaning of equality and order and how those relationships can be propagated. More complex inferences involve detailed analysis of the stated relationships. Perhaps the most challenging area of temporal inference is reasoning over disjunctive temporal constraints. Simple forms of disjunction do not sufficiently increase the expressive power of a language while unrestricted use of disjunction makes the analysis NP-hard. In many cases a set of disjunctive constraints can be converted to disjunctive normal form and familiar methods of inference can be applied to the conjunctive sub-expressions. This process itself is NP-hard but it is made more tractable by careful expansion of a tree-structured search space.

Fox, B. R.↗

NASA NTRS1994

Decision-Tree Program

IND computer program introduces Bayesian and Markov/maximum-likelihood (MML) methods and more-sophisticated methods of searching in growing trees. Produces more-accurate class-probability estimates important in applications like diagnosis. Provides range of features and styles with convenience for casual user, fine-tuning for advanced user or for those interested in research. Consists of four basic kinds of routines: data-manipulation, tree-generation, tree-testing, and tree-display. Written in C language.

Buntine, Wray↗

NASA NTRS2009

Using Decision Trees to Detect and Isolate Simulated Leaks in the J-2X Rocket Engine

The goal of this work was to use data-driven methods to automatically detect and isolate faults in the J-2X rocket engine. It was decided to use decision trees, since they tend to be easier to interpret than other data-driven methods. The decision tree algorithm automatically "learns" a decision tree by performing a search through the space of possible decision trees to find one that fits the training data. The particular decision tree algorithm used is known as C4.5. Simulated J-2X data from a high-fidelity simulator developed at Pratt & Whitney Rocketdyne and known as the Detailed Real-Time Model (DRTM) was used to "train" and test the decision tree. Fifty-six DRTM simulations were performed for this purpose, with different leak sizes, different leak locations, and different times of leak onset. To make the simulations as realistic as possible, they included simulated sensor noise, and included a gradual degradation in both fuel and oxidizer turbine efficiency. A decision tree was trained using 11 of these simulations, and tested using the remaining 45 simulations. In the training phase, the C4.5 algorithm was provided with labeled examples of data from nominal operation and data including leaks in each leak location. From the data, it "learned" a decision tree that can classify unseen data as having no leak or having a leak in one of the five leak locations. In the test phase, the decision tree produced very low false alarm rates and low missed detection rates on the unseen data. It had very good fault isolation rates for three of the five simulated leak locations, but it tended to confuse the remaining two locations, perhaps because a large leak at one of these two locations can look very similar to a small leak at the other location.

Schwabacher, Mark A.↗

NASA NTRS1990

Evolutionary tree reconstruction

It is described how Minimum Description Length (MDL) can be applied to the problem of DNA and protein evolutionary tree reconstruction. If there is a set of mutations that transform a common ancestor into a set of the known sequences, and this description is shorter than the information to encode the known sequences directly, then strong evidence for an evolutionary relationship has been found. A heuristic algorithm is described that searches for the simplest tree (smallest MDL) that finds close to optimal trees on the test data. Various ways of extending the MDL theory to more complex evolutionary relationships are discussed.

Cheeseman, Peter↗

NASA NTRS2011

Spatial Query for Planetary Data

Science investigators need to quickly and effectively assess past observations of specific locations on a planetary surface. This innovation involves a location-based search technology that was adapted and applied to planetary science data to support a spatial query capability for mission operations software. High-performance location-based searching requires the use of spatial data structures for database organization. Spatial data structures are designed to organize datasets based on their coordinates in a way that is optimized for location-based retrieval. The particular spatial data structure that was adapted for planetary data search is the R+ tree.

Shams, Khawaja S.↗

NASA NTRS2021

Estimating Bare Earth in Sparse Boreal Forests With WorldView Stereo Imagery

Circumboreal forests are currently experiencing rapid climate warming which is altering their structure, productivity, and status as a carbon sink. Very-high resolution (VHR, <2 m) stereo derived digital surface models are available to monitor these forests, but, a similar resolution digital terrain model (DTM) is required to extract information about tree height, which is often used to estimate carbon content. To our knowledge, no openly available VHR DTM currently exists. To address this need, we developed approaches to extract DTMs by filtering VHR stereo point clouds (PCs) in sparse canopies of Alaska. Our evaluation consisted of two stereo processing methods with three PC search radii, at six different tree canopy cover (TCC) intervals. We found VHR DTMs were robust for estimating bare ground at TCC intervals less than 40% with vertical errors <1.6 m using airborne small footprint light detection and ranging (LiDAR) as reference.

Christopher S R Neigh↗

NASA NTRS2021

Estimating Bare Earth in Sparse Boreal Forests With WorldView Stereo Imagery

Christopher S. R. Neigh↗

NASA NTRS2004

Finding Minimum-Power Broadcast Trees for Wireless Networks

Some algorithms have been devised for use in a method of constructing tree graphs that represent connections among the nodes of a wireless communication network. These algorithms provide for determining the viability of any given candidate connection tree and for generating an initial set of viable trees that can be used in any of a variety of search algorithms (e.g., a genetic algorithm) to find a tree that enables the network to broadcast from a source node to all other nodes while consuming the minimum amount of total power. The method yields solutions better than those of a prior algorithm known as the broadcast incremental power algorithm, albeit at a slightly greater computational cost.

Arabshahi, Payman↗

NASA NTRS2011

NASA's Global Change Master Directory: Discover and Access Earth Science Data Sets, Related Data Services, and Climate Diagnostics

NASA's Global Change Master Directory provides the scientific community with the ability to discover, access, and use Earth science data, data-related services, and climate diagnostics worldwide. The GCMD offers descriptions of Earth science data sets using the Directory Interchange Format (DIF) metadata standard; Earth science related data services are described using the Service Entry Resource Format (SERF); and climate visualizations are described using the Climate Diagnostic (CD) standard. The DIF, SERF and CD standards each capture data attributes used to determine whether a data set, service, or climate visualization is relevant to a user's needs. Metadata fields include: title, summary, science keywords, service keywords, data center, data set citation, personnel, instrument, platform, quality, related URL, temporal and spatial coverage, data resolution and distribution information. In addition, nine valuable sets of controlled vocabularies have been developed to assist users in normalizing the search for data descriptions. An update to the GCMD's search functionality is planned to further capitalize on the controlled vocabularies during database queries. By implementing a dynamic keyword "tree", users will have the ability to search for data sets by combining keywords in new ways. This will allow users to conduct more relevant and efficient database searches to support the free exchange and re-use of Earth science data. http://gcmd.nasa.gov/

Aleman, Alicia↗

NASA NTRS2018

Silhouette-Informed Trajectory Generation Through a Wire Maze for Small UAS

Current rapidly-exploring random tree (RRT) algorithms rely on proximity query packages that often include collision checkers, tolerance verification, and distance computation algorithms for the generation of safe paths. In this paper, we broaden the information available to the path-planning algorithm by incorporating silhouette information of nearby obstacles in conflict. A silhouette-informed tree (SIT) is generated through the flight-safe region of a wire maze for a single unmanned aerial system (UAS). The silhouette is used to extract local geometric information of nearby obstacles and provide path alternatives around these obstacles. Thus, focusing the search for the generation of new tree branches near these obstacles, and decreasing the number of samples required to explore the narrow corridors within the wire maze. The SIT is then processed to extract a path that connects the initial location of the UAS with the goal, reduce the number of line segments in this path if possible, and smooth the resulting path using Pythagorean Hodograph Bezier curves. To ensure that the smoothed path remains in the flight-safe region of the configuration space, a tolerance verification algorithm for Bezier curves and convex polytopes in three dimensions is proposed. Lastly, temporal specifications are imposed on the smoothed path in the shape of an arbitrary speed profile.

Puig-Navarro, Javier↗

NASA NTRS2006

Onboard Classifiers for Science Event Detection on a Remote Sensing Spacecraft

Typically, data collected by a spacecraft is downlinked to Earth and pre-processed before any analysis is performed. We have developed classifiers that can be used onboard a spacecraft to identify high priority data for downlink to Earth, providing a method for maximizing the use of a potentially bandwidth limited downlink channel. Onboard analysis can also enable rapid reaction to dynamic events, such as flooding, volcanic eruptions or sea ice break-up. Four classifiers were developed to identify cryosphere events using hyperspectral images. These classifiers include a manually constructed classifier, a Support Vector Machine (SVM), a Decision Tree and a classifier derived by searching over combinations of thresholded band ratios. Each of the classifiers was designed to run in the computationally constrained operating environment of the spacecraft. A set of scenes was hand-labeled to provide training and testing data. Performance results on the test data indicate that the SVM and manual classifiers outperformed the Decision Tree and band-ratio classifiers with the SVM yielding slightly better classifications than the manual classifier.

classification↗

NASA NTRS1997

Abstract Datatypes in PVS

PVS (Prototype Verification System) is a general-purpose environment for developing specifications and proofs. This document deals primarily with the abstract datatype mechanism in PVS which generates theories containing axioms and definitions for a class of recursive datatypes. The concepts underlying the abstract datatype mechanism are illustrated using ordered binary trees as an example. Binary trees are described by a PVS abstract datatype that is parametric in its value type. The type of ordered binary trees is then presented as a subtype of binary trees where the ordering relation is also taken as a parameter. We define the operations of inserting an element into, and searching for an element in an ordered binary tree; the bulk of the report is devoted to PVS proofs of some useful properties of these operations. These proofs illustrate various approaches to proving properties of abstract datatype operations. They also describe the built-in capabilities of the PVS proof checker for simplifying abstract datatype expressions.

Owre, Sam↗

NASA NTRS1990

Unstructured mesh methods for CFD

Mesh generation methods for Computational Fluid Dynamics (CFD) are outlined. Geometric modeling is discussed. An advancing front method is described. Flow past a two engine Falcon aeroplane is studied. An algorithm and associated data structure called the alternating digital tree, which efficiently solves the geometric searching problem is described. The computation of an initial approximation to the steady state solution of a given poblem is described. Mesh generation for transient flows is described.

Peraire, J.↗

NASA NTRS1990

Real-time image processing II; Proceedings of the Meeting, Orlando, FL, Apr. 16-18, 1990

The present conference discusses topics in the fields of feature extraction and implementation, filter and correlation algorithms, optical correlators, high-level algorithms, and digital image processing for ranging and remote driving. Attention is given to a nonlinear filter derived from topological image features, IR image segmentation through iterative thresholding, orthogonal subspaces for correlation masking, composite filter trees and image recognition via binary search, and features of matrix-coherent optical image processing. Also discussed are multitarget tracking via hybrid joint transform correlator, binary joint Fourier transform correlator considerations, global image processing operations on parallel architectures, real-time implementation of a differential range finder, and real-time binocular stereo range and motion detection.

Juday, Richard D.↗

NASA NTRS2002

PEGASUS 5: An Automated Pre-Processor for Overset-Grid CFD

An all new, automated version of the PEGASUS software has been developed and tested. PEGASUS provides the hole-cutting and connectivity information between overlapping grids, and is used as the final part of the grid generation process for overset-grid computational fluid dynamics approaches. The new PEGASUS code (Version 5) has many new features: automated hole cutting; a projection scheme for fixing gaps in overset surfaces; more efficient interpolation search methods using an alternating digital tree; hole-size optimization based on adding additional layers of fringe points; and an automatic restart capability. The new code has also been parallelized using the Message Passing Interface standard. The parallelization performance provides efficient speed-up of the execution time by an order of magnitude, and up to a factor of 30 for very large problems. The results of three example cases are presented: a three-element high-lift airfoil, a generic business jet configuration, and a complete Boeing 777-200 aircraft in a high-lift landing configuration. Comparisons of the computed flow fields for the airfoil and 777 test cases between the old and new versions of the PEGASUS codes show excellent agreement with each other and with experimental results.

Suhs, Norman E.↗

NASA NTRS1990

Model authoring system for fail safe analysis

The Model Authoring System is a prototype software application for generating fault tree analyses and failure mode and effects analyses for circuit designs. Utilizing established artificial intelligence and expert system techniques, the circuits are modeled as a frame-based knowledge base in an expert system shell, which allows the use of object oriented programming and an inference engine. The behavior of the circuit is then captured through IF-THEN rules, which then are searched to generate either a graphical fault tree analysis or failure modes and effects analysis. Sophisticated authoring techniques allow the circuit to be easily modeled, permit its behavior to be quickly defined, and provide abstraction features to deal with complexity.

Sikora, Scott E.↗

NASA NTRS1992

STARBASE: Database software for the automated plate scanner

The Automated Plate Scanner (APS) of the University of Minnesota, a unique high speed 'flying spot' laser scanner, is currently being used to scan and digitize the 936 O and E plate pairs of the first epoch Palomar Sky Survey. The resultant database will be used to produce a catalog of approximately a billion stars and several million galaxies. The authors describe the ongoing development of a dedicated APS database management system which will be made available to the astronomical community via INTERNET. A specialized DBMS called STARBASE has been written to provide fast access to the hundreds of millions of images collected by the APS. This system provides an initial reduction mode for parameterizing APS images and classifying image types using a novel set of neural network image classifiers. A second analysis mode, which will be that commonly used by the general user, provides for searches of the database which may be constrained by any combination of physical and positional parameters. Through the use of pointer hash trees, the system has been optimized for extremely fast positional searches using either right ascension and declination on the sky or linear X and Y positions on the POSS field. In addition to fast data retrieval, the system provides a graphical interface for displaying scatter plots or histograms of the collected data. In addition, a specialized image display system is being developed to allow the user to view densitometric data for all objects classified as extended by the neural network system. Finally, STARBASE has a flexible programmable interface which allows other programs to access information in the database. This allows users to write applications suited to their particular needs to process APS data.

Odewahn, S. C.↗

NASA NTRS1988

Design principles for an interactive program derivation system

The main design principles of an interactive program transformation system called FOCUS are outlined. Its important characteristics are its human-oriented deduction techniques based replacement, emphasis on small search spaces, and the use of a tree structure to organize program derivations. The tree structure presents to the user a static picture of the derivation process and promotes flexibility in the development of derivations. The system keeps track of dependencies between different parts of derivations, and records the derivation activity for later use in automatic replay.

Reddy, Uday S.↗