Los enjambres auto-organizados son fascinantes. Si usted ha crecido viendo a las hormigas hacer sus cosas, ahora puede ver un enjambre de 1000 pequeños robots que hacen formas sin tener ninguno el control de esto. Los kilobots, que así se llaman, son pequeños y muy simples. Se mueven usando las vibraciones que se pasan en los canales a través de sus tres pequeñas patas alámbricas. Esto es barato pero significa que los robots se mueven lentos comparativamente y eso hace que el crear una forma determinada lleve tiempo.
Los kilobots básicamente se pueden mover en una dirección dada, comunicarse con sus vecinos y sentirlos. Esta es la habilidad que le permite a los kilobots auto-organizarse. El siguiente video muestra perfectamente de lo que estamos hablando:
Lo más interesante -aparte de ver a los robots hacer la forma- es el cómo es que la crean. Todos los robots tienen el mismo programa e increíblemente, aún así generan diferentes partes de la forma que van a crear. Parece magia, pero todo puede explicarse vía la teoría de los autómatas celulares. Recordemos el juego de la vida de Conway, que genera patrones or demás complejos a partir de seguir las mismas sencillas reglas.
Por ejemplo, en el caso de los robots, cuatro de ellos se colocan en lugares cerca del enjambre inicial. Sirven para establecer el sistema de coordenadas que cada robot puede usar. La posición de cada robot es relativa a los robots sembrados. Estos tienen un programa diferente y simplemente dicen donde están, donde se encuentran. Entonces uno de los robots sembrados manda un mensaje, un gradiente de cero, que se usa para darles a todos los robots el sentido de dónde están en el enjambre. Todos ellos ponen su gradiente en valores menores a los gradientes que transmiten los otros robots, es decir, aquellos cercanos a los robots sembrados tienen gradiente de 1. Los robots cercanos a los que tienen ese nuevo valor, tienen un gradiente de 2, y así sucesivamente.
Todos los otros robots reciben el mismo programa que contiene una imagen de la forma que los robots tratan de construir en forma de bitmap. Solamente los robots en los bordes del enjambre se pueden mover a nuevas posiciones. Los robots saben que están en el borde porque tienen un valor gradiente mayor que el de sus vecinos. Si el robot tiene vecinos con gradiente igual entonces un valor de identificación (ID) se usa para romper el empate y el robot con distancia lejana máxima se empieza a mover, siguiendo el borde en el grupo que se mueve en sentido de lasa agujas del reloj.
Eventualmente encontrará tres robots que saben donde están por el sistema de coordenadas definido por los robots sembrados. De cualquier manera pueden usar esta información para saber en qué parte del sistema de coordenadas están y si tienen la forma deseada o no. Entonces continúan siguiendo el borde hasta que o se detienen porque se logró la forma o se encuentran un robot que ya se detuvo y que tiene un gradiente mayor que el propio. En ese caso este robot también se detiene.
La forma en que el proceso se detiene depende de cuantos robots hay y la forma de la figura creada. Si simplemente no hay suficientes robots, entonces todos se detienen y la forma queda incompleta. Pero hay el número correcto entonces todos se detienen con la forma esperada completa. Hay muchos detalles finos en este algoritmo pero esta es la idea principal.
El algoritmo está basado en los gradientes morfogénicos y es similar a la geometría inventada por Harry Blum en 1967. En este autómata celular, se tienen reglas que dependen de un campo de profundidad, es decir, la distancia más corta al borde de la forma a crear.
Referencias: