Harold Abelson, Don Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas F. Knight, Jr., Radhika Nagpal, Erik Rauch, Gerald Jay Sussman, Ron Weiss
Laboratorio de Inteligencia Artificial del MIT

Computación Amorfa

Resumen

La computación amorfa es el desarrollo de los principios organizacionales por medio de lenguajes de programación para la obtención de un comportamiento coherente a partir de la cooperación de cientos de partes no confiables que están interconectadas de forma desconocida, irregular y que varían en el tiempo. El impulso de la computación amorfa parte de la exploración en el campo de la micro-fabricación y en la biología fundamental, cada uno de los cuales es la base del núcleo de la tecnología que hace posible la construcción y el crecimiento enorme de unidades de procesamiento de información casi idénticas a un bajo costo. Este artículo establece una agenda de investigación para entender el potencial de la computación amorfa y el estudio de algunos progresos iniciales, ambos en programación y fabricación. Describimos algunos enfoques de programación de sistemas amorfos, que están inspirados por metáforas de la biología y la física. También presentamos las ideas básicas de la computación celular, un enfoque para construir circuitos digitales lógicos dentro de células vivas mediante la representación de los niveles lógicos en la concentración de proteínas del ADN.

En las siguientes dos décadas, emergerán dos tecnologías – la micro-fabricación y la ingeniería celular – tomaremos esta posibilidad para armar cientos de sistemas que incorporan unidades de procesamiento de información a un bajo costo, siempre que 1) todas la unidades necesitan trabajar correctamente; y 2) no hay necesidad de fabricar disposiciones geométricamente precisas de unidad o interconexiones precisas entre ellas.

Los componentes micro-electrónicos son cada vez más baratos en su fabricación, podemos anticiparnos a una combinación de circuitos lógicos, micro sensores, transistores y dispositivos de comunicación integrados en un mismo integrado con el objetivo de producir partículas que podrían ser mezcladas con materiales tales como pintura, geles y concreto. Imagine recubrir puentes o construcciones con pintura inteligente que puede sentir y reportar sobre el tráfico, la fuerza de viento y monitorear la estructura de la construcción. Una pared cubierta por pintura inteligente podrá sentir las vibraciones, prevenir intentos de robo por intrusos o cancelar el ruido.

Aún más sorprendente, habido un progreso impresionante en la compresión individual de los mecanismos bioquímicos de las células, esto apunta a que seremos capaces de aprovechar estos mecanismos para la construcción de circuitos lógicos digitales. Imagine una disciplina llamada ingeniería celular que podría construir a la medida células biológicas para funcionar como sensores o agentes, se podría llegar a fabricar vehículos programables para enviar farmacéuticos a nivel celular, o crear fabricas químicas de ensamblaje de estructuras a nano escala. La habilidad de fabricar tales sistemas parece estar incluida en nuestra investigación, aunque todavía no está a nuestro alcance.

La micro-fabricación es solamente una parte de la historia. Los computadores digitales siempre han sido construidos para comportarse como herramientas precisas y confiables, y casi todas las técnicas de organización computacional dependen de esta precisión y confiabilidad. Entonces mientras tanto podemos imaginar una producción grande de elementos computacionales individuales – si son partículas micro-fabricadas o células inteligentes – tenemos algunas ideas para realizar una programación eficiente. La oportunidad de explotar estas nuevas tecnologías plantea un amplio reto conceptual, el cual llamamos el reto de la Computación Amorfa:

Como un ingeniero puede especificar, coherentemente el comportamiento en la cooperación de un número inmenso de partes que estas interconectadas de forma desconocida, irregular y que varían en el tiempo.

Este artículo establece una agenda de investigación para potencializar la computación amorfa y un estudio inicial del progreso actual, ambos en programación y fabricación.

Una de las tareas críticas es identificar apropiadamente los principios de organización y las metodologías de programación para controlar los sistemas amorfos. Discutimos algunas ideas preliminares en la sección 1, prestando mayor atención a los consejos de la biología. El crecimiento de la forma en organismos demuestra que las formas bien definidas y las estructuras funcionales se pueden desarrollar a través de la interacción de las células bajo el control de un programa genético, a pesar de que la disposición y número de células son variables. En consecuencia, la biología puede ser una rica fuente de metáforas para inspirar nuevas metodologías de programación para sistemas amorfos.

Como ilustración, se describe como los medio amorfos puede ser programados para generar patrones complejos, tales como un gráfico de interconexiones definidas arbitrariamente. El programa se organiza de acuerdo a la metáfora de la botánica donde “Growing Points” y “Tropisms” controlan la diferenciación de los agentes computacionales amorfos para formas diversos elementos del patrón. Otra metáfora en la programación bio-inspirada incluye marcadores de propagación a través de la difusión y control de la forma por medio de la movilidad celular. También exploramos técnicas inspiradas por la física, donde observamos que los procesos fundamentales en el mundo de la física son modelos conservadores que sugieren procesos conservadores por métodos de intercambio local.

Los avances en la computación amorfa pueden exigir nuevas maneras de abordar la tolerancia a fallos. Tradicionalmente, se busca obtener resultados correctos a pesar de las partes no confiables mediante la introducción de redundancia para detectar errores y sustituto de partes malas. Pero en el régimen amorfo, obtener la respuesta correcta puede ser una idea equivocada: parece difícil describir mecanismos tales como el desarrollo embrionario como la producción de un organismo apropiado mediante la corrección de las malas partes y comunicaciones rotas. La verdadera pregunta es cómo estructurar sistemas abstractos, entonces como obtener respuestas aceptables, con alta probabilidad, incluso en cara de la falta de fiabilidad.

Además de nuevas metodologías de programación, la explotación de la potencia de la computación amorfa requerirá nuevos sustratos físicos. Es fácil imaginar las partículas computacionales que combinan la comunicación y el procesamiento, y no parece haber ningún obstáculo fundamental para la construcción de estos.

Un enfoque más agresivo para la fabricación de sistemas amorfos se ve en la biología, no sólo como una metáfora, sino como la tecnología de implementación real de una nueva actividad de la computación celular, que es el tema de la sección 2 de este documento. Las células biológicas son fábricas químicas auto-reproductoras que son controlados por un programa escrito en el código genético. Como ingenieros, podemos tomar el control de este proceso para hacer nuevos organismos con determinadas propiedades deseadas. En principio es posible construir una familia de puertas lógicas, donde las señales están representadas por las concentraciones de proteínas de las uniones del ADN, y donde el amplificador no lineal se lleva a cabo por el direccionamiento “in vivo” del ADN en la síntesis de proteínas. Avanzar aquí requiere extensos experimentos y mediciones para caracterizar las propiedades estáticas y dinámicas de las puertas lógicas de proteínas. También se requiere el desarrollo de nuevos conjuntos de herramientas para apoyar el diseño, el análisis y la construcción de circuitos biológicos y este documento describimos algunos de estos.

Además de las posibles aplicaciones obvias de la computación celular a la medicina y para la detección química, las células programadas podrían permitirnos fabricar nuevos materiales y estructuras a escala molecular. El mundo biológico ya nos proporciona una variedad de mecanismos útiles y eficaces, como los motores flagelares. Si lograramos que las células coopereen para construir conjuntos organizados de dichos motores, con interfaces accesibles para poder controlarlas, podríamos decir que este avance tendria una considerencion significante en la ingenieria. Además, los polímeros conjugados biológicamente, como el caroteno, pueden conducir la electricidad, y pueden ser montados en componentes activos. Si nosotros, como ingenieros, podemos adquirir el dominio de los mecanismos de diferenciación biológica, la morfogénesis y la formación de patrones, podemos usar entidades biológicas como agentes de construcción para el esamblaje y mantenimiento de sistemas electrónicos ultramicroscópicos complejos. En la Sección 3 se especula sobre cómo podría llevarse a cabo esto.

Paradigma de la Programación en Sistemas Amorfos

Un medio de computación amorfo es un sistema irregularmente posicionado, es asíncrono y sus elementos computan e interaccionan localmente. Podemos modelar esto como una colección de “partículas computacionales” salpicados irregularmente sobre una superficie o dispersas a través del volumen de un contenedor. Las partículas son posiblemente defectuosa, sensibles al medio ambiente, y pueden efectuar acciones. En general, las partículas individuales pueden ser móviles, pero las exploraciones iniciales de programación que se describen aquí, no hacen frente a esta posibilidad.

Cada partícula tiene un potencial de cálculo moderado y una modesta cantidad de memoria. Las partículas no están sincronizadas, aunque suponemos que se calculan a velocidades similares, ya que todos se fabrican por el mismo proceso. Las partículas están programados de forma idéntica, aunque cada partícula tiene medios para almacenar el estado local y la facultad de generar números aleatorios. En general, las partículas no tienen ningún conocimiento a priori de sus posiciones u orientaciones.

Cada partícula se puede comunicar con algunos vecinos cercanos. En los sistemas amorfos de componentes micro-fabricados, las partículas pueden comunicarse a través de radio de corta distancia; células bio-ingenieriles podrían comunicarse por medios químicos. Para nuestros propósitos, vamos a suponer que hay algún tipo de comunicación de radio r, que es grande en comparación con el tamaño de las partículas y de los pequeños en comparación con el tamaño de todo el área o volumen, y que dos partículas se pueden comunicar si están dentro de la distancia r.

Suponemos que el número de partículas es muy grande. Por lo tanto, todo el medio amorfo puede ser considerado como un sistema masivo computacional paralelo, y las investigaciones anteriores en la computación paralela masiva, como la investigación en autómatas celulares, es una fuente de ideas para tratar con sistemas amorfos. Los sistemas amorfos presentan un mayor reto que los autómatas celulares, sin embargo, debido a que sus mecanismos deben ser independiente de la configuración detallada y la fiabilidad de las partículas. Por ejemplo, la pintura inteligente debe ser capaz de determinar las propiedades geométricas de la superficie que la recubren, sin el conocimiento inicial de las posiciones de las partículas en la pintura.

Otra fuente de ideas puede ser la investigación en sistemas auto-organizados, que ha expuesto cómo algunos comportamientos coherentes de sistemas a gran escala pueden “emerger” de interacciones puramente locales de las partículas individuales. La computación amorfa podría explotar fenómenos similares, pero no es nuestro objetivo de estudiar los principios de la auto-organización en sí. Como ingenieros, debemos aprender a construir sistemas de modo que terminen organizándose o comportándose de forma a priori, no sólo a medida que ocurre la evolución.

De la propagación de la onda a la formación de patrones

Para tener una idea de lo que sería programar un sistema amorfo, considere un simple proceso de propagación de la onda. Una partícula inicial “de anclaje”, elegido por una señal desde el medio ambiente o mediante la generación de un valor aleatorio, transmite un mensaje a cada uno de sus vecinos. Estos se propagan el mensaje a sus vecinos, y así sucesivamente, para crear una onda de difusión que se extiende por todo el sistema. El mensaje puede contener un número de saltos, que cada partícula puede almacenar y se incrementará antes de la retransmisión, ignorando los valores más altos posteriores para evitar que la onda se propague hacia atrás. El recuento de los saltos proporcionan estimaciones de distancia entre particulas: un punto alcanzado en n pasos será más o menos la distancia nr distancia. La calidad de esta estimación depende de la distribución de las partículas. Estas relaciones se han estudiado ampliamente en las investigaciones de redes de paquetes de radio. (Véase, por ejemplo, Kleinrock y Silvester[10])

Para las partículas sobre una superficie, se puede producir sistemas de coordenadas de dos dimensiones mediante la propagación de ondas a partir de dos anclas (partículas de referencia). El uso de tres anclajes establece un sistema de coordenada triangular, que puede proporcionar una mayor precisión, especialmente por la técnica de aumentado suavizado como se comenta por Coore [3] y Nagpal [14]. En un trabajo relacionado, Katzenelson [9] describe cómo establecer las coordenadas globales sobre una región mediante la propagación de coordenadas conocidas por partículas en la frontera.

La propagación de ondas con la cantidad de saltos, como las observaciones de Nagpal [14], es evocadora de los gradientes formados por difusión química que se cree que juega un papel en la formación de patrones biológicos. En consecuencia, podemos tratar de organizar los procesos amorfos imitando fenómenos gradientes observadas en la biología.

A modo de ejemplo, podemos utilizar las ondas de difusión para producir regiones de tamaño controlado, simplemente por tener los procesadores que transmiten el mensaje sólo si el número de saltos esta por debajo de un límite designado. Una vez que una región se genera de esta manera, podemos utilizarlo para controlar el crecimiento de otras regiones. Por ejemplo, dos partículas A y B podrían producir una ola de difusión, pero la onda de B podrían ser transmitida sólo por las partículas que no han visto la ola de A. Basándose en una metáfora biológica, podríamos interpretarlo como que A genera una ola que “inhibe el crecimiento” que ha comenzado a partir de B. En un programa un poco más elaborado, la onda B puede ser transmitida sólo por partículas vecinas cercanas a A (de la misma forma para A) . Nuestra metáfora biológica podría interpretar esto; explicando que la región de cultivo de B tiene un “tropismo” que se atrae hacia A.

Estos mecanismos de onda de difusión que corresponden a la computación amorfa son debido a que los fenómenos brutos de crecimiento, la inhibición, y el tropismo son insensibles a la disposición precisa de las partículas individuales, siempre y cuando la distribución es razonablemente densa. Además, si las partículas individuales no funcionan, o dejar de transmitir, el resultado no va a cambiar mucho, siempre y cuando no hayan suficientes partículas.

Sobre la base de este tipo de animación del desarrollo biológico, Coore [4] ha desarrollado un lenguaje de programación llamado el growing-point language, (GPL), que permite a los programadores detallar patrones complejos, tales como la especificacion de la interconexión de un circuito electrónico. Las especificaciones se compila en una máquina de estado uniforme para el computo de las partículas en un medio amorfo. Todas las partículas tienen la misma programación. Como resultado del programa, las partículas “se diferencian” por los componentes del patrón.

El lenguaje Coore representa procesos en términos de una metáfora botánica llamada “puntos de crecimiento” (growing-point). Un punto de crecimiento es una actividad de un grupo de partículas computacionales vecinas que pueden propagarse a una zona de superposición. Los puntos de crecimiento pueden dividirse, morir o fusionarse con otros puntos de crecimiento. Como punto de crecimiento pasa a través de su vecino, puede establecer de manera permanente una parte de sus estados en las partículas que visita. Podemos interpretar esto como el punto de crecimiento que establece un material en particular a su paso. El punto de crecimiento puede ser sensible a determinados mensajes difundidos, y en la propagación de sí mismo, se puede presentar un tropismo hacia una fuente, lejos de una fuente, o mover de una manera que intenta mantener la “concentración” de algún mensaje constante y difuso. Las partículas que representan materiales particulares pueden “segregar” mensajes difusibles apropiadas que atraen o repelen a los puntos de crecimiento específicos.

(define-growing-point (make-red-branch length)
(material red-stuff)
(size 5)
(tropism (and (away-from red-pheromone)
(and (keep-constant source-1-pheromone)
(keep-constant source-2-pheromone))))
(avoids green-pheromone)
(actions
(secrete 2 red-pheromone)
(when ((< length 1)
(terminate))
(default
(propagate (- length 1))))))

El programa define un proceso de punto de crecimiento llamado make -red- branch, que toma un parámetro llamado length. Este material  de punto de crecimiento llamado red – stuff “crece” en un tamaño de 5. Hace que cada partícula se mueve a través de cada bit estableciendo un estado que se identificará como una partícula  red-stuff, y también provoca que la partícula se propague en una onda media de 5 lúpulos que convierte de manera similar las partículas cercanas que van a ser de tipo red-stuff. el punto se mueve creciendo según un tropismo que dirige lejos de cualquier fuente de red-pheromone, de tal manera que la concentración de feromonas secretadas por source-1 y la source-2 se mantienen constantes , con el fin de evitar cualquier fuente de color del green-pheromone. Todas las partículas que son red-stuff ocultan red-pheromone; en consecuencia, el punto de crecimiento tenderá a alejarse del material ya establecido. El valor del parámetro de longitud determina la cantidad de pasos del punto de crecimiento que debe moverse. Si la longitud es de menos de 1 el punto de crecimiento termina. De lo contrario se propaga el crecimiento de la longitud al menos un paso.

Observe cómo este lenguaje alienta al programador a pensar en términos de entidades abstractas como los puntos de crecimiento y feromonas. El compilador GPL traduce estos programas de alto nivel en un conjunto idéntico de directivas para cada una de las partículas de cómputo individuales. Las directivas son compatibles con el sistema de ejecución de la GPL que se ejecuta en cada partícula. En efecto, la abstracción del punto de crecimiento proporciona una conceptualización acerca de la computación en paralelo.

Descargar Articulo