SEARCH · Engineering Papers

Results for “randomized 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 649 records · Page 36

All sources NASA NTRS DOE OSTI

DOE OSTI2016

SU-G-JeP3-05: Geometry Based Transperineal Ultrasound Probe Positioning for Image Guided Radiotherapy

Purpose: The use of ultrasound (US) imaging in radiotherapy is not widespread, primarily due to the need for skilled operators performing the scans. Automation of probe positioning has the potential to remove this need and minimize operator dependence. We introduce an algorithm for obtaining a US probe position that allows good anatomical structure visualization based on clinical requirements. The first application is on 4D transperineal US images of prostate cancer patients. Methods: The algorithm calculates the probe position and orientation using anatomical information provided by a reference CT scan, always available in radiotherapy workflows. As initial test, we apply the algorithm on a CIRS pelvic US phantom to obtain a set of possible probe positions. Subsequently, five of these positions are randomly chosen and used to acquire actual US volumes of the phantom. Visual inspection of these volumes reveal if the whole prostate, and adjacent edges of bladder and rectum are fully visualized, as clinically required. In addition, structure positions on the acquired US volumes are compared to predictions of the algorithm. Results: All acquired volumes fulfill the clinical requirements as specified in the previous section. Preliminary quantitative evaluation was performed on thirty consecutive slices of two volumes, on which the structures are easily recognizable. The mean absolute distances (MAD) between actual anatomical structure positions and positions predicted by the algorithm were calculated. This resulted in MAD of 2.4±0.4 mm for prostate, 3.2±0.9 mm for bladder and 3.3±1.3 mm for rectum. Conclusion: Visual inspection and quantitative evaluation show that the algorithm is able to propose probe positions that fulfill all clinical requirements. The obtained MAD is on average 2.9 mm. However, during evaluation we assumed no errors in structure segmentation and probe positioning. In future steps, accurate estimation of these errors will allow for better evaluation of the achieved accuracy.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2018

Stochastic basis adaptation and spatial domain decomposition for partial differential equations with random coefficients

We present a novel approach for high-dimensional stochastic partial differential equations that decomposes the computational domain into smaller disjoint subdomains and reduces the random dimension in each subdomain to save computational costs. The proposed approach combines spatial domain decomposition and stochastic basis adaptation in each subdomain. We adapt the stochastic basis in each subdomain such that the local solution has a low-dimensional random space representation. To compute the stochastic solution in each subdomain, we use the Neumann-Neumann algorithm, where we first estimate the interface solution and then evaluate the interior solution in each subdomain using the interface solution as a boundary condition. The interior solutions in each subdomain are computed independently of each other, which reduces the operation count from $\approx O(N^\alpha)$ to $\approx O(M^\alpha),$ where $N$ is the total number of degrees of freedom, $M$ is the number of degrees of freedom in each subdomain, and the exponent $\alpha>1$ depends on the uncertainty quantification method used. In addition, the localized nature of solutions makes the proposed approach highly parallelizable. We illustrate the accuracy and efficiency of the approach for a steady-state diffusion equation with a random space-dependent diffusion coefficient.

uncertainty quantification, basis adaptation↗

DOE OSTI2018

A new technique for luminosity measurement using 3D pixel modules in the ATLAS IBL detector

The Insertable B-Layer (IBL) is the innermost layer of the ATLAS tracking system. It consists of planar pixel modules in the central region and 3D pixel modules at the two extremities. We use the longitudinal cluster-size distributions in 3D modules of the IBL to determine the number of pixel clusters per bunch crossing produced by primary charged particles in randomly triggered collision events, and to suppress the associated backgrounds. This Pixel-Cluster-Counting algorithm can provide both bunch-integrated and bunch-by-bunch relative-luminosity measurements, and thereby contribute independent constraints to the understanding and the evaluation of the systematic uncertainties that dominate the luminosity determination at the ATLAS experiment.

3D Pixel Module↗

DOE OSTI2023

Spoofing Cross-Entropy Measure in Boson Sampling

Cross-entropy (XE) measure is a widely used benchmark to demonstrate quantum computational advantage from sampling problems, such as random circuit sampling using superconducting qubits and boson sampling (BS). We present a heuristic classical algorithm that attains a better XE than the current BS experiments in a verifiable regime and is likely to attain a better XE score than the near-future BS experiments in a reasonable running time. The key idea behind the algorithm is that there exist distributions that correlate with the ideal BS probability distribution and that can be efficiently computed. The correlation and the computability of the distribution enable us to postselect heavy outcomes of the ideal probability distribution without computing the ideal probability, which essentially leads to a large XE. Our method scores a better XE than the recent Gaussian BS experiments when implemented at intermediate, verifiable system sizes. Much like current state-of-the-art experiments, we cannot verify that our spoofer works for quantum-advantage-size systems. However, we demonstrate that our approach works for much larger system sizes in fermion sampling, where we can efficiently compute output probabilities. Finally, we provide analytic evidence that the classical algorithm is likely to spoof noisy BS efficiently.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

DOE OSTI2023

Resilient Communication Scheme for Distributed Decision of Interconnecting Networks of Microgrids

Networking of microgrids can provide the operational flexibility needed for the increasing number of DERs deployed at the distribution level and supporting end-use demand when there is loss of the bulk power system. But, networked microgrids are vulnerable to cyber-physical attacks and faults due to the complex interconnections. As such, it is necessary To design resilient control systems to support the operations of networked microgrids in responses to cyber-physical attacks and faults. This paper introduces a resilient communication scheme for interconnecting multiple microgrids to support critical demand, in which the interconnection decision can be made distributedly by each microgrid controller even in the presence of cyberattacks to some communication links or microgrid controllers. This scheme blends a randomized peer-to-peer communication network for exchanging information among controllers and resilient consensus algorithms for achieving reliable interconnection agreement. The network of 6 microgrids divided from a modified 123-node test distribution feeder is used to demonstrate the effectiveness of the proposed resilient communication scheme.

Vu, Thanh Long↗

DOE OSTI2024

Distributed Automatic Generation Control Considering DPV Using T&D Dynamic Co-Simulation

The increasing adoption of distributed energy resources (DERs) over the last decade warrants a reconsideration of control of generation resources. This paper proposes a distributed Automatic Generation Control (AGC) using transmission-and-distribution (T&D) dynamic co-simulation framework for the efficient DPV frequency regulation services. The co-simulation framework allows AGC units to exchange the information for distributed AGC, based on their adopted communication network topology. As a result, a cost-effective automatic generation control is achieved with DPV and conventional generators. The proposed distributed AGC is based on the gossip algorithm in which the neighboring AGC units share the relevant local information with each other and updates their share of AGC regulation signal. Distributed photovoltaics (DPV) unit contribute to AGC response based on their headroom capacity via DER aggregators. The algorithm is tested on IEEE-14 bus transmission system under conditions of generation failure and random load variation to observe effective frequency regulations service offered by DPVs and other AGC units. The study shows that DPV can effectively participate in AGC with the proposed distributed control framework.

automatic generation control↗

DOE OSTI2018

Parallel Markov Random Fields for Image Segmentation (PMRF-IS) v1.0

This software performs multi-label segmentation of 2D/3D images. It is highly accurate, results rely on use of an Markov random field (MRF) formulation. It runs in both shared and distributed memory parallel modes. MRF algorithms are powerful tools in image analysis to explore contextual information of data.

Heinemann, Colleen↗

DOE OSTI2022

Proposal for a quantum random number generator using coherent light and a non-classical observable

The prototype quantum random number (random bit) generator (QRNG) consists of one photon at a time falling on a 50:50 beam splitter followed by random detection in one or the other output beams due to the irreducible probabilistic nature of quantum mechanics. Due to the difficulties in producing single photons on demand, in practice, pulses of weak coherent (laser) light are used. In this paper, we take a different approach, one that uses moderate coherent light. It is shown that a QRNG can be implemented by performing photon-number parity measurements. For moderate coherent light, the probabilities of obtaining even or odd parity in photon counts are 0.5 each. Photon counting with single-photon resolution can be performed through use of a cascade of beam splitters and single-photon detectors, as was done recently in a photon-number parity-based interferometry experiment involving coherent light. We highlight the point that unlike most quantum-based random number generators, our proposal does not require the use of classical de-biasing algorithms or post-processing of the generated bit sequence.

Gerry, Christopher C.↗

DOE OSTI2022

Data Science and Machine Learning for Genome Security

This report describes research conducted to use data science and machine learning methods to distinguish targeted genome editing versus natural mutation and sequencer machine noise. Genome editing capabilities have been around for more than 20 years, and the efficiencies of these techniques has improved dramatically in the last 5+ years, notably with the rise of CRISPR-Cas technology. Whether or not a specific genome has been the target of an edit is concern for U.S. national security. The research detailed in this report provides first steps to address this concern. A large amount of data is necessary in our research, thus we invested considerable time collecting and processing it. We use an ensemble of decision tree and deep neural network machine learning methods as well as anomaly detection to detect genome edits given either whole exome or genome DNA reads. The edit detection results we obtained with our algorithms tested against samples held out during training of our methods are significantly better than random guessing, achieving high F1 and recall scores as well as with precision overall.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2019

Computational optical physical unclonable function

A system or method for encryption of data includes a light source, a random optical element and a light detection element. The light source is arranged to transmit an input data signal to the random optical element. The light source is incident on the random optical element such that the input data signal is randomly scattered by the random optical element to generate an image at on the detector disposed at an output of the random optical element. The image received by the detector is applied to a compressive sensing algorithm to generate a transfer function. The transfer function defines a relationship between the input data signal and the image to enable estimation and reconstruction of the input data signal.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Computational optical physical unclonable function

Birch, Gabriel Carlisle↗

DOE OSTI2016

On the asymptotic distribution of block-modified random matrices

We study random matrices acting on tensor product spaces which have been transformed by a linear block operation. Using operator-valued free probability theory, under some mild assumptions on the linear map acting on the blocks, we compute the asymptotic eigenvalue distribution of the modified matrices in terms of the initial asymptotic distribution. Moreover, using recent results on operator-valued subordination, we present an algorithm that computes, numerically but in full generality, the limiting eigenvalue distribution of the modified matrices. Our analytical results cover many cases of interest in quantum information theory: we unify some known results and we obtain new distributions and various generalizations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2014

Augmenting Microarray Data with Literature-Based Knowledge to Enhance Gene Regulatory Network Inference

Gene regulatory networks are a crucial aspect of systems biology in describing molecular mechanisms of the cell. Various computational models rely on random gene selection to infer such networks from microarray data. While incorporation of prior knowledge into data analysis has been deemed important, in practice, it has generally been limited to referencing genes in probe sets and using curated knowledge bases. We investigate the impact of augmenting microarray data with semantic relations automatically extracted from the literature, with the view that relations encoding gene/protein interactions eliminate the need for random selection of components in non-exhaustive approaches, producing a more accurate model of cellular behavior. A genetic algorithm is then used to optimize the strength of interactions using microarray data and an artificial neural network fitness function. The result is a directed and weighted network providing the individual contribution of each gene to its target. For testing, we used invasive ductile carcinoma of the breast to query the literature and a microarray set containing gene expression changes in these cells over several time points. Our model demonstrates significantly better fitness than the state-of-the-art model, which relies on an initial random selection of genes. Comparison to the component pathways of the KEGG Pathways in Cancer map reveals that the resulting networks contain both known and novel relationships. The p53 pathway results were manually validated in the literature. 60% of nonKEGG relationships were supported (74% for highly weighted interactions). The method was then applied to yeast data and our model again outperformed the comparison model. Our results demonstrate the advantage of combining gene interactions extracted from the literature in the form of semantic relations with microarray analysis in generating contribution-weighted gene regulatory networks. This methodology can make a significant contribution to understanding the complex interactions involved in cellular behavior and molecular physiology.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2025

Automated Construction of Artificial Lattice Structures with Designer Electronic States

Manipulating matter with a scanning tunneling microscope (STM) enables the creation of atomically defined artificial structures that host designer quantum states. However, the time-consuming nature of the manipulation process, coupled with the sensitivity of the STM tip, constrains the exploration of diverse configurations and limits the size of the designed features. In this study, we present a reinforcement learning (RL)-based framework for creating artificial structures by spatially manipulating carbon monoxide (CO) molecules on a copper substrate by using the STM tip. The automated workflow combines molecule detection and manipulation, employing deep-learning-based object detection to locate CO molecules and linear assignment algorithms to allocate these molecules to designated target sites. We initially perform molecule maneuvering based on randomized parameter sampling for sample bias, tunneling current set point, and manipulation speed. This data set is then structured into an action trajectory used to train an RL agent. The model is subsequently deployed on the STM for real-time fine-tuning of the manipulation parameters during structure construction. Our approach incorporates path-planning protocols coupled with active drift compensation to enable atomically precise fabrication of structures with significantly reduced human input while realizing larger-scale artificial lattices with the desired electronic properties. Furthermore, using our approach, we demonstrate the automated construction of an extended artificial graphene lattice and confirm the existence of a characteristic Dirac point in its electronic structure. Further challenges regarding the RL-based structural assembly scalability are discussed.

Algorithms↗

DOE OSTI2018

Transport in Random Media With Inhomogeneous Mixing Statistics

The Levermore-Pomraning (LP) model has been investigated for use in implicit Monte Carlo (IMC) algorithms to describe thermal photon transport computations in stochastically mixed cells with material energy coupling. For purely absorbing non-emitting materials, the LP-model is known to predict the exact material averaged fluxes when the mixing statistics are Markovian. In the presence of scattering or reemmission, or if the mixing is non-Markovian, the LP-model is approximate and has greatly diminished accuracy for optically thick, highly scattering materials. Nevertheless, the model enables a robust extension of the simple atomic mix approximation to accommodate spatial correlation effects through well characterized parameters such as mean chord lengths. In this work, we construct exact analytical solutions of the LP-equations for piecewise constant spatial variation of the material chord lengths. It is not possible in general to obtain closed form solutions when the chord lengths are continuous functions of space, although we briefly examine special conditions under which this is feasible. However, by allowing an arbitrarily fine spatial segmentation of the medium it is possible to construct highly refined solutions to fit desired spatial chord length profiles. Material volume fractions that are consistent with the chord lengths are first constructed by solving the associated Chapmann-Kolmogorov equations and applied to obtain the material averaged fluxes in two settings: when the materials are purely absorbing, and when scattering is present in rod model geometry. Illustrative numerical results for the volume fractions and material averaged fluxes are obtained by implementing the algorithms in MATLAB for spatially linear and quadratic variations of the chord lengths.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

DOE OSTI2017

Sampling-Based Motion Planning Algorithms for Replanning and Spatial Load Balancing

The common theme of this dissertation is sampling-based motion planning with the two key contributions being in the area of replanning and spatial load balancing for robotic systems. Here, we begin by recalling two sampling-based motion planners: the asymptotically optimal rapidly-exploring random tree (RRT*), and the asymptotically optimal probabilistic roadmap (PRM*). We also provide a brief background on collision cones and the Distributed Reactive Collision Avoidance (DRCA) algorithm. The next four chapters detail novel contributions for motion replanning in environments with unexpected static obstacles, for multi-agent collision avoidance, and spatial load balancing. First, we show improved performance of the RRT* when using the proposed Grandparent-Connection (GP) or Focused-Refinement (FR) algorithms. Next, the Goal Tree algorithm for replanning with unexpected static obstacles is detailed and proven to be asymptotically optimal. A multi-agent collision avoidance problem in obstacle environments is approached via the RRT*, leading to the novel Sampling-Based Collision Avoidance (SBCA) algorithm. The SBCA algorithm is proven to guarantee collision free trajectories for all of the agents, even when subject to uncertainties in the knowledge of the other agents’ positions and velocities. Given that a solution exists, we prove that livelocks and deadlock will lead to the cost to the goal being decreased. We introduce a new deconfliction maneuver that decreases the cost-to-come at each step. This new maneuver removes the possibility of livelocks and allows a result to be formed that proves convergence to the goal configurations. Finally, we present a limited range Graph-based Spatial Load Balancing (GSLB) algorithm which fairly divides a non-convex space among multiple agents that are subject to differential constraints and have a limited travel distance. The GSLB is proven to converge to a solution when maximizing the area covered by the agents. The analysis for each of the above mentioned algorithms is confirmed in simulations.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Distribution of centrality measures on undirected random networks via the cavity method

The Katz centrality of a node in a complex network is a measure of the node’s importance as far as the flow of information across the network is concerned. For ensembles of locally tree-like undirected random graphs, this observable is a random variable. Its full probability distribution is of interest but difficult to handle analytically because of its “global” character and its definition in terms of a matrix inverse. Leveraging a fast Gaussian Belief Propagation-Cavity algorithm to solve linear systems on tree-like structures, we show that i) the Katz centrality of a single instance can be computed recursively in a very fast way, and ii) the probability P ( K ) that a random node in the ensemble of undirected random graphs has centrality K satisfies a set of recursive distributional equations, which can be analytically characterized and efficiently solved using a population dynamics algorithm. We test our solution on ensembles of Erdős-Rényi and Scale Free networks in the locally tree-like regime, with excellent agreement. The analytical distribution of centrality for the configuration model conditioned on the degree of each node can be employed as a benchmark to identify nodes of empirical networks with over- and underexpressed centrality relative to a null baseline. We also provide an approximate formula based on a rank- 1 projection that works well if the network is not too sparse, and we argue that an extension of our method could be efficiently extended to tackle analytical distributions of other centrality measures such as PageRank for directed networks in a transparent and user-friendly way.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2022

Construction of Women’s All-Around Speed Skating Event Performance Prediction Model and Competition Strategy Analysis Based on Machine Learning Algorithms

Introduction Accurately predicting the competitive performance of elite athletes is an essential prerequisite for formulating competitive strategies. Women’s all-around speed skating event consists of four individual subevents, and the competition system is complex and challenging to make accurate predictions on their performance. Objective The present study aims to explore the feasibility and effectiveness of machine learning algorithms for predicting the performance of women’s all-around speed skating event and provide effective training and competition strategies. Methods The data, consisting of 16 seasons of world-class women’s all-around speed skating competition results, used in the present study came from the International Skating Union (ISU). According to the competition rules, distinct features are filtered using lasso regression, and a 5,000 m race model and a medal model are built using a fivefold cross-validation method. Results The results showed that the support vector machine model was the most stable among the 5,000 m race and the medal models, with the highest AUC (0.86, 0.81, respectively). Furthermore, 3,000 m points are the main characteristic factors that decide whether an athlete can qualify for the final. The 11th lap of the 5,000 m, the second lap of the 500 m, and the fourth lap of the 1,500 m are the main characteristic factors that affect the athlete’s ability to win medals. Conclusion Compared with logistic regression, random forest, K-nearest neighbor, naive Bayes, neural network, support vector machine is a more viable algorithm to establish the performance prediction model of women’s all-around speed skating event; excellent performance in the 3,000 m event can facilitate athletes to advance to the final, and athletes with outstanding performance in the 500 m event are more likely competitive for medals.

Liu, Meng↗