Sistemas complejos adaptativos Autómatas celulares Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES http://carlosreynoso.com.ar

2 Objetivos Clarificar la especie de los modelos descentralizados, microscópicos o down-to-top Profundizar en cuestiones de tratabilidad, emergencia y modelado Presentar instrumentos y describir estado de la cuestión Sugerir prácticas en torno del modelado urbano

3 Agenda Modelos microscópicos vs macroscópicos Autómatas celulares Herramientas disponibles Aplicaciones a la problemática urbana Estudios de casos Conclusiones y propuestas Ejercicios de práctica Modelos de segregación, tráfico, drenaje, ambulación peatonal y evacuación

4 Modelos descentralizados Imperativos en casos en que se desconocen las ecuaciones básicas, o se conocen pero son intratables Limitaciones de ODE y PDE Análogos a la forma distribuida de IA No hay control centralizado Alguna (leve) analogía con modelos rizomáticos de Deleuze-Guattari y con las tácticas de Michel de Certeau Formas específicas de orden: Auto-organización como emergente de la diferencia casi azarosa en el bajo nivel – Patrones de orden surgen del azar (BZ) Caos como emergente de principios deterministas (ecuación logística)

5 Sistemas complejos adaptativos Autómatas celulares Redes booleanas aleatorias Modelos basados en agentes autónomos Vida artificial Sociedades artificiales Cultura artificial Meta-heurísticas evolutivas

6 Engine oculto de SimCity, SimEarth, etc

7 Autómatas celulares ¿Es posible hacer una máquina que produzca otras máquinas tan complejas como ella misma? John von Neumann – Stanislav Ulam Basados en lógica viviente antes del descubrimiento del código genético Bateson puro: procesamiento de información, aprendizaje, evolución Modelo de tablero de damas (Checkerboard model) – Sakoda – Schelling Autómatas de teselación, estructuras celulares, arrays iterativos Inherentemente dinámicos y espaciales 

8 Vecindades Moore Von Neumann Margolus (Hexagonal, gases)

9 John Conway Juego de la vida Reglas: Inactiva, 3 activas: Nace Activa, 2 o 3 activas: Estasis Otros casos: Muere Survival/birth 23/3 Regla semi-totalística Depende del estado de las 8 vecinas y del estado propio Estables, periódicos, móviles, reproductores Deslizadores o planeadores (Gliders) Arma o pistola deslizadora (Glider gun) Life32: Switchen – Patrón más pequeño que se propaga indefinidamente Gun30 – Bill Gosper’s

10 Objetos fijos, periódicos y móviles Pistola de Gosper

11 Autómatas celulares – Stephen Wolfram Tipo I – Atractor de punto fijo Tipo II – Atractor periódico (108) Tipo III – Atractor caótico (18) Tipo IV – Atractor complejo Coincidencia con la jerarquía de Chomsky y con conductas de la ecuación logística

12 Wolfram - Tipos

13 Codificación binaria [Cuadro de diálogo de Visions Of Chaos]

14 Ejemplos Reglas 30 y 150 Necesidad de comprender exactamente el sentido de la numeración binaria y los bits [p. ej. Edgar Morin]

15 Visions of Chaos – AC de tráfico* * Los vehículos corren de izquierda a derecha. La simulación se puede escuchar con la música correspondiente . Ver regla 30, 60 etc

16 Desafíos epistemológicos (1/2) Auto-organización y complejidad emergente de reglas muy simples Vínculo entre micro y macro Vínculo entre agencia y estructura Complejidad sin aleatoriedad ni numerosidad No hay mayor complejidad si se agrega azar No hay formas más ricas de complejidad si se aumenta el número de elementos

17 Desafíos epistemológicos (2/2) Si un modelo tan simple es inmanejable conceptualmente, habrá que guardarse de pensar la sociedad en términos lineales de sentido común Explosión combinatoria en modelos pequeños: ¿es tratable nuestro modelo de escala mayor? Conceptualización de agencia individual y totalidad

Herramientas

19 Herramientas AC de propósito general y modelos espaciales Autómatas celulares *Mirek’s Cellebration *DUEM *Golly *Modelo de Von Thunen Life 32 Capow Cafun Java CASim

20 Mirek’s Cellebration Uno de los programas de mejor performance y mayor control, pero no programable en alto nivel Se pueden incorporar DLLs en C, C++ o equivalente Limitaciones inherentes al modelo básico Reglas deterministas Comportamiento monotónico Cambio de estado solamente No tiene concepto de patch Impropio para expresar condicionalidades complejas Calidad gráfica modesta (comparar con Visions of Chaos) No evoluciona desde hace algunos años Ventajas No hay que programar Muchísimas implementaciones por ser el programa de referencia

21 Reglas Mcell (1/2) Wolfram Class IV 1d Totalistic: Roots Auto-replicador Edward Fredkin: regla más simple (Vote / Fredkin) Orden a partir del caos Reacción de Beluzov-Zhabotinsky: Generations – BelZhav, RainZha Mescolanza (Hodgepodge) (Gerhard-Schuster): UserDLL-Hodge Simulated Annealing: Vote-Vote4-5 Majority Rules: LGTG, Majority (Sakoda) Conway’s Life: Life

22 Reglas Mcell (2/2) Difusión limitada por agregación (Random walk): UserDLL-DLA Langton, reproducción de DNA UserDLL-DNA Reglas Greenberg-Hastings CA excitables – Cyclic CA 313 – CCA - Cyclic spirals – GH Macaroni GH (nucleación de espirales simétricos)

23

24 Golly Herramienta más profesional, viva y reciente Código abierto: http://golly.sourceforge.net Totalmente programable (scripting en Perl y Python) Varias capas de acción simultáneas Documentación exhaustiva

25 Golly http://golly.sourceforge.net/

26 DUEM (1/2) Dynamic Urban Evolutionary Model Elaborado por equipo de Batty en UCL http://www.casa.ucl.ac.uk/software/duem.asp Se puede bajar de la página o instalar del DVD de software Documentos referidos a su uso: Batty - Cities as complex systems Batty-Xie-Sun – Modelling urban dynamics through GIS-based evolutionary models

27 DUEM (2/2)

28 Modelo de Von Thunen No guarda relación con ACs pero los complementa Esquemático pero adaptable Para comprender la problemática, más que para modelado real

29 SpaCelle http://www.spatial-modelling.info/Cellular-Automata-SPACELLE

30 The Conway of Life 3D

31 a) Sugerencia de práctica Consultar bibliografía relevante Batty – Torrens – O’Sullivan – Bäck – Di Gregorio Estudiar el ambiente de programación Elaborar un modelo de dinámica urbana simple en Golly, SpaCelle o Mirek’s – P. ej. DLA

32 b) Ejercicios – Quo Vadis http://www.quovadis-simulation.de/src/about.php

33 Quo Vadis – Diseño de escenario

34 Campo estático del piso* *Describe la distancia de una celda a una salida

35 Campo estático y vecindades

36 Campo dinámico del piso

37 Categorías adicionales (1/2) Velocidad única o múltiples velocidades (de 1 a 5) Delta: diferencia entre el tiempo del modelo y el tiempo real Tiempo máximo de reacción: mide el tiempo que necesita un peatón para darse cuenta que existe un proceso de evacuación Objetivos [targets]: lugares por los que se querrá pasar antes de ir a una salida Se puede configurar si los miembros de un grupo escogerán una salida determinada o se dirigirán a la que esté más cerca Copper field – Hacia qué cuadrante elegirán moverse los miembros de un grupo [0, 1, 2, 3]

38 Categorías adicionales (2/2) La influencia del campo estático y dinámico se configura con ks y kd. También se puede definir la difusión y decadencia del piso dinámico. Se puede configurar cada cuantos cuadros se refresca el cuadro de control. En caso de corredores se puede evaluar la formación de carriles [lanes]. El proceso de evacuación se puede guardar como un video, pasar más lento, volver para atrás, etc. Como parte del video, se puede añadir un diálogo de datos estadísticos.

39 Análisis…

40 Modelos de escape

41 Ejercicio con Quo Vadis Diseñar modelo de evacuación de la sala de conferencias de este curso, incluyendo los pisos inmediatos Computar y analizar la dinámica correspondiente

42 Ejercicios – Traffic Cellular Automata (Sven Maerivoet) http://smtca.dyns.cx/ - Requiere JRE 1.3.1

43 Modelos de tráfico implementados SMTCA

44 Modelo de tráfico – Regla 184 AC unidimensional Interpretación: 125 pasos con densidades iniciales de 25%, 50% y 75% La densidad de vehículos corresponde al color

45 Otros modelos de tráfico Ver http://carlosreynoso.com.ar/automatas-celulares Universidad de Delaware

46 Simulación de tráfico http://www.cie.unam.mx/~arp/simulation1.html

47 Simulación de tráfico http://www.thp.uni-koeln.de/~as/Mypage/simulation.html

48 Simulación de tráfico Simulación de tráfico http://sjsu.rudyrucker.com/~han.jiang/applet/

Aplicaciones

50 Aplicaciones: Problemas urbanos de localización diferencial y relocalización Sakoda – Valencias de segregación y sospecha

51 Aplicaciones de sociología urbana Thomas Schelling - Segregación Ejemplo con Moduleco

52 Reelaboración del modelo de Schelling por Michael Batty (UCL)* *Cities as complex systems

53 Aplicaciones en estudios sociales con dimensión espacial Rainer Hegselmann Modelos complejos, grillas irregulares Examen de las implicancias epistemológicas para las ciencias sociales

54 Rainer Hegselmann - Correspondencias

55 Estudios de casos con SLEUTH SLEUTH = Slope, Land use, Exclusion, Urban extent, Transportation, Hillshade Antes llamado Clarke Cellular Automata Urban Growth Model Aplicación de referencia en proyección urbana Desarrollado por Keith Clarke en la UC en Santa Barbara Las iniciales del nombre describen los datos de entrada Las reglas se basan en 5 coeficientes

56 Slope – Término de GIS y análisis geo-espacial (véase DEM) Se pueden generar de bases de datos topográficas

57 Excluded Montañas, aguas, etc

58 Transportation Incluye análisis de conectividad (sintaxis espacial)

59 Hillshade Usado como fondo para especificar la extensión espacial

60 Sitio de referencia http://www.ncgia.ucsb.edu/projects/gig/

61 Proyecciones de uso de la tierra de la NASA http://earthobservatory.nasa.gov/Newsroom/view.php?id=24480

62 Proyección de crecimiento (SLEUTH) Eficiencia aproximada superior al 80%

63 Predicciones Helsinki 2050* ’Controlled’ Growth ’Free’ Growth railroads + stations main roads + railroads accessibility roads as lines *Ver Urban Generator

64 Proyección de crecimiento e impacto ecológico http://www.insipub.com/rjss/2007/72-82.pdf

65 Proyección de crecimiento (SLEUTH)

66 Metronamica (Alternativa a DUEM, pero > € 15.000)

67 Ejercicio con Metronamica Archivo de escenario en Documentos>Geonamica>Metronamica…

68 Ejercicios y documentación incluidos en Demo

69 Evacuación – Situaciones de pánico Surgimiento de atascos desproporcionados, senderos de contraflujo, cambios oscilatorios en los contraflujos en los cuellos de botella, brotes de conducta de rebaño, dependencia no monotónica del tiempo de evacuación respecto de parámetros inimaginables (el campo dinámico del piso, la paradoja de Braess), efectos de fricción, efectos de más-rápido-es-más-lento en situaciones de pánico, pánico fantasma, freezing-by-heating, formación de “dedos” viscosos, surgimiento de flujos más ordenados mediante la ampliación de las oscilaciones. MicroPedSim, SimWalk, SUMO http://www.thp.uni-koeln.de/~as/Mypage/Pedestrians/twodoors.html

70 Proyección de diseño 3D Diseñador arquitectónico 3D de Kicinger - NLA

71 Modelado arquitectónico 3D con Wolfram Mathematica® Player

72 Emulando uso de la tierra con Wolfram Mathematica® Player

73 Emulando regla de tráfico 184 con Wolfram Mathematica® Player

74 Componiendo música con CA en Wolfram Mathematica® Player

75 Elaboraciones mixtas y complejas Geographic Automata Systems (GAS)+OBEUS Object-Based Environment for Urban Simulation Elaborado parcialmente en disertación y discontinuado Modelos espaciales más realistas y complejos Triángulos de Voronoi) Ejercicios con Wingeom > Other > Background > Open bitmap Ver referencias en obras más recientes de Torrens y Benenson

76 Ron Eglash (African fractals) Owari, mancala Grupo en marcha - Vida Mancala

77 Wolfram – Patrones culturales Columnas de Uruk, catedral de Anagni Regla 126 (Triángulo de Sierpiński)

78 Música – Automatous Monk http://www.automatous-monk.com/

Problemas

80 Problemas de modelos complejos (1/2) No es fácil imaginar las reglas Hoy en día se emplean metaheurísticas evolucionarias para inducir las reglas convenientes No hay certidumbre en relevancia de las variables consideradas Demasiadas variables, demasiados grados de libertad  combinatoria de magnitud ultra-astronómica 5 x 5 x 2 grados de libertad = 33 millones de combinaciones Pequeñas diferencias en valores pueden conducir a comportamientos disímiles Ejemplo: clases de Wolfram

81 Problemas de modelos complejos (2/2) Los escenarios de equilibrio no son sensibles a las condiciones iniciales Pero si el sistema es complejo, tiene extrema sensitividad a condiciones iniciales La trayectoria del comportamiento difiere aunque las condiciones iniciales sean casi idénticas No hay principios algorítmicos que permitan predecir el comportamiento de un sistema particular Alto índice de defección o falta de disponibilidad en el desarrollo de estos sistemas RuiCells para inundaciones y erupciones volcánicas, CA de Kicinger para modelado arquitectónico

Conclusiones

83 Conclusiones (1/4) Insuficiencia de modelos con “juego libre de variables” Estadísticas multivariadas macroscópicas Ecuaciones diferenciales no lineales Necesidad de coordinar semántica del modelo con datos arqueológicos, sociales o urbanos específicos y de mezclar formalismos e intercambiar formatos GIS, raster bitmaps, vectores, CAD Probablemente los mejores modelos para comparación de datos multivariados Cómo se mide una realidad contra una proyección

84 Conclusiones (2/4) Necesidad de comprender mejor la dinámica de los sistemas complejos No deben usarse para “explicar” casos concretos, sino para describir clases genéricas de comportamiento (equilibrio, oscilación, caos, complejidad, modelos de crecimiento) El comportamiento es emergente de interacciones locales. No resulta de relaciones lineales entre “causas” y “efectos” (aunque el modelo es determinista)

85 Conclusiones (2/3) Importancia o inevitabilidad del modelado Peligros latentes Modelos demasiado realistas y explosión combinatoria Principio KISS (Keep it simple, stupid) Interpretación tendiente al individualismo metodológico (incluso en textos como el de Resnik) No hay un modelo universal Requerimiento de programación para problemas puntuales O pagar el costo de programas orientados al problema

86 Conclusiones (3/3) Necesidad de tratar problemas a niveles más elementales que lo acostumbrado Aún así, no siempre los problemas son tratables Eficiencia en modelos predictivos de impacto ecológico y sustentabilidad Herramienta fundamental de toma de decisiones en cuestiones espaciales Sugerencia: Elegir un ambiente adecuado y profundizar en él SLEUTH, SpaCelle, Metronamica…

87 Recursos Wolfram – A new kind of science Von Neumann – Artículos fundacionales de los autómatas celulares Hegselmann – Artículos sobre modelos celulares en ciencias sociales Cientos de documentos sobre ACs en archivos de Diseño Urbano Meister - Simulation of crowd dynamics… (Tesis) http://carlosreynoso.com.ar 

88 Recursos Georg Meister, Simulation of crowd dynamics with special focus on building evacuations. Tesis de maestría. Hamburgo, Universidad de Ciencias Aplicadas. Aplicación de referencia: Quo Vadis

89 University College, London http://www.casa.ucl.ac.uk/software/duem.asp

90 Página de Schadschneider & Kirchner - Pedestrian http://www.thp.uni-koeln.de/~as/Mypage/Pedestrians/pedest_2.html

91 Recursos

92 Recursos

93 Recursos

94 Recursos

95 Recursos Modelos de drenaje y flujo (Coppola & al), evaluación de riego ambiental (Douvinet & al), incluyendo lava y flujos piroclásticos Atención: lo líquido no es un estado más de la materia como lo sólido o lo gaseoso, sino un objeto de mucha mayor complejidad

96 http://carlosreynoso.com.ar/automatas-celulares

¿Preguntas? http://carlosreynoso.com.ar