Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Np”

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.

At least 1,315 records · Page 73
All sourcesNASA NTRSDOE OSTI
NASA NTRS2019

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Hadfield, Stuart↗
NASA NTRS2020

History and Logic Model NASA Goddard Space Flight Center Instrument and Payload Systems Engineering Technical Performance Study

Historically, some NASA missions have exceeded schedule and cost commitments. Studies suggest technical performance is a contributor. The 1980 NASA Project Management Study concluded, "one of the most significant contributors to cost and schedule growth is inadequate definition of technical and management aspects of a program..." (as cited in GAO/NSIAD-93-97, p. 11). The 1991 NASA Roles and Missions Report identified a "need for increased emphasis on technological readiness and requirements on the front end of a program" (as cited in GAO/NSIAD-93-97, p. 11). The 1992 NASA Program Costs Report stated that NASA officials identified, among other things, "insufficient definition studies... [and] program redesigns and technical complexities" as reasons for cost and schedule overruns (GAO/NSAID-93-97, p. 11). The 2002 Task Force on Acquisition of National Security Space Programs found "requirements definition and control issues, unhealthy cost bias in proposal evaluation, widespread lack of budget reserves required to implement high risk programs on schedule, and an overall underappreciation of the importance of appropriately staffed and trained system engineering staff to manage the technologically demanding and unique aspects of space programs" (DoD, 2003, p.i.) In 2007, The NASA Office of the Chief Engineer chartered the NASA Instrument Capability Study (NICS) “to determine whether NASA instrument developers are facing challenges that impact the capability to design and build quality instruments or whether there are flaws in the acquisition strategy evidenced by schedule delays, cost overruns, and increased technical risk via design deficiencies. The... team was also chartered to determine if occurrences [are]... isolated cases or if there are generic issues... If the issues [are] found to be generic, the team [is] to offer solutions to recover such capability" (NICS Report, 2008, p. vi). The 2008 NICS Report, led by Goddard Space Flight Center (GSFC), identified challenges to instrument technical performance consistent with findings from previous reports. In 2017, the Instrument Project Division (IPD) Implementation Study was initiated to determine if there was a change in meeting schedule and cost commitments after implementing certain NICS recommendations. In 2018, the Instrument Technical Performance Study was initiated to determine the current state of Instrument Technical Performance in the GSFC Payload & Instrument Systems Engineering Branch. The purpose of the combined studies is to answer the question, "Is there a relationship between meeting NASA scientific instrument technical success and meeting schedule and cost commitments? If yes, what is the relationship?" References Department of Defense Office of the Under Secretary of Defense for Acquisition, Technology, and Logistics. (2003). The report of the defense science board/ air force scientific advisory board joint task force on acquisition of national security space programs. Washington DC. Government Accounting Office. (1992). NASA program costs: Space missions require substantially more funding than initially estimated. GAO/NSIAD-93-97. Washington DC. National Aeronautics and Space Administration, National Oceanic and Atmospheric Agency, Department of Defense. (2008). The NASA instrument capability study final report. NP-2008-11-058-GSFC. Washington DC.

Robbins, Geraldine↗
NASA NTRS2020

A Multi-Sims Investigation of Water Content and D/H Ratios in Roberts Massif 04262 with Insight to Sources of Hydrogen in Maskelynite

We want to define the H2O content ([H2O]) and hydrogen (H) isotope composition of meteoritic material from Mars [1-3] with motivation to understand Mars’ volatile history, constrain geochemical signatures of interior water reservoirs (i.e. the Martian mantle) and explore effects of planetary (e.g. planet formation, magma ocean degassing) and local (e.g. volcanic degassing, impact melting and degassing) processes on H incorporated in minerals. Secondary ion mass spectrometry (SIMS) allows multiple avenues to address these questions. However, application to (1) precious astromaterials and (2) low level H measurements, pose specific challenges that are further complicated when combined. We present preliminary data of a multi-approach (SIMS vs. NanoSIMS) study of H in Roberts Massif 04262 (RBT 04262), an enriched lherzolitic shergottite with nonpoikilitic (NP) and poikilitic (P) lithologies [4]. We analyze olivine, pyrox-ene, and melt inclusions to compare indigenous mantle water, with impact-generated maskelynite to investigate H signatures due to shock.

Dudley, J. M.↗
NASA NTRS2020

Silver Foam A Long-Term Passive Biocide for Potable Water Systems: 2020 Update

A spacecraft water disinfection system suitable for extended length space exploration missions should prevent or control the growth of microbes, prevent or limit biofilm formation, and prevent microbiologically-influenced corrosion. In addition, the system should have minimal maintenance requirements, the effluent should be chemically compatible with all materials in contact with the water, be safe for human consumption, and suitable to be shared across international spacecraft platforms and mission architectures. Silver ions are a proven broad spectrum biocide and the chosen potable water biocide for future exploration missions. The leading technology for actively dosing silver in future water systems is based on electrolytic production. Several challenges remain with this approach which have prompted additional investigations into alternative dosing techniques. Control-release technology is an attractive option for developing a high-reliability passive silver dosing device. This paper describes the development of a nanoparticle (NP)/polyurethane (PU) composite foam for the controlled release of silver ions, and is intended to build upon the 2019 International Conference on Environmental Systems (ICES) paper of the same name. In this paper, the technical background and results from the updated silver chloride (AgCl) NP/PU composite foam synthesis and property testing is provided. The ultimate goal of the project is to develop a stable and reliable passive dosing silver ion release device for use in future spacecraft potable water systems.

Irwin, Tesia D.↗
NASA NTRSDate not supplied

Silver Foam: A Novel Approach for Long-Term Passive Dosing of Biocide in Spacecraft Potable Water Systems

A spacecraft water disinfection system suitable for extended length space exploration should prevent or control the growth of microbes, prevent or limit biofilm formation, and prevent microbiologically influenced corrosion. In addition, the system should have minimal maintenance requirements,should be chemically compatible with all materials in contact with the water, be safe for human consumption, and suitable to be shared across international spacecraft platforms and mission architectures. Silver ions are a proven broad-spectrum biocide under consideration as a potable water biocide for future exploration missions. The leading technology for actively dosing silver in future water systems is based on electrolytic production. Several challenges remain with this approach that have prompted additional investigations into alternative dosing techniques. Control-release technology is an attractive option for developing a high-reliability passive silver dosing device. This paper describes the development of a silver chloride (AgCl) nanoparticle (NP)/polyurethane (PU) composite foam for the controlled release of silver ions, and is intended to build upon the 2019 International Conference on Environmental Systems (ICES) paper number 272.This paper provides the technical background and results from the updated AgClNP/PU composite foam (AgFoam) synthesis and property testing. The ultimate goal of the project is to develop a stable and reliable passive dosing silver ion release device for use in future spacecraft potable water systems.

Tesia Dawn Irwin↗
NASA NTRS2022

Simultaneous Stoquasticity

Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.

Jacob Bringewatt↗
NASA NTRS2020

Multi-Agent Motion Planning using Deep Learning for Space Applications

State-of-the-art motion planners cannot scale to a large number of systems. Motion planning for multiple agents is an NP (non-deterministic polynomial-time) hard problem, so the computation time increases exponentially with each addition of agents. This computational demand is a major stumbling block to the motion planner's application to future NASA missions involving the swarm of space vehicles. We applied a deep neural network to transform computationally demanding mathematical motion planning problems into deep learning-based numerical problems. We showed optimal motion trajectories can be accurately replicated using deep learning-based numerical models in several 2D and 3D systems with multiple agents. The deep learning-based numerical model demonstrates superior computational efficiency with plans generated 1000 times faster than the mathematical model counterpart.

Madani, Ramtin↗
NASA NTRSDate not supplied

Simultaneous Stoquasticity

Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.

Monte Carlo↗
NASA NTRSDate not supplied

Assessment of the 10-year Ozone Profile Record Derived from Suomi NPP OMPS-LP

In this presentation we evaluate ozone profile retrievals from Ozone Mapping and Profiling Suite Limb Profiler (OMPS-LP) launched in October 2011 on Suomi NPP satellite. The data from OMPS-LP were re-processed with the new retrieval algorithm that combines measurements from UV and VIS parts of the spectra to retrieve a single ozone profile between 12.5 km (or cloud tops) and 57.5 km. To improve ozone retrievals in the Upper Troposphere Lower Stratosphere (UTLS) region, a new aerosol correction with a gamma-function particle size distribution was implemented. The OMPS-LP altitude registration was also adjusted in the new version to ensure the stability of the ozone record. The continuous ozone profile observations with Suomi NPP OMPS LP exceeds 10 years. We will compare OMPS-LP ozone profiles with coincident stratospheric ozone measurements from NASA Aura MLS, ISS SAGE III, and OMPS NP and with the observations in UTLS and middle stratosphere from a ground-based network of ozone sonde stations to evaluate accuracy and precision of OMPS-LP retrievals and overall stability of the record. We will also investigate the quality of stratospheric ozone columns obtained from OMPS-LP and estimate the contribution of various errors to integrated stratospheric columns from OMPS-LP.

stratospheric ozone↗
NASA NTRS2022

On the Effects of Cloud Water Content on Passive Microwave Snowfall Retrievals

The Bayesian passive microwave retrievals of snowfall often rely on mathematical matching of the observed vectors of brightness temperature with an a priori database of precipitation profiles and their corresponding brightness temperatures. Mathematical proximity does not necessarily lead to consistent retrievals due to limited information content of passive microwave observations. This paper defines imposter (genuine) vectors of brightness temperature as those that are mathematically close but physically inconsistent (consistent) and characterizes them through the Silhouette Coefficient (SC) analysis. The Neyman–Pearson (NP) hypothesis testing is used to separate the imposter and genuine brightness temperatures based on their associated values of cloud ice (IWP) and liquid water path (LWP), given by coincidences of CloudSat Profiling Radar (CPR) and the Global Precipitation Measurement (GPM) Microwave Imager (GMI). The study determines thresholds for IWP and LWP that allow optimal identification of imposter brightness temperatures of non-snowing and snowing clouds, which can mislead the passive microwave retrieval algorithms to falsely detect or miss the snowfall events. It is demonstrated that emission signal of supercooled liquid water in snowing clouds can lead to improved passive microwave retrieval of snowfall and conditioning the retrievals to the cloud IWP and LWP can result in marginal correction of the snowfall detection probability; however, reduce the probability of false alarm by 6%–8% over sea ice and open oceans.

Snowfall↗
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 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

Seeing is Believing: Monitoring Future Time Temporal Logic

Runtime monitors for future-time unbounded temporal logics like RVLTL, LTL 3 and FLTL, have double-exponential (2^2^n) worst-case space complexity bounds in size of the input formula. The semantics of these logics require monitors to perform general satisfiability solving for LTL expressions, a well-studied problem whose computational complexity is NP-hard and PSPACE-complete. This paper introduces an unbounded future-time linear temporal logic defined over a lattice. We call our logic an incremental temporal logic as it can be viewed as incrementally constructing proofs about the trace. On this account, we view online runtime monitoring as a decision procedure for proofs systems about incrementally growing traces. We demonstrate that our incremental temporal logic allows monitor construction to void satisfiability solving while still soundly detecting when the property is violated in an online fashion. This enables asymptotic improvements in space complexity. As proof, we provide a procedure to construct monitors that utilize linear space and time in the size of the input formula, while remaining constant in the size of the input stream and suitable for online monitoring. We further demonstrate, through several examples, that our incremental temporal logic is straightforward to adopt and practical for runtime verification.

temporal logic↗
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

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

In this research, the strategic deconfliction of unmanned aircraft systems for an urban package delivery environment with two depots and multiple drop-off locations is studied. This research aims to formulate a mathematical model to compute both the departure sequence and scheduled time of departure for each unmanned aircraft system at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. However, the problem formulation results in an NP-hard mixed-integer nonlinear programming problem for the global optimal solution, so instead, a "rolling horizon with𝑘-position search"heuristic method is developed. The simulation studies show that an increase in the value of𝑘(the parameter used to determine the size of the local neighborhood) reduces the average ground delay at the cost of an increase in the computation time for a given problem size. The study also shows an order of magnitude increase in the maximum number of flights scheduled with the integration of rolling horizon (time decomposition) compared to those without the integration of rolling horizon in the heuristic algorithm for a given computation time cut off.

UTM↗
NASA NTRSDate not supplied

Rolling Horizon with K-Position Search Method for Strategic Deconfliction of Package Delivery UAS

This research focuses on the strategic deconfliction of unmanned aircraft systems (UAS) in an urban package delivery environment with two depots and multiple drop-off locations. Since the formulated mixed-integer nonlinear programming (MINLP) problem is non-deterministic polynomial-time (NP) hard, a heuristic algorithm called "rolling horizon with k-position search (KPS)" is used to compute the departure sequence and scheduled time of departure (STD) of each UAS at a depot, considering temporal constraints at en-route crossing waypoints and depots for strategic deconfliction. The simulation studies show that an increase in the value of k (local neighborhood search) in the KPS reduces the average ground delay at the cost of an increase in the computation time for a given number of UAS, size of the rolling horizon window, and number of depots involved in the local neighborhood search. The studies also show that for a given rolling horizon window, the computation time increases exponentially with an increase in the total number of UAS flights when serial processing the local neighborhood search of KPS (with k > 1) and drops by an order of magnitude upon performing the local neighborhood search of KPS using parallel processing instead of serial processing. The computation time drops with the reduction in air traffic complexity of a scenario for a given number of flights, k (local neighborhood search), and rolling horizon window.

UTM↗
NASA NTRS2024

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↗
DOE OSTI2020

FLEET: Flexible Efficient Ensemble Training for Heterogeneous Deep Neural Networks

Parallel training of an ensemble of Deep Neural Networks (DNN) on a cluster of nodes is an effective approach to shorten the process of neural network architecture search and hyper-parameter tuning for a given learning task. Prior efforts have shown that data sharing, where the common preprocessing operation is shared across the DNN training pipelines, saves computational resources and improves pipeline efficiency. Data sharing strategy, however, performs poorly for a heterogeneous set of DNNs where each DNN has varying computational needs and thus different training rate and convergence speed. This paper proposes FLEET, a flexible ensemble DNN training framework for efficiently training a heterogeneous set of DNNs. We build FLEET via several technical innovations. We theoretically prove that an optimal resource allocation is NP-hard and propose a greedy algorithm to efficiently allocate resources for training each DNN with data sharing. We integrate data-parallel DNN training into ensemble training to mitigate the differences in training rates and introduce checkpointing into this context to address the issue of different convergence speeds. Experiments show that FLEET significantly improves the training efficiency of DNN ensembles without compromising the quality of the result.

Guan, Hui↗