Entrevista número 27


"El poder de las hormigas artificiales reside en que trabajan juntas"

©Guy Theraulaz

Marco Dorigo nació en Milán, Italia, en 1961. Se doctoró en ingeniería electrónica de sistemas e información en 1992 en el Politécnico de su ciudad natal y recibió el título de "Agregado de la Enseñanza Superior en Inteligencia Artificial" por la Universidad Libre de Bruselas en 1995. Entre 1992 y 1993 fue investigador del Instituto Internacional de Ciencias de la Computación de Berkeley, California. Después cumplió las mismas funciones en el convenio de colaboración entre la OTAN y el CNR. Empezó a trabajar en el laboratorio del IRIDIA de la Universidad Libre de Bruselas en 1996, donde actualmente se desempeña como investigador del Fondo Nacional para Investigación Científica de Bélgica (FNRS). Su principal línea de investigación son los "algoritmos sobre hormigas", una innovadora área de investigación que inició en su trabajo de doctorado. También está interesado en la computación evolutiva, la robótica autónoma y la potenciación del aprendizaje. Dorigo ha publicado varios libros y más de 50 artículos científicos sobre estos temas. Entre los primeros destacan: "Swarm Intelligence: From Natural to Artificial Systems", escrito junto con Eric Bonabeau y Guy Theraulaz (New York: Oxford University Press, 1999); "Robot shaping: An Experiment un Behavior Engineering", junto con M. Colombetti (MIT Press/ Bradford Books; y "New Ideas in Optimization", junto con F. Glover (McGraw-Hill, Londres, 1999). Recientemente, Marco Dorigo publicó un artículo en la revista Nature sobre las hormigas artificiales. En 1996 se le concedió el Premio Italia para Inteligencia Artificial.

P.-- ¿Su doctorado en Milán tenía algo que ver con inteligencia artificial?

R.-- Sí, durante mi doctorado (1989-1991) trabajaba sobre computación evolutiva. Era una línea para el aprendizaje y la potenciación de la autonomía en robots pequeños, por una parte, y también para investigar los insectos sociales y los algoritmos sobre las hormigas, por la otra. En 1998 escribí un libro sobre el tema del aprendizaje de los robots, que publicó la editorial del MIT. Después, mi interés en los robots disminuyó y me concentré cada vez más en la "inteligencia del enjambre" y los algoritmos de las hormigas. En 1999 publiqué un libro sobre este tema junto con otros dos co-autores con quienes nunca tuve un encuentro personal. Todo lo hicimos a través de Internet. Ahora tenemos un proyecto financiado por la Comunidad Europea, o sea que en algún momento creo que los conoceré personalmente.

P.-- Bien, explíqueme que hace con las hormigas.

R.-- Lo que intento hacer es usar la conducta social de los insectos para diseñar nuevos algoritmos que se puedan utilizar para resolver algunos problemas prácticos. No soy un biólogo, leo artículos y libros escritos por biólogos y discuto con ellos, pero mi formación es la de un ingeniero con una fuerte preferencia por la Inteligencia Artificial. Y en mi universidad trabaja un eminente biólogo, Jean Louis Deneubourg. Los biólogos observan la conducta de las hormigas, ácaros, abejas y avispas y tratan de construir modelos simples que expliquen su comportamiento. Al observar estos animales uno a uno se descubre que cada individuo es muy simple. Pero juntos hacen cosas increíbles. Se trata de entender cómo ocurre esto. Los biólogos cada vez se apoyan más en los modelos matemáticos y las simulaciones por ordenador.

P.-- ¿Y ustedes, los ingenieros?

R.-- Para ver si los resultados coinciden con los datos reales, nosotros tomamos algunos de estos modelos y diseñamos algoritmos compuestos de numerosos agentes que imitan de alguna manera la conducta de los insectos reales. Pero con algunas características especiales. Por ejemplo. Mi primer trabajo trataba sobre un punto de intersección entre la biología y la ingeniería: la conducta de búsqueda de alimento de las hormigas. Lo que los biólogos han observado en la naturaleza es que las hormigas explotan primero las fuentes de alimentación que están más cerca del hormiguero. Y después se van a buscar las que están más lejos. Y si creas condiciones experimentales muy especiales, puedes mostrar esto muy rápidamente.

P.-- ¿Por ejemplo?

R.-- Si se ponen dos caminos hacia el alimento, las hormigas, que no tienen una visión global del territorio, siempre escogen el camino más corto. Lo que yo hice hace 10 años es pensar que sería posible utilizar esta estrategia para resolver problemas organizacionales. ¿Sabe usted lo que es un problema de optimización combinatoria? Es un problema en el que hay muchos componentes, muchos objetos y hay que ponerlos en secuencia para que el resultado final sea una función de la secuencia. Un ejemplo muy conocido de esto es el problema del viajante comercial. Si tiene que visitar 10 ciudades ¿cuál es el camino más corto para visitarlas todas en el menor tiempo posible? Ahora bien, si se toman 10 ciudades el problema no parece muy difícil. Si se toman 100, es muy complejo. Pero, en ambos casos, si se quiere una solución rápida, es fácil, pero si se quiere la mejor, es cuando las cosas se ponen complicadas.

P.-- La solución está en las hormigas.

R.-- Sí. Lo que hacemos es crear hormigas artificiales que son agentes de software, que se mueven de una ciudad a otra y todo se simula en un ordenador. Se mueven según parámetros probabilísticos y cuando encuentran la solución añaden un tipo de feromona, lógicamente una feromona artificial. En este caso, se trata de un número, o una señal claramente identificable para el resto de los agentes. El aspecto fascinante sobre cómo las hormigas verdaderas encuentran su camino es el trazado de los atajos. Una hormiga busca el camino y si tiene que doblar, a la izquierda o a la derecha, tiende a escoger el lado que tiene una mayor cantidad de feromonas. Esto lo hacemos con programación. Las hormigas artificiales escogen el camino más corto detectando las feromonas que sienten en las conexiones entre ciudades y cuando llegan al final depositan feromonas en las conexiones que han utilizado. Contra más corta sea la solución, más feromonas depositan. Mediante estos mecanismos y otras ayudas, obtenemos resultados muy buenos. En el campo de la inteligencia artificial se ha estudiado este problema durante 30 años y es muy difícil mejorar sus resultados. Nosotros hemos aplicado estas ideas para resolver también otro tipo de problemas.

P.-- ¿Cuáles?

R.-- Hay muchos problemas de comunicación que se pueden abordar mediante estas hormigas artificiales. Por ejemplo, la secuenciación de operaciones en la línea de producción o la asignación de gente a ciertos trabajos.

P.-- ¿Cómo se hace esto?

R.-- Tendría que meterme en honduras matemáticas. La forma de verlo es mediante un sendero dibujado sobre un planigrama. A veces es muy fácil explicarlo, como cuando se habla sobre ciudades interconectadas, otras no, como cuando tratas de resolver un problema de "catering". Esto último requiere un mayor conocimiento matemático.

P.-- ¿Hay mucha gente trabajando en este campo?

R.-- Esta parte de la investigación se denomina "la optimización del hormiguero". Dirijo un taller sobre esto en Bruselas y nos reunimos cada dos años. Este año celebramos el segundo taller y asistirán unas 60 personas, aunque creo que en total somos un centenar de investigadores en el mundo interesados en estos problemas.

P.-- ¿Qué aplicaciones pueden tener las hormigas artificiales?

R.-- Una de las aplicaciones de la estrategia del camino más corto de las hormigas que buscan alimentos es para establecer las rutas en Internet. La idea es muy similar a las que he explicado antes. Por ejemplo, podemos trazar un gráfico de Internet sobre un planigrama donde las conexiones entre los nodos sean sus aristas. Los nodos son los ordenadores y los encaminadores ("routers") en ese gráfico. Hay conexiones entre los nodos y el problema es como encaminar, dirigir, los mensajes entre los nodos. Si esto se toma como un problema estático es muy fácil resolverlo. Hay algoritmos que encuentran rápidamente el camino más corto entre dos nodos cualquiera. Pero en cuento metemos un problema dinámico en el baile, en el que la carga de trabajo u otras condiciones cambian rápidamente, las cosas se complican. Y esto es muy importante porque el costo de la conexión a Internet tiene que ver con el volumen de tráfico. Si hay mucho tráfico, el tiempo para ir de un nodo al otro es mas largo.

P.-- ¿Y no se pueden elaborar modelos algorítmicos de cómo esto cambia en tiempo real?

R.-- No. Se conocen algunos factores muy generales y no mucho más. Algunos investigadores pueden aplicar algún tipo de estructura relacionada con teorías del caos. Lo cual sugiere cuán impredecible es esto. Si quieres utilizar toda la capacidad de Internet necesitas algoritmos que pueden seguir el tráfico en tiempo real y adaptar la red en consecuencia.

P.-- ¿Qué significa adaptarla?

R.-- Deberías ser capaz de cambiar en cada nodo de la Red las instrucciones que se dan a cada paquete de datos que entra según su destino final, que debería ser el siguiente nodo. Esto habría que hacerlo en tiempo real. Hay mucha gente que está tratando de resolver esto. Nosotros lo estamos haciendo con las hormigas artificiales. Las enviamos a la Red y desde cada nodo se envían a los otros nodos a intervalos regulares todo el tiempo. Y así construyen una solución: encuentran el camino hacia su destino, miden cuanto toma llegar, después regresan al ordenador y actualizan las tablas de los "routers", los puntos de decisión. Si la solución que han encontrado es buena, si han encontrado un camino que es razonablemente corto, entonces incrementan la probabilidad de que en el futuro ese camino se utilice otra vez.

P.-- Y, por la misma razón, aumentará también el riesgo de que el nuevo camino experimente un "embotellamiento" en el futuro.

R.-- Exactamente. Aumenta la probabilidad de que se use más. Obviamente, para nosotros este es un problema dinámico porque cuando hay más rutas "buenas" mayor es la susceptibilidad de que se congestionen.

P.-- ¿Cómo se adapta la Red a esta política de "rutas buenas"?

R.-- Estas hormigas artificiales tienen que cambiar las tablas de los "routers". Cada nodo tiene su tabla. Cuando un paquete de información entra en un nodo, éste comprueba su tabla para saber a qué nodo debe enviarlo según su destino final. En cierto sentido, el paquete que entra en el nodo dice: "Mi destino es el nodo k, ¿adónde debo ir ahora?" y el nodo responde tras consultar su tabla: "Vete al nodo j". Estas tablas son deterministas: un paquete de datos entra y otro paquete de datos sale para un destino fijado. Nosotros usamos tablas probabilísticas: una hormiga entra en el nodo y las posibilidades de que salga hacia un lugar u otro son, por ejemplo, del 10, 20 o 70%. Los paquetes siempre escogen la ruta del 70% o la de mayor probabilidad de éxito. Las hormigas no, ¿por qué? Porque las hormigas que usan las tablas de los "routers" de una manera probabilística cambian las tablas un poco cada vez que las usan. Por tanto, las hormigas artificiales van desde el nodo A al nodo B, miden cuánto tiempo ha tomado, regresan y actualizan todas las tablas de los "routers" que han visitado. Si el camino es bueno, aumenta la probabilidad de usarlo. Y viceversa.

P.-- ¿Y esto lo hacen en todo Internet?

R.-- Bueno, lo único que hemos hecho hasta ahora es una simulación. Lo probamos en el esqueleto de la red troncal japonesa, donde están los "routers" y 57 nodos y en el National Science Foundation (NSF, EEUU) donde hay 14 nodos. O sea, el experimento lo hemos hecho sólo con "routers". Las hormigas están en la Red todo el tiempo, pero son como pequeñas bolsas de información y no aumentan el tráfico de manera apreciable. Hemos hecho bastantes experimentos con una simulación del trafico en estas redes. O sea, por el momento es sólo investigación, no se puede hacer en Internet porque, entre otras cosas, habría que cambiar muchas cosas en la propia infraestructura para que funcione. Tenemos pruebas muy buenas de que se pueden utilizar estos algoritmos, pero las aplicaciones todavía están un poco lejos.

P.-- Y el poder de estos algoritmos procede del hecho de que las hormigas colaboran.

R.-- Sí, colaboran porque exploran en paralelo y porque se mueven junto con el paquete de datos . Un problema en particular de Internet es que si quieres controlar algo necesitas información sobre el estado de las cosas, tienes que recibir paquetes de información y estos siempre te llegan con un cierto grado de retraso sobre la información que necesitas.

P.-- O sea, que distorsionan la información que están recogiendo.

R.-- Distorsionan y destilan la información, no te llega en estado puro. Para cuando la tienes, el estado de las cosas ya puede haber cambiado y quizá es tarde para emprender alguna acción. Es muy diferente con respecto, por ejemplo, al control del tráfico. Puedes obtener información sobre el tráfico desde multitud de fuentes, desde satélites hasta cámaras en las calles y carreteras, y obtener un promedio del flujo. En Internet es diferente, el tiempo que la información tarda en llegar a tí es del mismo orden de magnitud, la misma velocidad, que la del propio flujo de la información en la Red.

P.-- Es como usar un coche para medir el tráfico. El coche es parte del problema y la información que proporciona sería insuficiente cuando llegara al lugar desde donde se la quisiera utilizar.

R.-- Sí, este es uno de los problemas. El otro es que si quieres controlar un sistema debes saber cuál es su estado para poder calibrar la intervención que vas a hacer, para poder saber hacia dónde te diriges y el impacto de lo que estás haciendo. Por ejemplo, si quiero decirte hacia dónde tienes que ir, primero recojo información sobre tu posición y después te digo qué debes hacer, a qué velocidad debes moverte, etc. La velocidad a la que te muevas será inferior a la que yo obtengo información sobre tus movimientos. O sea, tendré tiempo para elaborar la información y devolvértela. Eso no es lo que sucede en Internet. La velocidad a la que obtienes información es la misma de la otra información que se mueve por el sistema. Eso representa el estado de las cosas en Internet. Una vez que obtienes la información ya es demasiado tarde, porque el estado ha cambiado. Nuestra solución es colocar agentes dentro de la Red y todo el tiempo cambian sólo un poquito el estado de Internet y tratan de rastrear el comportamiento de Internet muy lentamente, pero a la misma velocidad en que se mueve ésta.

P.-- Esto quiere decir que al colocar estos agentes en Internet miden no sólo el estado de Internet sino incluso los cambios marginales que ellos introducen.

R.-- No, no, el cambio marginal es insignificante, inapreciable. Es bueno, porque si no resultaría que tenías un problema, la congestión de Internet, y al añadir más información la congestionaría aún más. La parte negativa es prácticamente inapreciable y la parte positiva, averiguar el estado de la Red, es fenomenal. Otra forma de pensarlo es que cada hormiga está haciendo un experimento y mide cuanto tarda en ir de un nodo a otro. Y hay miles de ellas. Al recoger esta información te puedes formar una idea del estado del sistema. Lo interesante es que son las propias hormigas las que utilizan esta información para hacer más experimentos. No hay un observador externo, no hay un sistema central que controle todo.

P.-- ¿Cómo intercambian información entre ellas?

R.-- Mediante el cambio de las probabilidades en la tabla de los "routers", donde se toman las decisiones. Allí depositan una feromona artificial, un pequeño número que se añade a la tabla del "router" y que puede ser detectada por las otras hormigas y por los paquetes de datos. La diferencia entre las hormigas y los paquetes de datos es que las primeras utilizan estos valores de manera probabilística, mientras que los paquetes de datos los utilizan de una forma determinista, basan su decisión en los valores más altos.

P.-- Con esa información, la evolución del tráfico está cambiando todo el tiempo.

R.-- Sí.

P.-- Por ejemplo, si se manda más información sobre la ruta que tiene una probabilidad del 60%, el tráfico puede incrementarse y convertirse en un 10% de probabilidades de que los datos circulen a su máxima velocidad. Esa información no la tienen ahora los "routers".

R.-- No, no la tienen, pero es una pregunta difícil de responder, porque la forma como funciona Internet cambia todo el tiempo. La hipótesis más utilizada ahora es imaginar que en cada nodo hay algo de tráfico, lo cual es una aproximación de lo que ha sucedido en los meses anteriores. Entonces se utiliza un algoritmo que hace una proyección global para toda la Red. Ahora bien, si los organizadores de la Red se dan cuenta de que algunos nodos en particular están congestionados, vuelven a utilizar el algoritmo y hacen algunos cambios, esto ocurre cada día. La otra aproximación es si ven que entre Boston y Nueva York siempre hay "embotellamientos", construyen otra autopista, pero este es un tipo de solución completamente diferente de lo que estamos hablando, se trata simplemente de incrementar la capacidad de la infraestructura instalada.

P.-- ¿Y qué ocurre cuando hay eventos inesperados, cómo que un proveedor de acceso a Internet de repente ofrece acceso gratis y, probablemente, en unos pocos días tienes un incremento considerable del flujo de usuarios y de paquetes de datos en la Red?

R.-- Hacemos simulaciones de turbulencias e incrementos repentinos en la carga de datos desde unos nodos hacia otros. Lo que hemos comprobado es que el algoritmo se adapta muy rápidamente, mucho más que ninguno de los algoritmos con los que hemos hecho comparaciones. No quiero parecer excesivamente optimista al respecto, pero en las simulaciones realmente ha funcionado muy bien. El problema para la evaluación apropiada de estos experimentos es que tendríamos que hacerlos en Internet y no sólo en el laboratorio. Y no es fácil dar este paso. Pero si eres un organizador de la Red, prefieres tener un nivel más bajo de eficiencia si a cambio sabes lo que está pasando, porque entonces si emerge algún problema sabes cómo enfrentarlo. Los ingenieros suelen preferir los algoritmos determinísticos a los algoritmos probabilísticos, porque ofrecen un mayor margen de control. Esto ocurre tanto en Internet como en otras situaciones.

P.-- ¿Se pueden usar las hormigas artificiales para rastrear información específica en la Red?

R.-- Esa es una buena pregunta. En principio, debería ser posible. Hay millones de personas moviéndose por Internet de un nodo a otro. Si se toma una de estas personas, al parecer hay alguna lógica en su comportamiento, pero en lo fundamental éste es azaroso y caótico. La idea es: si tomamos a millones de ellos y sacamos un promedio, debería ser posible extraer algún modelo razonable de sus movimientos. Esto se puede hacer si se enlaza una hormiga a cada usuario para que deposite algunas feromonas a medida que se mueve. Es una dirección interesante y tiene relación con lo hablado antes. Ya llegaremos a esto.

P.-- Creo que uno de los factores claves en la economía-red, de la que todavía estamos lejos, será la posibilidad de seguir la vida de ciertas informaciones o la producción de conocimientos que enriquecen el sistema todo el tiempo a través de intercambios e interacciones. Por ejemplo, si publico en la Red que el Milán le ganó al Parma 2-0, esta es una información que usaré en un bar, pero que tendrá escasas repercusiones en Internet. Por lo menos, no enriquecerá el volumen de la información intercambiada en la Red, si acaso incrementará el volumen de la redundancia informativa. Pero si publico algo que es republicado multitud de veces en el sistema, que origina una producción de información nueva en multitud de lugares, etc., esta es entonces una información muy rica con un valor económico que se puede "medir" por las veces que rueda por Internet y el crecimiento informativo que provoca. El problema es que no hay forma de seguir este proceso. ¿Las hormigas nos pueden ayudar a hacerlo?

R.-- No lo sé, posiblemente se necesitarían hormigas más complejas para cumplir con una tarea de estas características. Necesitarían algo de memoria y otros rasgos que las hormigas actuales todavía no poseen. No sé si seremos capaces de hacer algo así en el futuro. Nuestras hormigas actuales son muy simples, con códigos muy sencillos, se requieren muchas al mismo tiempo y funcionan mediante pequeños cambios en el entorno en el que viven y no se comunican directamente entre ellas. Les basta reconocer estas modificaciones y utilizar esa información localmente. No hay forma de acceder a esta información mediante algún sistema central. Es como cuando vas en un coche y ves las señales en la carretera: alguien las ha puesto allí, pero tú también puedes añadir algunas e influir en el comportamiento de otra gente que las ve. Nadie tiene un mapa completo de las señales distribuidas. Así es como funcionan nuestras hormigas artificiales, y las reales también: ellas no tienen un mapa global del medio en que viven. Este es el rasgo distintivo de estos algoritmos

P.-- Pero es una idea potente. ¿Ha pasado usted de la fase de simulación al mundo real?

R.-- No, yo no. Hay colegas que están desarrollando algunas aplicaciones, aunque no conozco los detalles. Un amigo mío de Lugano, Luca Gambardella, aplicó estos algoritmos en una empresa que distribuye gasolina en la parte italiana de Suiza.

P.-- Me imagino que usted debe mantenerse al tanto de lo que se publica sobre el comportamiento de las hormigas biológicas.

R.-- Sí, me mantengo informado al respecto.

P.-- Bueno, usted sabe que uno de los rasgos más interesantes de las hormigas es la relación entre comportamientos agresivos/cooperativos. ¿Esto tiene alguna aplicación en el caso de las hormigas artificiales?

R.-- (Risas) Usted me está dando un montón de ideas. Pero no, no he trabajado sobre esto, aunque sería interesante explorarlo.

P.-- ¿Conoce usted el caso de las hormigas argentinas de la especie "Linepithema humile"? Al parecer, llegaron a EEUU en barcos comerciales hace un siglo. Ahora se han hecho dominantes en toda la costa oeste porque, por alguna razón, las hormigas locales no las reconocen como enemigas y terminan trabajando para ellas. El fenómeno es similar en varias regiones de Europa, incluída España, donde las hormigas argentinas se han establecido sin encontrar el rechazo que normalmente se produce entre hormigas rivales. Lo curioso es que, en Argentina, estas hormigas se mantienen tranquilitas en su hábitat y no destacan en absoluto con respecto al resto de especies. Cuando leí esto, pensé que ésta sería una idea interesante para la Red.

R.-- Sí, efectivamente, podría conseguirse que algunas hormigas consigan cierta información y otras no, aunque trabajen en el mismo medio.

P.-- ¿Cómo ve usted la evolución de las hormigas artificiales a mediano plazo?

R.-- Lo que estamos discutiendo es cómo usar no sólo hormigas, sino otros insectos sociales para diseñar robots capaces de auto-ensamblarse. Son robots simples, con capacidad de aprendizaje, que descubren las formas y funcionalidades necesarias para cumplir con una tarea y se las incorporan. Dicho de otra manera, con las hormigas artificiales podemos construir robots diferentes gracias a una "conducta de construcción de hormigueros". Las termitas, por ejemplo, construyen nidos muy complejos. Pero una termita sola no tiene un plan de cómo hacerlo. Utilizan las feromonas como una forma indirecta de comunicación para conseguir sus objetivos. Se han hecho algunos experimentos en los que se deja que unas termitas empiecen la construcción del hormiguero. Entonces se las quita de en medio y se ponen otras termitas en su lugar, las cuales continúan como si conocieran el plan del hormiguero. Pero, en realidad, no lo conocen, simplemente reaccionan a lo que encuentran en el entorno. Ya están programadas por la naturaleza para desarrollar este comportamiento que resulta en la construcción del nido. Esta es una idea muy interesante porque si matas a una termita, otra ocupará su lugar. En el caso de los robots que se auto-ensamblan nadie se preocupará si alguno se rompe, siempre habrá otro en su lugar, todo el sistema funcionará mediante una capacidad especial para auto-repararse.

P.-- ¿Se ha experimentado con esto?

R.-- Los japoneses están haciendo algo, también en EEUU. Pero lo que nosotros estamos pensando es diferente. Queremos basarnos en la "inteligencia del enjambre" para programar a estos robots. Estas son ideas nuevas, nadie ha hecho nada sobre esto todavía. Usted me pregunta sobre el futuro de estas investigaciones. Hay una serie de direcciones. Los algoritmos basados en la inteligencia del enjambre abren un campo completamente nuevo y se pueden aplicar a muchas situaciones. Otra cuestión es probar ciertas propiedades matemáticas. Por ejemplo, un matemático austríaco ya ha demostrado la convergencia del algoritmo a la solución óptima. Y finalmente tenemos los algoritmos genéticos, un área donde hay mucha gente trabajando para tratar de entender su funcionamiento. Todo esto es muy nuevo y no sabemos todavía cómo evolucionará.