Um único algoritmo pode ajudar os robôs a tomar boas decisões em tempo real

Em 2018, o programa AlphaZero do Google DeepMind aprendeu sozinho os jogos de xadrez, shogi e Go usando aprendizado de máquina e um algoritmo especial para determinar os melhores movimentos para vencer um jogo dentro de uma grade definida. Agora, uma equipe de pesquisadores da Caltech desenvolveu um algoritmo análogo para robôs autônomos – um sistema de planejamento e controle de tomada de decisão que ajuda robôs em movimento livre a determinar os melhores movimentos a serem feitos enquanto navegam no mundo real.

“Nosso algoritmo realmente cria estratégias e, em seguida, explora todos os movimentos possíveis e importantes e escolhe o melhor por meio de simulação dinâmica, como jogar muitos jogos simulados envolvendo robôs em movimento”, diz Soon-Jo Chung, Bren Professor de Controle e Sistemas Dinâmicos da Caltech e sênior cientista pesquisador do JPL, que o Caltech gerencia para a NASA. “A inovação revolucionária aqui é que criamos uma maneira muito eficiente de encontrar o movimento seguro ideal que os métodos típicos baseados em otimização nunca encontrariam.”

A equipe descreve a técnica, que eles chamam de Spectral Expansion Tree Search (SETS), no artigo de capa de dezembro da revista Robótica Científica.

Muitos robôs podem se mover livremente e em qualquer direção. Considere, por exemplo, um robô humanóide projetado para ajudar uma pessoa idosa em uma casa. Tal robô deve ser capaz de se mover de muitas maneiras diferentes e, essencialmente, em qualquer direção dentro do espaço, à medida que encontra obstáculos ou eventos inesperados ao completar suas tarefas. O conjunto de movimentos, obstáculos e desafios desse robô será muito diferente daquele de um carro autônomo, por exemplo.

Como, então, um único algoritmo pode guiar diferentes sistemas robóticos para tomar as melhores decisões para se moverem ao seu redor?

“Você não quer que um designer tenha que criar esses movimentos à mão e dizer: ‘Este é o conjunto discreto de movimentos que o robô deve ser capaz de fazer'”, diz John Lathrop, estudante de pós-graduação em controle e sistemas dinâmicos. na Caltech e co-autor principal do novo artigo. “Para superar isso, criamos o SETS.”

SETS utiliza teoria de controle e álgebra linear para encontrar movimentos naturais que utilizam as capacidades de uma plataforma robótica em toda a sua extensão em um ambiente físico.

O conceito básico subjacente é baseado em Monte Carlo Tree Search, um algoritmo de tomada de decisão também usado pelo AlphaZero do Google. Aqui, Monte Carlo significa essencialmente algo aleatório, e a pesquisa em árvore refere-se à navegação em uma estrutura ramificada que representa as relações de dados em um sistema. Nessa árvore, uma raiz se ramifica nos chamados nós filhos, que são conectados por arestas.

Usando o Monte Carlo Tree Search para um jogo como Go, os movimentos possíveis são representados como novos nós, e a árvore cresce à medida que mais amostras aleatórias de trajetórias possíveis são tentadas. O algoritmo executa os movimentos possíveis para ver os resultados finais dos diferentes nós e depois seleciona aquele que oferece o melhor resultado com base em uma avaliação de pontos.

O problema, explica Lathrop, é que ao usar essa estrutura de árvore ramificada para sistemas dinâmicos contínuos, como robôs operando no mundo físico, o número total de trajetórias na árvore cresce exponencialmente. “Para alguns problemas, tentar simular todas as possibilidades e depois descobrir qual é a melhor levaria anos, talvez centenas de anos”, diz ele.

Para superar isso, o SETS aproveita uma compensação exploração/exploração. “Queremos tentar simular trajetórias que não investigamos antes – isso é exploração”, diz Lathrop. “E queremos continuar buscando caminhos que anteriormente renderam altas recompensas – isso é exploração. Ao equilibrar a exploração e a exploração, o algoritmo é capaz de convergir rapidamente para a solução ideal entre todas as trajetórias possíveis.”

Por exemplo, se um robô começar a calcular algumas ações possíveis que ele determina que o fariam bater em uma parede, não há necessidade de investigar nenhum dos outros nós naquele galho da árvore.

“Essa troca de exploração/exploração e pesquisa sobre os movimentos naturais do robô permite que nossos robôs pensem, se movam e se adaptem a novas informações em tempo real”, diz Benjamin Rivière, pesquisador de pós-doutorado associado em engenharia mecânica e civil na Caltech e co. -autor principal do artigo.

O SETS pode executar uma pesquisa em uma árvore inteira em cerca de um décimo de segundo. Durante esse tempo, ele pode simular milhares a dezenas de milhares de trajetórias possíveis, selecionar a melhor e então agir. O ciclo continua continuamente, dando ao sistema robótico a capacidade de tomar muitas decisões a cada segundo.

Uma característica fundamental do algoritmo SETS é que ele pode ser aplicado essencialmente a qualquer plataforma robótica. Os recursos e capacidades não precisam ser programados individualmente. No novo artigo, Chung e seus colegas demonstram a utilidade bem-sucedida do algoritmo em três ambientes experimentais completamente diferentes – algo que é muito raro em artigos sobre robótica.

No primeiro, um drone quadrotor foi capaz de observar quatro bolas brancas pairando enquanto evitava quatro bolas laranja, tudo isso enquanto navegava em um campo de aviação repleto de correntes de ar perigosas ou térmicas que ocorrem aleatoriamente. O experimento com drones foi conduzido no Centro de Sistemas e Tecnologias Autônomas (CAST) da Caltech.

No segundo, o algoritmo aprimorou um motorista humano de um veículo terrestre sobre esteiras para navegar por uma pista estreita e sinuosa sem bater nas grades laterais. E na configuração final, o SETS ajudou um par de naves espaciais amarradas a capturar e redirecionar um terceiro agente, que poderia representar outra nave espacial, um asteróide ou outro objeto.

Uma equipe de estudantes e pesquisadores da Caltech está atualmente aplicando uma versão do algoritmo SETS a um carro da Indy que participará do Indy Autonomous Challenge no Consumer Electronics Show (CES) em Las Vegas, no dia 9 de janeiro.