Transcript Swarm Intelligence and Bio

2007 Fall Comp790-058 Lecture
Sang Woo Lee
What is Biologically Inspired Algorithm?
Swarm Intelligence
Evolutionary Computation
Application in Motion Planning
 Trail-Laying Robots for Robust Terrain Coverage
 Dynamic Redistribution of a Swarm of Robots
 Evolving Schooling Behaviors to Escape from
Predator
Simulate biological phenomena or model
Working algorithm in nature
Proven its efficiency and robustness by
natural selection
Dealing too complex problems
Incapable to solve by human proposed
solution
Absence of complete mathematical model
Existing of similar problem in nature
Adaptation
Self-organization
Communication
Optimization
Robotic
 Multi-Robot Motion Planning
 Self-configuration
Network
 Distributed autonomous system
 Routing algorithm
Social Organization
 Traffic control
 Urban planning
Computer Immunology
Boids in Nick’s lecture
Well known flocking algorithm
Flocking
Separation
Alignment
Cohesion
Machine Learning in Dave’s lecture
Neural Network
Supervised learning Method
Population of simple agents
Decentralized
Self-Organized
No or local communication
Example
Ant/Bee colonies
Bird flocking
Fish schooling
Meta-heuristic Optimization
Inspired from the behavior of ant
colonies
Shortest paths between the nest and a
food source
Evaporating pheromone trail
Probabilistic path decision
Biased by the amount of pheromone
Converge to shortest path
Ant trips on shorter path returns quicker
Longer path lose pheromone by evaporating
Solved problems
Traveling Salesman Problem
Quadratic Assignment Problem
Job Shop Scheduling
Vehicle and Network Routing
Dussutour, A., Fourcassié, V., Helbing, D.
& Deneubourg, J. L. Optimal traffic organ
ization in ants under crowded conditions.
Nature 428, 70-73 (2004)
Research on ant path selection in bottleneck situation
Maximizing traffic volume
Symmetrical traffic in narrow path
 Threshold width between 10.0 and 6.0mm
Pushed Ant is redirected to other path
Symmetry restored before the maximum
flow
 Benefits of using a single trail
 Condensed trail - Better orientation guidance and
stronger stimulus
 High-density - Good information exchange
Optimize the rate of food return
 Proved by analytical model and experiment
J. Svennebring and S. Koenig, “Traillaying robots. for robust terrain
coverage,”, Proc. of IEEE International
Conference on Robotics and Automation
2003, Volume: 1, On page(s): 75- 82 vol.
1
Inspired by Ant forage
Exploration & Coverage
Pebbles III robot
6 infrared proximeter
Bump sensor, 2 motors
Lay trails – Black pen to track trail
8 Trail sensor
Node Counting
Robot repeated enter cells
Counting by markers in cell
Move to smallest number
No communication
Very limited sensing
Very limited computing power
Marking current cell
Sensing markers of neighbor cells
Assumptions on theoretical foundation
Move discrete step
Mark cell uniformly
No noise in sensor
By the way, it works even
Uneven quality trail
Some missing trail
Pushed to other location
Obstacle Avoidance Behavior
Inversely proportional to the distance
Weight for each direction sensor
Trail Avoidance Behavior
Fixed length
Trail sensor with recent past information
Weight Balancing of two behavior
Need to well balanced
Work well with
Uneven quality trail
Move another location
Removing patches of trail
Faster than random walk
Until some threshold
Too many trails result large coverage time
With no cleaning of Trail
Coverage time grow steeply
With cleaning of Trail
Same as ant pheromone
Works good with many coverage number
A. Halasz, M. Ani Hsieh, S. Berman, V. Ku
mar. Dynamic Redistribution of a Swarm
of Robots Among Multiple Sites, 2007 IE
EE/RSJ International Conference on Intelli
gent Robots and Systems.
Inspired by Ant house-hunting
Probability of initiating recruitment depends
on the site’s quality
Superior site scout has shorter latency to
recruit
Recruitment type
 Summon fellow by tandem run
 Passive majority by transport
Transport recruitment of new site triggered
by population (Over the quorum)
Recruitment speed difference amplified by
quorum requirement
Collectively distributes itself to multiple
sites
Predefined proportion
No inter-agent communication
Similar to task/resource allocation
Scalable
Using fraction rather than agent number
Graph G
Strongly connected graph
Edge
Transition rate Kij
Transition time Tij
Maximum transition capacity
All agents know Graph G
Property
Stability
Convergence
To a unique stable equilibrium point
Proved analistically
Transition in equilibrium state
Fast transition makes more idle trips
Extension
Inject Quorum sensing
Fast converge, less idle transition
Adjacent sites communication
Quorum information instantly available
Transition rate switch
Above quorum to below quorum
Set to maximum transition rate
Stable
Converges asymptotically
Problem
Increasing quorum increase convergence
speed
Too big quorum make system stuck by high
transition rates
Inspired from the natural processes that
involve evolution
Genetic algorithm
Evolution strategies, evolutionary
programming, genetic programming
Use a population of competing
candidate solutions
Reproduce and evolve themselves
Evolution
Combination
Alteration
Selection
Increases the proportion of better solutions in
the population
Better one survives!
T. Oboshi, S. Kato, A. Mutoh and H. Itoh,
Collective or Scattering: Evolving
Schooling Behaviors to Escape from
Predator, edited by R. Standish, M. A.
Bedau and Abbass, H. A., Artificial Life
VIII (MIT Press, Cambridge, MA, 2002), p.
386.
Evolving schooling behavior by Genetic
Algorithm
Fish’s schooling behavior
Use Aoki’s model
Assuming 2-D world
Movement
Speed and Direction
Four basic behavior patterns
Repulsion behavior
Move with a high parallel orientation
Biosocial attraction
Searching behavior
Reference individual
Nearer one selected with greater probability
Direction determined by
Previous direction
Four basic behavior patterns
Wobbling with normal distribution
Speed
Gamma distribution
Considering predator‘s existence
Urgent mode
Sensing predator approaching
Direction determined by
Lerp with 4 variables
Parallel to neighbor
Attracted to neighbor
Averting from predator
Away from predator
Chase detected prey
Random search
Predator's sensory field
k times larger
Distribution of predator's speed
n times faster
The artificial ecology
BL – body length of individual
Size : 40BL * 40BL
N prey, 1 predator
If prey < N
Create next generation prey
Genetic algorithm
 Gene of individual
 Weight of urgent mode pattern
 Each of 10 bit
 Selection
 Surviving time
 Evolution
 Crossover each weight region of two parent
 5% mutation for each bit
 Parent selection probability
 Proposition to surviving time
Average Proposition of 4 weight
B(attract) becomes lower
D(away) becomes higher
A(parallel) becomes higher
Evolve for schooling
More for evading
Average Proposition of 4 weight against
n (predator’s speed)
More schooling when lower risk
More evading when higher risk
Scattered evasion is more efficient with high
risk
If predator is too fast, no strategy survives
Polarization
Average
angle
deviation
Bio-inspired algorithms has many
application
Simple algorithm becomes emergent logic
Useful for too complex problems
Very useful for swarm of robot control
Simple computation
Decentralized and self-organized
Need no or local communication
Useful to establish group behavior
 de Castro, Leandro N. Recent Developments in Biologically Inspire
d Computing, Hershey, PA, USA: Idea Group Publishing, 2004. p vi
i.
 Dussutour, A., Fourcassié, V., Helbing, D. & Deneubourg, J. L. Opti
mal traffic organization in ants under crowded conditions. Nature
428, 70-73 (2004)
 J. Svennebring and S. Koenig, “Trail-laying robots. for robust
terrain coverage,”, Proc. of IEEE International Conference on
Robotics and Automation 2003, Volume: 1, On page(s): 75- 82 vo
l.1
 A. Halasz, M. Ani Hsieh, S. Berman, V. Kumar. Dynamic Redistributi
on of a Swarm of Robots Among Multiple Sites, 2007 IEEE/RSJ Int
ernational Conference on Intelligent Robots and Systems.
 T. Oboshi, S. Kato, A. Mutoh and H. Itoh, Collective or Scattering:
Evolving Schooling Behaviors to Escape from Predator, edited by
R. Standish, M. A. Bedau and Abbass, H. A., Artificial Life VIII (MIT
Press, Cambridge, MA, 2002), p. 386.