Grupo - BOIDS

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 as partículas BOIDs são geradas aleatoriamente com uma posição e velocidade aleatória. Após é dado um passo temporal e, para cada BOID, são contados os objetos vizinhos que estão dentro de um raio R de interação e em seguida computadas e atualizadas as seguintes regras:

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 é um coeficiente de separação.

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.

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}x_{i}{\vec {r}}_{i}$, N sendo o número de partículas dentro do raio de interação.

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

Regras complementares e mais complexas como desviar de objetos e perseguir objetivos podem ser adicionadas para diferentes estudos.

Inicialmente são sorteadas posições e velocidades para os objetos. As regras são então calculadas a cada loop de passo. 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. Após o cálculo das novas posições e velocidades é somado um incremento de tempo e o algoritmo recomeça.

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.

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.