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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
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↗
NASA NTRS1999

A Survey of Collective Intelligence

This chapter presents the science of "COllective INtelligence" (COIN). A COIN is a large multi-agent systems where: i) the agents each run reinforcement learning (RL) algorithms; ii) there is little to no centralized communication or control; iii) there is a provided world utility function that, rates the possible histories of tile full system. Tile conventional approach to designing large distributed systems to optimize a world utility does not use agents running RL algorithms. Rather that approach begins with explicit modeling of the overall system's dynamics, followed by detailed hand-tuning of the interactions between the components to ensure that they "cooperate" as far as the world utility is concerned. This approach is labor-intensive, often results in highly non-robust systems, and usually results in design techniques that, have limited applicability. In contrast, with COINs we wish to solve the system design problems implicitly, via the 'adaptive' character of the RL algorithms of each of the agents. This COIN approach introduces an entirely new, profound design problem: Assuming the RL algorithms are able to achieve high rewards, what reward functions for the individual agents will, when pursued by those agents, result in high world utility? In other words, what reward functions will best ensure that we do not have phenomena like the tragedy of the commons, or Braess's paradox? Although still very young, the science of COINs has already resulted in successes in artificial domains, in particular in packet-routing, the leader-follower problem, and in variants of Arthur's "El Farol bar problem". It is expected that as it matures not only will COIN science expand greatly the range of tasks addressable by human engineers, but it will also provide much insight into already established scientific fields, such as economics, game theory, or population biology.

Wolpert, David H.↗
NASA NTRS2001

Bargaining for Open Skies

In this paper we analyze the bargaining problem between countries when negotiating bilateral air service agreements. To do so, we use the methods of bargaining and game theory. We give special attention to the case where a liberal minded country is trying to convince a less liberal country to agree to bilateral open skies, and the liberal country might also unilaterally open up its market. The following analysis is positive in the sense that the results help explain and predict the outcome of negotiations under different payoffs and structures of the bargaining process. They are normative in the sense that adequate manipulation of the bargaining conditions can ensure a desired outcome.

Wojahn, Oliver W.↗
NASA NTRS2004

A Survey of Collectives

Due to the increasing sophistication and miniaturization of computational components, complex, distributed systems of interacting agents are becoming ubiquitous. Such systems, where each agent aims to optimize its own performance, but where there is a well-defined set of system-level performance criteria, are called collectives. The fundamental problem in analyzing/designing such systems is in determining how the combined actions of self-interested agents leads to 'coordinated' behavior on a iarge scale. Examples of artificial systems which exhibit such behavior include packet routing across a data network, control of an array of communication satellites, coordination of multiple deployables, and dynamic job scheduling across a distributed computer grid. Examples of natural systems include ecosystems, economies, and the organelles within a living cell. No current scientific discipline provides a thorough understanding of the relation between the structure of collectives and how well they meet their overall performance criteria. Although still very young, research on collectives has resulted in successes both in understanding and designing such systems. It is eqected that as it matures and draws upon other disciplines related to collectives, this field will greatly expand the range of computationally addressable tasks. Moreover, in addition to drawing on them, such a fully developed field of collective intelligence may provide insight into already established scientific fields, such as mechanism design, economics, game theory, and population biology. This chapter provides a survey to the emerging science of collectives.

Tumer, Kagan↗
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 classical, and minimax techniques are described. A unified general formulation and solution for the minimax approach, 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 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 NTRS2004

Product Distributions for Distributed Optimization

With connections to bounded rational game theory, information theory and statistical mechanics, Product Distribution (PD) theory provides a new framework for performing distributed optimization. Furthermore, PD theory extends and formalizes Collective Intelligence, thus connecting distributed optimization to distributed Reinforcement Learning (FU). This paper provides an overview of PD theory and details an algorithm for performing optimization derived from it. The approach is demonstrated on two unconstrained optimization problems, one with discrete variables and one with continuous variables. To highlight the connections between PD theory and distributed FU, the results are compared with those obtained using distributed reinforcement learning inspired optimization approaches. The inter-relationship of the techniques is discussed.

Bieniawski, Stefan R.↗
NASA NTRS2005

Distributed Adaptive Control: Beyond Single-Instant, Discrete Variables

In extensive form noncooperative game theory, at each instant t, each agent i sets its state x, independently of the other agents, by sampling an associated distribution, q(sub i)(x(sub i)). The coupling between the agents arises in the joint evolution of those distributions. Distributed control problems can be cast the same way. In those problems the system designer sets aspects of the joint evolution of the distributions to try to optimize the goal for the overall system. Now information theory tells us what the separate q(sub i) of the agents are most likely to be if the system were to have a particular expected value of the objective function G(x(sub 1),x(sub 2), ...). So one can view the job of the system designer as speeding an iterative process. Each step of that process starts with a specified value of E(G), and the convergence of the q(sub i) to the most likely set of distributions consistent with that value. After this the target value for E(sub q)(G) is lowered, and then the process repeats. Previous work has elaborated many schemes for implementing this process when the underlying variables x(sub i) all have a finite number of possible values and G does not extend to multiple instants in time. That work also is based on a fixed mapping from agents to control devices, so that the the statistical independence of the agents' moves means independence of the device states. This paper also extends that work to relax all of these restrictions. This extends the applicability of that work to include continuous spaces and Reinforcement Learning. This paper also elaborates how some of that earlier work can be viewed as a first-principles justification of evolution-based search algorithms.

Wolpert, David H.↗
NASA NTRS2005

A Comparative Study of Probability Collectives Based Multi-agent Systems and Genetic Algorithms

We compare Genetic Algorithms (GA's) with Probability Collectives (PC), a new framework for distributed optimization and control. In contrast to GA's, PC-based methods do not update populations of solutions. Instead they update an explicitly parameterized probability distribution p over the space of solutions. That updating of p arises as the optimization of a functional of p. The functional is chosen so that any p that optimizes it should be p peaked about good solutions. The PC approach works in both continuous and discrete problems. It does not suffer from the resolution limitation of the finite bit length encoding of parameters into GA alleles. It also has deep connections with both game theory and statistical physics. We review the PC approach using its motivation as the information theoretic formulation of bounded rationality for multi-agent systems. It is then compared with GA's on a diverse set of problems. To handle high dimensional surfaces, in the PC method investigated here p is restricted to a product distribution. Each distribution in that product is controlled by a separate agent. The test functions were selected for their difficulty using either traditional gradient descent or genetic algorithms. On those functions the PC-based approach significantly outperforms traditional GA's in both rate of descent, trapping in false minima, and long term optimization.

Huang, Chien-Feng↗
NASA NTRS2011

Modeling Humans as Reinforcement Learners: How to Predict Human Behavior in Multi-Stage Games

This paper introduces a novel framework for modeling interacting humans in a multi-stage game environment by combining concepts from game theory and reinforcement learning. The proposed model has the following desirable characteristics: (1) Bounded rational players, (2) strategic (i.e., players account for one anothers reward functions), and (3) is computationally feasible even on moderately large real-world systems. To do this we extend level-K reasoning to policy space to, for the first time, be able to handle multiple time steps. This allows us to decompose the problem into a series of smaller ones where we can apply standard reinforcement learning algorithms. We investigate these ideas in a cyber-battle scenario over a smart power grid and discuss the relationship between the behavior predicted by our model and what one might expect of real human defenders and attackers.

Lee, Ritchie↗
NASA NTRSDate not supplied

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↗
NASA NTRSDate not supplied

Off-Nominal Event Analysis in Autonomous Flights Based on Explainable Artificial Intelligence

A key objective in the Urban Air Mobility program at NASA is to intelligently perform an autonomous flight in a complex urban environment under all weather conditions with guaranteed levels of safety. To accomplish this, the mission manager (central decision-making module) of the vehicle needs to make informed decisions between various Courses of Action (CoA) based on its' interpretation of the inputs it receives. If an off-nominal event is detected either based on the amalgamation of sensor data or the use of machine learning models, the mission manager may greatly benefit from identification of the input features that most likely contributed to that specific event. Such an understanding is usually not possible to obtain from the classical machine learning models (deep learning) due to the inherent black box like structure. However, this understanding is achieved using eXplainable Artificial Intelligence (XAI) models that provide a human interpretable rationale for the predictions made. This work presents a game theory inspired XAI model for the off-nominal assessment of autonomous flights. The proposed approach based on Shapley values is model agnostic, provides local as well as global explanation and satisfies the four axioms (efficiency, symmetry, dummy, additivity) to achieve fair contribution. The versatility of the approach is first demonstrated on a simulated dataset in which the significance of each input to flight phase prediction is clearly identified. Subsequently, data from simulated flight trajectories are fed into the model which reveal the input features that most likely contributed to a rotor failure event thereby empowering the mission manager to take the appropriate CoA.

autonomy↗
NASA NTRSDate not supplied

Off-Nominal Event Analysis in Autonomous Flights Based on Explainable Artificial Intelligence

A key objective in the Urban Air Mobility program at NASA is to intelligently perform an autonomous flight in a complex urban environment under all weather conditions with guaranteed levels of safety. To accomplish this, the mission manager (central decision-making module) of the vehicle needs to make informed decisions between various Courses of Action (CoA) based on its' interpretation of the inputs it receives. If an off-nominal event is detected either based on the amalgamation of sensor data or the use of machine learning models, the mission manager may greatly benefit from identification of the input features that most likely contributed to that specific event. Such an understanding is usually not possible to obtain from the classical machine learning models (deep learning) due to the inherent black box like structure. However, this understanding is achieved using eXplainable Artificial Intelligence (XAI) models that provide a human interpretable rationale for the predictions made. This work presents a game theory inspired XAI model for the off-nominal assessment of autonomous flights. The proposed approach based on Shapley values is model agnostic, provides local as well as global explanation and satisfies the four axioms (efficiency, symmetry, dummy, additivity) to achieve fair contribution. The versatility of the approach is first demonstrated on a simulated dataset in which the significance of each input to flight phase prediction is clearly identified. Subsequently, data from simulated flight trajectories are fed into the model which reveal the input features that most likely contributed to a rotor failure event thereby empowering the mission manager to take the appropriate CoA.

autonomy↗
NASA NTRSDate not supplied

Multi-Party Flight Trajectory Negotiation for Upper Class E Traffic Management

A new operational concept has been proposed in Upper Class E airspace at or above 60,000 feet (Flight Level / FL600), which will allow operators of diverse vehicle characteristics to cooperatively manage and share their operational intents with neighboring operators to avoid conflict. There is a consensus in the community that negotiation for strategic deconfliction is needed, but there are no specific guidelines for how the negotiation should be conducted. There is a need for a structured and cooperative way to resolve the conflict between a wide variety of aircraft projected to be operating in Upper Class E for the negotiation to be carried out routinely. The use of negotiation models are a promising solution that can resolve conflict risks during flight in real-time while taking into account the uncertainty of future vehicle positions and dynamic business considerations. A two-party negotiation model has been researched, but as the traffic demand grows, there is a higher likelihood of conflict involving multiple aircraft that would require a method to handle multi-party conflict. This paper proposes a cooperative multi-party negotiation model inspired by game theory concepts for application to flight trajectory negotiation in Upper Class E traffic management. This model can be applied in flight with operators communicating directly after a potential conflict is detected. Some of the model’s benefits include allowing business costs to be private to operators, allowing operators to collaborate together to find conflict-free flight trajectories, and being compatible with different aircraft and operation types. This model provides a structured procedure for conflict resolution that can handle conflict involving multiple parties, assuming each operator is willing to take on a small cost to themselves in order to reduce the total cost to the group.

Upper Class E Traffic Management (ETM)↗
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↗
NASA NTRS2008

Game-Based Learning Theory

Persistent Immersive Synthetic Environments (PISE) are not just connection points, they are meeting places. They are the new public squares, village centers, malt shops, malls and pubs all rolled into one. They come with a sense of 'thereness" that engages the mind like a real place does. Learning starts as a real code. The code defines "objects." The objects exist in computer space, known as the "grid." The objects and space combine to create a "place." A "world" is created, Before long, the grid and code becomes obscure, and the "world maintains focus.

Laughlin, Daniel↗
NASA NTRS1972

Differential games.

General discussion of the theory of differential games with two players and zero sum. Games starting at a fixed initial state and ending at a fixed final time are analyzed. Strategies for the games are defined. The existence of saddle values and saddle points is considered. A stochastic version of a differential game is used to examine the synthesis problem.

Varaiya, P. P.↗