Transcript Pasadena-

Swarm Intelligence: The Method
Behind the Mobs
Robert J. Marks II
Distinguished Professor
of Electrical & Computer Engineering,
Baylor University
Bio-Engineering for
the Exploration of Space
NASA Office of Biological and Physical Research
Program Review
California Institute of Technology
December 17-18, 2003
1
What are the competing paradigms?
CONJUNCTIVE Approach
Do this1 and this2 and this3 and this4 and this5 to get that.
Result: Highly
complex and brittle
design. Loose this4
and your system
can fail.
Conjunctive statement:
A
j
C
j
2
What are the competing paradigms?
DISJUNCTIVE Approach
(Do this1 to get that ) or (Do this2 to get that ) or (Do this3 to
get that ) or (Do this4 to get that )
Result: Highly robust
and fault tolerant
design. Loose this4 and
you’re still in business.
Disjunctive statement:
 A
j
 C
j
3
What are the competing paradigms?
Is… DISJUNCTIVE = CONJUNCTIVE?
Is…
(Do this1 to get that ) or (Do this2 to get that ) or (Do this3 to
get that ) or (Do this4 to get that )
= (Do this1 and this2 and this3 and this4 ) to get that.
???
 A
j
In a Boolean sense,
j
 C 
A
j
C
j
4
Disjunctive vs. Conjunctive
Disjunctive reasoning sometimes referred to as
“The Combs Method”*
Examples of Complex Disjunctive Systems
1. Swarms: Insects & People
2. Your Body
3. Animal motor functions
4. Genomic symbiogenesis
•
•
•
William E. Combs
J. J. Weinschenk, W. E. Combs, R. J. Marks II, “Avoidance of rule explosion by mapping fuzzy systems to a disjunctive rule
configuration,” IEEE Int’l Conference on Fuzzy Systems, St. Louis, MO, 2003, pp 43-48.
J. J. Weinschenk, R. J. Marks II, W. E. Combs, “Layered URC fuzzy systems: a novel link between fuzzy systems and neural
networks,” Proc. IEEE Intl’ Joint Conf. on Neural Networks, Portland, OR, 2003, pp. 2995-3000.
J. J. Weinschenk, W. E. Combs, R. J. Marks II, “On the avoidance of rule explosion in fuzzy inference engines,” Submitted to
IEEE Trans. Fuzzy Systems, November 12, 2003.
* Earl Cox, The Fuzzy Systems Handbook, Academic Press/ Morgan Kaufman.
5
DR vs. CR Scorecard
Property
Conjunctive Reasoning (CR)
Disjunctive Reasoning (DR)
Scalability
Exponential
Linear
Plasticity
Rigid
Plastic
Coupling
High
Low
Low
High
Low
High
For low order systems, CR
most closely parallels human
cognitive inference..
For complex systems, DR most
closely parallels human cognitive
inference.
Robustness
Fault
Tolerance
Cognitive
Parallel
Parallel &
Distributed
Processing
Ability
Parallel
and
distributed DR is readily applied to
processing
increases
the distributed processing as each
complexity of most properties. unit has a relationship with the
consequent that is independent of
the other units.
6
Applied Symbiogenesis: A Disjunctive Process
System
Evolved
System
Disjunctively
Addend
Forced
Symbiotic
Adaptation
New
Feature
Heterogeneous
Disjunctive Design:
Genomic
Programming
Acquiring Genomes: A Theory of the Origins of Species by Lynn Margulis and Dorion Sagan
7
Designing a Running Man
joint
Ball
Heal
Pressure
Pressure
If…
If…
The ball
pressure is
high
The heal
pressure is
high
OR
Then…
Then…
Rotate joint
CW
Rotate joint
CCW
Impose:
Forced symbiotic adaptation
8
Homogeneous Disjunctive Systems: Swarm Intelligence
9
Applications: Warfare & Game Theory
Aviation Weekly , Sept 29, 2003
10
Applications: Business
“Swarm Intelligence: A Whole New Way to
Think About Business”
Harvard Business Review, May 2002
Using swarm intelligence optimization,
Southwest Airlines slashed freight transfer
rates by as much as 80%.
“Similar research into the behavior of
social insects has helped … Unilever,
McGraw Hill, and Capital One, to develop
more efficient ways to schedule factory
equipment, divide tasks among workers,
organize people , and even plot strategy.”
11
Applications: Telecommunications
Scientific American, March 2000
“Several companies are [using
swarm intelligence] for handling the
traffic on their networks. France
Télécom and British
Telecommunications have taken an
early lead in applying antbased
routing methods to their systems…
The ultimate application,
though, may be on the Internet,
where traffic is particularly
unpredictable.”
12
Plants and Distributed Computing
cactus
leaf
cocklebur
•
• Leaves have openings called stomata that open wide to
let CO2 in, but close up to prevent precious water vapor
from escaping. Plants attempt to regulate their stomata to
take in as much CO2 as possible while losing the least
amount of water.
• “[The] results are consistent with the proposition that a
plant solves its optimal gas exchange problem through an
emergent, distributed computation performed by its
leaves.”
• Patches of open or closed stomata sometimes move
around a leaf at constant speed
• “Under some conditions, stomatal apertures become
synchronized into patches that exhibit richly complicated
dynamics, similar to behaviors found in cellular automata
that perform computational tasks.” “Our values are
statistically indistinguishable from those of the same
correlations found in the dynamics of automata that
compute.”
Peak, D. A., West, J. D., Messinger, S. M & Mott, K. A. Evidence for complex, collective dynamics and emergent, distributed computation in plants. Proceedings of the National Academy of
Sciences USA, 101, 918 - 922, (2004).
13
Applications: Optimization
Particle Swarm: An
(enormously effective!)
multi- agent
optimization algorithm
based on the
biomimetics of bird
flight.
14
Application: Fiction
15
What is Swarm Intelligence?
Simple Rules for Multiple Agents.
Indy 500’s Rules
–Drive Fast
–Turn Left
16
Another rule…
– Drive Fast
– Turn Left
– Don’t hit stuff
• Emergent Behavior
– Competition- Winning!
17
The Dumb Termite Clearing Wood
RULES
• Run around randomly until you bump
into a piece of wood.
• Pick it up.
• Run around randomly until you bump
into a piece of wood.
• Put it down.
• Repeat forever.
Q: What does this do?
18
Looking for Your Lost Pet Turtle Under a Lamppost
Multi-Agent searching in the presence of sensor range
inhomogeneity.
Tradeoffs:
• Easier to look
under lamppost
• Want to look
uniformly in
around the area.
Pareto Optimization
(Efficient Frontier)
Agent Rule:
1. Diminishing Radius
Momentum – if the visible
radius decreases, the
momentum is increased.
2. Don’t tred on me.
Emergent Behavior: A
parameter to tune between
the optimization criteria.
19
A Simple Disjunctive Extension
Multi-Agent Criteria: Uncover important search
area in the presence of sensor range inhomogeneity
Antecedents:
Important Parameters:
1. Distance from
Unexplored Area
2. Location of Newly
Discovered area
3. Distance of Nearest
Agent
4. Radius
Diminishment
Consequents: • Constraints:
Velocity Components
1. In direction of new
discovery
2. In direction of
unexplored area
1. Information is
local, or,
2. Information
obtained from
stygmergy.
3. Away from nearby
agents
4. In direction of
diminished radius
20