SEARCH · Search NASA

Results for “Monte Carlo 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 37 records · Page 2

All sources NASA NTRS DOE OSTI

NASA NTRS2015

Adaptive Stress Testing of Airborne Collision Avoidance Systems

This paper presents a scalable method to efficiently search for the most likely state trajectory leading to an event given only a simulator of a system. Our approach uses a reinforcement learning formulation and solves it using Monte Carlo Tree Search (MCTS). The approach places very few requirements on the underlying system, requiring only that the simulator provide some basic controls, the ability to evaluate certain conditions, and a mechanism to control the stochasticity in the system. Access to the system state is not required, allowing the method to support systems with hidden state. The method is applied to stress test a prototype aircraft collision avoidance system to identify trajectories that are likely to lead to near mid-air collisions. We present results for both single and multi-threat encounters and discuss their relevance. Compared with direct Monte Carlo search, this MCTS method performs significantly better both in finding events and in maximizing their likelihood.

Verification and Validation↗

NASA NTRSDate not supplied

Adaptive Stress Testing of Collision Avoidance Systems for Small UASs with Deep Reinforcement Learning

The next-generation Airborne Collision Avoidance System for smaller UASs (ACAS sXu) is currently being developed and tested by the Federal Aviation Administration (FAA) to provide detect-and-avoid capability for small unmanned aircraft operating beyond line-of-sight. Due to the complexity and safety-critical nature of the system, safety validation is important not only for the certification of the final system, but also for informing changes during the iterative development process. In this paper, we analyze a prototype of ACAS sXu in simulated aircraft encounters to discover scenarios of small near mid-air collisions (sNMACs), an important safety event in which two aircraft come closer than 50 feet horizontally and 15 feet vertically. Due to the size and complexity of the system as well as rarity of sNMAC events, traditional methods such as Monte Carlo testing often require informed setup and targeting to elicit failures. However, such a dependence on domain knowledge can be incompatible with the independent verification and validation (IV&V) process, the aim of which is to discover unforeseen issues. To address these challenges, we apply an accelerated validation method called adaptive stress testing (AST) to find the most likely sNMAC scenarios without reliance on system introspection. AST uses reinforcement learning to adapt the search towards the most promising areas of the search space as it progresses. We use a state-of-the-art deep reinforcement learning algorithm, proximate policy optimization, to more efficiently search the large and continuous state space. We find that this approach significantly improves the performance of AST compared to a prior approach based on Monte Carlo tree search. We perform experiments using AST to find sNMAC events under various encounter configurations, varying parameters pertaining to dynamics and coordination. Our experiments show AST to be very effective at finding sNMAC scenarios. We summarize our findings, presenting high-level categories of discovered sNMACs and specific examples of encounters in each category.

aircraft collision avoidance↗

DOE OSTI2024

Learning the stable and metastable phase diagram to accelerate the discovery of metastable phases of boron

Boron, an element of captivating chemical intricacy, has been surrounded by controversies ever since its discovery in 1808. The complexities of boron stem from its unique position between metals and insulators in the Periodic Table. Recent computational studies have shed light on some of the stable boron allotropes. However, the demand for multifunctionality necessitates the need to go beyond the stable phases into the realm of metastability and explore the potentially vast but elusive metastable phases of boron. Traditional search for stable phases of materials has focused on identifying materials with the lowest enthalpy. Here, we introduce a workflow that uses reinforcement learning coupled with decision trees, such as Monte Carlo tree search, to search for stable and metastable boron phases, with enthalpy as the objective. We discover new boron metastable phases and construct a phase diagram that locates their phase space (T, P) at different levels of metastability (ΔG) from the ground state and provides useful information on the domains of relative stability of the various stable and metastable boron phases.

42 ENGINEERING↗

DOE OSTI2025

Development and assessment of hierarchical multi-reward reinforcement learning based potential for silicene with state-of-the-art models

We develop a new interatomic force field for Silicene, a 2D material with a buckled hexagonal lattice structure with high polymorphism. We introduce new parameterizations of a Tersoff model using a hierarchical multi-reward reinforcement learning (RL) methodology coupled with a continuous Monte Carlo Tree Search optimization. Our model significantly outperforms existing methods by enhancing the accuracy of predictions for the structural and thermodynamic properties of seven silicene polymorphs-including structure, energy, equation of state, elasticity, and phonon dispersion-when compared to established models. We further make a comprehensive comparison of the various models in predicting the mechanical and thermal properties of silicene. We trace the origin of the improved performance to the description of the angular dependence in the bond-order term, suggesting that modifying the angular terms in short-range models is essential to capture the structural diversity in low dimensional systems.

2D materials↗

DOE OSTI2026

Hierarchical Reinforcement Learning of a Short-Range Bond-Order Potential for Silica: Analytic Embedding of Coordination with Classical Efficiency

Reinforcement learning (RL) has recently emerged as a data-efficient strategy to parametrize short-range interatomic potentials. Building on our past RL optimization of pairwise silica models, we extend the framework to a bond-order (Tersoff-type) potential that provides an analytic embedding of local coordination through a three-body term. A hierarchical RL workflow combining continuous-action Monte Carlo Tree Search and property-based rewards efficiently explores the 26-dimensional parameter space, sequentially optimizing lattice parameters, densities, angles, and cohesive energies of 21 silica polymorphs. The resulting models, Q-Tersoff and ML-Tersoff, reproduce the energetic ordering of low-energy phases and capture the angular correlations and amorphous structure factors of silica with improved fidelity over pairwise force fields, while remaining orders of magnitude faster than high-dimensional machine-learned potentials. Both models underperform for elastic constants and high-energy frameworks, delineating the limits of the current analytic form. The approach establishes a general and interpretable route to angle-aware, short-range potentials that bridge physics-based and machine-learned descriptions of silicate materials.

36 MATERIALS SCIENCE↗

DOE OSTI2026

Machine Learning an Ab-Initio Based Bond-Order Potential for Bismuthene

Bismuthene is a heavy 2D material whose strong spin–orbit coupling and recently observed single-element ferroelectricity have intensified interest in its structural, vibrational, and transport properties. Accurate modeling of these behaviors requires a short-range interatomic potential that can reproduce the underlying bonding physics at a fraction of the computational cost of first-principles methods. However, such a potential is currently unavailable. Here, in this work, we construct a Tersoff bond-order potential for β-bismuthene using a reinforcement-learning framework that integrates a continuous Monte Carlo Tree Search with a simplex-based local optimizer. The optimized parameter sets reproduce first-principles lattice constants, cohesive energy, the equation of state, elastic constants, and phonon dispersion. We validate the models by performing thermal-conductivity calculations and uniaxial fracture simulations our findings confirm the reliability of the resulting models across multiple thermomechanical regimes. Comparison of the three best solutions reveals how differences in pairwise interactions, angular terms, and bond-order behavior govern phonon features and mechanical responses. We demonstrate an interpretable and computationally efficient potential for bismuthene and demonstrate a general reinforcement-learning strategy for developing bond-order models in emerging 2D materials.

deformation↗

DOE OSTI2022

Multi-reward Reinforcement Learning Based Bond-Order Potential to Study Strain-Assisted Phase Transitions in Phosphorene

Here, we introduce a multi-reward reinforcement learning (RL) approach to train a flexible bond-order potential (BOP) for 2D phosphorene based on ab initio training data sets. Our approach is based on a continuous action space Monte Carlo tree search algorithm that is general and scalable and presents an efficient multiobjective optimization scheme for high-dimensional materials design problems. As a proof-of-concept, we deploy this scheme to parametrize multiple structural and dynamical properties of 2D phosphorene polymorphs. Our RL-trained BOP model adequately captures the structure, energetics, transformation barriers, equation of state, elastic constants, and phonon dispersions of various 2D P polymorphs. We use this model to probe the impact of temperature and strain rate on the phase transition from black (α-P) to blue phosphorene (β-P) through molecular dynamics simulations. A decrease in critical strain for this phase transition with increase in temperature is observed, and the underlying atomistic mechanisms are discussed.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2022

Machine learning overcomes human bias in the discovery of self-assembling peptides

Peptide materials have a wide array of functions, from tissue engineering and surface coatings to catalysis and sensing. Tuning the sequence of amino acids that comprise the peptide modulates peptide functionality, but a small increase in sequence length leads to a dramatic increase in the number of peptide candidates. Traditionally, peptide design is guided by human expertise and intuition and typically yields fewer than ten peptides per study, but these approaches are not easily scalable and are susceptible to human bias. Here, in this work, we introduce a machine learning workflow—AI-expert—that combines Monte Carlo tree search and random forest with molecular dynamics simulations to develop a fully autonomous computational search engine to discover peptide sequences with high potential for self-assembly. We demonstrate the efficacy of the AI-expert to efficiently search large spaces of tripeptides and pentapeptides. The predictability of AI-expert performs on par or better than our human experts and suggests several non-intuitive sequences with high self-assembly propensity, outlining its potential to overcome human bias and accelerate peptide discovery.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2023

Reinforcement learning based hybrid bond-order coarse-grained interatomic potentials for exploring mesoscale aggregation in liquid–liquid mixtures

Exploring mesoscopic physical phenomena has always been a challenge for brute-force all-atom molecular dynamics simulations. Although recent advances in computing hardware have improved the accessible length scales, reaching mesoscopic timescales is still a significant bottleneck. Coarse-graining of all-atom models allows robust investigation of mesoscale physics with a reduced spatial and temporal resolution but preserves desired structural features of molecules, unlike continuum-based methods. Here, we present a hybrid bond-order coarse-grained forcefield (HyCG) for modeling mesoscale aggregation phenomena in liquid–liquid mixtures. The intuitive hybrid functional form of the potential offers interpretability to our model, unlike many machine learning based interatomic potentials. We parameterize the potential with the continuous action Monte Carlo Tree Search (cMCTS) algorithm, a reinforcement learning (RL) based global optimizing scheme, using training data from all-atom simulations. The resulting RL-HyCG correctly describes mesoscale critical fluctuations in binary liquid–liquid extraction systems. cMCTS, the RL algorithm, accurately captures the mean behavior of various geometrical properties of the molecule of interest, which were excluded from the training set. The developed potential model along with the RL-based training workflow could be applied to explore a variety of other mesoscale physical phenomena that are typically inaccessible to all-atom molecular dynamics simulations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2022

An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2023

Top-down design of protein architectures with reinforcement learning

As a result of evolutionary selection, the subunits of naturally occurring protein assemblies often fit together with substantial shape complementarity to generate architectures optimal for function in a manner not achievable by current design approaches. We describe a “top-down” reinforcement learning–based design approach that solves this problem using Monte Carlo tree search to sample protein conformers in the context of an overall architecture and specified functional constraints. Cryo–electron microscopy structures of the designed disk-shaped nanopores and ultracompact icosahedra are very close to the computational models. The icosohedra enable very-high-density display of immunogens and signaling molecules, which potentiates vaccine response and angiogenesis induction. Our approach enables the top-down design of complex protein nanomaterials with desired system properties and demonstrates the power of reinforcement learning in protein design.

Science & Technology - Other Topics↗

DOE OSTI2022

tenzing

SAND2022-3576 O tenzing provides techniques for improving the performance of key applications and libraries. The program is specified as a directed acyclic graph of operations. It uses Monte-Carlo tree search to explore the design space of possible implementations and applies machine learning to the observed empirical performance to deliver design guidance to users. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

SciDAC↗

NASA NTRS2020

Adaptive Stress Testing: Finding Likely Failure Events with Reinforcement Learning

Finding the most likely path to a set of failure states is important to the analysis of safety-critical systems that operate over a sequence of time steps, such as aircraft collision avoidance systems and autonomous cars. In many applications such as autonomous driving, failures cannot be completely eliminated due to the complex stochastic environment in which the system operates.As a result, safety validation is not only concerned about whether a failure can occur, but also discovering which failures are most likely to occur. This article presents adaptive stress testing (AST), a framework for finding the most likely path to a failure event in simulation. We consider a general black box setting for partially observable and continuous-valued systems operating in an environment with stochastic disturbances. We formulate the problem as a Markov decision process and use reinforcement learning to optimize it. The approach is simulation-based and does not require internal knowledge of the system, making it suitable for black-box testing of large systems. We present different formulations depending on whether the state is fully observable or partially observable. In the latter case, we present a modified Monte Carlo tree search algorithm that only requires access to the pseudorandom number generator of the simulator to overcome partial observability. We also present an extension of the framework, called differential adaptive stress testing (DAST), that can find failures that occur in one system but not in another. This type of differential analysis is useful in applications such as regression testing, where we are concerned with finding areas of relative weakness compared to a baseline. We demonstrate the effectiveness of the approach on an aircraft collision avoidance application, where a prototype aircraft collision avoidance system is stress tested to find the most likely scenarios of near mid-air collision.

Verification and Validation↗

NASA NTRS2022

Scheduling For Urban Air Mobility Using Safe Learning

This work considers the scheduling problem for Urban Air Mobility (UAM) vehicles travelling between origin-destination pairs with both hard and soft trip deadlines. Each route is described by a discrete probability distribution over trip completion times (or delay) and over interarrival times of requests (or demand) for the route along with a fixed hard or soft deadline. Soft deadlines carry a cost that is incurred when the deadline is missed. An online, safe scheduler is developed that ensures that hard deadlines are never missed and that average cost of missing soft deadlines is minimized. The system is modelled as a Markov Decision Process (MDP) and safe model based learning is used to find the probabilistic distributions over route delays and demand. Monte Carlo Tree Search (MCTS) Earliest Deadline First (EDF) is used to safely explore the learned models in an online fashion and develop a near-optimal non-preemptive scheduling policy. These results are compared with Value Iteration (VI) and MCTS (Random) scheduling solutions.

Urban Air Mobility↗

NASA NTRSDate not supplied

Scheduling for Urban Air Mobility using Safe Learning

Urban Air Mobility↗

NASA NTRSDate not supplied

Battery State-of-Health Aware Path Planning for a Mars Rover

A rover mission consists of visiting waypoints to gather scientific samples based on set requirements. However, rovers face operational uncertainties during the mission, affecting the performance of its electrical and mechanical components and overall mission success. Hence, it is critical to have a decision-making framework that is aware of the health state of the components when planning the path of the vehicle. In particular, battery degradation, and consequently the battery State of Health (SOH), can affect the optimality of decisions made by the autonomous system in the long term. This paper presents a decision-making system that incorporates information on the energy drawn from the battery (based on the vehicle’s velocity), terrain conditions, and model-based prognostic modules to assess the impact on the battery’s state of charge (SoC). The decision-making system was formulated as a Markov Decision Process (MDP) to reach the goal destination by sending commands in a determined amount of time while maintaining the battery SoC within the policy stated. The MDP problem was programmed using the open-source framework POMDPs.jl, which has a variety of online and offline solvers. To solve the MDP problem online, we used Monte Carlo Tree Search (MCTS). Results from simulations demonstrate the effect that battery degradation and charging plans have on decision-making.

Prognostics↗

DOE OSTI2023

Monte Carlo Thought Search: Large Language Model Querying for Complex Scientific Reasoning in Catalyst Design

Discovering novel catalysts requires complex reasoning involving multiple chemical properties and resultant trade-offs, leading to a combinatorial growth in the search space. While large language models (LLM) have demonstrated novel capabilities for chemistry through complex instruction following capabilities and high quality reasoning, a goal-driven combinatorial search using LLMs has not been explored in detail. In this work, we present a Monte Carlo Tree Search-based approach that improves beyond state-of-the-art chain-of-thought prompting variants to augment scientific reasoning. We introduce two new reasoning datasets: 1) a curation of computational chemistry simulations, and 2) diverse questions written by catalysis researchers for reasoning about novel chemical conversion processes. We improve over the best baseline by 25.8\% and find that our approach can augment scientist's reasoning and discovery process with novel insights.\footnote{All resources will be publicly available upon publication.

Sprueill, Henry W.↗

DOE OSTI2020

Progress Toward the First Search for Bound Neutron Oscillation into Antineutron in a Liquid Argon TPC

This note presents current progress for a neutron-antineutron oscillation ($n–\overline{n}$) search in MicroBooNE paving the way for the first search analysis of such process in a Liquid Argon Time Projection Chamber (LArTPC). Convolutional Neural Network (CNN) and Boosted Decision Tree (BDT) algorithms were used to select signal $n–\overline{n}$ events over cosmogenic backgrounds. The CNN-only, BDT-only, and the combined (CNN+BDT) methods were demonstrated on the Monte-Carlo signal and background events. Validation of the CNNonly and the BDT-only methods was carried out on a small dataset of MicroBooNE Run1 off-beam data, setting the starting point toward further improvement of the analysis.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗