Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Minimax problem”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2011

TPSAS-NF1676L-12321-DND

The operation of some networks, such as air transportation networks, can be complicated by congestion through a small subset of nodes. The congestion may be influenced by the connectivity of the network, or by the presence of constraints restricting the flow through particular nodes. This work investigates the effects of both connectivity and node flow constraints on the operation of a network. We develop the Minimax Node Load Problem (MNLP), a multicommodity flow model which minimizes the worst-case flow through any node in a given input network. The optimal solution to this problem provides us with the minimax node load, which we propose as a measure of network congestion. Keeping the number of nodes fixed, we first increase connectivity in a series of networks, and observe that topologies with more distributed connections result in a reduction in the minimax node load. However, when connectivity is increased further, the reductions diminish and are accompanied by solutions with undesirable qualities such as longer commodity paths. We then perform a second set of experiments over the same network, constraining flow through different subsets of nodes at different magnitudes of flow restriction, finding that (1) more constrained nodes lead to the largest increases in minimax node load and (2) constraints on the most connected nodes have the greatest effect on both congestion and commodity path length.

Douglas W Lee↗
NASA NTRS2011

TPSAS-NF1676L-12264-DND

The operation of some networks, such as air transportation networks, can be complicated by congestion through a small subset of nodes. The congestion may be influenced by the connectivity of the network, or by the presence of constraints restricting the flow through particular nodes. This work investigates the effects of both connectivity and node flow constraints on the operation of a network. We develop the Minimax Node Load Problem (MNLP), a multicommodity flow model which minimizes the worst-case flow through any node in a given input network. The optimal solution to this problem provides us with the minimax node load, which we propose as a measure of network congestion. Keeping the number of nodes fixed, we first increase connectivity in a series of networks, and observe that topologies with more distributed connections result in a reduction in the minimax node load. However, when connectivity is increased further, the reductions diminish and are accompanied by solutions with undesirable qualities such as longer commodity paths. We then perform a second set of experiments over the same network, constraining flow through different subsets of nodes at different magnitudes of flow restriction, finding that (1) more constrained nodes lead to the largest increases in minimax node load and (2) constraints on the most connected nodes have the greatest effect on both congestion and commodity path length.

Douglas Lee↗
NASA NTRS1970

Chebyshev minimax control theory

General, closed-form, analytical solutions are determined for certain classes of C-minimax control problems, several alternative mathematical theories are derived, and a controller design theory is developed to give optimal control in the presence of unmeasureable external disturbances.

Johnson, C. D.↗
NASA NTRS1984

Analytical redundancy and the design of robust failure detection systems

The Failure Detection and Identification (FDI) process is viewed as consisting of two stages: residual generation and decision making. It is argued that a robust FDI system can be achieved by designing a robust residual generation process. Analytical redundancy, the basis for residual generation, is characterized in terms of a parity space. Using the concept of parity relations, residuals can be generated in a number of ways and the design of a robust residual generation process can be formulated as a minimax optimization problem. An example is included to illustrate this design methodology. Previously announcedd in STAR as N83-20653

Chow, E. Y.↗
NASA NTRS1972

Design of minimax output feedback controller for system with parameter uncertainty

The problem of controlling a time-invariant system with parameter uncertainty is considered with incomplete state feedback. The controller is designed by minimaximizing a quadratic performance criterion and a sensitivity (or loss) criterion, involving the state of the system, the control, and the uncertainty vector. The resulting optimal controller is linear and optimal feedback gain matrix must satisfy a set of nonlinear algebraic equations. some algorithms for algebraic minimax problems are presented.

Basuthakur, S.↗
NASA NTRS1987

Optimal trajectories for aeroassisted, coplanar orbital transfer

Classical and minimax optimal control problems arising in the study of aeroassisted coplanar orbit transfer from a high planetary orbit to a low one are considered. Attention is given to (1) the minimization of the energy required for the maneuver; (2) minimization of the time integral of the heating rate; (3) minimization of the time of flight during the atmospheric portion of the trajectory; (4) maximization of the time of flight during the atmospheric portion of the trajectory; (5) minimization of the time integral of the path inclination; and (6) minimization of the sum of the squares of the entry and exit path inclinations.

Miele, A.↗
NASA NTRS2010

A Minimax Network Flow Model for Characterizing the Impact of Slot Restrictions

This paper proposes a model for evaluating long-term measures to reduce congestion at airports in the National Airspace System (NAS). This model is constructed with the goal of assessing the global impacts of congestion management strategies, specifically slot restrictions. We develop the Minimax Node Throughput Problem (MINNTHRU), a multicommodity network flow model that provides insight into air traffic patterns when one minimizes the worst-case operation across all airports in a given network. MINNTHRU is thus formulated as a model where congestion arises from network topology. It reflects not market-driven airline objectives, but those of a regulatory authority seeking a distribution of air traffic beneficial to all airports, in response to congestion management measures. After discussing an algorithm for solving MINNTHRU for moderate-sized (30 nodes) and larger networks, we use this model to study the impacts of slot restrictions on the operation of an entire hub-spoke airport network. For both a small example network and a medium-sized network based on 30 airports in the NAS, we use MINNTHRU to demonstrate that increasing the severity of slot restrictions increases the traffic around unconstrained hub airports as well as the worst-case level of operation over all airports.

Lee, Douglas W.↗
NASA NTRS1989

Optimal trajectories for hypervelocity flight

Optimal trajectories for hypervelocity flight of interest in aeroassisted orbital transfer are discussed. Both coplanar and noncoplanar transfer are studied. More precisely, the geosynchronous-earth-orbit-, high-earth orbit- and low-earth-orbit-to-low earth-orbit transfers are considered in connection with a spacecraft that is controlled during the atmospheric pass by the angle of attack (coplanar case) or by the angle of attack and the angle of bank (noncoplanar case). Within the framework of classical optimal control, the following problems are studied: minimize the energy required for orbital transfer; maximize the time of flight during the atmospheric portion of the trajectory; and minimize the time integral of the square of the path inclination. Within the framework of minimax optimal control, the problem studied is to minimize the peak rate. Numerical solutions for the problems are obtained by means of the sequential gradient-restoration algorithm. The engineering implications of the results are discussed.

Miele, A.↗
NASA NTRS1992

An inverse dynamics approach to trajectory optimization and guidance for an aerospace plane

The optimal ascent problem for an aerospace planes is formulated as an optimal inverse dynamic problem. Both minimum-fuel and minimax type of performance indices are considered. Some important features of the optimal trajectory and controls are used to construct a nonlinear feedback midcourse controller, which not only greatly simplifies the difficult constrained optimization problem and yields improved solutions, but is also suited for onboard implementation. Robust ascent guidance is obtained by using combination of feedback compensation and onboard generation of control through the inverse dynamics approach. Accurate orbital insertion can be achieved with near-optimal control of the rocket through inverse dynamics even in the presence of disturbances.

Lu, Ping↗
NASA NTRS1973

Output feedback for linear multivariable systems with parameter uncertainty.

A minimax design method is applied to the problem of obtaining an acceptable output feedback matrix for linear multivariable systems with parameter uncertainty. The result is a set of nonlinear matrix equations (similar to those obtained by Levine and Athans (1970)), which must be solved for the feedback matrix. An example illustrates the technique and the fact that better results are achieved for large parameter variation than with a purely nominal design.

Basuthakur, S.↗
NASA NTRS1991

Trajectory optimization and guidance for a hypersonic vehicle

The optimal ascent problem for a hypersonic vehicle is formulated as an inverse dynamic problem. This formulation is essential in solving the trajectory optimization problem via the nonlinear programming approach. Both minimum-fuel and minimax type of performance indices are considered. The results reveal important features of the optimal trajectory and controls, and they are subsequently used to construct a nonlinear feedback midcourse control law. This control law not only greatly simplifies the difficult constrained optimization problem and yields improved solutions, but is also suitable for onboard implementation. Finally, off-nominal trajectory guidance is addressed using combination of feedback compensation and onboard generation of control through the inverse dynamics approach.

Lu, Ping↗
NASA NTRS2012

A Risk-Constrained Multi-Stage Decision Making Approach to the Architectural Analysis of Mars Missions

This paper presents a novel risk-constrained multi-stage decision making approach to the architectural analysis of planetary rover missions. In particular, focusing on a 2018 Mars rover concept, which was considered as part of a potential Mars Sample Return campaign, we model the entry, descent, and landing (EDL) phase and the rover traverse phase as four sequential decision-making stages. The problem is to find a sequence of divert and driving maneuvers so that the rover drive is minimized and the probability of a mission failure (e.g., due to a failed landing) is below a user specified bound. By solving this problem for several different values of the model parameters (e.g., divert authority), this approach enables rigorous, accurate and systematic trade-offs for the EDL system vs. the mobility system, and, more in general, cross-domain trade-offs for the different phases of a space mission. The overall optimization problem can be seen as a chance-constrained dynamic programming problem, with the additional complexity that 1) in some stages the disturbances do not have any probabilistic characterization, and 2) the state space is extremely large (i.e, hundreds of millions of states for trade-offs with high-resolution Martian maps). To this purpose, we solve the problem by performing an unconventional combination of average and minimax cost analysis and by leveraging high efficient computation tools from the image processing community. Preliminary trade-off results are presented.

entry, descent, and landing (EDL)↗
NASA NTRS1989

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗