EL ALGORITMO DE FLOCKING

 

El algoritmo de Flocking se refiere a la simulación del movimiento colectivo de entidades autopropulsadas (que se desplazan de manera autónoma), tomando como base el comportamiento de rebaños de animales en la naturaleza, como bandadas de aves, cardúmenes de peces, enjambres de insectos o grupos de bacterias; este modelo no requiere una coordinación central, ya que las acciones generales resultan de reglas locales aplicados por los individuos. Este fenómeno fue explicado por primera vez en 1987 por Craig Reynolds en su programa "Boids" (bird-oid object), donde se representan unos agentes que se mueven siguiendo tres principios fundamentales: separación (evitar colisiones), alineación (sincronizar la dirección con los vecinos) y cohesión (dirigirse hacia el centro del grupo); gracias a esta lógica, las aves pueden adaptar su vuelo en función de los movimientos de sus compañeras, logrando así que las bandadas se desplacen de manera sincronizada y fluida; este trabajo fue formalizado en el artículo "Flocks, Herds, and Schools: A Distributed Behavioral Model" y sentó las bases de modelos computacionales bioinspirados.

En clustering, el algoritmo de flocking se aplica en el agrupamiento de datos con un enfoque basado en agentes, donde cada agente es un punto de datos que se visualiza como un "boid" interactuando con sus vecinos más cercanos, lo que da lugar a agrupaciones autoorganizadas; a diferencia de métodos como k-means, este enfoque no necesita semillas iniciales ni particiones predefinidas, además, permite trabajar con datos en alta dimensión al proyectarlos en una cuadrícula bidimensional, facilitando así su visualización y recuperación.

Este algoritmo, además de ser clasificado como basado en agentes, también se relaciona con algoritmos de clustering dinámico, en este caso, los grupos de agentes pueden formarse, disolverse y reorganizarse de manera dinámica dependiendo de las interacciones y del entorno; asimismo, podemos considerarlo un algoritmo evolutivo y natural, ya que se inspira en el comportamiento natural de aves, peces, etc; por último, es un algoritmo distribuido, dado que cada agente toma decisiones de manera independiente, basadas en información local.

REGLAS DEL FLOCKING

1. Separación: Los agentes evitan acercarse a otros agentes, ya que podrían ocurrir colisiones.
 

2. Alineación: Los agentes alinean su dirección de movimiento con la dirección media de sus vecinos.

 

3. Cohesión: Los agentes tienden a dirigirse hacia el centro de masa de sus vecinos, para agruparse.

Otras reglas opcionales son:

4. Límites del entorno: Evitar que los agentes salgan del área definida.

5. Evitar obstáculos: Adaptar la trayectoria con el fin de esquivar obstáculos en el entorno.

PASOS DEL ALGORITMO

1. Inicio

- Generamos un conjunto de 𝑁 puntos aleatorios en un espacio 2D. Cada punto tiene:

* Una posición inicial $p_i=(x_i,y_i)$.
* Una velocidad inicial $v_i=(v_{xi},v_{yi})$.
* Un rango de percepción (radio de influencia) para detectar vecinos cercanos.

- Definimos los pesos de las fuerzas:

* $w_{sep}$ para separación.
* $w_{ali}$ para alineación.
* $w_{coh}$ para cohesión.

2. Iteraciones del Algoritmo

- El algoritmo funciona mediante iteraciones y en cada paso actualiza las posiciones de los puntos.

Paso 1: Identificar vecinos, para cada punto $p_i$ se tienen los puntos vecinos $p_j$ dentro del rango de percepción, para lo cual, se calcula la distancia euclidiana si $||p_i-p_j||\le R$, donde $R$ es el rango de percepción.

Paso 2: Calcular las fuerzas basada en vecinos para cada punto $p_i$.

i) Separación ($F_{\text{sep}}$): Evita la colisión con los vecinos cercanos, empujando a $p_i$ lejos de los puntos más cercanos; $p_i$ y $p_j$ son las posiciones de los agentes $i$ y $j$.

$$F_{\text{sep}}=-\sum _{j\in \text{vecinos}}\frac{(p_i-p_j)}{\Vert p_i-p_j{\Vert }^2}$$

ii) Alineación ($F_{\text{ali}}$): Ajusta la dirección de movimiento de $p_i$ para alinearse con sus vecinos, observándose movimientos sincronizados; en la ecuación, $v_j$ es la velocidad del vecino $j$.

$$F_{\text{ali}}=\frac{1}{N_{\text{vecinos}}}\sum _{j\in \text{vecinos}}{v}_j$$

iii) Cohesión ($F_{\text{coh}}$): Atrae a $p_i$ hacia el centro de masa de sus vecinos.

$$F_{\text{coh}}=\frac{1}{N_{\text{vecinos}}}\sum _{j\in \text{vecinos}}(p_j-p_i)$$

 

Paso 3: Combinar fuerzas para determinar la nueva dirección y velocidad de $p_i$:

$$F_{\text{total}}=w_{\text{sep}}{F}_{\text{sep}}+w_{\text{ali}}{F}_{\text{ali}}+w_{\text{coh}}{F}_{\text{coh}}$$

Donde $w_{\text{sep}},w_{\text{ali}},w_{\text{coh}}$ son los pesos que ajustan la influencia relativa de cada regla.

- Actualizamos la velocidad y posición del punto:

$$v_i^{\text{nuevo}}=v_i+F_{\text{total}}$$

$$p_i^{\text{nuevo}}=p_i+v_i^{\text{nuevo}}$$

3. Repetir hasta converger

Repetimos el cálculo de las fuerzas y la actualización de posiciones haciendo varias iteraciones hasta que los puntos (aves) formen grupos estables (clústeres) y que el movimiento también se estabilice.


4. Resultados

Después de varias iteraciones, se agrupan los puntos en clústeres naturales según interacción local, entonces cada clúster se convierte en una "bandada" homogénea.

PARÁMETROS

- Rango de interacción (qué tan cerca deben estar los agentes para influirse mutuamente).
- Velocidad máxima (rapidez con la que un agente puede moverse).
- Pesos de las fuerzas (controlan la importancia relativa de separación, alineación y cohesión).
- Rango de percepción (qué vecinos son considerados en las reglas).
- Distancia mínima (espacio personal de cada agente para evitar colisiones).
- Tiempo de actualización (intervalo de tiempo entre actualizaciones del estado del sistema).

APLICACIONES

- En agrupamiento de datos para encontrar grupos de puntos similares por medio del movimiento colectivo.
- En la simulación de sistemas dinámicos para modelar el comportamiento de enjambres o grupos (p.e. bandadas de aves, cardúmenes de peces, etc.)
- En robótica para coordinar los movimientos de diferentes robots autónomos en un escenario de trabajo común (p.e. para la coordinación de drones).
- En optimización para resolver problemas complejos a través de la búsqueda cooperativa de soluciones.
- En efectos visuales y en animación para la recreación de comportamientos colectivos en películas y videojuegos.
- En gestión de redes para optimización de redes distribuidas de sensores.
- En biología computacional para la simulación del comportamiento de los animales.
- En sistemas multiagente para la coordinación en sistemas descentralizados.
- Etc.

VENTAJAS Y LIMITACIONES

- Puede adaptarse a datos dinámicos.
- No es necesario conocer el número de clústeres de antemano.
- Es apropiado para espacios multidimensionales de grandes dimensiones.
- Sin embargo, es sensible a la elección de los parámetros.
- Es menos escalable a la hora de manejar un número de agentes muy grande.
- Puede verse afectado por el ruido existente en los datos.

EJEMPLO BÁSICO DEL ALGORITMO DE FLOCKING EN PYTHON

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

# Parámetros del sistema
N = 100                 # Número de aves
iterations = 200        # Número de iteraciones
range_perception = 1.5  # Rango de percepción
w_sep = 1.5             # Peso de separación
w_ali = 1.0             # Peso de alineación
w_coh = 1.0             # Peso de cohesión
speed_limit = 0.1       # Límite de velocidad

# Inicializar posiciones y velocidades
np.random.seed(42)
positions = np.random.rand(N, 2) * 10
velocities = (np.random.rand(N, 2) - 0.5) * 0.2

# Función para calcular distancias euclidianas
def euclidean_distance(a, b):
    return np.linalg.norm(a - b, axis=1)

# Actualización de posiciones y velocidades
def update(frame):
    global positions, velocities
    new_velocities = velocities.copy()
    for i in range(N):
        # Vecinos dentro del rango de percepción
        distances = euclidean_distance(positions[i], positions)
        neighbors = np.where((distances > 0) & (distances <= range_perception))[0]
        
        if len(neighbors) > 0:
            # Separación
            sep_force = np.sum((positions[i] - positions[neighbors]) /
                                (distances[neighbors][:, None]**2 + 1e-6), axis=0)
            sep_force = -sep_force
            
            # Alineación
            ali_force = np.mean(velocities[neighbors], axis=0)
            
            # Cohesión
            center_of_mass = np.mean(positions[neighbors], axis=0)
            coh_force = center_of_mass - positions[i]
            
            # Combinar fuerzas
            total_force = w_sep * sep_force + w_ali * ali_force + w_coh * coh_force
            new_velocity = velocities[i] + total_force
            
            # Limitar velocidad
            speed = np.linalg.norm(new_velocity)
            if speed > speed_limit:
                new_velocity = new_velocity / speed * speed_limit
            new_velocities[i] = new_velocity
    
    # Actualizar posiciones y velocidades
    velocities[:] = new_velocities
    positions[:] = positions + velocities
    
    # Limitar posiciones dentro del área
    positions[:] = np.mod(positions, 10)
    
    # Actualizar la animación
    scatter.set_offsets(positions)
    return scatter,

# Crear la figura
fig, ax = plt.subplots(figsize=(6, 6))
ax.set_xlim(0, 10)
ax.set_ylim(0, 10)
scatter = ax.scatter(positions[:, 0], positions[:, 1], color="blue")

# Animación
ani = FuncAnimation(fig, update, frames=iterations, interval=50, blit=True)

plt.show()

 

En términos visuales, al inicio los puntos se encuentran dispersos de manera aleatoria en la primera iteración; cuando los puntos más cercanos empiezan a moverse hacia el centro de su grupo local, las fuerzas de separación hacen que no se agrupen demasiado, en cambio, la alineación y la cohesión ayudan a definir el grupo; y después de varias iteraciones, los puntos acaban agrupándose en clústeres bien delimitados, siguiendo así el comportamiento de las bandadas de aves.

Otros ejemplos: (1), (2), (3), (4).

 

Finalmente, el Flocking es un algoritmo inspirado en la naturaleza, basado en reglas sencillas que dan como resultado comportamientos colectivos y complejos; su capacidad de adaptación lo hace perfecto para las aplicaciones a sistemas dinámicos, distribuidos y autónomos.

 

 

Referencia: (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11).