La #ormiga de Langton

Uno de mis objetivos durante el presente curso académico es profundizar en algunos campos en los que la informática supone un importante apoyo para el estudio del medio ambiente y la biología. Por ejemplo, desarrollando aplicaciones que hagan uso de sistemas de información geográfica para representar la evolución de poblaciones en un determinado entorno físico. El uso de la inteligencia y la vida artificial para modelar sistemas siempre me ha interesado sobremanera y, ya que Ecología es una de las asignaturas que cursaré en Ambientales durante 2011-2012, espero poder sacar partido a mis conocimientos en la materia para adquirir otros mucho más profundos e interesantes.

Un primer paso lo ha supuesto entretenerme durante la tarde de ayer en programar un algoritmo muy básico dentro del mundo de los autómatas celulares: la hormiga de Langton. Esta primera aproximación la he desarrollado sobre un mundo bidimensional y he implementado dos tipos de malla, una cuadrada que es la que puede verse en el vídeo de ejemplo y una hexagonal, representable en el modo de texto pero de forma no muy intuitiva.

Primera versión de la hormiga de Langton (C# con un visor en modo texto)

Para quienes no la conozcáis, la hormiga de Langton consiste en un sistema determinista, dinámico y discreto, que puede entenderse como un autómata celular, una máquina de Turing bidimensional o un sistema de agentes. Aunque la versión más básica de la misma consiste en un mundo bidimensional infinito (aunque por motivos de representación suelen hacerse simulaciones con toros finitos, como es el caso de mi ejemplo, con el borde izquierdo “unido” al derecho y el superior al inferior) en el que se mueve nuestra hormiga cambiando el color de la celda sobre la que se sitúa en cada momento del tiempo, lo cierto es que resulta interesante extender las características de la hormiga para mostrar movimientos y comportamientos más complejos, como colorear de distinto modo las celdas o moverse según otros patrones o en mundos más complejos. También es posible incluir más hormigas en el sistema, por supuesto.

El comportamiento más básico de la hormiga es el siguiente:

• Situamos la hormiga en un mundo representado por una malla cuadrada cuyas casillas pueden estar coloreadas de blanco o negro.
• La hormiga pude moverse en la dirección de cualquiera de los cuatro puntos cardinales, siempre según las siguientes reglas (conjunto básico):
• Si la hormiga está en una casilla blanca, gira 90º a la derecha, cambia el color de la casilla y se mueve adelante una unidad.
• Si la hormiga está en una casilla negra, gira 90º a la izquierda, cambia el color de la casilla y se mueve adelante una unidad.

La hormiga fue descubierta al mundo en un artículo de la revista Physica D en 1986 escrito por el especialista en vida artificial (es uno de los padres fundadores de esta línea de investigación) Christopher Langton, que estudiaba por aquel entonces modelos de autómatas simples dotados de comportamientos complejos.

Un par de años después, el entonces estudiante de informática Greg Turk propuso varios ejemplos de máquinas de Turing bidimensionales que “caminaban” sobre su cinta en lugar de hacer que esta se moviese bajo las mismas. Una de esas máquinas resultó ser la hormiga de Langton, y en conjunto recibieron el evocativo nombre de turmites (“turmitas”, algo así como termitas de Turing). El matemático y divulgador A.K. Dewdney dedicó uno de sus artículos en Scientific American a este tema.

Nuestra hormiga hizo una tercera aparición dentro de los modelos para la simulación de dinámica de fluidos a niveles microscópicos en Física. Uno de estos modelos, en concreto el de de Ruijgrok-Cohen, se corresponde con el de una partícula que se mueve entre desviadores que cambian su trayectoria y que pueden ser modificados por los impactos de la misma, igual que ocurre con la hormiga de Langton y el comportamiento que presenta en la malla que comprende su mundo.

El comportamiento de la hormiga es muy curioso. Después de un periodo en el que describe unos movimientos aparentemente caóticos comienza a construir una "autopista" siguiendo un patrón que comprende 104 avances o pasos. En el vídeo que incluyo como demostración esto ocurre a partir de veinte segundos.

Mi intención es liberar el código fuente (está en C#, de ahí lo de #ormiga) que vaya generando a lo largo de mis aventuras en estos mundos virtuales, incluso el de este “periodo de repaso” a algunos sistemas realmente simples, pero lo cierto es que creo que esperaré un poco más antes de publicar el de la hormiga de Langton, ya que me gustaría hacerla mucho más configurable. Ahora mismo es posible cambiar el tipo de rejilla y usar más de un agente en ella, pero no especificar reglas de movimiento para la hormiga o, tal y como me gustaría, tener un mundo tridimensional por el que pueda moverse.

Espero que os interese el tema y que, además, sirva de punto de arranque para una serie de entradas que posiblemente se espacien pero también prolonguen en el tiempo.