Sincronización de sistemas complejos y control de caos Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES http://carlosreynoso.com.ar

Objetivos Clarificar la epistemología Problema Problema bien planteado (Hadamard) Problema inverso Cómo se construye un sistema (complejo) Orientación constructiva: W. Ross Ashby – Introducción a la cibernética Cómo se identifica/reconstruye un sistema a partir de datos (p. ej. series temporales) Distribuciones estadísticas – Análisis de recurrencia Dar orientación heurística ante la especificidad sistémica: Sistemas cerrados Sistemas abiertos Sistemas distribuidos / Agentes múltiples Subsunción de sistemas en metasistemas Control de sistemas complejos (caóticos) Definir orientaciones actuales en sincronización y control de sistemas complejos

Agenda Demarcación Sistemas complejos Dinámica no lineal Dinámica colectiva Emergencia Sincronización de sistemas caóticos y aleatorios Control de sistemas caóticos Coordinación de sistemas multi-agentes (swarm intelligence) [si hay tiempo] Sistemas complejos adaptativos como sistemas en interacción [si el tiempo sobra] Modelos de pizarra como sistemas en interacción* * http://carlosreynoso.com.ar Arquitectura de software – Estilos arquitectónicos

Taxonomía de modelos

Jerarquía de la complejidad Chomsky Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares. Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto. Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde  no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto. Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que  puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

Jerarquía de la complejidad Chomsky Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares. Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto. Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde  no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto. Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que  puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

Jerarquía de la complejidad Chomsky Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares. Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto. Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde  no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto. Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que  puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

Jerarquía de la complejidad Chomsky Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares. Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto. Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde  no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto. Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que  puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

Demarcación Complejidad No hay definición canónica Clases de complejidad 4 convencionales – 488 clases de complejidad computacional Modelo dominante: dinámica no lineal* Caos determinista Sensitividad extrema a las condiciones iniciales Atractores extraños Distribuciones de ley de potencia Clases de universalidad No linealidad – Definiciones impropias Exclusión de complejidad desorganizada Exclusión de numerosidad Complexity Zoo

Bifurcación de Feigenbaum

Sincronización

Christiaan Huygens (1665)

Sincronización - Historia . . . It is quite worth noting that when we suspended two clocks so constructed from two hooks imbedded in the same wooden beam, the motions of each pendulum in opposite swings were so much in agreement that they never receded the least bit from each other and the sound of each was always heard simultaneously. Further, if this agreement was disturbed by some interference, it reestablished itself in a short time. For a long time I was amazed at this unexpected result, but after a careful examination finally found that the cause of this is due to the motion of the beam, even though this is hardly perceptible. The cause is that the oscillations of the pendula, in proportion to their weight, communicate some motion to the clocks.

Lord Raleigh (1842-1919)* When two organ-pipes of the same pitch stand side by side, complications ensue which not unfrequently give trouble in practice. In extreme cases the pipes may almost reduce one another to silence. Even when the mutual influence is more moderate, it may still go so far as to cause the pipes to speak in absolute unison, in spite of inevitable small differences. Descubridor del argón, premio Nóbel 1905 – Explicó el azul del cielo y analizó los solitones

Appleton & Van der Pool Considering the simplest case, they showed that the frequency of a generator can be entrained, or synchronized, by a weak external signal of a slightly different frequency. These studies were of great practical importance because triode generators became the basic elements of radio communication systems. The synchronization phenomenon was used to stabilize the frequency of a powerful generator with the help of one which was weak but very precise

Sincronización Fenómeno universal que se manifiesta en el entrañamiento [entrainment] de ritmos de sistemas auto-sostenidos en interacción Modelos básicos: Autoosciladores* Corazón, nota sostenida, una botella de agua dada vuelta, etc Oscilan por sí mismos, no por impulso exterior Difícil de cambiar el ritmo oscilatorio Debe haber fuente de poder (son sistemas disipativos) [condición relajada últimamente] Son no lineales Después de revisión de Andronov pueden ser periódicos, aperiódicos o irregulares Las transiciones son descriptibles mediante teoría de la bifurcación p. ej. * Clase de modelos no lineales bien conocidos en física y dinámica no lineal

Sincronización Refinamiento de las definiciones: Ajuste de ritmos de objetos que oscilan debido a interacciones débiles Entrañamiento o locking Sincronización in-phase o anti-phase (en la misma dirección o en la contraria) Sincronización no es: Resonancia Acoplamiento fuerte (unifica los sistemas) Mera variación sincrónica de dos variables (modelo predador-presa) Sincronización es un proceso dinámico complejo – No es un estado

Sincronización de seres vivientes Documentado por siglos El movimiento de las plantas continúa incluso con aislamiento de la fuente de luz Relojes internos: ritmos circadianos (circa dies) S. XVIII – sincronización de las luciérnagas en Siam – Grillos en todas partes Algunas explicaciones son más notables que el fenómeno reportado Sincronización de las ondas cerebrales (Wiener)

Sincronización en general Strogatz: ¿Puede la sincronización surgir de miles de metrónomos sin inteligencia? La respuesta es que sí. Funciona siempre, bajo ciertas condiciones. La coherencia de un rayo de láser viene de trillones de átomos pulsando al unísono, todos emitiendo fotones de la misma fase y frecuencia Fenómenos en diversos objetos sugieren que la conexión entre ellos es matemática. Todos los ejemplos son variaciones del mismo tema: auto-organización, el surgimiento espontáneo de orden a partir del caos Alguna conexión con criticalidad auto-organizada

Art Winfree Descubrió que el fenómeno es altamente no lineal (1960s) Modelo de los corredores Los que corren más parecido no se sincronizan mejor Winfree descubrió que la sincronización mutua es análoga a la transición de fase Vinculó dinámica no lineal con mecánica estadística

Sincronización - Referencias

Sincronización - Referencias

Sincronización - Referencias

Sincronización - Referencias Otros textos de Strogatz (2003), Balanov & otros (2009), etc

Control de caos

Escenario ¿Cómo se entienden los sistemas complejos entre sí? Sincronización Sistemas complejos adaptativos Autómatas celulares Redes booleanas aleatorias Modelos basados en agentes Modelos mixtos de inteligencia distribuida Eventualmente redes de agentes, sistemas o lo que fuere Estilos de pizarra en arquitectura de software ¿Cómo se entiende uno con diversos sistemas complejos? Si no son caóticos, puede que sean intratables Si son caóticos (o si se los hace caóticos), con control de caos...

Control de sistemas caóticos Sensitividad como indeseable  Sensitividad como conveniente en situaciones prácticas Una pequeña inversión puede generar un resultado inmenso La aplicación juiciosa de una intervención puede dirigir la trayectoria hacia un punto deseado del atractor y producir una serie de sistemas dinámicos deseados Se ha demostrado experimentalmente en muchas situaciones. Su aplicación generalizada es todavía cuestión en desarrollo Principio ergódico – En sistemas no perturbados puede insumir demasiado tiempo el pasaje por una región dada del atractor

Antecedentes Años 90 Ott, Grobi y Yorke – Modelo OGY Eventualmente puede tomar mucho tiempo Otros modelos introdujeron mejoras en órdenes de magnitud de 10

Control de sistemas caóticos Ditto & Pecora (1993) Textos de Kapitaniak (1996)

Control de sistemas caóticos Fradkov (1996) Boccaletti, Grebogi y otros (2000)

Metaheurísticas de inteligencia distribuida

Poblaciones de sistemas Problemas de tratabilidad Algoritmo genético Programación evolutiva Swarm intelligence Ant colony optimization Modelos de agentes autónomos

Metaheuríticas - Referencias

Metaheurísticas - Referencias

Estilo de pizarra Materiales en documentos de estilos en arquitectura de software (http://carlosreynoso.com.ar)

Recursos 620 libros de dinámica no lineal, complejidad, geometría fractal & redes complejas 2000 documentos esenciales 180 programas freeware o similar

Referencias (1/x) Reynoso, Carlos – Complejidad y caos: Una exploración antropológica. Buenos Aires, SB Ediciones, 2006 Grupo Antropocaos – Exploraciones en antropología de la complejidad. Idem. Eglash, Ron – African fractals. New Brunswick, Rutgers University Press, 1999. Eve, Raymond, Sara Horsfall & Mary Lee. Chaos, complexity and sociology. Myth, models, and theories. Thousand Oaks, Sage, 1997.

Referencias Jelle Kok – Cooperation and learning in Cooperative multiagent systems – Tesis, Universidad de Amsterdam, 2006 Field-based coordination for pervasive multiagent systems – Springer, 2005

Materiales específicos http://carlosreynoso.com.ar Página de Curso de contexto Clave: turing

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