Ameba eletrônica resolve problema impossível para supercomputadores

Redação do Site Inovação Tecnológica - 11/12/2020

O robô ameboide resolve os problemas de forma similar à que organismos unicelulares usam para procurar comida - o que é um tipo de computação analógica.
[Imagem: Masashi Aono]

Problema combinatorial

Uma "ameba eletrônica" conseguiu obter uma solução aproximada do histórico problema do caixeiro-viajante.

Nem mesmo os mais modernos supercomputadores digitais conseguem resolver esse problema de otimização combinatorial em tempo viável na prática porque o número de possíveis soluções que os programas precisam avaliar aumenta exponencialmente com o tamanho do problema - um efeito também conhecido como explosão combinatória.

Inúmeras tarefas de aplicação do mundo real, como planejamento e programação em logística e automação, são formuladas matematicamente como problemas de otimização combinatória - a versão original do "problema do caixeiro-viajante" busca a rota mais eficiente para que um vendedor comece a trabalhar em uma cidade e retorne a ela depois de viajar para todas as diferentes cidades em uma lista.

Tendo em vista a utilidade prática da questão, várias tentativas têm sido feitas de resolver esses problemas em tempos viáveis usando simuladores quânticos, processadores analógicos e até um novo tipo de computador, conhecido como "máquina Ising".

Enquanto essas soluções futurísticas não ficam prontas, Kenta Saito e colegas da Universidade de Hokkaido, no Japão, propuseram uma tecnologia mais simples: um pequeno robô que imita uma ameba, um organismo unicelular.

Diagrama do circuito da ameba eletrônica. À esquerda, o núcleo da ameba; à direita, fora de escala, o sistema de barras transversais com resistências programáveis.
[Imagem: Amoeba Energy]

Computação analógica

A ameba é conhecida por maximizar sua colheita de alimentos de forma eficiente, deformando seu corpo. Saito conseguiu imitar a dinâmica da ameba eletronicamente usando um circuito analógico, o que torna sua solução também uma espécie de processador analógico.

O pequeno robô foi colocado sobre uma matriz de rotas eletricamente condutoras na qual as interseções entre as rotas apresentam diferentes valores de resistência elétrica, o que permite programar de maneira simples as exigências e restrições das rotas, como cidades já visitadas ou cidades sem ligação direta.

Saito usou seu processador analógico ameboide para encontrar a rota mais curta para um caixeiro-viajante que precisa visitar 4 cidades. A seguir, para não precisar construir matrizes cada vez maiores, ele programou o comportamento da ameba eletrônica em um simulador e utilizou para avaliar o desempenho em problemas de grande porte.

O algoritmo encontrou soluções válidas de alta qualidade com um comprimento de rota significativamente menor do que o comprimento médio obtido pela amostragem aleatória. Além disso, o tempo necessário para encontrar uma solução válida e eficiente cresceu apenas linearmente com o número de cidades, enquanto um algoritmo tradicional faz esse tempo crescer exponencialmente.

"Como o computador analógico consiste em um circuito simples e compacto, ele pode lidar com muitos problemas do mundo real nos quais entradas, restrições e solicitações mudam dinamicamente, e pode ser embutido em dispositivos IoT como um microchip para economia de energia," disse o professor Masashi Aono.

Mais tópicos