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.

15 records

All sources NASA NTRS DOE OSTI

NASA NTRSDate not supplied

Monte Carlo Tree Search for Integrated Planning, Learning, and Execution in Nondeterministic Python

We present a novel use of Monte Carlo Tree Search (MCTS),adapted to explore a search space produced by the choice points embedded in Python code. The choice points are non-deterministic assignment statements and subroutine calls. We present MCTS extensions required for doing tree search in this context which includes control constructs like hierarchical decomposition (subroutine calls), iterative while loops and conditional statements. We demonstrate how the system works in a simulated rideshare scenario in an urban setting, and present preliminary experiments as a proof of concept.

Automatic planning↗

NASA NTRS2021

Monte Carlo Tree Search Methods for the Earth-Observing Satellite Scheduling Problem

This work explores on-board planning for the single spacecraft, multiple ground station Earth-observing satellite scheduling problem through artificial neural network function approximation of state–action value estimates generated by Monte Carlo tree search (MCTS). An extensive hyperparameter search is conducted for MCTS on the basis of performance, safety, and downlink opportunity utilization to determine the best hyperparameter combination for data generation. A hyperparameter search is also conducted on neural network architectures. The learned behavior of each network is explored, and each network architecture’s robustness to orbits and epochs outside of the training distributions is investigated. Furthermore, each algorithm is compared with a genetic algorithm, which serves to provide a baseline for optimality. MCTS is shown to compute near-optimal solutions in comparison to the genetic algorithm. The state–action value networks are shown to match or exceed the performance of MCTS in six orders of magnitude less execution time, showing promise for execution on board spacecraft.

Adam P. Herrmann↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

We present the Multi-Route Weighted Package Delivery Problem (MRWPDP) and a scalable solution methodology as a major step towards enabling an airspace deconfliction service for drone delivery operations. The problem is motivated by Strategic deconfliction under the FAA’s “Unmanned Aircraft Systems Traffic Management” Concept of Operations. MRWPDP falls under a class of vehicle routing and scheduling problems, and as such is NP-Hard. In MRWPDP, a graph network is given which consists of depots, drop-off sites, and multiple routes connecting the two. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is to optimally schedule the departure time and assign routes to a known set of vehicles at the depot. We propose a heuristic solution to the problem by borrowing techniques from Mixed Integer Linear Programming (MILP), Constraint Programming, and Monte Carlo Tree Search (MCTS). The resulting hybrid framework is MCTS with Bound-and-Prune (BP) and rapid simulated updates (U), or MCTS-BP-U. This approach is able to quickly provide a feasible solution for MRWPDP, even for large problem instances up to 1000 vehicles. We provide a MILP formulation of MRWPDP and compare its performance against MCTS-BP-U in terms of solution quality. An agent-based model simulation is conducted as a final step to validate the efficacy of our approach.

air traffic scheduling↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Hybrid Monte Carlo Tree Search Approach

air traffic scheduling↗

NASA NTRS2021

Lila: Optimal Dispatching in Probabilistic Temporal Networks using Monte Carlo Tree Search

Executing a Probabilistic Simple Temporal Network (PSTN) amounts at scheduling, i.e. \textit{dispatch}, a set of events under time uncertainty. This constitutes a NP-hard online optimization problem. The right execution time must be dynamically assigned to each event of the PSTN such that the temporal constraints are met, whereas activity durations are progressively observed as the execution unfolds. We propose a dispatching algorithm based on Monte Carlo Tree Search, called Lila, with the following characteristics: (i) it is an anytime algorithm, both offline and online, proven asymptotically optimal; (ii) it returns the current probability of success, either before or at any moment during operations; (iii) it handles any possible continuous or discrete, even non-parametric, probability distributions, as well as inter-dependencies between random variables, exogenous and endogenous uncertainty; and (iv) can be easily extended to handle probabilistic external events, PSTNs with resources, PSTNs with cutoff times and precondition chains, etc. Lila is universal in the sense that it can handle any dispatching protocol, simply by specifying it to the algorithm. It has the unlimited flexibility offered by the simulation paradigm, whilst it asymptotically converges to optimal decisions and/or robustness approximations.

Chien, Steve A.↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Monte Carlo Tree Search Approach

Numerous unmanned aircraft systems operating at low altitudes to deliver goods and services may one day become ubiquitous in our cities. In the Unmanned Aircraft Systems (UAS) Traffic Management (UTM) framework, such a concept is envisioned, where aerial vehicles operate beyond visual line of sight (BVLOS) within specifically reserved and time stamped “corridors” in the airspace. For example, these corridors or operational intent volumes can connect an aerial vehicle’s origin site to its destination site for package delivery operations. There may also be more than one corridor available for an aerial vehicle to choose from and often different corridors may intersect with one another. Thus, it is imperative to ensure flight trajectories belonging to different aerial vehicles are not in conflict. Per the UTM CONOPs, we assume that a vehicle almost always stays inside its corridor or operational volume. This work provides a framework for strategic deconfliction of UTM or package delivery drones, where we schedule the departure time of all vehicles subject to various temporal constraints (including the corridor deconfliction at the intersections). We present the “multi-route weighted package delivery problem” which serves as an exemplifying model for strategic deconfliction in UTM. In the multi-route weighted package delivery problem, a graph network is given which consists of a set of depots (source) and drop-off (destination) nodes, with multiple routes (defined as a sequence of waypoints) connecting the depots to drop-off nodes. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is for a known set of aerial vehicles to depart from the depots, choose a route and take off time, while avoiding conflicts with other aerial vehicles, and minimizing both risk and distance traveled. We provide a mixed integer linear programming (MILP) formulation of the problem, as well as a heuristic solution based on Monte Carlo Tree Search (MCTS) – a method used in game theory and artificial intelligence – to overcome limitations inherent to optimal solvers. Computational results show the advantages of using MCTS over the MILP formulation; the former can provide a sub-optimal solution quickly, and may sometimes even reach an optimal solution, whereas the latter may not even produce a solution in reasonable time. Furthermore, results from both the MILP formulation and MCTS methods were validated using a preliminary agent-based simulator implementing the UTM concept of operations. Thus, the MCTS method can be seen as a scalable solution to the complex multi-route weighted package delivery problem and may possibly be extended to similar complex optimization problems.

Kenny Chour↗

NASA NTRS2021

Lila: Optimal Dispatching in Probabilistic Temporal Networks using Monte Carlo Tree Search

No abstract provided

Chien, Steve A.↗

NASA NTRSDate not supplied

Adaptive Stress Testing of Trajectory Predictions in Flight Management Systems

To find failure events and their likelihoods in flight-critical systems, we investigate the use of an advanced black-box stress testing approach called adaptive stress testing. We analyze a trajectory predictor from a developmental commercial flight management system which takes as input a collection of lateral waypoints and en-route environmental conditions. Our aim is to search for failure events relating to inconsistencies in the predicted lateral trajectories. The intention of this work is to find likely failures and report them back to the developers so they can address and potentially resolve shortcomings of the system before deployment. To improve search performance, this work extends the adaptive stress testing formulation to be applied more generally to sequential decision-making problems with episodic reward by collecting the state transitions during the search and evaluating at the end of the simulated rollout. We use a modified Monte Carlo tree search algorithm with progressive widening as our adversarial reinforcement learner. The performance is compared to direct Monte Carlo simulations and to the cross-entropy method as an alternative importance sampling baseline. The goal is to find potential problems otherwise not found by traditional requirements-based testing. Results indicate that our adaptive stress testing approach finds more failures and finds failures with higher likelihood relative to the baseline approaches.

adaptive stress testing↗

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↗

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↗

NASA NTRS2026

Benchmarking Bayesian Optimization Frameworks and Acquisition Strategies for Materials Discovery and Autonomous Laboratories

Bayesian optimization (BO) can accelerate materials discovery by guiding expensive experiments toward the most promising processing conditions. We systematically compare five BO surrogate and framework combinations (Gaussian processes in Ax, Gaussian processes and Monte-Carlo neural networks in BayBE, random forests in Lolopy, and tree-structured Parzen (TPE) estimators in Hyperopt) on three benchmarks that mimic common materials design tasks (a discrete solid-electrolyte composition space, a hybrid discrete/continuous laminate-composite design problem solved with micromechanics modeling, and the continuous Ishigami analytic function which is a standard optimization benchmark). Each BO surrogate is paired with posterior mean, probability of improvement, and expected improvement acquisition functions and run for 100 trials from randomized initial samples with uniform random search providing a control. Across five random seeds per setting, BayBE’s Gaussian-process surrogate with expected improvement consistently reached ≥95 % of the known optimum in the fewest evaluations, while Lolopy’s random forest matched or exceeded GP performance on purely categorical or mixed spaces at a higher computational cost. Posterior mean alone often stagnated at local optima, underscoring the need for exploration, whereas probability and expected improvement balanced exploration and exploitation leading to better optimization in fewer trials. Execution times ranged from milliseconds for TPE to minutes for neural-network and random-forest surrogates. These results establish baseline expectations for BO in automated materials laboratories and highlight expected improvement with Gaussian processes as a reliable first choice, with random forests offering a strong alternative when categorical variables dominate. The benchmark suite and code are released to facilitate future surrogate, acquisition, and constraint-handling research in data-driven materials optimization.

Bayesian optimization↗