### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

# Game Theory and Vehicle Dynamic

Game Theory and Vehicle Dynamic

by

Tweet## Saeid Khosravani

on 25 March 2013#### Transcript of Game Theory and Vehicle Dynamic

The Nash Equilibrium Notes Multi-Objective & Game-Theory (cc) photo by Metro Centric on Flickr (cc) photo by Franco Folini on Flickr (cc) photo by jimmyharris on Flickr (cc) photo by Metro Centric on Flickr the study of mathematical model of conflict and cooperation between intelligent rational decision-makers ... small Mechanical and Mechatronics Engineering Game Theory

&

Vehicle Control Outline Game Theory

Nash Equilibrium

Differential Game Theory

Optimal Control and Game Theory

Multi Objective Optimization

Vehicle Control Definition John von Neuman (1903-1957) co-authored, Theory of Games and Economic Behavior, with Oskar Morgenstern in 1940s, establishing game theory as a field.

John Nash (1928 - ) developed a key concept of game theory (Nash equilibrium) which initiated many subsequent results and studies

Since 1970s, game-theoretic methods have come to dominate microeconomic theory and other fields

Nobel prizes

Nobel prize in Economic Sciences 1994 awarded to Nash, Harsanyi

(Bayesian games) and Selten (subgame perfect equilibrium)

2005, Auman and Schelling got the Nobel prize for having enhanced

our understanding of cooperation and conflict through game theory

2007 Leonid Hurwicz, Eric Maskin and Roger Myerson won Nobel Prize

for having laid the foundations of mechanism design theory. History Representation of games The games studied by game theory are well-defined mathematical objects.

A game consists of a set of players, a set of moves

(or strategies) available to those players, and a specification of payoffs

for each combination of strategies. Who is interacting? What are their options? What are their incentives? Information: What do they know? Rationality: How do they think? Further Explanation Discipline aiming at modeling situations in which actors have to make decisions which have mutual, possibly conflicting, consequences Example: should a company invest in a new plant, or enter a new market, considering that the competition may make similar moves? Most widespread kind of game: non-cooperative (meaning that the players do not attempt to find an agreement about their possible moves) and cooperative (two or more player attempt to obtain maximum benefit working together - In cooperative game theory, binding agreements are allowed and the unit of analysis is the group or coalition. ) Different Games Non-cooperative

static games Repeated games Stochastic games Cooperative Games Dynamic games ODE for state,

Optimization utility over time,

HJB and dynamic programming Evolutional game Dominant strategy is a player's best strategy, i.e., a strategy that yields the highest utility for the player regardless of what strategies the other players choose. Quiet Fink Quiet Fink 1,1 4,0 0,4 3,3 Player 1 Player 2 Prisoner’s dilemma Strict dominance

strictly best strategy, for any strategy of the other player(s) . Two suspects in a major crime held for interrogation in separate cells

If they both stay quiet, each will be convicted with a minor

offence and will spend 1 year in prison

If one and only one of them finks, he will be freed and used as a witness against the other who will spend 4 years in prison

If both of them fink, each will spend 3 years in prison Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Prisonner's

Delimma Different

Nash Equilibrium Quiet Fink Quiet Fink 1,1 4,0 0,4 3,3 Player 1 Player 2 Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Quiet Fink Quiet Fink 2,3 0,0 0,0 3,2 Player 1 Player 2 Prisoner’s dilemma Strict dominance

strictly best strategy, for any strategy of the other player(s) . Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Does the Nash equilibrium always exist?

Is it efficient ?

One measure of efficiency is Pareto optimality.

In some references a strategy profile that achieves a Pareto optimal payoff distribution can sometimes be referred to as a Pareto optimal strategy Pareto Optimal

Nash Equilibrium Nash Equilibrium (3,3) is not a good equilibrium because there is no guarantee that P1 also fink.

On the other hand even if P2 be sure that P1 will fink, the best action is to Fink. Multiple

Nash

Equilibrium Two-person, zero-sum differential game basic idea: two players control the dynamics of some evolving system, and one tries to maximize, the other to minimize, a payoff functional that depends upon the trajectory. Cooperative Game Theory Players have mutual benefit to cooperate

Bargaining situation

A number of individuals have a common interest to cooperate but a conflicting interest on how to cooperate

A cooperative game means that the players agree to form

coalitions under the expectation that, by working together

a mutually beneficial outcome can be obtained. Preliminary

definitions Multiobjective optimization

and

Game Theory Saeid Khosravani convert multi-objective optimization problem to a single-objective optimization problem (i.e. considering one of the cost function as the leader and the other as its constraints)

transform multi-objective optimization problem into multiple single-objective optimization problems

Minimax theory

Goal Programming

Weighted Sum

Evolutionary Algorithms

Game theory General Form Linear Function Extension to

Non-Linear Open Problem Game Theory

and

Vehicle Control Vehicle Dynamic Prof. Ahmadian’s group used Co-operative differential Game theory to find Nash equilibrium of cost function (quadratic form) , and consequently optimal solution of the problem.

Although their simulation shows improvement in control of the vehicle, one may ask, if we can model vehicle system control and driver as players of a Game?!

What are utilities and payoffs?

The driver can not be a player because when control strategy is on, he can not decide whether use the controller or not?

It is quite hard to consider controller as a player as well!

Does Optimal Control theory provide us the best solution for this circumstance?! Discussion Research Up to now there are no nice (i.e. easily checkable) conditions

ensuring the existence of solution for Riccati Equations.

On the other hand numerical solutions approaches are time consuming

and may not be efficient and applicable in real-time.

Driver models are usually based on preview of the road ahead Discussion Driver / VSC interaction model The Driver’s Steering input and the Controller’s compensated yaw moment are defined as two dynamic players of the game “Vehicle Stability” Modeling as a LQR/LQT Nonlinear VEHICLE MODEL for simulation

Linear model for Control Course Notes on the internet.

T. Basar and G.J. Olsder, Dynamic Non-cooperative Game Theory, 2nd edition, SIAM Classics,. 1999

Tamaddoni, S., Taheri, S., and Ahmadian, M., "Linear Quadratic Game Theory Approach to Optimal Preview Control of Vehicle Lateral Motion," SAE Int. J. of Passeng. Cars – Mech. Syst. 4(1)

M. A. Johnson, 2011, A Differential Game-Based Control methods for uncertain continuous time Nonlinear systems, University of Florida References Thank you s4khosra@uwaterloo.ca Non-cooperative static games Repeated

games Stochastic

games Cooperative

Games Dynamic

games Best Choice for P2 http://www.engineering.uwaterloo.ca/~s4khosra/

Full transcript&

Vehicle Control Outline Game Theory

Nash Equilibrium

Differential Game Theory

Optimal Control and Game Theory

Multi Objective Optimization

Vehicle Control Definition John von Neuman (1903-1957) co-authored, Theory of Games and Economic Behavior, with Oskar Morgenstern in 1940s, establishing game theory as a field.

John Nash (1928 - ) developed a key concept of game theory (Nash equilibrium) which initiated many subsequent results and studies

Since 1970s, game-theoretic methods have come to dominate microeconomic theory and other fields

Nobel prizes

Nobel prize in Economic Sciences 1994 awarded to Nash, Harsanyi

(Bayesian games) and Selten (subgame perfect equilibrium)

2005, Auman and Schelling got the Nobel prize for having enhanced

our understanding of cooperation and conflict through game theory

2007 Leonid Hurwicz, Eric Maskin and Roger Myerson won Nobel Prize

for having laid the foundations of mechanism design theory. History Representation of games The games studied by game theory are well-defined mathematical objects.

A game consists of a set of players, a set of moves

(or strategies) available to those players, and a specification of payoffs

for each combination of strategies. Who is interacting? What are their options? What are their incentives? Information: What do they know? Rationality: How do they think? Further Explanation Discipline aiming at modeling situations in which actors have to make decisions which have mutual, possibly conflicting, consequences Example: should a company invest in a new plant, or enter a new market, considering that the competition may make similar moves? Most widespread kind of game: non-cooperative (meaning that the players do not attempt to find an agreement about their possible moves) and cooperative (two or more player attempt to obtain maximum benefit working together - In cooperative game theory, binding agreements are allowed and the unit of analysis is the group or coalition. ) Different Games Non-cooperative

static games Repeated games Stochastic games Cooperative Games Dynamic games ODE for state,

Optimization utility over time,

HJB and dynamic programming Evolutional game Dominant strategy is a player's best strategy, i.e., a strategy that yields the highest utility for the player regardless of what strategies the other players choose. Quiet Fink Quiet Fink 1,1 4,0 0,4 3,3 Player 1 Player 2 Prisoner’s dilemma Strict dominance

strictly best strategy, for any strategy of the other player(s) . Two suspects in a major crime held for interrogation in separate cells

If they both stay quiet, each will be convicted with a minor

offence and will spend 1 year in prison

If one and only one of them finks, he will be freed and used as a witness against the other who will spend 4 years in prison

If both of them fink, each will spend 3 years in prison Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Prisonner's

Delimma Different

Nash Equilibrium Quiet Fink Quiet Fink 1,1 4,0 0,4 3,3 Player 1 Player 2 Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Quiet Fink Quiet Fink 2,3 0,0 0,0 3,2 Player 1 Player 2 Prisoner’s dilemma Strict dominance

strictly best strategy, for any strategy of the other player(s) . Components of the Prisoner’s dilemma

Rational Players: the prisoners

Strategies: Stay quiet (Q) or Fink (F)

Solution: What is the Nash equilibrium of the game?

Representation in Strategic Form Does the Nash equilibrium always exist?

Is it efficient ?

One measure of efficiency is Pareto optimality.

In some references a strategy profile that achieves a Pareto optimal payoff distribution can sometimes be referred to as a Pareto optimal strategy Pareto Optimal

Nash Equilibrium Nash Equilibrium (3,3) is not a good equilibrium because there is no guarantee that P1 also fink.

On the other hand even if P2 be sure that P1 will fink, the best action is to Fink. Multiple

Nash

Equilibrium Two-person, zero-sum differential game basic idea: two players control the dynamics of some evolving system, and one tries to maximize, the other to minimize, a payoff functional that depends upon the trajectory. Cooperative Game Theory Players have mutual benefit to cooperate

Bargaining situation

A number of individuals have a common interest to cooperate but a conflicting interest on how to cooperate

A cooperative game means that the players agree to form

coalitions under the expectation that, by working together

a mutually beneficial outcome can be obtained. Preliminary

definitions Multiobjective optimization

and

Game Theory Saeid Khosravani convert multi-objective optimization problem to a single-objective optimization problem (i.e. considering one of the cost function as the leader and the other as its constraints)

transform multi-objective optimization problem into multiple single-objective optimization problems

Minimax theory

Goal Programming

Weighted Sum

Evolutionary Algorithms

Game theory General Form Linear Function Extension to

Non-Linear Open Problem Game Theory

and

Vehicle Control Vehicle Dynamic Prof. Ahmadian’s group used Co-operative differential Game theory to find Nash equilibrium of cost function (quadratic form) , and consequently optimal solution of the problem.

Although their simulation shows improvement in control of the vehicle, one may ask, if we can model vehicle system control and driver as players of a Game?!

What are utilities and payoffs?

The driver can not be a player because when control strategy is on, he can not decide whether use the controller or not?

It is quite hard to consider controller as a player as well!

Does Optimal Control theory provide us the best solution for this circumstance?! Discussion Research Up to now there are no nice (i.e. easily checkable) conditions

ensuring the existence of solution for Riccati Equations.

On the other hand numerical solutions approaches are time consuming

and may not be efficient and applicable in real-time.

Driver models are usually based on preview of the road ahead Discussion Driver / VSC interaction model The Driver’s Steering input and the Controller’s compensated yaw moment are defined as two dynamic players of the game “Vehicle Stability” Modeling as a LQR/LQT Nonlinear VEHICLE MODEL for simulation

Linear model for Control Course Notes on the internet.

T. Basar and G.J. Olsder, Dynamic Non-cooperative Game Theory, 2nd edition, SIAM Classics,. 1999

Tamaddoni, S., Taheri, S., and Ahmadian, M., "Linear Quadratic Game Theory Approach to Optimal Preview Control of Vehicle Lateral Motion," SAE Int. J. of Passeng. Cars – Mech. Syst. 4(1)

M. A. Johnson, 2011, A Differential Game-Based Control methods for uncertain continuous time Nonlinear systems, University of Florida References Thank you s4khosra@uwaterloo.ca Non-cooperative static games Repeated

games Stochastic

games Cooperative

Games Dynamic

games Best Choice for P2 http://www.engineering.uwaterloo.ca/~s4khosra/