Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Game theory”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS2005

Distributed Optimization

We demonstrate a new framework for analyzing and controlling distributed systems, by solving constrained optimization problems with an algorithm based on that framework. The framework is ar. information-theoretic extension of conventional full-rationality game theory to allow bounded rational agents. The associated optimization algorithm is a game in which agents control the variables of the optimization problem. They do this by jointly minimizing a Lagrangian of (the probability distribution of) their joint state. The updating of the Lagrange parameters in that Lagrangian is a form of automated annealing, one that focuses the multi-agent system on the optimal pure strategy. We present computer experiments for the k-sat constraint satisfaction problem and for unconstrained minimization of NK functions.

Macready, William↗
NASA NTRS2001

Improving Simulated Annealing by Replacing Its Variables with Game-Theoretic Utility Maximizers

The game-theory field of Collective INtelligence (COIN) concerns the design of computer-based players engaged in a non-cooperative game so that as those players pursue their self-interests, a pre-specified global goal for the collective computational system is achieved as a side-effect. Previous implementations of COIN algorithms have outperformed conventional techniques by up to several orders of magnitude, on domains ranging from telecommunications control to optimization in congestion problems. Recent mathematical developments have revealed that these previously developed algorithms were based on only two of the three factors determining performance. Consideration of only the third factor would instead lead to conventional optimization techniques like simulated annealing that have little to do with non-cooperative games. In this paper we present an algorithm based on all three terms at once. This algorithm can be viewed as a way to modify simulated annealing by recasting it as a non-cooperative game, with each variable replaced by a player. This recasting allows us to leverage the intelligent behavior of the individual players to substantially improve the exploration step of the simulated annealing. Experiments are presented demonstrating that this recasting significantly improves simulated annealing for a model of an economic process run over an underlying small-worlds topology. Furthermore, these experiments reveal novel small-worlds phenomena, and highlight the shortcomings of conventional mechanism design in bounded rationality domains.

Wolpert, David H.↗
NASA NTRS2001

Improving Simulated Annealing by Recasting it as a Non-Cooperative Game

The game-theoretic field of COllective INtelligence (COIN) concerns the design of computer-based players engaged in a non-cooperative game so that as those players pursue their self-interests, a pre-specified global goal for the collective computational system is achieved "as a side-effect". Previous implementations of COIN algorithms have outperformed conventional techniques by up to several orders of magnitude, on domains ranging from telecommunications control to optimization in congestion problems. Recent mathematical developments have revealed that these previously developed game-theory-motivated algorithms were based on only two of the three factors determining performance. Consideration of only the third factor would instead lead to conventional optimization techniques like simulated annealing that have little to do with non-cooperative games. In this paper we present an algorithm based on all three terms at once. This algorithm can be viewed as a way to modify simulated annealing by recasting it as a non-cooperative game, with each variable replaced by a player. This recasting allows us to leverage the intelligent behavior of the individual players to substantially improve the exploration step of the simulated annealing. Experiments are presented demonstrating that this recasting improves simulated annealing by several orders of magnitude for spin glass relaxation and bin-packing.

Wolpert, David↗
NASA NTRS2004

Improving Search Algorithms by Using Intelligent Coordinates

We consider algorithms that maximize a global function G in a distributed manner, using a different adaptive computational agent to set each variable of the underlying space. Each agent eta is self-interested; it sets its variable to maximize its own function g (sub eta). Three factors govern such a distributed algorithm's performance, related to exploration/exploitation, game theory, and machine learning. We demonstrate how to exploit alI three factors by modifying a search algorithm's exploration stage: rather than random exploration, each coordinate of the search space is now controlled by a separate machine-learning-based player engaged in a noncooperative game. Experiments demonstrate that this modification improves simulated annealing (SA) by up to an order of magnitude for bin packing and for a model of an economic process run over an underlying network. These experiments also reveal interesting small-world phenomena.

Wolpert, David H.↗
NASA NTRS1990

Time-optimal Aircraft Pursuit-evasion with a Weapon Envelope Constraint

The optimal pursuit-evasion problem between two aircraft including a realistic weapon envelope is analyzed using differential game theory. Six order nonlinear point mass vehicle models are employed and the inclusion of an arbitrary weapon envelope geometry is allowed. The performance index is a linear combination of flight time and the square of the vehicle acceleration. Closed form solution to this high-order differential game is then obtained using feedback linearization. The solution is in the form of a feedback guidance law together with a quartic polynomial for time-to-go. Due to its modest computational requirements, this nonlinear guidance law is useful for on-board real-time implementation.

Menon, P. K. A.↗
NASA NTRS2013

AGATE: Adversarial Game Analysis for Tactical Evaluation

AGATE generates a set of ranked strategies that enables an autonomous vehicle to track/trail another vehicle that is trying to break the contact using evasive tactics. The software is efficient (can be run on a laptop), scales well with environmental complexity, and is suitable for use onboard an autonomous vehicle. The software will run in near-real-time (2 Hz) on most commercial laptops. Existing software is usually run offline in a planning mode, and is not used to control an unmanned vehicle actively. JPL has developed a system for AGATE that uses adversarial game theory (AGT) methods (in particular, leader-follower and pursuit-evasion) to enable an autonomous vehicle (AV) to maintain tracking/ trailing operations on a target that is employing evasive tactics. The AV trailing, tracking, and reacquisition operations are characterized by imperfect information, and are an example of a non-zero sum game (a positive payoff for the AV is not necessarily an equal loss for the target being tracked and, potentially, additional adversarial boats). Previously, JPL successfully applied the Nash equilibrium method for onboard control of an autonomous ground vehicle (AGV) travelling over hazardous terrain.

Huntsberger, Terrance L.↗
NASA NTRS1995

A Game Theoretic Fault Detection Filter

The fault detection process is modelled as a disturbance attenuation problem. The solution to this problem is found via differential game theory, leading to an H(sub infinity) filter which bounds the transmission of all exogenous signals save the fault to be detected. For a general class of linear systems which includes some time-varying systems, it is shown that this transmission bound can be taken to zero by simultaneously bringing the sensor noise weighting to zero. Thus, in the limit, a complete transmission block can he achieved, making the game filter into a fault detection filter. When we specialize this result to time-invariant system, it is found that the detection filter attained in the limit is identical to the well known Beard-Jones Fault Detection Filter. That is, all fault inputs other than the one to be detected (the "nuisance faults") are restricted to an invariant subspace which is unobservable to a projection on the output. For time-invariant systems, it is also shown that in the limit, the order of the state-space and the game filter can be reduced by factoring out the invariant subspace. The result is a lower dimensional filter which can observe only the fault to be detected. A reduced-order filter can also he generated for time-varying systems, though the computational overhead may be intensive. An example given at the end of the paper demonstrates the effectiveness of the filter as a tool for fault detection and identification.

Chung, Walter H.↗
NASA NTRS1969

Nonzero-sum differential games.

Differential games theory with nonzero sum for application to economic analysis, discussing Nash equilibrium, minimax and noninferior strategies set

Ho, Y. C.↗
NASA NTRS1970

Differential games

Differential game theory, discussing two player zero sum situation

Varaiya, P. P.↗
NASA NTRS1983

Dynamics and control of forward swept wing aircraft

Aspects of non-zero differential game theory with application to multivariable control synthesis and optimal linear control law design using optimum parameter sensitivity analysis are discussed.

Schmidt, D. K.↗
NASA NTRS1988

Methodology for determination and use of the no-escape envelope of an air-to-air-missile

A large gap exists between optimal control and differential-game theory and their applications. The purpose of this paper is to show how this gap may be bridged. Missile-avoidance of realistically simulated infrared heat-seeking, fire-and-forget missile is studied. In detailed simulations, sweeping out the discretized initial condition space, avoidance methods based on pilot experience are combined with those based on simplified optimal control analysis to derive an approximation to the no-escape missile envelopes. The detailed missile equations and no-escape envelopes were then incorporated into an existing piloted simulation of air-to-air combat to generate missile firing decisions as well as missile avoidance commands. The use of these envelopes was found to be effective in both functions.

Neuman, Frank↗
NASA NTRS1989

Study of a pursuit-evasion guidance law for high performance aircraft

The study of a one-on-one aircraft pursuit-evasion guidance scheme for high-performance aircraft is discussed. The research objective is to implement a guidance law derived earlier using differential game theory in conjunction with the theory of feedback linearization. Unlike earlier research in this area, the present formulation explicitly recognizes the two-sided nature of the pursuit-evasion scenario. The present research implements the guidance law in a realistic model of a modern high-performance fighter aircraft. Also discussed are the details of the guidance law, implementation in a highly detailed simulation of a high-performance fighter, and numerical results for two engagement geometries. Modifications of the guidance law for onboard implementation is also discussed.

Williams, Peggy S.↗
NASA NTRS1991

Real-time simulation of helicopter air-to-air combat

The AUTOMAN computer program develops automated maneuvering decisions for helicopters during air-to-air combat over hilly terrain. Recently, the capabilities of this program have been extended and enhanced significantly. The revised program was installed at the NASA Ames manned flight-simulation facility to drive a computer-generated image of an enemy helicopter, thereby providing an adversary for the human pilot. Maneuvers are selected by employing game theory. Enhancements include a guidance law for target acquisition when a firing opportunity arises; fire-control sequence logic; improved low-flying capabilities; line-of-sight computations for the cockpit field-of-view, terrain obstructions, and visual range limits; use of terrain for masking; air-to-air collision-avoidance maneuvers; decision on dispensing flares and chaff; and adjustable levels of pilot experience. The program was found to be extremely useful for both rotorcraft handling-quality evaluations and air-to-air combat training.

Austin, Fred↗
NASA NTRS1992

Robustness of solutions to a benchmark control problem

The robustness of 10 solutions to a benchmark control design problem presented at the 1990 American Control Conference has been evaluated. The 10 controllers have second-to-eighth-order transfer functions and have been designed using several different methods, including H-infinity optimization, loop-transfer recovery, imaginary-axis shifting, constrained optimization, structured covariance, game theory, and the internal model principle. Stochastic robustness analysis quantifies the controllers' stability and performance robustness with structured uncertainties in up to six system parameters. The analysis provides insights into system response that are not readily derived from other robustness criteria and provides a common ground for judging controllers produced by alternative methods. One important conclusion is that gain and phase margins are not reliable indicators of the probability of instability. Furthermore, parameter variations actually may improve the likelihood of achieving selected performance metrics, as demonstrated by results for the probability of settling-time exceedance.

Stengel, Robert F.↗
NASA NTRS1997

An Algorithm for Integrated Subsystem Embodiment and System Synthesis

Consider the statement,'A system has two coupled subsystems, one of which dominates the design process. Each subsystem consists of discrete and continuous variables, and is solved using sequential analysis and solution.' To address this type of statement in the design of complex systems, three steps are required, namely, the embodiment of the statement in terms of entities on a computer, the mathematical formulation of subsystem models, and the resulting solution and system synthesis. In complex system decomposition, the subsystems are not isolated, self-supporting entities. Information such as constraints, goals, and design variables may be shared between entities. But many times in engineering problems, full communication and cooperation does not exist, information is incomplete, or one subsystem may dominate the design. Additionally, these engineering problems give rise to mathematical models involving nonlinear functions of both discrete and continuous design variables. In this dissertation an algorithm is developed to handle these types of scenarios for the domain-independent integration of subsystem embodiment, coordination, and system synthesis using constructs from Decision-Based Design, Game Theory, and Multidisciplinary Design Optimization. Implementation of the concept in this dissertation involves testing of the hypotheses using example problems and a motivating case study involving the design of a subsonic passenger aircraft.

Lewis, Kemper↗
NASA NTRS1999

Transonic Flutter Suppression Control Law Design Using Classical and Optimal Techniques with Wind-Tunnel Results

The benchmark active controls technology and wind tunnel test program at NASA Langley Research Center was started with the objective to investigate the nonlinear, unsteady aerodynamics and active flutter suppression of wings in transonic flow. The paper will present the flutter suppression control law design process, numerical nonlinear simulation and wind tunnel test results for the NACA 0012 benchmark active control wing model. The flutter suppression control law design processes using (1) classical, (2) linear quadratic Gaussian (LQG), and (3) minimax techniques are described. A unified general formulation and solution for the LQG and minimax approaches, based on the steady state differential game theory is presented. Design considerations for improving the control law robustness and digital implementation are outlined. It was shown that simple control laws when properly designed based on physical principles, can suppress flutter with limited control power even in the presence of transonic shocks and flow separation. In wind tunnel tests in air and heavy gas medium, the closed-loop flutter dynamic pressure was increased to the tunnel upper limit of 200 psf. The control law robustness and performance predictions were verified in highly nonlinear flow conditions, gain and phase perturbations, and spoiler deployment. A non-design plunge instability condition was also successfully suppressed.

Mukhopadhyay, Vivek↗
NASA NTRS1999

Transonic Flutter Suppression Control Law Design, Analysis and Wind Tunnel Results

The benchmark active controls technology and wind tunnel test program at NASA Langley Research Center was started with the objective to investigate the nonlinear, unsteady aerodynamics and active flutter suppression of wings in transonic flow. The paper will present the flutter suppression control law design process, numerical nonlinear simulation and wind tunnel test results for the NACA 0012 benchmark active control wing model. The flutter suppression control law design processes using (1) classical, (2) linear quadratic Gaussian (LQG), and (3) minimax techniques are described. A unified general formulation and solution for the LQG and minimax approaches, based on the steady state differential game theory is presented. Design considerations for improving the control law robustness and digital implementation are outlined. It was shown that simple control laws when properly designed based on physical principles, can suppress flutter with limited control power even in the presence of transonic shocks and flow separation. In wind tunnel tests in air and heavy gas medium, the closed-loop flutter dynamic pressure was increased to the tunnel upper limit of 200 psf The control law robustness and performance predictions were verified in highly nonlinear flow conditions, gain and phase perturbations, and spoiler deployment. A non-design plunge instability condition was also successfully suppressed.

Mukhopadhyay, Vivek↗