Swarm-Based Traffic Simulation: Darya Popiv, TUM - JASS 2006

Swarm-Based Traffic
Simulation
Darya Popiv, TUM JASS 2006
Content
Introduction
Swarm Intelligence
Pheromones in Traffic Simulation
Vehicular Model and Environment
Software: SuRJE
Introduction: Why to do Traffic

Simulation?
Traffic congestions
Economical Implications
Social Implications
Increasing amount of
accidents
Perfect tool for road
planning
Introduction: How to do Traffic

Simulation?
Macro model
Treats traffic flow as a fluid not taking into
account individual agents
Navier-Stokes equation
Micro model
Treats traffic flow as the result of the
interaction between individual agents
Well-known approach: Nagel-Schreckenberg
cellular automata
Introduction: How to do Traffic

Simulation?
Micro model in more detail: drivers act as
individual agents, influenced by
traffic rules
signs
traffic lights
others drivers driving
Swarm-based Traffic Simulation

Micro model simulation
Interaction between agents is based on
swarm intelligence
Content
Introduction
Swarm Intelligence
Software: SuRJE
Swarm Intelligence
Swarm Intelligence is a property of
systems of non-intelligent robots exhibiting
collectively intelligent behavior. [G. Beni,
"Swarm Intelligence in Cellular Robotic Systems", Proc. NATO Adv.
Workshop on Robotics and Biological Systems, 1989 ]
Characteristics of a swarm:
distributed, no central control or data source
perception of environment, i.e. sensing
ability to change environment
examples: ant colonies, termites, bees
Swarm Intelligence: Stigmergy

Stigmergy is a method of communication
in emergent systems in which the
individual parts of the system
communicate with one another by
modifying their local environment
Ants communicate to one another by
laying down pheromones along their trails
Swarm Intelligence in Traffic

Simulation
Cars, like ants, leave pheromones
Pheromones are expressed in terms of visual
and perceptional signals
Braking lights
Turning lights
Changes in speed
Cars sniff pheromones dropped by other

cars and adjust their speed and direction
accordingly
Content
Introduction
Swarm Intelligence
Software: SuRJE
Pheromones in Traffic Simulation:

Rules
Pheromone rules on numerical level
Pheromones fade over time
Faster cars leave longer tails of pheromones
Stronger pheromones are dropped when:
Car changes lanes
Car brakes
Car stops

Illustration
Driving, changing lanes, stopping

Algorithm
Sniffs pheromone in front, if not yet
arrived to destination point
Decelerate, if tailing distance to the next
car is less than strength of pheromone
suggests
Accelerate, if there is no pheromone or
tailing distance is greater than suggested
by pheromone strength

Algorithm cont.
Stop, if needed
Make decision about upcoming turn
(change lanes?)
Drop single pheromone, or a trail of
pheromones
Update car position
Content
Introduction
Swarm Intelligence
Software: SuRJE

in Traffic Simulation
Besides interaction among agents, there are
external factors that also influence how traffic
behaves
Shape of the road
Traffic signs
Driving rules
Relationship between vehicle agents and

environment defines
Where vehicles can go
Speed limit
How to act at intersections
Vehicular Environment
Road map is represented by connected
graph
Each agent in the system has its route,
defined by road map and rules
Agent only need to know agents in
neighboring lanes and through
intersections
Vehicle Movement
Route planning
Choose closest direction to the direction straight to
destination point, i.e. with the help of Dijkstras
shortest path algorithm
Route re-planning
Occurs if agent was unable to get into an appropriate
lane due to congestions
Starting point is updated and the new route is
calculated
Route execution
Lane changing is triggered by upcoming turn
Content
Introduction
Swarm Intelligence
Software: SuRJE
Software: SuRJE (Swarms under

R&J using Evolution)
Developed by the
research group at
University of Calgary,
Ricardo Hoar and
Joanne Penner
Map-building mode
Multi-lane roads,
connections, lights,
signs, speed limits
Set points, interpolate:
straight/curved roads
SuRJE: Parameters
Begin/end journey
Rate, at which cars
are seeded into the
system
Probability for the
agent to reach one or
another ending point
of the journey
SuRJE: Parameters
Strength of pheromone
Mean tailing distance and deviation
Mean speed limit and deviation
Mean stopping distance
Physical maximum
acceleration/decelaration
Software: SuRJE
Run mode
Run swarm of cars on
the road
SuRJE: Goal of Simulation

Minimize average waiting time for all cars
total driving ditot
waiting times witot
fitness measure for each car i
overall traffic congestion
SuRJE: Means to reach Goal

Minimize overall traffic congestion by adjusting
time sequences of the traffic lights
Extend/decrease green time

Swap two timing sequences
Reassign the starting sequence
Probabilities for mutation operations are set by user
Swarm voting
Car casts vote whenever stopped
Lights with most votes will with higher probability
Increase their green period
Reduce green period for one of their opposing lights
Software: SuRJE
The process of evolution on traffic light
sequences
SuRJE: Straight Alley Testbed
SuRJE: Straight Alley Testbed
SuRJE: Looptown
SuRJE: Looptown
28 lights, 9 intersections
300 cars are seeded with following rates
per second:
A 0.23
B 0.31
C 0.23
D 0.23
Improvement: 26% decrease of waiting

time
Conclusion
New approach on micro traffic simulation is
introduced
Biological behavior of colonies, such as ants, can
be applied to social interactions, i.e. traffic flow
Algorithms should be chosen
Route planning
Adaptive Behavior
Probability of collisions dynamic emergence of
obstacles

Swarm-Based Traffic Simulation: Darya Popiv, TUM - JASS 2006

Uploaded by

Copyright:

Available Formats

Swarm-Based Traffic Simulation: Darya Popiv, TUM - JASS 2006

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Swarm-Based Traffic Simulation: Darya Popiv, TUM - JASS 2006

Uploaded by

Copyright:

Available Formats

Swarm-Based Traffic

Introduction: Why to do Traffic

Introduction: How to do Traffic

Introduction: How to do Traffic

Swarm-based Traffic Simulation

Swarm Intelligence: Stigmergy

Swarm Intelligence in Traffic

Cars sniff pheromones dropped by other

Pheromones in Traffic Simulation:

Pheromones in Traffic Simulation:

Pheromones in Traffic Simulation:

Pheromones in Traffic Simulation:

Vehicular Model and Environment

Relationship between vehicle agents and

Software: SuRJE (Swarms under

SuRJE: Goal of Simulation

overall traffic congestion

SuRJE: Means to reach Goal

Extend/decrease green time

SuRJE: Straight Alley Testbed

SuRJE: Straight Alley Testbed

Improvement: 26% decrease of waiting

You might also like