Contexto Histórico

Desenvolvido por Craig Reynolds em 1986, é um algoritmo que busca, por meio de regras de comportamento, reproduzir o comportamento sincronizado de grupos de animais. Por exemplo manadas de animais terrestres, cardumes de peixes, bando de pássaros e etc. O nome BOID corresponde ao encurtamento da expressão em inglês “bird-oid object”, que se refere a um objeto “tipo pássaro”. Seu trabalho foi publicado em 87 sob o título original, em inglês, "Flocks, herds and schools: A distributed behavioral model". O modelo base de Craig já fora utilizado para diversas implementações e estudos. Como estudo comportamental de medo, interação entre animais via olfato modelando feromônios, mudança de liderança de um bando, dentre muitas outras aplicações interessantes.

Motivação

O movimento de animais em sincronia é extremamente complexo e é chave para sua sobrevivência em bando. Peixes, pássaros e mamíferos terrestres tem esse tipo de comportamento principalmente no que diz respeito a defesa em momentos em que sentem em perigo. A concentração intimida e o movimento confunde seus predadores. Além de ser extremamente prazeroso assistir um bando de pássaros ou um cardume de peixes em sua dança sincronizada.

Este trabalho busca, em suas etapas, reproduzir um cardume de peixes em seu padrão síncrono de movimento e, posteriormente, na presença de um ou mais predadores.

O Algoritmo

Inicialmente são sorteadas posições e velocidades aleatórias para os objetos. As regras são então calculadas a cada de passo temporal. Embora cada boid tenha liberdade sobre todo o espaço descrito, o seu comportamento é influenciado apenas por outros dentro de uma região circular centrada no objeto dita raio de interação (R). Após o cálculo das novas posições e velocidades é somado um incremento de tempo e o algoritmo recomeça.

Separação

Interação de repulsão entre os indivíduos para evitar superconcentração local (ou no caso extremo uma superposição). Um potencial análogo à Lei de Coulomb para cargas de mesmo sinal: ${\vec {V}}_{j}={\frac {S({\vec {p}}_{j}-{\vec {p}}_{k})}{||{\vec {r}}||^{2}}}$ , onde ${\vec {r}}=(x_{j}-x_{k}){\hat {i}}+(y_{j}-y_{k}){\hat {j}}$ e $S$ é o coeficiente de separação.

Fig1. link:https://en.wikipedia.org/wiki/Boids#/media/File:Rule_separation.gif

Alinhamento (vetor velocidade)

A velocidade média dos parceiros próximos influencia o vetor velocidade do objeto, fazendo-o ter um comportamento parecido com sua vizinhança.

${\vec {V}}_{j}^{n+1}=(1-M){\vec {V}}_{j}^{n}+M{\frac {1}{k}}\Sigma _{i=1}^{k}{\vec {V}}_{i}$ , com $k$ sendo o número de vizinhos dentro do raio de interação.

Fig2. link:https://en.wikipedia.org/wiki/Boids#/media/File:Rule_alignment.gif

Coesão

Os BOIDs interagentes tem um potencial de mola entre si, fazendo com que tenham a tendência de mover-se em direção ao centro de massa do grupo. Calculando primeiramente o centro de massa (CM) das partículas vizinhas utiliza-se da força elástica para simular uma mola entre o objeto e o CM da vizinhança.

${\vec {r}}_{CM}={\frac {1}{N}}\Sigma _{i=1}^{n}{\vec {r}}_{i}$ , N sendo o número de partículas dentro do raio de interação.

${\vec {V}}_{j}=C({\vec {r}}_{j}-{\vec {r}}_{CM})$ , C é o coeficiente elástico.

Fig3. link:https://en.wikipedia.org/wiki/Boids#/media/File:Rule_cohesion.gif

Ruído

Para reproduzir melhor um ser vivo, um pequeno ruído compõe a velocidade. Isso faz com que tenhamos uma maior flutuação no caminho que os boids traçam.

sendo $\zeta$ um número real aleatório, $V_{x}=\cos {(\zeta )}V_{x}+\sin {(\zeta )}V_{y}$ e $V_{y}=-\sin {(\zeta )}V_{x}+\cos {(\zeta )}V_{y}$

Predador

A partícula que representa o predador é como se fosse uma barreira repulsiva. Obedecendo, também, a Lei de Coulomb. No presente trabalho o predador não persegue os BOIDs, apenas se desloca em linha reta no plano com velocidade constante.

Aqui[1] é possível ver o comportamento de um cardume de peixes na presença de algumas arraias.

Resultados e Discução

Nosso modelo foi simulado com condições de contorno periódicas numa área quadrada de lado $L=1000$ . Abaixo apresentamos os resultados para cada regra isoladamente e ao final todas funcionando simultaneamente com e sem a presença do predador.

Separação

Aqui temos, como esperado, um corportamento semelhante ao de um gás ideal. Que busca um estado de menor energia ocupando todo o espaço disponível. Note que poucas regiões tem mais de 3 objetos próximos.

Simulação apenas da regra de separação entre BOIDS.

Coesão

Para a coesão temos um comportamento semelhante ao condensamento de um gás em gotas ou gotículas. As regiões mais concentradas (círculo verde) perdem um pouco de sua capacidade de mobilidade e se tornam atrativas para partículas vizinhas (círculos azuis). Ao passo que objetos isolados (círculos roxos) se comportam independentemente até encontrarem um, ou mais, vizinhos ou regiões de alta concentração.

Simulação apenas da regra de coesão entre BOIDS.

Na animação abaixo temos o comportamento dinâmico do sistema para o parâmetro $S$ crescente. Note que, de fato, a medida que $S$ aumenta, também ocorre o aumento da concentração dos BOIDs.

Simulação apenas da regra de coesão entre BOIDS.

Alinhamento (vetor velocidade)

Na regra de alinhamento temos o comportamento do vetor velocidade do objeto sendo influenciado pela velocidade das partículas na vizinhança. Na imagem estática fica difícil de diferenciar da regra de separação, porém, note como aqui há mais regiões com 3 ou mais BOIDs bem próximos. Em alguns casos pode-se notar que quase ocorre uma superposição.

Simulação apenas da regra de alinhamento entre BOIDS.

BOIDS.

Predador

BOIDs na presença de dois predadores.

Conclusão

Desenvolvimento em C

Abaixo verá trechos do código em linguagem de programação C utilizados no trabalho para as regras e etapas.

Link para o /codigo completo.

Coesão

      //**********Coesao Entre Particulas e CM**********//
      
      
      for(m=0;m<N;m++){ // laço das particulas 
	if(norm(r[j][1]-r[m][1],r[j][0]-r[m][0])<R){// se as particulas tiverem a uma distancia menor q "R"
	  cont++;          // acrescenta no contador 
	  x = x + r[m][0]; // acrescenta na posicao das particulas na comp. x
	  y = y + r[m][1]; // acrescenta na posicao das particulas na comp. y
	}	 
      }
      
      if(cont>1){ // se contador for cont > 1
	x = x/cont;     // media aritmetica na componente x       
	y = y/cont;     // media aritmetica a componente y
	
	v[j][0] = v[j][0] - C*(r[j][0] - x)/L; // atualiza velocidade c potencial de mola na componente x
	v[j][1] = v[j][1] - C*(r[j][1] - y)/L; // atualiza velocidade c potencial de mola na componente y 
      }

Separação

      //**********Separacao Entre Particulas**********//
      
      for(l=0;l<N;l++){ //laço para particulas
	if(l==j){  // se a particula for ela mesma nao faz nada 
	  
	}else{     // se nao é ela entao
	  
	  if(norm(r[j][0]-r[l][0],r[j][1]-r[l][1])<rmin){ // se as particulas estao a uma distancia menor que  "rmin"
	    v[j][0] = v[j][0] + S*(r[j][0] - r[l][0])/pow(norm(r[l][0]-r[j][0],r[l][1]-r[j][1]),2); // Atualiza velocidade c potencial analogo a lei de Coulomb na componente x
	            
	    v[j][1] = v[j][1] + S*(r[j][1] - r[l][1])/pow(norm(r[l][0]-r[j][0],r[l][1]-r[j][1]),2); // Atualiza velocidade c potencial analogo a lei de Coulomb na componente y
	            
	  }
	}
      }

Alinhamento (vetor Velocidade)

    //**********Media da Velocidade dos Vizinhos**********//
      
      
      for(k=0;k<N;k++){ // laço para todas as particulas
	if(k == j){  // se eh a mesma particula nao faz nada
	}else if(norm(r[j][1]-r[k][1],r[j][0]-r[k][0])<erre){ 
	  kont++;              // se eh outra particula acrescenta no contador
	  vmx = vmx + v[k][0]; // acrescenta a velocidade na componente x
	  vmy = vmy + v[k][1]; // acrescenta a velocidade na componente y
	}
      }
      
      if(kont > 1){
	v[j][0] = (1-M)*v[j][0] + M*(vmx/kont); // media com peso M para a vel.
	v[j][1] = (1-M)*v[j][1] + M*(vmy/kont); // dos vizinhos e a propria
      }

Ruído

      //**********Ruido**********//
      if(rand()%2 == 0){ // criterio para decidir a fase
	randomi = - rand()/RAND_MAX; // fase
      }else{
	randomi = rand()/RAND_MAX; // fase
      }
      v[j][0] = cos(randomi)*v[j][0] + sin(randomi)*v[j][1];  // rotaçao
      v[j][1] = - sin(randomi)*v[j][0] + cos(randomi)*v[j][1]; // rotaçao

Predador

      //Barreira puntual no centro
      if(norm(r[j][0] -bx, r[j][1] - by) < ERRE){ // se a particula ta a menos
	                                          //  de "ERRE" entao
	
	if(r[j][0] < bx && r[j][1] < by){ // se estiver atras e abaixo
	  v[j][0] = v[j][0] - B*norm(r[j][0] - bx, r[j][0] - bx)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	  v[j][1] = v[j][1] - B*norm(r[j][1] - by, r[j][1] - by)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	  
	}else if(r[j][0] > bx && r[j][1] < by){ // se estiver a frente e abaixo
	  v[j][0] = v[j][0] + B*norm(r[j][0] - bx, r[j][0] - bx)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	  v[j][1] = v[j][1] - B*norm(r[j][1] - by, r[j][1] - by)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	  
	}else if(r[j][0] < bx && r[j][1] > by){ // se estiver abaixo e acima
	  v[j][0] = v[j][0] - B*norm(r[j][0] - bx, r[j][0] - bx)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5);// atualiza velocidade com potencial analogo "gravitac"
	  v[j][1] = v[j][1] + B*norm(r[j][1] - by, r[j][1] - by)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5);// atualiza velocidade com potencial analogo "gravitac"
	  
	}else if(r[j][0] > bx && r[j][1] > by){// se estiver a frente e acima
	  v[j][0] = v[j][0] + B*norm(r[j][0] - bx, r[j][0] - bx)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	  v[j][1] = v[j][1] + B*norm(r[j][1] - by, r[j][1] - by)/pow(norm(r[j][0] - bx, r[j][1]- by),1.5); // atualiza velocidade com potencial analogo "gravitac"
	}

      }

Referências

https://en.wikipedia.org/wiki/Boids
Reynolds, C. W. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings) pages 25-34.
Vicsek, T.; Czirok, A.; Ben-Jacob, E.;; Cohen, I.; Shochet, O. (1995). "Novel type of phase transition in a system of self-driven particles". Physical Review Letters. 75: 1226–1229. arXiv:cond-mat/0611743

Grupo - BOIDS

Índice

Contexto Histórico

Motivação

O Algoritmo

Separação

Alinhamento (vetor velocidade)

Coesão

Ruído

Predador

Resultados e Discução

Separação

Coesão

Alinhamento (vetor velocidade)

Predador

Conclusão

Desenvolvimento em C

Coesão

Separação

Alinhamento (vetor Velocidade)

Ruído

Predador

Referências

Menu de navegação

Grupo - BOIDS

Contexto Histórico

Motivação

O Algoritmo

Separação

Alinhamento (vetor velocidade)

Coesão

Ruído

Predador

Resultados e Discução

Separação

Coesão

Alinhamento (vetor velocidade)

Predador

Conclusão

Desenvolvimento em C

Coesão

Separação

Alinhamento (vetor Velocidade)

Ruído

Predador

Referências

Menu de navegação

Pesquisa