Introdução aos Métodos em
Simulação Computacional
Adriana Racco
CSC - Coordenação de Sistemas e Controle
Laboratório Nacional de Computação Científica
1
Autômato celular
2
Autômato celular
John von Neumann foi o primeiro a
propor um modelo simples para tentar
reproduzir vida.
3
Autômato celular
Tempo e espaço discretos
Estados bem definidos
Regras de evolução que
dependem da vizinhança
4
Rede e célula
Rede é toda a região que será
usada na simulação. Ela é
dividida em células.
Uma célula ou sítio é o menor
pedaço da rede.
5
Clusters
Cluster é um conjunto de células vizinhas, que
estejam no mesmo estado.
Cluster percolante – é um cluster que atravessa
toda a rede.
6
Formato das células
As células podem ter de várias formas, desde que
num mesmo autômato todas as células sejam de uma
mesma forma.
Triangular
7
Formato das células
As células podem ter de várias formas, desde que
num mesmo autômato todas as células sejam de uma
mesma forma.
Hexagonal
8
Formato das células
As células podem ter de várias formas, desde que
num mesmo autômato todas as células sejam de uma
mesma forma.
Quadrangular
9
Vizinhança de Neumann
Primeiros vizinhos
Segundos vizinhos
10
Vizinhança de Moore
Primeiros vizinhos
Segundos vizinhos
11
Vizinhança aleatória
12
Vizinhança arbitrária
A vizinhança arbitrária é determinada pelo modelo.
Exemplo:
Primeiros vizinhos
Segundos vizinhos
13
Estados dos sítios
Os estados dos sítios tem que ser bem definidos e finitos.
Exemplos:
0 ou 1 – ocupado ou vazio, vivo ou morto,
spin up ou spin down etc…
0,1 ou 2 – referente a espécie que ocupa cada sítio,
número de indivíduos.
14
Condições de contorno
• Periódicas (1D - anel ou 2D - toro)
• Fechadas
• Abertas
15
Regras
As regras podem depender do estado do próprio
sítio e dos sítios vizinhos.
Podemos criar campos e influência da geografia
do sistema.
Podem ser determinísticas ou probabilísticas.
Processo Markoviano - depende apenas do
estado atual dos sítios.
16
Jogo da vida
John Conway (1970)
Estados possíveis - vivo ou morto
Morte
Solidão - um ou zero vizinhos
Superpopulação – quatro vizinhos
Nascimento – células vazias com três vizinhos
Sobrevivência - dois ou três vizinhos.
http://www.bitstorm.org/gameoflife
17
Boid - Craig Reynolds (1986)
-Criar uma população que vive em bando.
- 3 D (cubo)
- As três regras simples eram :
• Evitar entrar na frente de seus vizinhos;
• Se manter na média da cabeceira do bando;
•
Se manter na posição média de seus vizinhos.
- Acrescentaram novas regras sobre desviar de obstáculos e
cumprir metas, de tal forma que os indivíduos se movessem
como um bando, modificando sua velocidade para manter o
equilíbrio.
18
Boid - Craig Reynolds (1986)
http://www.lsi.usp.br/~rponeves/diss/dissert.htm#_Toc52116928
19
Boid - Craig Reynolds (1986)
http://www.lsi.usp.br/~rponeves/diss/dissert.htm#_Toc52116928
20
Boid - Craig Reynolds (1986)
Animação computacional
•"Breaking The Ice" - exibido em 1987 - SIGGRAPH
•"O Rei Leão" e "O Retorno de Batman"
Simulação de pessoas entrando em um gramado de futebol e
o posicionamento correto dentro dele.
21
Agentes
“Agentes autônomos são sistemas computacionais que habitam
algum ambiente de dinâmica complexa, sentem e agem
autonomamente neste ambiente e, fazendo isso, realizam uma
série de objetivos ou tarefas para os quais foram designados”.
[MAES, 1995]
Considerar comportamentos emergentes <- ideal para vida
artificial ALIFE
22
Agentes
 Autonomia: “agentes operam sem intervenção direta
de humanos ou outros, e tem algum controle sobre suas
ações e estados internos”;
 Habilidade social: “interação entre agentes”;
23
Agentes
 Reatividade: “agentes percebem seu ambiente e
respondem as mudanças que ocorrem nele”;
 Pro-atividade: “agentes não simplesmente agem
em resposta ao seu ambiente, são capazes de
tomar uma iniciativa para atingir determinado
objetivo”.
24
Sites interessantes
http://www.di.ufpe.br/~iobl/monografia
Aplicações gráficas de AC
http://madeira.cc.hokudai.ac.jp/RD/takai/automata.htmal
25
Geração de texturas
Y.Takai, N.K.Takai, and K.J.Nakamori: "Exploration
of the reaction-diffusion textures", Proc. Int. Conf. on
Modelling and Simulation , 1998
26
Listras
27
Zebra
28
Sistemas de partículas
Y.Takai, K.Ecchu, and N.K.Takai: "A cellular automaton
model of particle motions and its applications", The
Visual Computer , vol.11, no.5, 1995
29
Sistemas de partículas
30
Fogo
31
Fogo com vento
32
Colisão
33
Queda d’água
34
Queda d’água
35
Automato celular
Burning – Incêndio na floresta
Percolação
Contagem de clusters
Automatos celulares em 1D
Fractais
Formação
Dimensão fractal
36