Simulação de Tráfego Veicular com Autômatos Celulares

Prévia do material em texto

Simulação de tráfego veicular com 
autômatos celulares
Mauricio Kischinhevsky – IC/UFF
 
Introdução à Ciência da Computação (2012.1)
 
Resumo
● Problema: aumento progressivo do número de 
veículos, composição heterogênea da frota 
(automóveis, veículos de transporte coletivo e de 
carga, etc.), custo de ampliação da malha viária
● Objetivo: compreensão do fenômeno, auxiliar na 
otimização do uso da malha viária (sinalização, 
educação, sistema de interconexão) e sua 
expansão, decisões de curto prazo e análise de 
contingências
● Escala de análise: microscópica → macroscópica
● Técnicas utilizadas: equações diferenciais, lattice 
gas, autômatos celulares
 
Modelos de escoamento contínuo
● A análise do tráfego se faz com o auxílio de 
equações diferenciais similares às da dinâmica de 
fluidos
● LW – Lighthill & Witham (equação de continuidade, 
exemplo mais simples) 
→ Estes modelos são empregados desde ~1965 e ainda 
propiciam um ambiente para a compreensão dos efeitos 
macroscópicos do tráfego (retenções e reabsorções). 
Baseiam-se em condições em um ponto, apesar de só 
fazerem sentido em “volumes representativos”
∂ ρ
∂ t
+
∂( ρV )
∂ x
=±v ( x ,t )
 
Modelos baseados em análise microscópica
(1) Cinética de Gás
→ Estes modelos são empregados com “upscaling” a partir de 
regras microscópicas, e produzem um modelo macroscópico da 
forma
Com número de veículos constante. A velocidade tem 
dependência não local: 
0)( =
∂
∂+
∂
∂
ξ
ς
τ
ρρ
)()
1
(
)(
)(
)(1)(
2
max
max
0
0
2
V
a
a BTV
A
AV
VV
x
AVV
x
V
t
δ
ρ
ρ
ρ
ρτ
ρ
τ
ρ
ρ
−
−
−+
∂
∂−=
∂
∂+
∂
∂
 
Modelos baseados em análise microscópica
● A velocidade de equilíbrio dinâmico não-local tem a forma
● O fator de Boltzmann
● A variância intra-faixa é aproximada pela relação constitutiva 
 
Modelos baseados em análise microscópica
O modelo não local de tráfego baseado em cinética de gases 
pode incluir um termo adicional referente a frenagem 
antecipatória, que funciona como um termo de viscosidade na 
equação de fluidos obtida. Nos resultados, o termo de 
viscosidade puramente local resulta em corcovas não-físicas 
nas curvas de densidade, enquanto a não-localidade da 
frenagem os evita.
●Tem-se que resolver (numericamente) uma equação da forma 
Vários métodos numéricos podem ser usados para integrar a 
equação acima ao longo do tempo. Não é necessária 
computação de alto desempenho para o problema macroscópico 
ser resolvido (ex: upwind, Lax-Friedrichs, Lax-Wendroff).
 
Modelos baseados em análise microscópica
(2) Modelo contínuo baseado em equações diferenciais 
ordinárias e autômatos celulares (car following).
 Cada veículo é simulado. Há três comportamentos 
principais que são considerados:
 a. aceleração;
 b. desaceleração por frenagem;
 c. mudanças de faixa (em modelos multifaixa).
 
Vários fatores tem que ser considerados: taxa de 
aceleração, distância para antecipação, tamanho dos 
veículos, composição da frota, distância de segurança, 
nível de ansiedade para mudança de faixa, velocidade 
objetivo, probabilidade de flutuação de velocidade, etc. 
Podem-se ter até 50 parâmetros nos simuladores.
 
Modelos baseados em análise microscópica
(2.1) Modelo contínuo baseado em equações diferenciais 
ordinárias.
 Um dos exemplos (e o mais simples) é denominado IDM 
(Modelo do Motorista Inteligente). Baseia-se em alguns 
parâmetros e utiliza as equações a seguir.
Parâmetros (com valores típicos): velocidade desejada 
(120km/h), distância em tempo do veículo da frente (1,5s), 
aceleração máxima (1m/s2), desaceleração cômoda 
(2m/s2), distância mínima (2m), distância de 
congestionamento (0,5m) e expoente de aceleração(4). 
 
Modelos baseados em análise microscópica
(2.1) Modelo contínuo baseado em equações diferenciais 
ordinárias.
 Aceleração: termos de via livre e desaceleração por 
proximidade. 
 
Onde S* é o gap mínimo desejado, dado por
 
Modelos baseados em análise microscópica
(2.1) Modelo contínuo baseado em equações diferenciais 
ordinárias.
 Outros modelos foram propostos, como o Human Driver Model 
– HDM, para o qual outros parâmetros/aspectos são incluídos:
 Tempo finito de reação (reação não instantânea a impulsos);
 Antecipações temporal e espacial; 
 Antecipação em relação às condições globais de tráfego.
●Métodos numéricos: passo simples (Euler, RK2, RK4), múltiplo 
(Adams-Moulton, BDF). Sistemas com 2N incógnitas /passo de 
tempo.
 
Modelos baseados em análise microscópica
(2.2) Modelo discreto baseado em autômatos celulares.
● Autômatos celulares: 
 Máquina de estado finito
 Domínio discretizado em células
 Cada célula tem seu estado definido conforme o 
 seu estado atual e dos seus vizinhos
●Definição de AC:
 L - representa a discretização em uma grade regular,
 formada por células (c) de dimensão D;
 S é o conjunto finito de estados;
 N é a vizinhança adotada, tal que c є L então N(c) є L, e
 f : (S;N) → S é a função de transição.
 
Modelos baseados em análise microscópica
 Autômatos celulares: vizinhança 
 
 
 
Modelos baseados em análise microscópica
 Autômatos celulares: condições de contorno 
 
 
 
Modelos baseados em análise microscópica: 
introdução
 Autômatos celulares: “Conway´s the game of life” e 
comportamento de multidão. 
 
●No modelo básico, as condições a analisar em cada 
instante de tempo, e que determinam o instante seguinte, 
são relativas ao número de vizinhos de uma célula, e o 
estado desta. Várias geometrias e definições de vizinhança 
são possíveis. Em simulações de evolução de D.I., a 
vizinhança pode ter abrangência global com pesos 
(mobilidade).
● Exemplos:
 http://www.youtube.com/watch?v=Fkwjxb-1dxE ,
 http://ped-net.org/index.php?id=26&ID=253 
http://www.youtube.com/watch?v=Fkwjxb-1dxE
http://ped-net.org/index.php?id=26&ID=253
 
Modelos baseados em análise microscópica
 Autômatos celulares: regras básicas para tráfego. 
●Modelo NaSch (1992) 
 Reproduz os fenômenos básicos do tráfego
Variáveis discretizadas:
 Posição em célula (x). Extensão: multicélula.
 Velocidade em células por segundo (v), v em [0; vmax]
 Tempo em segundos (t)
 A via é discretizada como malha (1D ou 2D)
 Representação da malha com x = 7,5m e t = 1s:
 
Modelos baseados em análise microscópica
 Autômatos celulares: regras básicas para tráfego. 
Com condição de contorno periódica tem-se:
 Via de comprimento L
 A posição X é a mesma que X + L
 Deslocamento dos veículos é dado pela regra de 
transição
 Velocidade dada em células por instante de tempo
 Nova posição dada por acréscimo de v.t, v
 
Modelos baseados em análise microscópica
 Autômatos celulares: observáveis principais. 
Principais grandezas para análise do tráfego:
 Densidade - Número de veículos em um trecho da pista
 Velocidade - Velocidade média dos veículos
 Fluxo - Veículos que passam por uma seção da pista
 
Modelos baseados em análise microscópica
Diagrama fundamental: Fluxo x densidade
- Livre: 0 < ρ < c1
- Meta-estabilidade: 
 c1 < ρ < c2
- Congestionado:
 ρ > c2
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos baseados em análise microscópica
 
Modelos microscópicos: pseudocódigo TACUFF
 
Modelos microscópicos: pseudocódigo TACUFF
 
Modelos microscópicos: exemplo de resultado TACUFF
 
Modelos microscópicos: exemplo de resultado TACUFF
 
Modelos microscópicos: exemplo de resultado TACUFF
 
Modelos microscópicos: exemplo de resultado TACUFF
 
Modelos microscópicos: TACUFF multifaixa
 
Modelos microscópicos: TACUFF multifaixa
 
Modelos microscópicos: TACUFF multifaixa
 
Modelos microscópicos:TACUFF multifaixa
 
Modelos microscópicos: multifaixa e referências 
Nagel, K.; Schreckenberg, M. A cellular automaton model
for freeway tra c. Journal de Physique I, v. 2, p.ffi
2221–2229, dez. 1992
KNOSPE, W. et al. A realistic two-lane tra c model forffi
highway tra c. J. Phys. A, v. 35, p. 3369–3388, 2002ffi
Exemplo de Simulador 2 faixas com características comportamentais 
e entrada calibráveis: 
http://vwitme011.vkw.tu-dresden.de/~treiber/MicroApplet/
ZAMITH, M. ; LEAL TOLEDO, R. C. P. ; KISCHINHEVSKY, M. ; Brandão, D. ; Montenegro, A.A. ; 
Clua, E.W.G. ; Lima, E.B. . A probabilistic cellular automata model for highway traffic simulation. 
In: Proceedings of the International Conference on Computational Science - ICCS, 2010.
ZAMITH, M. ; LEAL TOLEDO, R. C. P. ; KISCHINHEVSKY, M. ; Clua, E.W.G. ; Brandão, D. ; 
Montenegro, A.A. ; Lima, E.B. . A Parallelizable Probabilistic Cellular Automata Model for 
Highway Traffic Simulation: Periodic and Open Boundaries Conditions. In: 9th International 
Meeting on High Performance Computing for Computational Science, VECPAR 2010.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37