Créditos:Imagem: Jose-Luis Olivares, MIT; iStock
Um novo algoritmo reduz o tempo de viagem ao identificar atalhos que um robô pode seguir no caminho até seu destino.
Se um robô viajando para um destino tiver apenas dois caminhos possíveis, ele precisará apenas comparar o tempo de viagem das rotas e a probabilidade de sucesso. Mas se o robô estiver atravessando um ambiente complexo com muitos caminhos possíveis, escolher a melhor rota em meio a tanta incerteza pode rapidamente se tornar um problema intratável.
Os pesquisadores do MIT desenvolveram um método que poderia ajudar este robô a raciocinar com eficiência sobre as melhores rotas para seu destino. Eles criaram um algoritmo para construir roteiros de um ambiente incerto que equilibra o equilíbrio entre a qualidade do roteiro e a eficiência computacional, permitindo que o robô encontre rapidamente uma rota percorrível que minimize o tempo de viagem.
O algoritmo começa com caminhos que certamente são seguros e encontra automaticamente atalhos que o robô poderia seguir para reduzir o tempo total de viagem. Em experimentos simulados, os pesquisadores descobriram que seu algoritmo pode alcançar um melhor equilíbrio entre desempenho e eficiência do planejamento em comparação com outras linhas de base, que priorizam um ou outro.
Este algoritmo pode ter aplicações em áreas como a exploração, talvez ajudando um robô planejando a melhor maneira de viajar até à borda de uma cratera distante na superfície irregular de Marte. Também poderia ajudar um drone de busca e resgate encontrando a rota mais rápida para alguém preso em uma montanha remota.
“Não é realista, especialmente em ambientes externos muito grandes, que você saiba exatamente onde pode ou não atravessar. Mas se tivermos apenas um pouco de informação sobre o nosso ambiente, podemos usá-la para construir um roteiro de alta qualidade”, diz Yasmin Veys, estudante de pós-graduação em engenharia elétrica e ciência da computação (EECS) e autora principal de um artigo sobre este assunto.
Veys escreveu o artigo com Martina Stadler Kurtz, estudante de pós-graduação do Departamento de Aeronáutica e Astronáutica do MIT, e o autor sênior Nicholas Roy, professor de aeronáutica e astronáutica do MIT e membro do Laboratório de Ciência da Computação e Inteligência Artificial do MIT (CSAIL). A pesquisa será apresentada na Conferência Internacional sobre Robótica e Automação.
Gerando gráficos
Para estudar o planejamento de movimento, os pesquisadores muitas vezes pensam no ambiente de um robô como um gráfico, onde uma série de “arestas”, ou segmentos de linha, representam caminhos possíveis entre um ponto de partida e um objetivo.
Veys e seus colaboradores usaram uma representação gráfica chamada Problema do Viajante Canadense (CTP), cujo nome vem dos motoristas canadenses frustrados que precisam voltar atrás e encontrar uma nova rota quando a estrada à frente está bloqueada pela neve.
Em um CTP, cada aresta do gráfico tem um peso associado a ela, que representa quanto tempo esse caminho levará para ser percorrido e uma probabilidade de quão provável é ser percorrido. O objetivo de um CTP é minimizar o tempo de viagem até o destino.
Os pesquisadores se concentraram em como gerar automaticamente um gráfico CTP que representasse efetivamente um ambiente incerto.
“Se estivermos navegando em um ambiente, é possível que tenhamos alguma informação, então não estamos apenas entrando às cegas. Embora não seja um plano de navegação detalhado, ele nos dá uma ideia do que estamos trabalhando. O ponto crucial deste trabalho é tentar capturar isso no gráfico CTP”, acrescenta Kurtz.
O seu algoritmo assume que esta informação parcial – talvez uma imagem de satélite – pode ser dividida em áreas específicas (um lago pode ser uma área, um campo aberto outra, etc.)
Cada área tem uma probabilidade de o robô poder atravessá-la. Por exemplo, é mais provável que um robô não aquático consiga atravessar um campo do que um lago, portanto a probabilidade de um campo seria maior.
O algoritmo usa essas informações para construir um gráfico inicial através do espaço aberto, mapeando um caminho conservador que é lento, mas definitivamente percorrível. Em seguida, ele usa uma métrica desenvolvida pela equipe para determinar quais arestas, ou atalhos através de regiões incertas, devem ser adicionadas ao gráfico para reduzir o tempo total de viagem.
Selecionando atalhos
Ao selecionar apenas atalhos que provavelmente serão percorríveis, o algoritmo evita que o processo de planejamento se torne desnecessariamente complicado.
“A qualidade do plano de movimento depende da qualidade do gráfico. Se esse gráfico não tiver bons caminhos, o algoritmo não poderá fornecer um bom plano”, explica Veys.
Depois de testar o algoritmo em mais de 100 experimentos simulados com ambientes cada vez mais complexos, os pesquisadores descobriram que ele poderia superar consistentemente os métodos básicos que não consideram probabilidades. Eles também o testaram usando um mapa aéreo do campus do MIT para mostrar que poderia ser eficaz em ambientes urbanos do mundo real.
No futuro, eles querem aprimorar o algoritmo para que ele possa funcionar em mais de duas dimensões, o que poderia permitir seu uso em problemas complicados de manipulação robótica. Eles também estão interessados em estudar a incompatibilidade entre os gráficos CTP e os ambientes do mundo real que esses gráficos representam.
“Os robôs que operam no mundo real são atormentados pela incerteza, seja nos dados dos sensores disponíveis, no conhecimento prévio sobre o ambiente ou sobre como outros agentes se comportarão. Infelizmente, lidar com essas incertezas acarreta um alto custo computacional”, diz Seth Hutchinson, professor e Cátedra KUKA de Robótica na Escola de Computação Interativa da Georgia Tech, que não esteve envolvido nesta pesquisa. “Este trabalho aborda essas questões propondo um esquema de aproximação inteligente que pode ser usado para calcular de forma eficiente planos tolerantes à incerteza.”
Esta pesquisa foi financiada, em parte, pelos Laboratórios de Pesquisa do Exército dos EUA sob a Aliança de Pesquisa Colaborativa de Sistemas e Tecnologias Inteligentes Colaborativas Distribuídas e pela Bolsa de Pós-Graduação Joseph T. Corso e Lily Corso.
Publicado em 25/03/2024 21h00
Artigo original:
Link original: