Transcript DynaTraffic

DynaTraffic – Models and
mathematical prognosis
Simulation of the distribution of traffic
with the help of Markov chains
What is this about?
• Models of traffic situations
• Graphs:
– Edges, Vertices
– Matrix representation
– Vector representation
• Markov chains
– States, transition probabilities
– Special states: periodic, absorbing, or transient
– Steady-state distribution
• Matrix vector multiplication
 DynaTraffic help to understand and learn these concepts
2
The goal: analysis of a traffic system
We are interested in this question:
„How many cars are there
at a certain time on a lane?”
In order to be able to make statements about the
development of a system, we need a model.
I.e., first we build a model and then we control and
observe this model.
3
Mathematical prognosis
step 1
Build a model of an everyday situation
Photo from a side perspective
5
Photo of the layout
© Google Imagery 2007
6
Model of the layout, with cars
7
Elements for the model without cars
Nodes
Arrows
 What does your model look like?
8
Model of the layout, without cars
Stop points  nodes
Lanes  edges
4
3
7
9
Representation in DynaTraffic
4
3
7
- Characters to label lanes
- Colored arrows and slightly different arrangement
10
Models
• Why does one build models?
– To better understand systems
– Models are a useful tool to examine systems
• Definition of a model: A simplified representation
used to explain the workings of a real world system
or event.
(Source: http://en.wiktionary.org/wiki/model)
• Mathematical Models try to capture the relevant
parameters of natural phenomena and to use these
parameters for predictions in the observed system.
11
Mathematical prognosis
step 2
Transformation of the model
Why a transformation method?
We are concerned with traffic on single lanes and
analyze the traffic with the help of a Markov model.
 For that lanes must be vertices
 Transformation of the situation graph!
13
Transformation recipe
Transformation of situation graph to line graph:
• Each edge become a vertex.
• There is an edge between two vertices, if one
can change from one lane to the other in the
traffic situation.
• Each vertex has an edge to itself.
14
Transformation step a)
Each edge becomes a vertex.
15
Transformation step b)
There is an edge between two vertices, if one can
change from one lane to the other in the traffic
situation.
16
Transformation step c)
Each vertex has an edge to itself.
I.e.: a car can remain on a lane!
17
The good news concerning
this transformation 
We do not need to do this transformation, it is
already done in DynaTraffic. But we should
understand it…
Situation graph
Line graph to the situation graph
18
Mathematical prognosis
step 3
Define assumptions
Define the process
• Every 10 seconds, each car takes a decision with a
certain probability (so-called transition probability):
– „I change to another lane“
– „I remain on this lane“
• The realization of decisions is called a transition: cars
change their state, if necessary.
20
The transition graph
The transition probabilities are
entered in the line graph
 Transition graph (= Markov chain)
21
Our Markov chain
The vertices represent possible states, i.e., lanes on
which a car can be.
The edges show to which other lanes a car can
change from each lane.
22
Meaning of
the transition probability?
„If there is a car on
lane A now, it will in
the next transition
change to lane B
with a probability
of 83%.
23
Alternative representation
of the transition graph
Transition graph
Transition matrix
24
How to read the transition matrix
From
To
25
Empty entries in
the transition matrix?
If an edge does not exist, there is a 0 in the
transition matrix at the corresponding entry.
26
Summary:
our traffic model
Photo
Model with cars
Model without cars
Transition matrix
Transition graph
27
Summary:
our traffic model
Step 1: build a model of an everyday situation
Photo
Model with cars
Step 3: define assumptions
Model without cars
Transition matrix
Transition graph
28
Demo DynaTraffic
29
Our Markov chain again
The vertices represent possible states, i.e., lanes on which a
car be.
The edges show on which other vertices a car can change
from one vertex, and with which probability this happens per
transition.
30
„Do a transition“?
To calculate how many cars there are going to be on
a certain lane, one needs:
– The number of cars on the individual lanes.
– The probabilities leading to the certain lane.
31
How many cars are on lane A
after the next transition?
Cars on individual lanes:
A: 3 cars
B: 4 cars
C: 7 cars
Probabilities leading to lane A:
A  A : 0.17
C  A : 0.83
Calculation:
3 * 0.17 + 7 * 0.83 = 6.32 cars
32
Probabilities for transitions
The required probabilities can directly be read from
the transition matrix!
3 * 0.17 + 7 * 0.83 = 6.32 cars
33
State vector
The number of cars per lane in the state vector notation
34
Calculate transitions
As seen: Multiplication of the first row of the
transition matrix with the current number of cars on
the first lane (= second entry of the state vector)
gives the new number of cars on the first lane.
35
Calculate transitions compactly
With a matrix vector multiplication a transition can be
calculated at once for all lanes!
36
Matrix vector multiplication
+
+
+
+
=
37
Properties of transition graphs
Based on the transition probabilities, certain states of
a transition graph can be classified. States can be
absorbing, periodic, or transient.
There are further steady-state distributions and
irreducible transition graphs.
38
Absorbing state
A state which has no out-going transition
with positive probability
 Over time all cars conglomerate there!
Where does this happen with real traffic?
- Junkyard
- dead-end one-way street ;-)
39
Periodic states
States take periodically the same values
Traffic oscillates between certain states.
Where are such streets in everyday life?
- e.g. between work and home
40
Transient state
A state to which a care can
never return.
41
Irreducible transition graph
Each state is reachable from every other state.
42
Is the following graph irreducible?
No!
(State D is not reachable from every other state!)
Which transition probabilites could
be changed in order to make this graph ireducible?
43
Properties of the transition matrix
Column sum = 1: stochastic matrix
Column sum ≠ 1:
Column sum < 1:
total number of cars goes toward 0
Column sum > 1:
total number of cars grow infinetly
44
Steady-state distribution
If a transition graph is irreducible and does not have
periodic states, then the system swings into a steadystate distribution, independently of the initial state.
45
Notation of transition probabilities
„The probability to change from
vertex A to vertex B is 10%”
P(A, B) = 0.1
46
Summary
Properties of states:
– Periodic: Cars move to and fro.
– Absorbing: All cars are finally there.
– Transient: A car never returns there.
Transitions graphs can be irreducible: Cars can change
from every state to every other state.
Distributions can be steady-state: the system has
swung into.
47
Models and their limitations
Lanes can hold a infinitely large number of cars in
our model. This is not realistic!
Therefore:
– Simulation stops, of > 2000 cars on a lane.
– In the upper-limit mode a individual upper limit
(< 2000) can be defined per lane.
48
The upper-limit mode
Possible application: Different parking areas. Cars
should fill the parking areas C, D, and E in this order.
49
Layout of parking areas in DynaTraffic
Upper limits of lanes are displayed
50
Process upper-limit:
lane C reached its capacity
Set all edges incident to C to 0.
 No more cars should arrive.
This is not a stochastic matrix any more!
 Columns must be normalized.
51
Process upper-limit:
lane C is unlocked again
Original row of the lane is reestablished
 Only outgoing edges are reestablished:
This is ok for all vertices.
 Normalize column sum.
52
What is this about?
• Models of traffic situations
• Graphs:
– Edges, Vertices
– Matrix representation
– Vector representation
• Markov chains
– States, transition probabilities
– Special states: periodic, absorbing, or transient
– Steady-state distribution
• Matrix vector multiplication
 DynaTraffic help to understand and learn these concepts
53
Summary
We model and analyze a traffic system with the help of
Markov chains.
– How does the traffic distribution evolve?
– Does the system swing into?
Like this we can make predictions about the system
based on our Markov model!
54
DynaTraffic
Situation
graph
Transition
graph
Control of transitions
State
statistics
Transition matrix
& state vector
55
Demo DynaTraffic
56