reynoso-automatas-celulares

+5

No comments posted yet

Comments

Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

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)

Slide 5

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

Slide 6

6 Engine oculto de SimCity, SimEarth, etc

Slide 7

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 

Slide 8

8 Vecindades Moore Von Neumann Margolus (Hexagonal, gases)

Slide 9

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

Slide 10

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

Slide 11

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

Slide 12

12 Wolfram - Tipos

Slide 13

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

Slide 14

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

Slide 15

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

Slide 16

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

Slide 17

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

Slide 18

Herramientas

Slide 19

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

Slide 20

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

Slide 21

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

Slide 22

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)

Slide 23

23

Slide 24

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

Slide 25

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

Slide 26

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

Slide 27

27 DUEM (2/2)

Slide 28

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

Slide 29

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

Slide 30

30 The Conway of Life 3D

Slide 31

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

Slide 32

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

Slide 33

33 Quo Vadis – Diseño de escenario

Slide 34

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

Slide 35

35 Campo estático y vecindades

Slide 36

36 Campo dinámico del piso

Slide 37

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]

Slide 38

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.

Slide 39

39 Análisis…

Slide 40

40 Modelos de escape

Slide 41

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

Slide 42

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

Slide 43

43 Modelos de tráfico implementados SMTCA

Slide 44

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

Slide 45

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

Slide 46

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

Slide 47

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

Slide 48

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

Slide 49

Aplicaciones

Slide 50

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

Slide 51

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

Slide 52

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

Slide 53

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

Slide 54

54 Rainer Hegselmann - Correspondencias

Slide 55

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

Slide 56

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

Slide 57

57 Excluded Montañas, aguas, etc

Slide 58

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

Slide 59

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

Slide 60

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

Slide 61

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

Slide 62

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

Slide 63

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

Slide 64

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

Slide 65

65 Proyección de crecimiento (SLEUTH)

Slide 66

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

Slide 67

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

Slide 68

68 Ejercicios y documentación incluidos en Demo

Slide 69

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

Slide 70

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

Slide 71

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

Slide 72

72 Emulando uso de la tierra con Wolfram Mathematica® Player

Slide 73

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

Slide 74

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

Slide 75

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

Slide 76

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

Slide 77

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

Slide 78

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

Slide 79

Problemas

Slide 80

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

Slide 81

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

Slide 82

Conclusiones

Slide 83

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

Slide 84

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)

Slide 85

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

Slide 86

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…

Slide 87

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 

Slide 88

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

Slide 89

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

Slide 90

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

Slide 91

91 Recursos

Slide 92

92 Recursos

Slide 93

93 Recursos

Slide 94

94 Recursos

Slide 95

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

Slide 96

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

Slide 97

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

Summary: Automatas celulares aplicados a la ciudad y la cultura

Tags: automatas celulares

URL: