Transcript Presentation

NuTech
Solutions, Inc.
Simulation and Evolution
Work Well Together
Lawrence “David” Davis
VP of Product Research
NuTech
Topics
Solutions, Inc.




Terminology
What is simulation?
What are evolutionary algorithms?
Some Case studies:





Investigating contacts
Target allocation
Army/NASA cockpit procedures
Interpreting data
Conclusions
NuTech
Terminology
Solutions, Inc.






Simulation
Monte Carlo Simulation
Evolutionary Algorithm
Genetic Algorithm
Heuristic
Evaluation Procedure
NuTech
About Simulation
Solutions, Inc.





Simulation involves reproducing
events at the level of detail we
care about
Can be done at a fine level of
detail (agent-based modeling)
Can be done at a higher level
Often has unexpected outcomes
Should include what we care
about and finesse the rest
NuTech
Solutions, Inc.
Simulation: doesn’t change
Our strategy: Adapts
NuTech
Solutions, Inc.
Why Evaluate with Simulations?

Simulations represent interactions
that we can’t capture in other
ways




Highly detailed effects
“Cascading” effects
Probabilistic effects
Statistical reports are possible
NuTech
Solutions, Inc.
What are Evolutionary Algorithms?





Genetic algorithms—evolution
simulated on a computer
We “evolve” the solutions to hard
problems instead of figuring them out
Good for problems where mathematical
techniques can’t be applied
Good when we need a reasonable
answer fairly quickly
Really good when used to find rule sets
or strategies that do well under
simulation
NuTech
Case Study:
Investigating Contacts
Solutions, Inc.




We have unidentified contacts in
the ocean
We have different types of assets
available (towed sensor arrays,
underwater vehicles, rulees, etc)
When we have a contact, we want
to allocate assets to investigate it
Success means determining what
the source of the contact was, and
continuing to monitor it if it
interests us
NuTech
Investigating Contacts:
Features of the Problem
Solutions, Inc.



The area the contact could be in
increases in size with time
Different assets may work well
together or may hamper each
other (underwater vehicles can
hinder surface listening devices)
We need to be able to investigate
other contacts if they occur, so we
might not want to allocate all our
assets to any one contact
NuTech
Features of the Simulation
Solutions, Inc.





We can model the arrival of contacts
probabilistically
When contacts occur, they modify the
probabilities of other contacts
When we learn about the contacts,
this modifies our view of the
probabilities
Some contacts don’t represent
interesting things
Some contacts are extremely
interesting
NuTech
We want to…
Solutions, Inc.



Find real contact sources at a
high rate of success
Investigate multiple contacts with
a high rate of success
Minimize cost of operations,
and/or number of assets used
NuTech
What the Simulator is Like
Solutions, Inc.




The simulator generates events with
probabilities based on our experience
It includes algorithms for computing
success rates at finding event sources
It includes algorithms for changing the
size of the search area with time
The simulator measurements of
success are sensitive to weather,
day/night, season, asset combinations,
type of source, etc.
NuTech
What’s in the Simulator
Solutions, Inc.




A driver that steps us forward in time
An event interpreter that creates events
based on the input probabilities
Objects of various types that can
interact: assets, sources, weather
events, and equipment
A statistics gatherer that tracks success
rates and other data that interests us
NuTech
Example of a Simulator Event
Solutions, Inc.





There is currently an unidentified contact
(a submarine) at location 1
Assets are allocated to investigate the
contact, using the current allocation and
search rules
The simulator knows the course of the
submarine
The simulator increases the probability of
other contacts related to this source along
its course
If a source of this type generally travels
alone, the probability of other contacts of
its type is reduced for some time
NuTech
Another Example of
a Simulator Event
Solutions, Inc.





There is currently an unidentified contact
(a fishing boat) at location 2
Assets are allocated to investigate the
contact, using the current allocation and
search rules
The simulator knows the course of the
fishing boat
The probability of other contacts related to
the boat along its course is increased
The probability of identifying the type of
source through radio and more detailed
monitoring is computed
NuTech
Solutions, Inc.
Example Rules for Asset Allocation



“If no other contacts are live and this
contact is within 200 miles of base, send
the slow but sensitive assets to
investigate”
“Don’t send towed arrays and underwater
assets to investigate the same contact”
“If there are three contacts in a straight
line, concentrate search in the area on the
projection of that line”
NuTech
How to Get Good Rule Sets
Solutions, Inc.






Start with randomly-generated rule sets, or
rule sets that represent human heuristics
Evolve better and better rule sets
Simulate months or years of activity to
evaluate a rule set
Use the desired features of the problem to
decide which are the good rule sets and
which are the bad ones
Make more rule sets, but let the good ones
proliferate more than the bad ones
Mutate and cross-breed rule sets
NuTech
The rule sets Get Better
Solutions, Inc.




The system, evolving rule sets that
function well in the context of the
simulator, produces a rule set that works
well for the kinds of contacts we are
simulating
Sometimes these rule sets can have
unexpected features
Mathematical techniques aren’t well suited
to find solutions in the context of
simulations
Evolutionary algorithms are very well
suited for finding good procedures under
evaluation by simulators
NuTech
Case Study: Target Allocation
Solutions, Inc.






Suppose you have a force faced with a
group of approaching unfriendly objects
How should you allocate fire in order to
achieve your goals?
Early decisions influence later ones
Important targets should receive more
attention
Some interactions between weapon types
are important: visual interference
Distance effects matter, as does target
change time, etc
NuTech
How to Evaluate a
Target Allocation Strategy
Solutions, Inc.





Important targets have a high probability of
being eliminated
Low probability of elimination of our force
members
Minimize duration of interaction
Minimize expenditure of ammunition
Minimize loss of crew
NuTech
Target Allocation is Similar to
Contact Investigation
Solutions, Inc.



This problem can be handled just like
investigating contacts, except that the
contacts are all considered at the same
time
A simulation of the interaction is a good
way to evaluate a blend of weaponry and a
targeting strategy
An evolutionary algorithm can be used to
find good target allocation rule sets
NuTech
Different Rule Sets for Different
Types of Engagements
Solutions, Inc.






Targets are aircraft
Targets are boats
Targets are mixed types
Targets are far away and of unknown types
We are moving
We have time constraints
NuTech
Solutions, Inc.
Example Rules for Target Allocation



(rule for one type of gun) Target the
incoming object with the highest
combination of importance and residual hit
probability
(low visibility) Switch targets when
probability of kill of the current target is
greater than 96%
Target the guns with the highest probability
of kills first
NuTech
Evolve Good Rule Sets
Solutions, Inc.



Evolve a high-performance rule set by
putting each candidate through a very large
number of simulated engagements of the
expected types, weighted by probability
Evolve rule sets for different types of
engagements by starting a different
evolutionary process for each type, and
creating rule sets that function well for that
type of engagement
Evolve different rule sets depending on the
objectives: high survivability, high kill rate,
deterrence, interdiction, etc.
NuTech
Case Study: NASA in-cockpit
Procedures Studies
Solutions, Inc.





A3I project (Army-NASA Aircrew Aircraft
Integration)
Also called MIDAS
Simulated the effects of required
procedures on cockpit crews (commercial
aircraft and Apache helicopter crews)
For commercial crews, simulated cockpit
information systems and their effect in
normal and emergency situations
For helicopter crews, simulated
effectiveness of mission procedures
NuTech
Example of a Simulator Event
Solutions, Inc.






There is a truck convoy ahead
Two helicopters are assigned to locate it
and deliver a missile strike
Pop-up and jinking procedures are used to
do reconnaissance and evasion of groundto-air missiles
One pilot locates the target for the other
Radio procedures, cognitive procedures,
and situational awareness are modeled
Simulation is critical in assessing the
impact of different equipment and mission
strategies
NuTech
Solutions, Inc.
Evolution can be Used to Find Good
Strategies and Displays



Measure pilot effectiveness through
hundreds of thousands of mission
simulations to find the best strategies
Evolve cockpit displays to find those that
give the highest levels of performance
across hundreds of thousands of mission
simulations
System used with minor modifications for
police emergency call stations and
astronaut repair missions
NuTech
Case Study:
Interpreting Data
Solutions, Inc.





We get LOFARgrams from listening
apparatus
Some contacts may be whales or fishing
boats
Some may be large metallic fish
Human experts can interpret the signals
with high accuracy
Humans tend to be best in the region and
conditions where they were trained—
Pacific, no storms, no whales in
background, etc
NuTech
The Task
Solutions, Inc.




Produce an expert system that can do what
the humans do
Big difficulty: identifying visual patterns
that the humans see easily (“lines” in the
data)
Expert system techniques didn’t produce
good results at line-tracing
Development team used a genetic
algorithm
NuTech
How the Algorithm Worked
Solutions, Inc.





Hundreds of LOFARgrams were marked by
humans so that the interesting lines were
identified
The genetic algorithm evolved rule sets for
interpreting the data
A rule was evaluated based on how well it
matched the human analysis
Over time, the system learned to do this as
well as humans
By changing the training cases, the system
could learn to do this in different locations,
conditions, and types of background noise
NuTech
Terminology
Solutions, Inc.






Simulation
Monte Carlo Simulation
Evolutionary Algorithm
Genetic Algorithm
Heuristic
Evaluation Procedure
NuTech
Solutions, Inc.
A Useful Extension
Simulation: Strategies adapt
Our strategy: Fixed
NuTech
Conclusions
Solutions, Inc.



Simulations can be more accurate and
informative than high-level or mathematical
models of an event
Probabilistic simulations show us what can
happen under a wide variety of conditions
Many interesting problems can be solved
very well if we simulate, evaluate, and
evolve