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

A Survey of Mathematical Structures for Lunar Networks

To sustain the current and increasing accessibility of space, a scalable communications infrastructure (i.e. the Solar System Internet, SSI) is necessary. The goal of this paper is to begin the discovery of the fundamental underlying mathematical structure of space networks to help the research community harness these structures for algorithm development and optimization. To ensure the applicability of the research, the approaches are considered through the lens of simulated scenarios inspired by the Artemis Back-to-the-Moon mission set for 2024. We note that any approach to an SSI must fit under the umbrella of Delay Tolerant Networking (DTN), due to celestial mobility, high link latencies, high variance in link latencies, disconnections, lack of end-to-end paths, and so on. These difficulties are exacerbated by the fact that the underlying structure of a space network is a time-evolving network and may experience multiple discontinuities in its topology. In this paper we propose several novel approaches to a mathematical foundation for Delay Tolerant Networking Theory that fall outside the traditional scope of temporal network theory. These techniques include methods from Topological Data Analysis, Dynamic Graph Analysis, Applied Algebraic Geometry, Probability Theory, and Game Theory. Some of these methods include tools adapted to the study of dynamic metric spaces, such as zigzag persistent homology and their higher parameter analogs. We find that several of these methods target desired engineering outcomes such as discovery and automatic sub-netting. While each approach is theoretical, they are also algorithmic in nature and offer immediate practical applications. The paper concludes with comparisons of the various methods along with suggestions for future work.

Delay tolerant networking↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques For Space Network Scalability

Routing in the space internet must face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this paper we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. We propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol (DTCP). In addition, we explore the underlying networking mechanisms such as multicast, neighbor discovery, and software defined networking that may be used to enable DTCP.

Delay Tolerant Networking↗
NASA NTRS2012

Colonel Blotto Games and Lancaster's Equations: A Novel Military Modeling Combination

Military strategists face a difficult task when engaged in a battle against an adversarial force. They have to predict both what tactics their opponent will employ and the outcomes of any resultant conflicts in order to make the best decision about their actions. Game theory has been the dominant technique used by analysts to investigate the possible actions that an enemy will employ. Traditional game theory can be augmented by use of Lanchester equations, a set of differential equations used to determine the outcome of a conflict. This paper demonstrates a novel combination of game theory and Lanchester equations using Colonel Blotto games. Colonel Blotto games, which are one of the oldest applications of game theory to the military domain, look at the allocation of troops and resources when fighting across multiple areas of operation. This paper demonstrates that employing Lanchester equations within a game overcomes some of practical problems faced when applying game theory.

Collins, Andrew J.↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques Applied to Contact Graph Routing

Routing in the space internet has to face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this presentation we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. Finally, we propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol.

Yael Kirkpatrick↗
NASA NTRS1984

Design of vibration isolation systems using multiobjective optimization techniques

The design of vibration isolation systems is considered using multicriteria optimization techniques. The integrated values of the square of the force transmitted to the main mass and the square of the relative displacement between the main mass and the base are taken as the performance indices. The design of a three degrees-of-freedom isolation system with an exponentially decaying type of base disturbance is considered for illustration. Numerical results are obtained using the global criterion, utility function, bounded objective, lexicographic, goal programming, goal attainment and game theory methods. It is found that the game theory approach is superior in finding a better optimum solution with proper balance of the various objective functions.

Rao, S. S.↗
NASA NTRS1995

Structural design using equilibrium programming formulations

Solutions to increasingly larger structural optimization problems are desired. However, computational resources are strained to meet this need. New methods will be required to solve increasingly larger problems. The present approaches to solving large-scale problems involve approximations for the constraints of structural optimization problems and/or decomposition of the problem into multiple subproblems that can be solved in parallel. An area of game theory, equilibrium programming (also known as noncooperative game theory), can be used to unify these existing approaches from a theoretical point of view (considering the existence and optimality of solutions), and be used as a framework for the development of new methods for solving large-scale optimization problems. Equilibrium programming theory is described, and existing design techniques such as fully stressed design and constraint approximations are shown to fit within its framework. Two new structural design formulations are also derived. The first new formulation is another approximation technique which is a general updating scheme for the sensitivity derivatives of design constraints. The second new formulation uses a substructure-based decomposition of the structure for analysis and sensitivity calculations. Significant computational benefits of the new formulations compared with a conventional method are demonstrated.

Scotti, Stephen J.↗
NASA NTRS2005

What Information Theory Says about Bounded Rational Best Response

Probability Collectives (PC) provides the information-theoretic extension of conventional full-rationality game theory to bounded rational games. Here an explicit solution to the equations giving the bounded rationality equilibrium of a game is presented. Then PC is used to investigate games in which the players use bounded rational best-response strategies. Next it is shown that in the continuum-time limit, bounded rational best response games result in a variant of the replicator dynamics of evolutionary game theory. It is then shown that for team (shared-payoff) games, this variant of replicator dynamics is identical to Newton-Raphson iterative optimization of the shared utility function.

Wolpert, David H.↗
NASA NTRS2004

What Information Theory Says About Best Response and About Binding Contracts

Product Distribution (PD) theory is the information-theoretic extension of conventional full- rationality game theory to bounded rational games. Here PD theory is used to investigate games in which the players use bounded rational best-response strategies. This investigation illuminates how to determine the optimal organization chart for a corporation, or more generally how to order the sequence of moves of the players / employees so as to optimize an overall objective function. It is then shown that in the continuum-time limit, bounded rational best response games result in a variant of the replicator dynamics of evolutionary game theory. This variant is then investigated for team games, in which the players share the same utility function, by showing that such continuum- limit bounded rational best response is identical to Newton-Raphson iterative optimization of the shared utility function. Next PD theory is used to investigate changing the coordinate system of the game, i.e., changing the mapping from the joint move of the players to the arguments in the utility functions. Such a change couples those arguments, essentially by making each players move be an offered binding contract.

Wolpert, David H.↗
NASA NTRS2004

Beyond Mechanism Design

The field of mechanism design is concerned with setting (incentives superimposed on) the utility functions of a group of players so as to induce desirable joint behavior of those players. It arose in the context of traditional equilibrium game theory applied to games involving human players. This has led it to have many implicit restrictions, which strongly limits its scope. In particular, it ignores many issues that are crucial for systems that are large (and therefore far off-equilibrium in general) and/or composed of non-human players (e.g., computer-based agents). This also means it has concentrated on issues that are often irrelevant in those broader domains (e.g., incentive compatibility). This paper illustrates these shortcomings by reviewing some of the recent theoretical work on the design of collectives, a body of work that constitutes a substantial broadening of mechanism design. It then presents computer experiments based on a recently suggested nanotechnology testbed that demonstrates the power of that extended version of mechanism design.

Wolpert, David H.↗
NASA NTRS1984

Multiobjective optimization in structural design with uncertain parameters and stochastic processes

The application of multiobjective optimization techniques to structural design problems involving uncertain parameters and random processes is studied. The design of a cantilever beam with a tip mass subjected to a stochastic base excitation is considered for illustration. Several of the problem parameters are assumed to be random variables and the structural mass, fatigue damage, and negative of natural frequency of vibration are considered for minimization. The solution of this three-criteria design problem is found by using global criterion, utility function, game theory, goal programming, goal attainment, bounded objective function, and lexicographic methods. It is observed that the game theory approach is superior in finding a better optimum solution, assuming the proper balance of the various objective functions. The procedures used in the present investigation are expected to be useful in the design of general dynamic systems involving uncertain parameters, stochastic process, and multiple objectives.

Rao, S. S.↗
NASA NTRS1984

Multiobjective optimization techniques for structural design

The multiobjective programming techniques are important in the design of complex structural systems whose quality depends generally on a number of different and often conflicting objective functions which cannot be combined into a single design objective. The applicability of multiobjective optimization techniques is studied with reference to simple design problems. Specifically, the parameter optimization of a cantilever beam with a tip mass and a three-degree-of-freedom vabration isolation system and the trajectory optimization of a cantilever beam are considered. The solutions of these multicriteria design problems are attempted by using global criterion, utility function, game theory, goal programming, goal attainment, bounded objective function, and lexicographic methods. It has been observed that the game theory approach required the maximum computational effort, but it yielded better optimum solutions with proper balance of the various objective functions in all the cases.

Rao, S. S.↗
NASA NTRS2004

Finding Bounded Rational Equilibria: Iterative Focusing - Part 1

A long-running difficulty with conventional game theory has been how to modify it to accommodate the bounded rationality characterizing all real-world players. A recurring issue in statistical physics is how best to approximate joint probability distributions with decoupled (and therefore far more tractable) distributions. It has recently been shown that the same information theoretic mathematical structure, known as Probability Collectives (PC) underlies both issues. This relationship between statistical physics and game theory allows techniques and insights from the one field to be applied to the other. In particular, PC provides a formal model-independent definition of the degree of rationality of a player and of bounded rationality equilibria. This pair of papers extends previous work on PC by introducing new computational approaches to effectively find bounded rationality equilibria of common-interest (team) games.

Wolpert, David H.↗
NASA NTRS2004

Finding Bounded Rational Equilibria: Alternative Lagrangians and Uncountable Move Spaces - Part 2

A long-running difficulty with conventional game theory has been how to modify it to accommodate the bounded rationality characterizing all real-world players. A recurring issue in statistical physics is how best to approximate joint probability distributions with decoupled (and therefore far more tractable) distributions. It has recently been shown that the same information theoretic mathematical structure, known as Probability Collectives (PC) underlies both issues. This relationship between statistical physics and game theory allows techniques and insights &om the one field to be applied to the other. In particular, PC provides a formal model-independent definition of the degree of rationality of a player and of bounded rationality equilibria. This pair of papers extends previous work on PC by introducing new computational approaches to effectively find bounded rationality equilibria of common-interest (team) games.

Wolpert, David H.↗
DOE OSTI2026

From Modular ADMS to Plug-and-Play Ops: Distribution Grid Operations with Platform-Level Orchestration to Enable Ambitious App Hosting

The core function of the distribution grid is to provide electricity to consumers affordably, reliably, and securely. In pursuing these core objectives, distribution utilities are accountable to customers, regulators, and in some cases, shareholders. Other third parties such as aggregators and microgrids can also have a stake in the smooth operation of the grid. Each of these stakeholders has economic, business, and/or governance objectives that inform their expectations of the distribution grid. This multi-objective, multi-stakeholder environment creates tension that must be reconciled to successfully design and operate the distribution grid. Innovative companies are competing to bring high-tech solutions to electric utilities and their customers that address each of these objectives. Many developers of advanced distribution management systems (ADMS) and distributed energy resource management systems (DERMS) have adopted a modular architecture that allows grid operators to select functions and features according to their individual system needs. A modular platform also allows the solution provider to develop and integrate specific new product modules; however, the need to pursue multiple objectives with a fixed set of controllable devices makes integration expensive whether it is done at the product development stage or the deployment stage. This cost creates a significant barrier to adoption and can lengthen the product to market time of new solutions. To fundamentally address the complexity of system integration for distribution grid operations, the U.S. Department of Energy Office of Electricity has funded the GridAPPS-D project at PNNL, which streamlines integration by contributing to standards development, defining system architecture, applying advanced mathematics, and developing open-source software to demonstrate the concept of an open data-integration platform for distribution operations. The open data-integration platform concept enables system operators and solution providers to deploy ambitious, best-of-breed applications (or apps) without continually reengineering for integration. Ambitious apps developed by different solution providers will inevitably attempt to achieve different control objectives with the same set of controllable devices. If the open platform itself can resolve these conflicts in a way that achieves the best available outcomes for all apps, doesn’t restrict the ambitious design of apps, and ensures safe and secure operations, apps will be able to plug-and-play with the platform at the same time as other ambitious apps. In this paper, we describe a framework called App Deconfliction that empowers a platform to assign setpoints to controllable devices based on the values preferred by different apps (and even external stakeholder entities like customers or aggregators). The App Deconfliction framework is compatible with several methods for determining setpoint values. We present two methods based on game theory that provide a subtle built-in incentive structure for developers to adapt their apps to the fact that they will be operating in a moderated multi-app environment and to favor device setpoints that have the most effect on their objectives over those that have the least effect. Our simulation-based demonstrations have shown that game-theory-based deconfliction can lead to a 7% improvement in control space utilization compared to design-based methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2006

Distributed Constrained Optimization with Semicoordinate Transformations

Recent work has shown how information theory extends conventional full-rationality game theory to allow bounded rational agents. The associated mathematical framework can be used to solve constrained optimization problems. This is done by translating the problem into an iterated game, where each agent controls a different variable of the problem, so that the joint probability distribution across the agents moves gives an expected value of the objective function. The dynamics of the agents is designed to minimize a Lagrangian function of that joint distribution. Here we illustrate how the updating of the Lagrange parameters in the Lagrangian is a form of automated annealing, which focuses the joint distribution more and more tightly about the joint moves that optimize the objective function. We then investigate the use of "semicoordinate" variable transformations. These separate the joint state of the agents from the variables of the optimization problem, with the two connected by an onto mapping. We present experiments illustrating the ability of such transformations to facilitate optimization. We focus on the special kind of transformation in which the statistically independent states of the agents induces a mixture distribution over the optimization variables. Computer experiment illustrate this for &sat constraint satisfaction problems and for unconstrained minimization of NK functions.

Macready, William↗
NASA NTRS1975

A state-of-the-art review of transportation systems evaluation techniques relevant to air transportation, volume 1

Mathematical and philosophical approaches are presented for evaluation and implementation of ground and air transportation systems. Basic decision processes are examined that are used for cost analyses and planning (i.e, statistical decision theory, linear and dynamic programming, optimization, game theory). The effects on the environment and the community that a transportation system may have are discussed and modelled. Algorithmic structures are examined and selected bibliographic annotations are included. Transportation dynamic models were developed. Citizen participation in transportation projects (i.e, in Maryland and Massachusetts) is discussed. The relevance of the modelling and evaluation approaches to air transportation (i.e, airport planning) is examined in a case study in St. Louis, Missouri.

Haefner, L. E.↗