Flight Test Results of a Distributed Merging Algorithm for Autonomous UAS Operations
Explore the source record for details and available documents.
Andrew Peters↗
SEARCH · Search NASA
Results for “distributed 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.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
A NASA Perspective on Quantum Computing: Algorithmic Opportunities and Challenges
In the last couple of decades, the world has seen several stunning instances of quantum algorithms that provably outperform the best classical algorithms. For most problems, however, it is currently unknown whether quantum algorithms can provide an advantage, and if so how to design quantum algorithms that realize such advantages. Today, classical heuristics are used to solve many of the most challenging computational problems arising in the practical world, algorithms that have been shown to be effective empirically but have not been mathematically proven to outperform other approaches. With the advent of quantum advantage, the ability of current quantum hardware to do certain computations beyond the ability of even that largest supercomputers, we have an unprecedented opportunity to explore heuristic quantum algorithms. The next few years will be exciting as empirical testing of quantum heuristic algorithms becomes more and more feasible. The talk will begin overview of the NASA QuAIL team’s ongoing quantum computing investigations, and then focus on both near-term and longer term algorithms for optimization, including distributed algorithms.
quantum computing↗
Generating Dominating Sets Using Locally Defined Centrality Measures
The dominating set problem has many practical applications but is well-known to be NP-hard. Therefore, there is a need for efficient heuristic algorithms, especially in applications such as ad hoc wireless networks. Most distributed algorithms proposed in the literature assume that each node has knowledge of the network structure. We propose a distributed heuristic algorithm that uses two rounds of communication, and where each node has only local information, both in terms of network structure and dominating set assignment. First, each node calculates a local centrality measure to determine whether it is part of the dominating set D. The second round guarantees D is a dominating set by adding any non-dominated nodes. We compare several centrality measures and show that the Shapley centrality, derived from the Shapley value in game theory, is theoretically motivated and performs well in practice on several synthetic and real-world networks.
Network↗
Efficient Parallel Algorithm For Direct Numerical Simulation of Turbulent Flows
A distributed algorithm for a high-order-accurate finite-difference approach to the direct numerical simulation (DNS) of transition and turbulence in compressible flows is described. This work has two major objectives. The first objective is to demonstrate that parallel and distributed-memory machines can be successfully and efficiently used to solve computationally intensive and input/output intensive algorithms of the DNS class. The second objective is to show that the computational complexity involved in solving the tridiagonal systems inherent in the DNS algorithm can be reduced by algorithm innovations that obviate the need to use a parallelized tridiagonal solver.
Moitra, Stuti↗
Distributed state-space generation of discrete-state stochastic models
High-level formalisms such as stochastic Petri nets can be used to model complex systems. Analysis of logical and numerical properties of these models of ten requires the generation and storage of the entire underlying state space. This imposes practical limitations on the types of systems which can be modeled. Because of the vast amount of memory consumed, we investigate distributed algorithms for the generation of state space graphs. The distributed construction allows us to take advantage of the combined memory readily available on a network of workstations. The key technical problem is to find effective methods for on-the-fly partitioning, so that the state space is evenly distributed among processors. In this paper we report on the implementation of a distributed state-space generator that may be linked to a number of existing system modeling tools. We discuss partitioning strategies in the context of Petri net models, and report on performance observed on a network of workstations, as well as on a distributed memory multi-computer.
Ciardo, Gianfranco↗
Improving Search Algorithms by Using Intelligent Coordinates
We consider algorithms that maximize a global function G in a distributed manner, using a different adaptive computational agent to set each variable of the underlying space. Each agent eta is self-interested; it sets its variable to maximize its own function g (sub eta). Three factors govern such a distributed algorithm's performance, related to exploration/exploitation, game theory, and machine learning. We demonstrate how to exploit alI three factors by modifying a search algorithm's exploration stage: rather than random exploration, each coordinate of the search space is now controlled by a separate machine-learning-based player engaged in a noncooperative game. Experiments demonstrate that this modification improves simulated annealing (SA) by up to an order of magnitude for bin packing and for a model of an economic process run over an underlying network. These experiments also reveal interesting small-world phenomena.
Wolpert, David H.↗
Distributed Augmentation, Hypersweeps, and Branch Decomposition of Contour Trees for Scientific Exploration
Contour trees describe the topology of level sets in scalar fields and are widely used in topological data analysis and visualization. A main challenge of utilizing contour trees for large-scale scientific data is their computation at scale using highperformance computing. To address this challenge, recent work has introduced distributed hierarchical contour trees for distributed computation and storage of contour trees. However, effective use of these distributed structures in analysis and visualization requires subsequent computation of geometric properties and branch decomposition to support contour extraction and exploration. In this work, we introduce distributed algorithms for augmentation, hypersweeps, and branch decomposition that enable parallel computation of geometric properties, and support the use of distributed contour trees as query structures for scientific exploration. Finally, we evaluate the parallel performance of these algorithms and apply them to identify and extract important contours for scientific visualization.
97 MATHEMATICS AND COMPUTING↗
Distributed topology control algorithm for multihop wireless netoworks
We present a network initialization algorithmfor wireless networks with distributed intelligence. Each node (agent) has only local, incomplete knowledge and it must make local decisions to meet a predefined global objective. Our objective is to use power control to establish a topology based onthe relative neighborhood graph which has good overall performance in terms of power usage, low interference, and reliability.
topology control distributed algorithm wireless ne↗
Digital image centering. II
Digital image centering algorithms were compared in a test involving microdensitometer raster scans of a refractor parallax series consisting of 22 stars on 26 plates. The highest accuracy in determining stellar image positions was provided by an algorithm which involved fitting of a symmetric Gaussian curve and a flat background to the image marginal density distributions. Algorithms involving transmission marginals instead of density marginals were found to be less accurate. The repeatability and computational efficiency of the digital image centering technique were also studied.
Auer, L. H.↗
Distributed Pressure Sensing for Enabling Self-Aware Autonomous Aerial Vehicles
Autonomous aerial transportation will be a fixture of future robotic societies, simultaneously requiring more stringent safety requirements and fewer resources for characterization than current commercial air transportation. More robust, adaptable, self-state estimation will be necessary to create such autonomous systems. We present a modular, scalable, distributed pressure sensing skin for aerodynamic state estimation of a large, flexible aerostructure. This skin used a network of 22 nodes that performed in-situ computation and communication of data collected from 74 pressure sensors, which were embedded into the skin panels of an ultra-lightweight 14-foot wingspan made from commutable, lattice-based subcomponents, and tested at NASA Langley Research Center's 14X22 wind tunnel. The density of the pressure sensors allowed for the use of a novel distributed algorithm to generate estimates of the wing lift contribution that were more accurate than the direct integration of the pressure distribution over the wing surface.
Daniel Cellucci↗
Neural networks and MIMD-multiprocessors
Two artificial neural network models are compared. They are the Hopfield Neural Network Model and the Sparse Distributed Memory model. Distributed algorithms for both of them are designed and implemented. The run time characteristics of the algorithms are analyzed theoretically and tested in practice. The storage capacities of the networks are compared. Implementations are done using a distributed multiprocessor system.
Vanhala, Jukka↗
Local Estimators for Spacecraft Formation Flying
A formation estimation architecture for formation flying builds upon the local information exchange among multiple local estimators. Spacecraft formation flying involves the coordination of states among multiple spacecraft through relative sensing, inter-spacecraft communication, and control. Most existing formation flying estimation algorithms can only be supported via highly centralized, all-to-all, static relative sensing. New algorithms are needed that are scalable, modular, and robust to variations in the topology and link characteristics of the formation exchange network. These distributed algorithms should rely on a local information-exchange network, relaxing the assumptions on existing algorithms. In this research, it was shown that only local observability is required to design a formation estimator and control law. The approach relies on breaking up the overall information-exchange network into sequence of local subnetworks, and invoking an agreement-type filter to reach consensus among local estimators within each local network. State estimates were obtained by a set of local measurements that were passed through a set of communicating Kalman filters to reach an overall state estimation for the formation. An optimization approach was also presented by means of which diffused estimates over the network can be incorporated in the local estimates obtained by each estimator via local measurements. This approach compares favorably with that obtained by a centralized Kalman filter, which requires complete knowledge of the raw measurement available to each estimator.
Fathpour, Nanaz↗
Streaming Matching and Edge Cover in Practice
Graph algorithms with polynomial space and time requirements often become infeasible for massive graphs with billions of edges or more. State-of-the-art approaches therefore employ approximate serial, parallel, and distributed algorithms to tackle these challenges. However, such approaches require storing the entire graph in memory and thus need access to costly computing resources such as clusters and supercomputers. In this paper, we present practical streaming approaches for solving massive graph problems using limited memory for two prototypical graph problems: maximum weighted matching and minimum weighted edge cover. For matching, we conduct a thorough computational study on two of the semi-streaming algorithms including a recent breakthrough result that achieves a $1/(2+\varepsilon)$-approximation of the weight while using $O( n \log W /\epsilon)$ memory (here $n$ is the number of vertices and $W$ is the maximum edge weight), designed by Paz and Schwartzman [SODA, 2017]. Empirically, we show that the semi-streaming algorithms produce matchings whose weight is close to the best $1/2$-approximate offline algorithm while requiring less time and an order-of-magnitude less memory. For minimum weighted edge cover, we develop three novel semi-streaming algorithms. Two of these algorithms require a single pass through the input graph, require $O(n \log n)$ memory, and provide a 2-approximation guarantee on the objective. We also leverage a relationship between approximate maximum weighted matching and approximate minimum weighted edge cover to develop a two-pass $3/2+\epsilon$-approximate algorithm with the memory requirement of Paz and Schwartzman's semi-streaming matching algorithm. These streaming approaches are compared against the state-of-the-art 3/2-approximate offline algorithm. The semi-streaming matching and the novel edge cover algorithms proposed in this paper can process graphs with several billions of edges in under 30 minutes using 6 GB of memory, which is at least an order of magnitude improvement from the offline (non-streaming) algorithms. For the largest graph, the best alternative offline parallel approximation algorithm (GPA+ROMA) could not finish in three hours even while employing hundreds of processors and 1 TB of memory. We also demonstrate an application of the semi-streaming algorithm by computing a matching using linearly bounded memory on item intersection graphs derived from three machine learning datasets, whereas the existing offline algorithms could not complete on one of these datasets since their memory requirements exceeded 1TB.
Ferdous, S M.↗
Assessment of Envelope- and Machine Learning-Based Electrical Fault Type Detection Algorithms for Electrical Distribution Grids
This study introduces envelope- and machine learning (ML)-based electrical fault type detection algorithms for electrical distribution grids, advancing beyond traditional logic-based methods. The proposed detection model involves three stages: anomaly area detection, ML-based fault presence detection, and ML-based fault type detection. Initially, an envelope-based detector identifying the anomaly region was improved to handle noisier power grid signals from meters. The second stage acts as a switch, detecting the presence of a fault among four classes: normal, motor, switching, and fault. Finally, if a fault is detected, the third stage identifies specific fault types. This study explored various feature extraction methods and evaluated different ML algorithms to maximize prediction accuracy. The performance of the proposed algorithms is tested in an emulated software–hardware electrical grid testbed using different sample rate meters/relays, such as SEL735, SEL421, SEL734, SEL700GT, and SEL351S near and far from an inverter-based photovoltaic array farm. The performance outcomes demonstrate the proposed model’s robustness and accuracy under realistic conditions.
24 POWER TRANSMISSION AND DISTRIBUTION↗
The Micro-Pulse Lidar Network (MPLNET): A Federated Network of Micro-pulse Lidars and AERONET Sunphotometers
We present the formation of a new global-ground based eye-safe lidar network, the NASA Micro-Pulse Lidar Network (MPLNET). The aim of MPLNET is to acquire long- term observations of aerosol and cloud vertical profiles at unique geographic sites within the NASA Aerosol Robotic Network (AERONET). MPLNET utilizes standard instrumentation and data processing algorithms for efficient network operations and direct comparison of data between each site. The micro-pulse lidar is eye-safe, compact, and commercially available, and most easily allows growth of the network without sacrificing standardized instrumentation goals. Network growth follows a federated approach, pioneered by AERONET, wherein independent research groups may join MPLNET with their own instrument and site. MPLNET sites produce not only vertical profile data, but also column-averaged products already available from AERONET (aerosol optical depth, sky radiance, size distributions). Algorithms are presented for each MPLNET data product. Real-time Level 1 data products (next-day) include daily lidar signal images from the surface to -2Okm, and Level 1.5 aerosol extinction profiles at times co-incident with AERONET observations. Quality assured Level 2 aerosol extinction profiles are generated after screening the Level 1.5 results and removing bad data. Level 3 products include continuous day/night aerosol extinction profiles, and are produced using Level 2 calibration data. Rigorous uncertainty calculations are presented for all data products. Analysis of MPLNET data show the MPL and our analysis routines are capable of successfully retrieving aerosol profiles, with the strenuous accounting of uncertainty necessary for accurate interpretation of the results.
Welton, Ellsworth J.↗
Virtual Agents-Based Attack-Resilient Distributed Control for Islanded AC Microgrid
Due to its dependence on a communication network, distributed secondary control of microgrids is susceptible to denial-of-service (DoS) attacks in channel shutdown mode, which may negatively impact the network connectivity and thus deteriorate the coordination and power sharing among distributed generators (DGs). Honeypot is a common method for cyber deception by introducing fake targets. However, in the context of microgrid, the misleading information spread by honeypots will also impact the system performance. This paper proposes an attack-resilient distributed control for AC microgrids utilizing virtual agents (VAs) to counteract both DoS edge and node attacks. The VAs are designed to not impact the system’s steady state during normal operation but to share information among neighboring real agents and serve as dummy targets for DoS attacks. The control with VAs is implemented by a primal-dual gradient based distributed algorithm to efficiently obtain a practical solution for voltage/frequency regulation and power sharing. The simulation results on a 4-DG test system and a modified IEEE 34-bus system show that 1) VAs do not impact the normal functionality of the test system, and 2) deploying VAs can enhance the resilience of the microgrid control against DoS edge and node attacks.
24 POWER TRANSMISSION AND DISTRIBUTION↗
Simulation of rotor blade element turbulence
A piloted, motion-based simulation of Sikorsky's Black Hawk helicopter was used as a platform for the investigation of rotorcraft responses to vertical turbulence. By using an innovative temporal and geometrical distribution algorithm that preserved the statistical characteristics of the turbulence over the rotor disc, stochastic velocity components were applied at each of twenty blade-element stations. This model was implemented on NASA Ames' Vertical Motion Simulator (VMS), and ten test pilots were used to establish that the model created realistic cues. The objectives of this research included the establishment of a simulation-technology basis for future investigation into real-time turbulence modeling. This goal was achieved; our extensive additions to the rotor model added less than a 10 percent computational overhead. Using a VAX 9000 computer the entire simulation required a cycle time of less than 12 msec. Pilot opinion during this simulation was generally quite favorable. For low speed flight the consensus was that SORBET (acronym for title) was better than the conventional body-fixed model, which was used for comparison purposes, and was determined to be too violent (like a washboard). For high speed flight the pilots could not identify differences between these models. These opinions were something of a surprise because only the vertical turbulence component on the rotor system was implemented in SORBET. Because of the finite-element distribution of the inputs, induced outputs were observed in all translational and rotational axes. Extensive post-simulation spectral analyses of the SORBET model suggest that proper rotorcraft turbulence modeling requires that vertical atmospheric disturbances not be superimposed at the vehicle center of gravity but, rather, be input into the rotor system, where the rotor-to-body transfer function severely attenuates high frequency rotorcraft responses.
Mcfarland, R. E.↗
A geometry package for generation of input data for a three-dimensional potential-flow program
The preparation of geometric data for input to three-dimensional potential flow programs was automated and simplified by a geometry package incorporated into the NASA Langley version of the 3-D lifting potential flow program. Input to the computer program for the geometry package consists of a very sparse set of coordinate data, often with an order of magnitude of fewer points than required for the actual potential flow calculations. Isolated components, such as wings, fuselages, etc. are paneled automatically, using one of several possible element distribution algorithms. Curves of intersection between components are calculated, using a hybrid curve-fit/surface-fit approach. Intersecting components are repaneled so that adjacent elements on either side of the intersection curves line up in a satisfactory manner for the potential-flow calculations. Many cases may be run completely (from input, through the geometry package, and through the flow calculations) without interruption. Use of the package significantly reduces the time and expense involved in making three-dimensional potential flow calculations.
Halsey, N. D.↗