Había oído campanas sobre una disciplina, 'swarm robotics' (robótica de enjambre) que buscaba justo eso, la colaboración entre robots para alcanzar logros fantásticos.
Pero el pequeño robot no sabía cómo hacerlo, y vagaba despistado y un poco al azar, deseoso de colaborar con otros robots pero sin saber qué hacer.
Hormigas y búsqueda de alimento
Y deambulando andaba cuando se topó con un hormiguero. Dirigió su cámara hacia la entrada del hormiguero y, no sin forzar para ello su algoritmo de detección de objetos, se admiró al ver enormes cantidades de pequeños seres que interactuaban entre sí, cuidaban larvas y a la hormiga reina, defendían el hormiguero y, sobre todo, establecían largas filas en búsqueda, exitosa por cierto, de alimento.
Este último aspecto fue lo que más llamó la atención de nuestro pequeño robot. ¿Cómo eran capaces las hormigas de deambular por grandes espacios de terreno, comunicarse entre sí los hallazgos y, de forma eficiente, establecer esas largas filas de pequeñas obreras en busca de los preciados nutrientes? Parecía magia.
Así que, ni corto ni perezoso, el robot 'se plantó' delante de una hormiga y se lo preguntó. Dime admirada hormiga, ¿Cuál es vuestra magia? ¿Cómo os organizáis para encontrar el mejor camino hasta vuestro alimento?
Y lo que le contó la hormiga le fascinó, por lo eficaz y por lo sencillo.
Querido y metálico robotito, le dijo la hormiga, el secreto no está en la masa, como las pizzas, sino en las feromonas.
¿Y qué es eso de una feromona? volvió a la carga el robot
Pues las feromonas son sustancias químicas específicas que 'soltamos por ahí' y que otras hormigas detectan y así permanecen a modo de rastro durante un tiempo aunque hay que reconocer que poco a poco se evapora. Pero eso tampoco nos viene mal.
Vale pero ¿y cómo lo hacéis? ¿Cuál es vuestro algoritmo?
No tengo ni idea de lo que es un algoritmo, replicó la hormiga, pero sí te puedo contar cómo trabajamos.
Cuando no tenemos ni idea de dónde hay alimento, cuando 'partimos de cero' por decirlo de alguna manera, simplemente nos movemos al azar, a ver qué encontramos. Pero si tenemos suerte, si una de nosotras encuentra alimento, no se queda ahí admirándolo o 'poniéndose morada' sino que retorna al hormiguero, y por el caminos vamos soltando nuestro rastro de feromonas. Además, si el camino es cortito, dejamos un rastro más grueso de feromonas, para indicar a las compañeras que esa localización es 'guai' porque por muy obreras y 'hormiguitas' que seamos, si nos cuesta poco llegar al alimento, pues mejor ¿No te parece?
Y claro, como no somos tontas, si cuando vamos a salir en búsqueda de alimentos ya hay rastros de feromonas, pues nada de búsqueda al azar, sino que seguimos los rastros que ya existen, que para algo otras nos han hecho el trabajo. Eso si. no nos olvidamos de hacer nuestra aportación y depositar nuestras propias feromonas en ese camino..
¿Te das cuenta de lo simple que es esto, pequeño ingenio metálico?
Si al grueso del rastro que dejamos, mayor cuanto más corto el camino, unimos la evaporación, los caminos cortos tenderán a tener más feromonas que los largos, tanto porque depositamos más feromonas como porque da menos tiempo a que se evaporen antes de que lleguen nuevas compañeras. Sin embargo, los rastros de feromonas en los caminos más largos, tenderán a desaparecer. Y claro, las nuevas hormigas refuerzan, con sus propias fermonas, esas feromonas de los caminos más cortos.
Y de esa forma tan tonta, al final, es como optimizamos la búsqueda de alimento, porque, casi sin querer, sólo depositando 'como Dios manda' nuestras feromonas y siguiendo adecuadamente el rastro de feromonas de otras que nos precedieron, acabamos encontrando el camino óptimo hasta nuestro alimento.
¿Cómo lo ves?
El algoritmo ACO ('Ant Colony Optimization')
Muy admirado quedó el robot de la habilidad de las hormigas y de cómo, con mecanismos muy sencillos, habían resuelto y optimizado un problema complejo.
Se despidió amablemente y se dijo: yo tengo que hacer lo mismo con otros robots.
Pero ¿Cómo lo hago, si yo no tengo feromonas?
Vale, feromonas no, pero sí que tengo estructuras de datos, algoritmos y capacidad de comunicación. Y otros robotitos como yo también los tienen.
Así que, pensando, pensando, llegó a conclusión de que podía representar mediante grafos las posibles opciones y los caminos entre ellas y que los diferentes robots compartiesen esa información. ¿Y las feromonas? ¿Qué serían? ¿Cómo marcarían los caminos? Pues nada, unos simples valores numéricos asociados a cada arco del grafo, e inicializados a cero al principio.
Al inicio, los robots elegirían recorrer el grafo de forma aleatoria o probabilista y cada robot, al recorrer el grafo, aumentaría un poco ese nivel de las feromonas numéricas de los arcos recorridos.
Pero claro, con eso sólo no valía, porque tendríamos más y más feromonas hasta el infinito. Así que el robot pensó en simular la evaporación mediante una función parametrizada mediante una tasa de evaporación, y que se ocupase de poco a poco disminuir el nivel de feromonas de los arcos (el numerito en cada arco) si no se producían nuevas aportaciones de feromonas.
Y así lo hizo. Y convenció a otros robots para que colaborasen con él usando el mismo algoritmos. Y fueron felices resolviendo colaborativamente problemas y consiguiendo grandes objetivos.
Moraleja
Cuando tienes que resolver un problema computacional complejo, no dejes de observar por si acaso la naturaleza por si algún ser vivo, o la propia naturaleza, lo ha resuelto ya, porque si es así, probablemente te inspire una solución válida y eficiente, y, lo que es más, con frecuencia basada en mecanismos sorprendentemente simples.
Nota
Aunque hemos atribuido a nuestro robot la invención del algoritmo ACO ('Ant Colony Optmization'), lo cierto es que esté fue diseñado por Marco Dorigo ya en los años noventa y que yo he tenido noticia de él y me he inspirado en el libro 'Robotic algortihms' de Gareth Morgan Thomas.
