Transcript S ystems Analysis Laboratory

Games and Bayesian Networks
in Air Combat Simulation Analysis
M.Sc. Jirka Poropudas and
Dr.Tech. Kai Virtanen
Systems Analysis Laboratory
Helsinki University of Technology
[email protected], [email protected]
S ystems
Analysis Laboratory
Helsinki University of Technology
Outline
• Air combat (AC) simulation
• Games in validation and optimization
– Estimation of games from simulation data
– Analysis of estimated games
• Dynamic Bayesian networks (DBNs)
– Estimation of DBNs from simulation data
– Analysis of estimated DBNs
• Conclusions
S ystems
Analysis Laboratory
Helsinki University of Technology
Air Combat Simulation
• Commonly used models based on
discrete event simulation
• Most cost-efficient and flexible method
Objectives for AC simulation studies:
• Acquire information on systems performance
• Compare tactics and hardware configurations
• Increase understanding of AC and its progress
S ystems
Analysis Laboratory
Helsinki University of Technology
Discrete Event Simulation Model
Simulation input
• Aircraft and
hardware
configurations
• Tactics
• Decision making
parameters
Aircraft, weapons
and hardware models
Simulation output
Decision making logic
• Number of kills and
losses
• Aircraft trajectories
• AC events
• etc.
Stochastic elements
Validation of the model?
Optimization of output?
Evolution of simulation?
S ystems
Analysis Laboratory
Helsinki University of Technology
Existing Approaches to Simulation Analysis
• Simulation metamodels
– Mappings from simulation input to output
- Response surface methods, regression models, neural networks
• Validation methods
– Real data, expert knowledge, statistical methods, sensitivity
analysis
• Simulation-optimization methods
– Ranking and selection, stochastic gradient approximation,
metaheuristics, sample path optimization
S ystems
Analysis Laboratory
Helsinki University of Technology
Limitations of Existing Approaches
• Existing approaches are one-sided
– Action of the adversary is not taken into account
– Two-sided setting studied with games
• Existing approaches are static
– AC is turned into a static event
– Time evolution studied with dynamic Bayesian networks
S ystems
Analysis Laboratory
Helsinki University of Technology
Games from Simulation Data
•
Definition of scenario
–
–
–
–
•
Simulation of the scenario
–
–
•
•
Aircraft, weapons, sensory and other systems
Initial geometry
Objectives = Measures of effectiveness (MOEs)
Available tactics and systems = Tactical alternatives
Input: tactical alternatives
Output: MOE estimates
Games estimated from the simulation data
Games used for validation and/or
optimization
S ystems
Analysis Laboratory
Helsinki University of Technology
Estimation of Games
Simulation
Game
Discrete tactical
alternatives x and y
Discrete decision
variables x and y
MOE estimates
Analysis of variance
RED
x1
x2
x3
y2
RED, min
y3
-0.077
0.855 0.885
-0.811
0.013 0.023
-0.833
0.036 0.004
S ystems
Analysis Laboratory
Helsinki University of Technology
BLUE, max
BLUE
y1
Payoff
x1
x2
x3
y1
II
I
I
y2
IV
III
III
y3
IV
III
III
Estimation of Games
Game
Simulation
Continuous tactical
alternatives x and y
Continuous decision
variables x and y
Regression analysis
Payoff
Experimental design
MOE estimates
0.6
0.5
Payoff
MOE
estimate
0.7
0.4
0.3
0.2
0.5
0.4
0.3
0.2
0.1
0.1
0
0
15
15
10
10
5
S ystems
5
0
Analysis Laboratory
Helsinki University of Technology
15
15
10
10
5
5
0
Analysis of Games
• Validation: Confirming that the simulation model
performs as intended
– Comparison of the scenario and properties of the game
– Symmetry, dependence between decision variables and payoffs,
best responses and Nash equilibria
• Optimization: Comparison of effectiveness of tactical
alternatives
– Different payoffs, best responses and Nash equilibria,
dominance between alternatives, max-min solutions
S ystems
Analysis Laboratory
Helsinki University of Technology
Example: Missile Support Time Game
Phase 3: Locked
Phase 1: Support
Phase 2: Extrapolation
y
Relay radar information on
the adversary to the missile
x
y
x
• Symmetric one-on-one scenario
• Tactical alternatives: Support times x and y
• Objective => MOE: combination of kill probabilities
• Simulation using X-Brawler
S ystems
Analysis Laboratory
Helsinki University of Technology
Game Payoffs
Regression models for kill probabilities:
Probability of Blue kill
Probability of Red kill
0.8
0.7
0.6
0.6
0.5
0.4
0.4
0.3
0.2
0.2
0.1
0
0
15
15
10
10
5
5
15
15
10
10
5
0
Payoff: Weighted sum of kill probabilities
• Blue: wB*Blue kill prob. + (1-wB)*Red kill prob.
• Red: wR*Red kill prob. + (1-wR)*Blue kill prob.
• Weights = Measure of aggressiveness
S ystems
Analysis Laboratory
Helsinki University of Technology
5
0
Best Responses
Best response =
Optimal support time against a given
support time of the adversary
WB=0
15
Nash equilibria:
Intersections of
the best responses
WR=0.5
10
WR=0.25
5
WR=0
0
S ystems
Analysis Laboratory
Helsinki University of Technology
WB=0.75
WR=0.75
Red’s support time y
Best responses with
different weights
WB=0.25 WB=0.5
0
5
10
Blue’s support time x
15
Analysis of Game
• Symmetry
– Symmetric kill probabilities and best responses
• Dependency
– Increasing support times => Increase of kill probabililties
• Different payoffs
– Increasing aggressiveness (higher values of wB and wR)
=> Longer support times
• Best responses & Nash equilibria
– Increasing aggressiveness (higher values of wB and wR)
=> Longer support times
S ystems
Analysis Laboratory
Helsinki University of Technology
DBNs from Simulation Data
•
Definition of simulation state
–
•
Simulation of the scenario
–
–
•
Input: tactical alternatives
Output: simulation state at all times
DBNs estimated from the simulation data
–
–
•
Aircraft, weapons, sensory and other systems
Network structure
Network parameters
DBNs used to analyze evolution of AC
–
–
Probabilities of AC states at time t
What if -analysis
S ystems
Analysis Laboratory
Helsinki University of Technology
Definition of State of AC
•
1 vs. 1 AC
•
Blue and Red
•
Bt and Rt = AC state at time t
•
State variable values
•
“Phases” of simulated pilots
– Part of the decision
making model
– Determine behavior and
phase transitions for
individual pilots
– Answer the question ”What is
the pilot doing at time t?”
S ystems
Analysis Laboratory
Helsinki University of Technology
Example of AC phases in X-Brawler
simulation model
Dynamic Bayesian Network for AC
• Dynamic Bayesian network
– Nodes = variables
– Arcs = dependencies
• Dependence between variables
described by
– Network structure
– Conditional probability tables
• Time instant t presented by
single time slice
• Outcome Ot depends on Bt and Rt
S ystems
Analysis Laboratory
Helsinki University of Technology
time slice
Dynamic Bayesian Network
Fitted to Simulation Data
• Basic structure of DBN is assumed
• Additional arcs added to improve fit
• Probability tables estimated from
simulation data
S ystems
Analysis Laboratory
Helsinki University of Technology
Evolution of AC
• Continuous probability
curves estimated from
simulation data
• DBN model re-produces
probabilities at discrete
times
• DBN gives compact and
efficient model for the
progress of AC
S ystems
Analysis Laboratory
Helsinki University of Technology
What If -Analysis
• Evidence on state of AC fed to DBN
• For example, blue is engaged within
visual range combat at time 125 s
– How does this affect the progress
of AC?
– Or AC outcome?
• DBN allows fast and efficient
updating of probability distributions
– More efficient what-if analysis
• No need for repeated re-screening
simulation data
S ystems
Analysis Laboratory
Helsinki University of Technology
Conclusions
• New approaches for AC simulation analysis
– Two-sided and dynamic setting
– Simulation data represented in informative and compact
form
• Game models used for validation and optimization
• Dynamic Bayesian networks used for analyzing the
evolution of AC
• Future research:
– Combination of the approaches => Influence diagram
games
S ystems
Analysis Laboratory
Helsinki University of Technology
References
» Anon. 2002. The X-Brawler air combat simulator management summary. Vienna,
VA, USA: L-3 Communications Analytics Corporation.
» Gibbons, R. 1992. A Primer in Game Theory. Financial Times Prenctice Hall.
» Feuchter, C.A. 2000. Air force analyst’s handbook: on understanding the nature of
analysis. Kirtland, NM. USA: Office of Aerospace Studies, Air Force Material
Command.
» Jensen, F.V. 2001. Bayesian networks and decision graphs (Information Science
and Statistics). Secaucus, NJ, USA: Springer-Verlag New York, Inc.
» Law, A.M. and W.D. Kelton. 2000. Simulation modelling and analysis. New York, NY,
USA: McGraw-Hill Higher Education.
» Poropudas, J. and K. Virtanen. 2007. Analyzing Air Combat Simulation Results with
Dynamic Bayesian Networks. Proceedings of the 2007 Winter Simulation
Conference.
» Poropudas, J. and K. Virtanen. 2008. Game Theoretic Approach to Air Combat
Simulation Model. Submitted for publication.
» Virtanen, K., T. Raivio, and R.P. Hämäläinen. 1999. Decision theoretical approach to
pilot simulation. Journal of Aircraft 26 (4):632-641.
S ystems
Analysis Laboratory
Helsinki University of Technology