Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “optimization problems”

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,657 records · Page 92

Efficient Method for Optimizing Placement of Sensors

A computationally efficient method has been developed to enable optimization of the placement of sensors for the purpose of diagnosis of a complex engineering system (e.g., an aircraft or spacecraft). The method can be used both in (1) designing a sensor system in which the number and positions of sensors are initially not known and must be determined and (2) adding sensors to a pre-existing system to increase the diagnostic capability. The optimal-sensor-placement problem can be summarized as involving the following concepts, issues, and subproblems: a) Degree of Diagnosability - This is a concept for characterizing the set of faults that can be discriminated by use of a given set of sensors. b) Minimal Sensor Set - The idea is one of finding a minimal set of sensors that guarantees a specific degree of diagnosability. c) Minimal-Cost Sensors - In a case in which different sensors are assigned with different costs, it is desired to choose the least costly set of sensors that affords a specific degree of diagnosability.

Fijany, Amir↗

Goal Selection for Embedded Systems with Oversubscribed Resources

We describe an efficient, online goal selection algorithm and its use for selecting goals at runtime. Our focus is on the re-planning that must be performed in a timely manner on the embedded system where computational resources are limited. In particular, our algorithm generates near optimal solutions to problems with fully specified goal requests that oversubscribe available resources but have no temporal flexibility. By using a fast, incremental algorithm, goal selection can be postponed in a "just-in-time" fashion allowing requests to be changed or added at the last minute. This enables shorter response cycles and greater autonomy for the system under control.

Rabideau, Gregg↗

Onboard Run-Time Goal Selection for Autonomous Operations

We describe an efficient, online goal selection algorithm for use onboard spacecraft and its use for selecting goals at runtime. Our focus is on the re-planning that must be performed in a timely manner on the embedded system where computational resources are limited. In particular, our algorithm generates near optimal solutions to problems with fully specified goal requests that oversubscribe available resources but have no temporal flexibility. By using a fast, incremental algorithm, goal selection can be postponed in a "just-in-time" fashion allowing requests to be changed or added at the last minute. This enables shorter response cycles and greater autonomy for the system under control.

Rabideau, Gregg↗

Tractable Goal Selection with Oversubscribed Resources

We describe an efficient, online goal selection algorithm and its use for selecting goals at runtime. Our focus is on the re-planning that must be performed in a timely manner on the embedded system where computational resources are limited. In particular, our algorithm generates near optimal solutions to problems with fully specified goal requests that oversubscribe available resources but have no temporal flexibility. By using a fast, incremental algorithm, goal selection can be postponed in a "just-in-time" fashion allowing requests to be changed or added at the last minute. This enables shorter response cycles and greater autonomy for the system under control.

Rabideau, Gregg↗

Combining Simulation Tools for End-to-End Trajectory Optimization

Trajectory simulations with advanced optimization algorithms are invaluable tools in the process of designing spacecraft. Due to the need for complex models, simulations are often highly tailored to the needs of the particular program or mission. NASA's Orion and SLS programs are no exception. While independent analyses are valuable to assess individual spacecraft capabilities, a complete end-to-end trajectory from launch to splashdown maximizes potential performance and ensures a continuous solution. In order to obtain end-to-end capability, Orion's in-space tool (Copernicus) was made to interface directly with the SLS's ascent tool (POST2) and a new tool to optimize the full problem by operating both simulations simultaneously was born.

Whitley, Ryan↗

QAOA Tutorial Outline

In this tutorial we discuss the quantum alternating operator ansatz (QAOA), which is a variational algorithm that can be used for approximate optimization of combinatorial problems with soft and hard constraints.We go through the design of the quantum circuit and its actual implementation in real hardware, discussing compilation issues such as gate synthesis and scheduling of all the required gates and qubit-swapping overhead.

Venturelli, Davide↗

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↗

Uncertainty reasoning in expert systems

Intelligent control is a very successful way to transform the expert's knowledge of the type 'if the velocity is big and the distance from the object is small, hit the brakes and decelerate as fast as possible' into an actual control. To apply this transformation, one must choose appropriate methods for reasoning with uncertainty, i.e., one must: (1) choose the representation for words like 'small', 'big'; (2) choose operations corresponding to 'and' and 'or'; (3) choose a method that transforms the resulting uncertain control recommendations into a precise control strategy. The wrong choice can drastically affect the quality of the resulting control, so the problem of choosing the right procedure is very important. From a mathematical viewpoint these choice problems correspond to non-linear optimization and are therefore extremely difficult. In this project, a new mathematical formalism (based on group theory) is developed that allows us to solve the problem of optimal choice and thus: (1) explain why the existing choices are really the best (in some situations); (2) explain a rather mysterious fact that fuzzy control (i.e., control based on the experts' knowledge) is often better than the control by these same experts; and (3) give choice recommendations for the cases when traditional choices do not work.

Kreinovich, Vladik↗

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↗

Layout optimization with algebraic multigrid methods

Finding the optimal position for the individual cells (also called functional modules) on the chip surface is an important and difficult step in the design of integrated circuits. This paper deals with the problem of relative placement, that is the minimization of a quadratic functional with a large, sparse, positive definite system matrix. The basic optimization problem must be augmented by constraints to inhibit solutions where cells overlap. Besides classical iterative methods, based on conjugate gradients (CG), we show that algebraic multigrid methods (AMG) provide an interesting alternative. For moderately sized examples with about 10000 cells, AMG is already competitive with CG and is expected to be superior for larger problems. Besides the classical 'multiplicative' AMG algorithm where the levels are visited sequentially, we propose an 'additive' variant of AMG where levels may be treated in parallel and that is suitable as a preconditioner in the CG algorithm.

Regler, Hans↗

The PARTY parallel runtime system

In the present automated system for the organization of the data and computational operations entailed by parallel problems, in ways that optimize multiprocessor performance, general heuristics for partitioning program data and control are implemented by capturing and manipulating representations of a computation at run time. These heuristics are directed toward the dynamic identification and allocation of concurrent work in computations with irregular computational patterns. An optimized static-workload partitioning is computed for such repetitive-computation pattern problems as the iterative ones employed in scientific computation.

Saltz, J. H.↗

Application of fuzzy theories to formulation of multi-objective design problems

Much of the decision making in real world takes place in an environment in which the goals, the constraints, and the consequences of possible actions are not known precisely. In order to deal with imprecision quantitatively, the tools of fuzzy set theory can by used. This paper demonstrates the effectiveness of fuzzy theories in the formulation and solution of two types of helicopter design problems involving multiple objectives. The first problem deals with the determination of optimal flight parameters to accomplish a specified mission in the presence of three competing objectives. The second problem addresses the optimal design of the main rotor of a helicopter involving eight objective functions. A method of solving these multi-objective problems using nonlinear programming techniques is presented. Results obtained using fuzzy formulation are compared with those obtained using crisp optimization techniques. The outlined procedures are expected to be useful in situations where doubt arises about the exactness of permissible values, degree of credibility, and correctness of statements and judgements.

Dhingra, A. K.↗

H(infinity) and H2 optimal controllers for periodic and multi-rate systems

The solutions to the optimal l2 to l2 disturbance rejection problem H(infinity) as well as to the LQG (linear quadratic Gaussian) H2 problem in periodic systems using the lifting technique are presented. Both problems involve a causality condition on the optimal LTI (linear time invariant) compensator when viewed in the lifted domain. The H(infinity) problem is solved using the Nehari's theorem, whereas in the H2 problem the solution is obtained using the projection theorem in Hilbert spaces. The authors demonstrate that exactly the same method of solution to the H(infinity) and H2 problems in periodic systems applies when considering the same problems in multirate sampled data systems.

Voulgaris, Petros G.↗

Application of numerical optimization to rotor aerodynamic design

Based on initial results obtained from the performance optimization code, a number of observations can be made regarding the utility of optimization codes in supporting design of rotors for improved performance. (1) The primary objective of improving the productivity and responsiveness of current design methods can be met. (2) The use of optimization allows the designer to consider a wider range of design variables in a greatly compressed time period. (3) Optimization requires the user to carefully define his problem to avoid unproductive use of computer resources. (4) Optimization will increase the burden on the analyst to validate designs and to improve the accuracy of analysis methods. (5) Direct calculation of finite difference derivatives by the optimizer was not prohibitive for this application but was expensive. Approximate analysis in some form would be considered to improve program response time. (6) Program developement is not complete and will continue to evolve to integrate new analysis methods, design problems, and alternate optimizer options.

Pleasants, W. A., III↗

Sensitivity calculations for a 2D, inviscid, supersonic forebody problem

The use of a sensitivity equation method to computer derivatives for optimization based design algorithms are discussed. The problem of designing an optimal forebody simulator is used to motivate the algorithm and to illustrate the basic ideas. Finally, how an existing computational fluid dynamics (CFD) code can be modified to compute sensitivities and a numerical example is presented.

Borggaard, Jeff↗

Multi-Objective Hybrid Optimal Control for Multiple-Flyby Interplanetary Mission Design using Chemical Propulsion

Preliminary design of high‐thrust interplanetary missions is a highly complex process. The mission designer must choose discrete parameters such as the number of flybys and the bodies at which those flybys are performed. For some missions, such as surveys of small bodies, the mission designer also contributes to target selection. In addition, real‐valued decision variables, such as launch epoch, flight times, maneuver and flyby epochs, and flyby altitudes must be chosen. There are often many thousands of possible trajectories to be evaluated. The customer who commissions a trajectory design is not usually interested in a point solution, but rather the exploration of the trade space of trajectories between several different objective functions. This can be a very expensive process in terms of the number of human analyst hours required. An automated approach is therefore very desirable. This work presents such an approach by posing the impulsive mission design problem as a multi‐objective hybrid optimal control problem. The method is demonstrated on several real‐world problems. Two assumptions are frequently made to simplify the modeling of an interplanetary high‐thrust trajectory during the preliminary design phase. The first assumption is that because the available thrust is high, any maneuvers performed by the spacecraft can be modeled as discrete changes in velocity. This assumption removes the need to integrate the equations of motion governing the motion of a spacecraft under thrust and allows the change in velocity to be modeled as an impulse and the expenditure of propellant to be modeled using the time‐independent solution to Tsiolkovsky's rocket equation [1]. The second assumption is that the spacecraft moves primarily under the influence of the central body, i.e. the sun, and all other perturbing forces may be neglected in preliminary design. The path of the spacecraft may then be modeled as a series of conic sections. When a spacecraft performs a close approach to a planet, the central body switches from the sun to that planet and the trajectory is modeled as a hyperbola with respect to the planet. This is known as the method of patched conics. The impulsive and patched‐conic assumptions significantly simplify the preliminary design problem.

Optimization↗

Four-body trajectory optimization

A comprehensive optimization program has been developed for computing fuel-optimal trajectories between the earth and a point in the sun-earth-moon system. It presents methods for generating fuel optimal two-impulse trajectories which may originate at the earth or a point in space and fuel optimal three-impulse trajectories between two points in space. The extrapolation of the state vector and the computation of the state transition matrix are accomplished by the Stumpff-Weiss method. The cost and constraint gradients are computed analytically in terms of the terminal state and the state transition matrix. The 4-body Lambert problem is solved by using the Newton-Raphson method. An accelerated gradient projection method is used to optimize a 2-impulse trajectory with terminal constraint. The Davidon's Variance Method is used both in the accelerated gradient projection method and the outer loop of a 3-impulse trajectory optimization problem.

Pu, C. L.↗