Otimização inspirada em formigas

6:51 am Inteligência Artificial, Robótica

O campo de inteligência artificial é cheio de técnicas inspiradas na natureza. Os dois exemplos mais famosos são redes neuronais, que emulam grupos de neurônios e suas conexões, e algoritmos genéticos, que tentam resolver um problema codificando a solução nos genomas de uma população artificial, sujeita à sobrevivência e recombinação dos mais fortes. Talvez falemos mais dessas técnicas por aqui, se houver interesse.

Hoje eu vou falar de uma outra técnica, ou família de técnicas: Ant Colony Optimization (ACO), ou otimização de colônias de formigas. ACO foi inventada por Marco Dorigo em 1992, e se baseia na capacidade de grupos de formigas de apresentar comportamento coletivo muito mais inteligente que o que uma formiga sozinha seria capaz de fazer. Por exemplo, formigas podem achar o melhor caminho entre o formigueiro e uma fonte de comida. Se algum obstáculo mudar o terreno, elas se adaptam rapidamente e encontram um novo caminho, como você pode ver na figura abaixo.

Adaptando o caminho

Isso acontece porque as formigas se “comunicam” de forma indireta, através do ambiente, usando feromônios. As formigas deixam uma trilha de feromônio pelo caminho que seguem. Quanto menor o caminho, mais forte o feromônio. Outras formigas tendem a seguir o feromônio mais forte. Caminhos alternativos, e piores, são abandonados porque o feromônio mais fraco depositado ali evapora com o tempo. Esse é o princípio básico de Ant Colony Optimization. O Dorigo usou essa capacidade para resolver o clássico problema do Caixeiro Viajante, com excelentes resultados.

Isso foi em 92. Hoje, o trabalho do Dorigo e de outros pesquisadores deu origem a todo um subcampo de pesquisa em computação, chamado de Inteligência de Enxame, que se baseia na premissa de usar agentes muito simples, mas que colaboram entre si, para atingir objetivos complexos e de forma robusta, ou seja, tolerante a falhas e mudanças no ambiente. Um exemplo interessante, também baseado em formigas, é clustering. As formigas sabem naturalmente agrupar objetos por grupos e fazem isso para limpar o formigueiro, separando comida de lixo.

Antes do agrupamentoDepois do agrupamento

A combinação de robustez e inteligência coletiva é muito interessante pro pessoal que trabalha com robótica. Agentes simples são baratos, se você tem um grupo de robôs que pode se adaptar à perda de um deles, por falha mecânica, falta de energia ou qualquer outro motivo, diminuem as chances de seu enorme investimento em robôs ir por água abaixo por um detalhe bobo.

O casamento de inteligência de enxame com robótica atende pelo nome de Swarm Robotics. Os robozinhos, sempre trabalhando em equipe, realmente têm um comportamento coletivo interessante. Por exemplo, eles aprendem que podem se conectar, formando um objeto maior, para passar por um obstáculo intransponível para um único robô:

Saltando um obstáculo

Eles também conseguem transportar grandes objetos, navegar um terreno em formação e otras cositas más. Aqui tem um bando de videos bacanas.

1 Resposta
  1. Renato Mendes Luz e Souza :

    Date: fevereiro 12, 2013 @ 11:01 pm

    Olá meu caro sou estudante da TI (Tecnologia da Informação). Este assunto que você colocou web é de uma importância par pois existem muitos professores estudando as formigas socialmente. A questão de algoritmo foi especial assunto colocado por você.