Search NASA⌕ Search

SEARCH · Search NASA

Results for “algorithm timings”

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,063 records · Page 59

Online fault adaptive control for efficient resource management in Advanced Life Support Systems

This article presents the design and implementation of a controller scheme for efficient resource management in Advanced Life Support Systems. In the proposed approach, a switching hybrid system model is used to represent the dynamics of the system components and their interactions. The operational specifications for the controller are represented by utility functions, and the corresponding resource management problem is formulated as a safety control problem. The controller is designed as a limited-horizon online supervisory controller that performs a limited forward search on the state-space of the system at each time step, and uses the utility functions to decide on the best action. The feasibility and accuracy of the online algorithm can be assessed at design time. We demonstrate the effectiveness of the scheme by running a set of experiments on the Reverse Osmosis (RO) subsystem of the Water Recovery System (WRS).

NASA Discipline Life Support Systems↗

Combined Bernstein Polynomial, Optimal Reciprocal Collision Avoidance, Differential Dynamic Programming for Trajectory Replanning and Collision Avoidance for UAM Vehicles

This paper presents an integration of Differential Dynamic Programming (DDP) with the Optimal Reciprocal Collision Avoidance (ORCA) algorithm as the basis for a new algorithm, titled Combined Bernstein Polynomial Optimal Reciprocal Collision Avoidance DDP (COBRA-DDP), for trajectory replanning and collision avoidance for Urban Air Mobility (UAM) vehicles. State-constrained variants of DDP provide the ability to plan trajectories while avoiding obstacles, but these methods require a large increase in computational time per iteration which hinders the overall speed of the algorithm. ORCA utilizes simplified dynamics to recognize potential collisions along a trajectory and provides an optimal velocity for the avoidance of multiple vehicles. These velocity commands, however, may not result in a dynamically feasible trajectory for DDP to plan around. As such, a Bernstein polynomial curve that considers the general dynamic constraints of the vehicle is generated to approximate a trajectory based on the velocity commands. COBRA-DDP optimizes this suggested trajectory via unconstrained DDP to provide a dynamically feasible trajectory that provides collision avoidance. This new trajectory can be applied to the vehicle or used to warm start the state constrained DDP algorithms to decrease computation time. Its benefits and effectiveness of the algorithm are demonstrated on a UAM Vertical Takeoff and Landing (VTOL) vehicle simulation with highly nonlinear dynamics.

Optimal Reciprocal Collision Avoidance↗

Unsteady transonic flow using Euler equations

An implicit, two factor, split flux, finite volume Euler equations solution algorithms is applied to the time accurate solution of transonic flow about an NACA 0012 airfoil and a rectangular planform supercritical wing undergoing pitch oscillations. Accuracy for Courant numbers greater than one is analyzed. Freezing the flux Jacobians can result in significant savings for steady state solutions; the accuracy of freezing flux Jacobians for unsteady results is investigated. The Euler algorithm results are compared with experimental results for an NACA 0012 and a rectangular planform supercritical wing.

Belk, Dave M.↗

Exploring Applications of Machine Learning for Wildfire Monitoring and Detection using Unmanned Aerial Vehicles

Wildfires are increasing in frequency and severity around the world, including the United States. The losses caused by wildfires could be mitigated if high-risk areas, hotspots, and flare-ups could be monitored continuously, such as through the use of Unmanned Aerial Vehicles (UAVs). This paper documents exploratory efforts using machine learning to determine efficient flight paths for UAVs and to detect wildfires using image classification. On path planning, three machine learning techniques—Genetic Algorithm, Simulated Annealing, and Dynamic Programming—were explored. Genetic Algorithm was found to be an effective approach for path planning for wildfire monitoring and surveillance by UAVs. For a scenario of 25 locations in a circular arrangement, the algorithm was able to return the optimal path. The accuracy and execution time was found to be sensitive to the algorithm hyperparameters selected, which was especially evident in scenarios with hundreds or thousands of locations. Simulated Annealing was also found to be an effective approach for UAV path planning, with a major benefit of avoiding getting trapped in local minima and being straightforward to implement. Like Genetic Algorithm, the performance of Simulated Annealing was also found to be sensitive to the algorithm hyperparameters selected. By comparison, Dynamic Programming guarantees optimality for any number of locations, but it was found to be less practical in terms of execution time for scenarios with more than about a couple dozen locations. On wildfire detection, image classification using deep learning with a convolutional neural network was explored. Transfer learning was found to be a useful technique to efficiently train deep learning models. Also, it was determined that GPU processing can increase training speed by an order of magnitude, which enables significantly faster development. For a validation test set of 500 images, there were only two false negatives and zero false positives. These results demonstrate that detecting wildfires in static cameras using machine learning is feasible and establish a baseline for using images captured by UAVs in flight for wildfire detection.

Wildfire management↗

Freeing Space for NASA: Incorporating a Lossless Compression Algorithm into NASA's FOSS System

NASA's Fiber Optic Strain Sensing (FOSS) system can gather and store up to 1,536,000 bytes (1.46 megabytes) per second. Since the FOSS system typically acquires hours - or even days - of data, the system can gather hundreds of gigabytes of data for a given test event. To store such large quantities of data more effectively, NASA is modifying a Lempel-Ziv-Oberhumer (LZO) lossless data compression program to compress data as it is being acquired in real time. After proving that the algorithm is capable of compressing the data from the FOSS system, the LZO program will be modified and incorporated into the FOSS system. Implementing an LZO compression algorithm will instantly free up memory space without compromising any data obtained. With the availability of memory space, the FOSS system can be used more efficiently on test specimens, such as Unmanned Aerial Vehicles (UAVs) that can be in flight for days. By integrating the compression algorithm, the FOSS system can continue gathering data, even on longer flights.

Fiechtner, Kaitlyn↗

A class of least-squares filtering and identification algorithms with systolic array architectures

A unified approach is presented for deriving a large class of new and previously known time- and order-recursive least-squares algorithms with systolic array architectures, suitable for high-throughput-rate and VLSI implementations of space-time filtering and system identification problems. The geometrical derivation given is unique in that no assumption is made concerning the rank of the sample data correlation matrix. This method utilizes and extends the concept of oblique projections, as used previously in the derivations of the least-squares lattice algorithms. Exponentially weighted least-squares criteria are considered for both sliding and growing memory.

Kalson, Seth Z.↗

Mapping unstructured grid problems to the connection machine

We present a highly parallel graph mapping technique that enables one to solve unstructured grid problems on massively parallel computers. Many implicit and explicit methods for solving discretizated partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The time spent communicating can limit the high performance promised by massively parallel computing. To eliminate this bottleneck, we map the graph of the irregular problem to the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. We show that, in comparison to a naive assignment of processors, our heuristic mapping algorithm significantly reduces the communication time on the Connection Machine, CM-2.

Hammond, Steven W.↗

Solving unstructured grid problems on massively parallel computers

A highly parallel graph mapping technique that enables one to efficiently solve unstructured grid problems on massively parallel computers is presented. Many implicit and explicit methods for solving discretized partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The cost of this communication can negate the high performance promised by massively parallel computing. To eliminate this bottleneck, the graph of the irregular problem is mapped into the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. It is shown that using the heuristic mapping algorithm significantly reduces the communication time compared to a naive assignment of processes to processors.

Hammond, Steven W.↗

Accelerated panel methods using the fast multipole method

Panel methods are commonly used in computational fluid dynamics for the solution of potential flow problems. The methods are a numerical technique based on the surface distribution of singularity elements. The solution is the process of finding the strength of the singularity elements distributed over the body's surface. This process involves the solution of the matrix problem Pq = p' for a set of unknowns q. The Fast Multipole Method is used to directly compute q without using matrix solvers. The algorithm works in O(N) time for N points, a great improvement over standard matrix solvers. In panel methods, the surface of a body is divided into a series of quadrilateral panels. The methods involve the computation of the influence of all other panels on each individual panel. The influence is based on the surface distribution, though this can be approximated by the area for distant panels. An alternative approximation, though with arbitrary accuracy, is to develop a multipole expansion about the center of the panel to describe the effect of a given panel on distant points in space. The expansion is based on the moments of the panel, thus allow the use of various surface distributions without changing the basic algorithm, just the computation of the various moments. The expansions are then manipulated in a tree walk to develop Taylor series expansions about a point in space which describe the effect of all distant panels on any point within a volume of convergence. The effect of near panels then needs to be computed directly, but the effect of all distant panels can be computed by simply evaluating the resulting expansion. The Fast Multipole Method has been applied to panel methods for the solution of source and doublet distributions. A major feature of the algorithm is that the algorithm does not change to derive the potential and velocity for sources and doublets. The same expansions can be used for both sources and doublets. Since the velocity is related to the potential, and the doublet potential is related to the z-component of the source velocity, all values can be derived from the same expansion by taking a series of partial derivatives. This requires more expansion terms to be kept since terms are lost in the process of taking partial derivatives. Thus to maintain accuracy for the doublet computation, more terms are required than if just evaluating for sources. The resulting Fast Multipole code should then parallelize better than classical panel methods due to the locality of data dependencies found in the Fast Multipole Method. Theoretically the parallelized code should execute in O(log N) time with O(N) processors, though this is not practical. Ongoing work includes implementing the parallel accelerated panel method, including methods to improve the load balancing of the problem by taking advantage of the known geometry of panels, and to encorporate sensitivity analysis into the algorithm.

Leathrum, James F., Jr.↗

User's manual for SYNC: A FORTRAN program for merging and time-synchronizing data

The FORTRAN 77 computer program SYNC for merging and time synchronizing data is described. The program SYNC reads one or more input files which contain either synchronous data frames or time-tagged data points, which can be compressed. The program decompresses and time synchronizes the data, correcting for any channel time skews. Interpolation and hold last value synchronization algorithms are available. The output from SYNC is a file of time synchronized data frames at any requested sample rate.

Maine, R. E.↗

A coarse-grid correction/nonlinear relaxation algorithm for the three-dimensional, compressible Navier-Stokes equations

A combined coarse-grid correction/upwind relaxation strategy to provide rapid convergence for 3D high-speed viscous flowfields is discussed an evaluated. The construction and analysis of a simple two-grid acceleration procedure based on 'hyperbolic' multigrid concepts is presented. Numerical simulations of a 2D compression-corner flowfield, a 3D crossing shock/turbulent boundary layer interaction, and a 3D scramjet inlet flowfield are presented to illustrate the benefits of the approach. Results indicate that the procedure generally converges two or more times faster than the baseline algorithm.

Edwards, Jack R.↗

Test results of flight guidance for fuel conservative descents in a time-based metered air traffic environment

The NASA developed, implemented, and flight tested a flight management algorithm designed to improve the accuracy of delivering an airplane in a fuel-conservative manner to a metering fix at a time designated by air traffic control. This algorithm provides a 3D path with time control (4D) for the TCV B-737 airplane to make an idle-thrust, clean configured (landing gear up, flaps zero, and speed brakes retracted) descent to arrive at the metering fix at a predetermined time, altitude, and airspeed. The descent path is calculated for a constant Mach/airspeed schedule from linear approximations of airplane performance with considerations given for gross weight, wind, and nonstandard pressure and temperature effects. The flight management descent algorithms are described and flight test results are presented.

Knox, C. E.↗

Parametric binary dissection

Binary dissection is widely used to partition non-uniform domains over parallel computers. This algorithm does not consider the perimeter, surface area, or aspect ratio of the regions being generated and can yield decompositions that have poor communication to computation ratio. Parametric Binary Dissection (PBD) is a new algorithm in which each cut is chosen to minimize load + lambda x(shape). In a 2 (or 3) dimensional problem, load is the amount of computation to be performed in a subregion and shape could refer to the perimeter (respectively surface) of that subregion. Shape is a measure of communication overhead and the parameter permits us to trade off load imbalance against communication overhead. When A is zero, the algorithm reduces to plain binary dissection. This algorithm can be used to partition graphs embedded in 2 or 3-d. Load is the number of nodes in a subregion, shape the number of edges that leave that subregion, and lambda the ratio of time to communicate over an edge to the time to compute at a node. An algorithm is presented that finds the depth d parametric dissection of an embedded graph with n vertices and e edges in O(max(n log n, de)) time, which is an improvement over the O(dn log n) time of plain binary dissection. Parallel versions of this algorithm are also presented; the best of these requires O((n/p) log(sup 3)p) time on a p processor hypercube, assuming graphs of bounded degree. How PBD is applied to 3-d unstructured meshes and yields partitions that are better than those obtained by plain dissection is described. Its application to the color image quantization problem is also discussed, in which samples in a high-resolution color space are mapped onto a lower resolution space in a way that minimizes the color error.

Bokhari, Shahid H.↗

The use of real-time, hardware-in-the-loop simulation in the design and development of the new Hughes HS601 spacecraft attitude control system

Realtime simulation and hardware-in-the-loop testing is being used extensively in all phases of the design, development, and testing of the attitude control system (ACS) for the new Hughes HS601 satellite bus. Realtime, hardware-in-the-loop simulation, integrated with traditional analysis and pure simulation activities is shown to provide a highly efficient and productive overall development program. Implementation of high fidelity simulations of the satellite dynamics and control system algorithms, capable of real-time execution (using applied Dynamics International's System 100), provides a tool which is capable of being integrated with the critical flight microprocessor to create a mixed simulation test (MST). The MST creates a highly accurate, detailed simulated on-orbit test environment, capable of open and closed loop ACS testing, in which the ACS design can be validated. The MST is shown to provide a valuable extension of traditional test methods. A description of the MST configuration is presented, including the spacecraft dynamics simulation model, sensor and actuator emulators, and the test support system. Overall system performance parameters are presented. MST applications are discussed; supporting ACS design, developing on-orbit system performance predictions, flight software development and qualification testing (augmenting the traditional software-based testing), mission planning, and a cost-effective subsystem-level acceptance test. The MST is shown to provide an ideal tool in which the ACS designer can fly the spacecraft on the ground.

Slafer, Loren I.↗

Analysis of sequencing and scheduling methods for arrival traffic

The air traffic control subsystem that performs scheduling is discussed. The function of the scheduling algorithms is to plan automatically the most efficient landing order and to assign optimally spaced landing times to all arrivals. Several important scheduling algorithms are described and the statistical performance of the scheduling algorithms is examined. Scheduling brings order to an arrival sequence for aircraft. First-come-first-served scheduling (FCFS) establishes a fair order, based on estimated times of arrival, and determines proper separations. Because of the randomness of the traffic, gaps will remain in the scheduled sequence of aircraft. These gaps are filled, or partially filled, by time-advancing the leading aircraft after a gap while still preserving the FCFS order. Tightly scheduled groups of aircraft remain with a mix of heavy and large aircraft. Separation requirements differ for different types of aircraft trailing each other. Advantage is taken of this fact through mild reordering of the traffic, thus shortening the groups and reducing average delays. Actual delays for different samples with the same statistical parameters vary widely, especially for heavy traffic.

Neuman, Frank↗

An Autonomous Onboard Targeting Algorithm Using Finite Thrust Maneuvers

In earlier investigations, the adaptation and implementation of a modified two-level corrections process as the onboard targeting algorithm for the Trans-Earth Injection phase of Orion is presented. The objective of that targeting algorithm is to generate the times of ignition and magnitudes of the required maneuvers such that the desired state at entry interface is achieved. In an actual onboard flight software implementation, these times of ignition and maneuvers are relayed onto Flight Control for command and execution. Although this process works well when the burn durations or burn arcs are small, this might not be the case during a contingency situation when lower thrust engines are employed to perform the maneuvers. Therefore, a new version of the modified two-level corrections process is formulated to handle the case of finite burn arcs. This paper presents the development and formulation of that finite burn modified two-level corrections process which can again be used as an onboard targeting algorithm for the Trans-Earth Injection phase of Orion. Additionally, performance results and a comparison between the two methods are presented. The finite burn two-level corrector formulation presented here ensures the entry constraints at entry interface are still met without violating the available fuel budget, while still accounting for much longer burn times in its design.

Scarritt, Sara K.↗

Volume 2: Explicit, multistage upwind schemes for Euler and Navier-Stokes equations

The objective of this study was to develop a high-resolution-explicit-multi-block numerical algorithm, suitable for efficient computation of the three-dimensional, time-dependent Euler and Navier-Stokes equations. The resulting algorithm has employed a finite volume approach, using monotonic upstream schemes for conservation laws (MUSCL)-type differencing to obtain state variables at cell interface. Variable interpolations were written in the k-scheme formulation. Inviscid fluxes were calculated via Roe's flux-difference splitting, and van Leer's flux-vector splitting techniques, which are considered state of the art. The viscous terms were discretized using a second-order, central-difference operator. Two classes of explicit time integration has been investigated for solving the compressible inviscid/viscous flow problems--two-state predictor-corrector schemes, and multistage time-stepping schemes. The coefficients of the multistage time-stepping schemes have been modified successfully to achieve better performance with upwind differencing. A technique was developed to optimize the coefficients for good high-frequency damping at relatively high CFL numbers. Local time-stepping, implicit residual smoothing, and multigrid procedure were added to the explicit time stepping scheme to accelerate convergence to steady-state. The developed algorithm was implemented successfully in a multi-block code, which provides complete topological and geometric flexibility. The only requirement is C degree continuity of the grid across the block interface. The algorithm has been validated on a diverse set of three-dimensional test cases of increasing complexity. The cases studied were: (1) supersonic corner flow; (2) supersonic plume flow; (3) laminar and turbulent flow over a flat plate; (4) transonic flow over an ONERA M6 wing; and (5) unsteady flow of a compressible jet impinging on a ground plane (with and without cross flow). The emphasis of the test cases was validation of code, and assessment of performance, as well as demonstration of flexibility.

Elmiligui, Alaa↗

Separation at Crossing Waypoints Under Wind Uncertainty in Urban Air Mobility

To enable high-density operations in major metropolitan areas, urban air mobility networks are anticipated to have air traffic management with higher levels of autonomy. To ensure that this type of autonomy is feasible, one of the critical steps from a safety and efficiency perspective is understanding various factors that affect the spatial separation between airborne flights and ensure that these factors can be managed. In terms of separation assurance and scheduling, an important real-world concern is that future states of aircraft cannot be perfectly predicted. The focus of this research paper is to understand how these prediction errors affect separation and scheduling services and to explore mitigation strategies to handle these errors. In this research, we have simulated these types of uncertainty by adding wind-prediction errors to trajectory predictions for separation. With these wind-prediction errors, we decompose the problem into two separate questions. First, using both simulation and analytical methods, we look at conflict-detection-only scenarios to understand how the wind errors affect required minimum temporal separation between crossing flights to ensure a specific spatial separation. Next, we study how trajectory errors effect conflict resolution, and we explore different combinations of scheduling and separation assurance to mitigate the effects of uncertainty between crossing flights. The conflict resolution algorithm aims to minimize necessary temporal separation between crossing flights under uncertainty, still ensuring safety-critical spatial separation. In summary, this research suggests that the required minimum temporal separation at a crossing waypoint is dependent on factors such as inbound crossing angle, the relative angle between wind direction and bearing of each route, wind magnitude, wind magnitude uncertainty, nominal cruise airspeed of aircraft, and look-ahead time of the conflict detection algorithm. This research also suggests that different combinations of scheduling and separation have different qualitative results. Using a combination of strategic, flow-based scheduling, tactical scheduling at crossings, speed control near crossing points, and separation management leads to a system that is insensitive to trajectory prediction errors with high throughput and flexibility for aircraft away from shared resources.

urban air mobility↗