Jugando con autómatas celulares (15)

2013-09-20

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Hoy vamos a crear un autómata no determinista: el modelo del incendio forestal. Este autómata trata de forma muy simplificada la evolución de un bosque en el que se producen incendios. El modelo que vamos a tratar tiene muy poco valor predictivo, pero tiene cierto interés matemático. Este autómata del incendio forestal tiene las siguientes características:

es un autómata celular no determinista;
está definido en una malla cartesiana;
los estados posibles son tres: 0 (claro), 1 (árbol) y 2 (fuego).
la evolución de una celda, que es no determinista, está influenciada por el estado de la propia celda y el de su vecindario de Moore (las celdas inmediatamente en contacto tanto según líneas coordenadas como en diagonal);
un claro pasa a estar ocupado por un árbol con una probabilidad dada;
un árbol sin fuego alrededor pasa a incendiarse con una probabilidad dada;
un árbol con algún fuego en su vecindario se incendia;
un terreno incendiado pasa a convertirse en un claro.

Vamos a trabajar con una malla bidimensional cíclica porque el caso bidimensional es similar al de una superficie forestal real y ya tenemos funciones para trabajar con mallas cíclicas y que nos permiten despreocuparnos de las condiciones de contorno.

Vecindarios

Vamos a definir vecindarios para el modelo del bosque forestal bidimensional. En primer lugar, crearemos una pequeña herramienta adicional que nos servirá para determinar si algún elemento de una lista (o los elementos correspondientes de un conjunto de listas) cumplen una determinada condición. Esta función se llama any y tiene la siguiente forma:
(define (any predicate . lists) (let ((current-arguments (map car lists)) (next-arguments (map cdr lists))) (or (apply predicate current-arguments) (if (null? (car next-arguments)) #f (apply any (cons predicate next-arguments))))))
Esta definición viene a ser como la descrita en SRFI-1. primer argumento, predicate, es una función que acepta tantos argumentos como listas le pasamos a any; esta función indica si sus argumentos cumplen o no cumplen una determinada condición. Tras predicate, any acepta una cantidad arbitraria de listas que empaqueta en lists.

Python 2 ya viene con una función llamada any, pero en vez de aceptar un predicado y un conjunto de listas, acepta meramente un iterable. Nuestra biblioteca está hecha pensando en Scheme, así que vamos a hacer una versión en Python para ver cómo se traduciría. Quedaría así de forma recursiva:
def any(predicate, *lists): current_arguments = map(lambda lst: lst[0], lists) next_arguments = map(lambda lst: lst[1:], lists) return (predicate(*current_arguments) or (False if (len(next_arguments[0]) == 0) else any(predicate, *next_arguments)))
Esto no funciona muy bien en Python. Una forma iterativa de hacer lo mismo sería así:
def any(predicate, *lists): for arguments in zip(*lists): result = predicate(*arguments) if result: return result return False

Ahora ya podemos definir vecindarios para el modelo del bosque forestal bidimensional. Nuestra función se llamará cyclic-forest-fire-neighbourhoods y aceptará una lista plana de celdas cells y una lista de dimensiones sizes que contiene el largo y el ancho de nuestro dominio. Podríamos devolver simplemente para cada celda ella misma junto a su vecindario de Moore, pero en vez de eso vamos a pasar solamente la información que interesa: el estado de la propia celda y si hay celdas incendiadas alrededor. Lo hacemos así:
(define (cyclic-forest-fire-neighbourhoods cells sizes) (define (nearby-fires? neighbourhood) (any (lambda (neighbour) (= neighbour 2)) neighbourhood)) (let* ((offsets '((-1 -1) (-1 0) (-1 1) (0 -1) (0 1) (1 -1) (1 0) (1 1))) (moore-neighbourhoods (cyclic-cartesian-neighbourhoods cells sizes offsets)) (fires (map nearby-fires? moore-neighbourhoods))) (zip cells fires)))
Quedaría así en Python:
def cyclic_forest_fire_neighbourhoods(cells, sizes): def nearby_fires_p(neighbourhood): return any(lambda neighbour: neighbour == 2, neighbourhood) offsets = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)) moore_neighbourhoods = cyclic_cartesian_neighbourhoods(cells, sizes, offsets) fires = map(nearby_fires_p, moore_neighbourhoods) return zip(cells, fires)

Regla

La regla es fácil de crear con la función stochastic-rule.
(define (forest-fire-rule tree-probability fire-probability) (stochastic-rule `(((0 #f) ((,(- 1 tree-probability) 0) (,tree-probability 1))) ((0 #t) ((,(- 1 tree-probability) 0) (,tree-probability 1))) ((1 #f) ((,(- 1 fire-probability) 1) (,fire-probability 2))) ((1 #t) ((1 2))) ((2 #f) ((1 0))) ((2 #t) ((1 0))))))
Es así en Python:
def forest_fire_rule(tree_probability, fire_probability): return stochastic_rule({(0, False): {1 - tree_probability: 0, tree_probability: 1}, (0, True): {1 - tree_probability: 0, tree_probability: 1}, (1, False): {1 - fire_probability: 1, fire_probability: 2}, (1, True): {1: 1}, (2, False): {1: 0}, (2, True): {1: 0}})
En las opciones deterministas, nos limitamos a dar una probabilidad igual a la unidad.

Puesta a prueba

Ya podemos probar nuestro autómata del incendio forestal. Las probabilidades tendrian que ser pequeñas, sobre todo la de incendio. Vamos a ver cómo quedaría en un tablero de veinte por veinte con unas probabilidades no muy altas:
(let* ((sizes '(20 20)) (tree-probability 1e-2) (fire-probability 1e-3) (rule (wrap-with-generator (forest-fire-rule tree-probability fire-probability) (uniform-generator 0))) (initial-cells (repeat 0 (apply * sizes))) (neighbourhoods (lambda (cells) (cyclic-forest-fire-neighbourhoods cells sizes))) (display-function (lambda (cells) (translate-and-display-cartesian-2d cells sizes " ^*")))) (interactive-step rule initial-cells neighbourhoods display-function))
Esto hace que los claros aparezcan como espacios en blanco, los árboles como acentos circunflejos y los fuegos como asteriscos. Con estos parámetros, aparece un fuego a la vigésima iteración:
^^ ^ ^^ ^ ^ ^^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^^ ^^ ^ ^ ^ * ^ ^ ^ ^ ^ ^ ^^ ^ ^ ^ ^ ^ ^^ ^ ^^^^^ ^ ^ ^ ^ ^ ^^^ ^^ ^^ ^ ^ ^^
El fuego es el asterisco que aparece en el centro. En realidad, esto depende del orden de evaluación de map y este orden no está definido en Scheme (sí lo está en la función map-in-order), así que el resultado depende de la implementación.

Puede ser más vistoso un resultado más grande:

Autómata del incendio forestal. Los píxeles grises son claros, los píxeles verdes son árboles y los píxeles rojos son incendios.