Novos algoritmos demonstram como um enxame de robôs simples pode ser feito para trabalhar juntos como um todo
No laboratório do Instituto de Tecnologia da Geórgia, os físicos estão experimentando robôs que parecem ter sido comprados em uma loja "tudo por US $ 1". Os robôs não podem se mover no espaço ou se comunicar. Basicamente, eles acenam com as mãozinhas, como besouros virados nas costas.
Mas se você montar muitos desses dispositivos, poderá obter algo do nada: eles se empurram, se empurram e se interligam. E, como resultado, eles começam a trabalhar como um todo.
Os pesquisadores estão estudando como controlar esses sistemas para que funcionem de maneira semelhante a um enxame de abelhas ou a uma colônia de formigas: cada indivíduo age com base no mesmo conjunto de regras, mas vários indivíduos que se reúnem podem exibir um comportamento complexo sem controle central.
“Nossa abordagem é a seguinte: descobrir qual é o modelo computacional mais simples necessário para realizar essas tarefas complexas? Diz
Dana Randall , especialista em TI da Georgettech, uma das líderes do projeto. "Buscamos elegância e simplicidade."
Randol, como programador, aborda a tarefa do ponto de vista dos algoritmos: qual é o conjunto mais simples de instruções com base em quais unidades individuais do enxame podem trabalhar, com base nos escassos dados que eles podem coletar, inevitavelmente levarão ao complexo comportamento conjunto necessário para os pesquisadores? Em novembro passado, Randall e colegas
publicaram um algoritmo para garantir que um enxame ideal de partículas possa se mover de maneira controlada.
Trabalhe com esses robôs, que os cientistas chamam de "smarticles" [smarticles; inteligente - inteligente, partícula - partícula / aprox. transl.] - parte da pesquisa no campo sobre a possibilidade de criação e a utilidade de robôs auto-organizados. Outros exemplos semelhantes incluem
robôs do tamanho de gotas sendo desenvolvidos na Universidade do Colorado, enxames de "
kilobots " da Universidade de Harvard e
svarmanoidia do laboratório belga. Em muitos casos, a idéia é imitar um fenômeno natural, como um movimento altamente organizado de uma colônia descentralizada de formigas ou um conjunto inconsciente e auto-programado de moléculas de DNA.
"Sabemos o que queremos de um enxame inteiro, mas para programá-lo, você precisa descobrir o que cada agente deve fazer separadamente", disse
Melvin Gauchi , pesquisador de
robótica do grupo de Harvard. "A parte mais difícil é entre esses dois níveis."
Dana Randall e Dan Goldman no Laboratório GoldmanCuidado com os líderes
Daniel Goldman é um físico de Georgetch que dirige o experimento Smarticle. Ele está interessado principalmente na física de materiais granulares ativos que podem mudar de forma. Entre seus slides para conferências está um momento do filme Homem-Aranha 3, demonstrando o
surgimento de um supervilão Sandman - grãos individuais de areia espalhados pelo deserto se reúnem na forma de um homem. Os smartphones são a maneira da Goldman de testar materiais granulares ativos em laboratório.
“Eles nos dão a oportunidade de usar a geometria para controlar as propriedades do material. Se você desfocar os olhos, pode imaginar que esse monte de smartphones é material real ”, disse Goldman.
Os smarticles têm membros curtos que podem balançar para frente e para trás. Eles reagem à luz e ao som de diferentes frequências. Eles podem ser programados para alterar a velocidade de movimentos dos membros em resposta às ações de outros smartphones próximos deles.
Os smartphones podem ser feitos para executar várias ações: compor (empilhar), expandir (distribuir) e mover. Essas manobras podem servir de base para a execução de funções mais complexas, mas mesmo essas tarefas são difíceis de resolver, pois os smartphones não entendem como estão localizados em relação a todo o grupo.
Para entender as possibilidades e dificuldades associadas à programação de comportamentos complexos, decorrentes de partes simples, vale lembrar o que exatamente é conhecido para cada artigo individual. Nem tanto. Ele não pode ver, sua memória é limitada e tudo o que ele sabe sobre outros smartphones com os quais ele deve coordenar ações, ele aprende quando encontra seus vizinhos imediatos.
"Imagine um homem em um show de rock com os olhos fechados", disse Joshua Daimad, estudante de ciências da computação da Universidade do Arizona que está trabalhando em um projeto de smartphones.
Uma estratégia pode ser a de nomear um líder para gerenciar o enxame - mas essa abordagem é vulnerável. Se o líder sofrer, todo o enxame falhará. O outro é dar a cada robô uma tarefa única no enxame, mas em larga escala essa abordagem é impraticável. "Programar 1000 robôs individualmente é quase impossível", disse
Jeff Dasek , pesquisador da
Harlin College of Engineering em Olin e ex-membro do grupo de pesquisa de sistemas auto-organizadores de Harvard que trabalha com enxames de
robôs subaquáticos . "Mas quando cada membro do grupo trabalha de acordo com as mesmas regras, seu código não muda, independentemente de você ter 10 robôs, 1.000 ou 10.000".
O algoritmo de enxame tem duas propriedades. Primeiramente, ele é distribuído, ou seja, funciona separadamente em cada uma das partículas do sistema (como cada
formiga nômade executa um conjunto simples de ações, dependendo das informações recebidas do ambiente). Em segundo lugar, inclui um elemento do acaso. Isso significa que se, por exemplo, uma formiga nômade sente a presença de outras cinco formigas por perto, então com 20% de probabilidade ela se moverá para a esquerda e 80% para a direita. Os algoritmos diferem aleatoriamente dos algoritmos determinísticos nos quais cada estágio é completamente determinado pelos anteriores.
A aleatoriedade pode parecer desnecessária para algoritmos - afinal, ao implementar um procedimento, você geralmente deseja obter um determinado resultado. Mas a aleatoriedade tem benefícios inesperados de desempenho, o que torna os algoritmos aleatórios adequados para uso em enxames.
Garantias aleatórias
Em 2015, Goldman e Randall discutiram a possibilidade de encontrar regras através das quais os smartphones pudessem trabalhar juntos como um todo. Randall percebeu que o comportamento que Goldman queria liderar o enxame era muito semelhante ao comportamento dos sistemas de partículas idealizados estudados em ciência da computação.
"E imediatamente pensei: sei exatamente o que precisa ser feito", disse Randall.
Para Randall, o comportamento dos smartphones lembrava um fenômeno modelado por cientistas da computação em muitos outros contextos. Um dos exemplos mais famosos é o surgimento de áreas segregadas. No final da década de 1960, o economista Thomas Schelling queria entender como a segregação por área ocorre na ausência de alguma força central que classifica as pessoas pela cor da pele. Ele imaginou uma pessoa hipotética olhando para seus vizinhos e decidindo uma mudança com base em quantos vizinhos se pareciam com ele. Quando uma pessoa se mudou, Schelling o mudou para um lugar aleatório no assentamento, onde o processo algorítmico de observação e tomada de decisão foi repetido. Schelling descobriu que, de acordo com suas regras, o surgimento de segregação de moradores é quase garantido, mesmo que algumas pessoas prefiram morar em diversas áreas.
William Savoy, estudante de pós-graduação no laboratório da GoldmanRandall percebeu que os smartphones em seu enxame se assemelham às pessoas no modelo Schelling. Nos dois casos, as unidades individuais devem tomar decisões sem conhecer sua posição no esquema global (elas apenas sabem o que vêem nas imediações). No modelo de Schelling, as decisões podem ser tomadas com um elemento aleatório - se os vizinhos forem diferentes de você, há uma chance de você se mudar e há uma chance de ficar.
Em 2016, Randol e colegas publicaram um
trabalho descrevendo partículas idealizadas vivendo em uma treliça e decidindo se fica ou se move, dependendo do número de partículas observadas ao seu redor. As decisões tomadas eram probabilísticas - sempre que as partículas "jogavam" um cubo ponderado para seleção. Randall et al. Mostraram que, se você atribuir o cubo de peso corretamente, poderá garantir a ocorrência de um enxame denso (assim como Schelling poderia provar que, se atribuir tolerância à diversidade aos residentes da área no nível certo, a segregação certamente aparecerá). Ajustando o algoritmo, eles também poderiam garantir que um enxame de partículas se movesse em um estado estendido.
A aleatoriedade do algoritmo ajuda as partículas no enxame a evitarem ficar presas nos selos locais, quando muitos subgrupos isolados se acumulam juntos, mas o enxame inteiro como um todo não é densificado. A aleatoriedade garante que, quando pequenos selos aparecerem, algumas unidades ainda decidirem se mudar para outro local, e o processo continuará até que um selo geral seja alcançado. Para evitar selos locais, é necessário um pouco de aleatoriedade; é necessário muito mais para fazer a transição de um estado compactado globalmente para um estado expandido.
Para o mundo real
Provar que as partículas no mundo teórico podem, executando um algoritmo simples, alcançar um certo comportamento em um enxame é uma coisa. Para implementar o algoritmo barato, propenso a falhas, smartphones reais, clicar em membros em uma caixa - é completamente diferente.
"Nossos colegas de teoria descobriram como programar essas coisas, mas ainda estamos no início da jornada e não podemos dizer que esses esquemas foram transferidos diretamente", disse Goldman.
Um problema era fazer com que os smartphones se movessem juntos. No início, quando os pesquisadores incluíam smartphones em um espaço limitado, esse grupo simplesmente se contraiu acidentalmente. Mas uma vez, quando os físicos observaram esse movimento caótico, uma bateria morreu em um dos smartphones. Goldman e colegas notaram que o enxame começou a se mover de repente na direção de uma unidade fixa. Os pesquisadores relataram essa descoberta inesperada para os teóricos, e eles aproveitaram essa dica. O trabalho levou à criação de uma nova versão do algoritmo, permitindo que o enxame idealizado sempre se movesse em uma determinada direção.
Pouco a pouco, as experiências em andamento no computador e as experiências físicas estão se aproximando. Os pesquisadores esperam finalmente provar teoricamente que o algoritmo básico, implementado por um método comum em um grande enxame de robôs pequenos e baratos, é garantido que leva ao comportamento desejado do enxame.
"Gostaríamos de alcançar um estado em que não detectássemos apenas um fenômeno quando a bateria acabar", disse Daimad. "Queremos que isso seja algo da categoria de conquista intencional."