Algoritmos para o freeze-tag e problemas de robótica de enxame relacionados

• Processo: 23/12529-8
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 31 de janeiro de 2024
• Data de Término da vigência: 30 de julho de 2024
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Lehilton Lelis Chaves Pedrosa
• Beneficiário: Lucas de Oliveira Silva
• Supervisor: Sandor P. Fekete
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: University of Technology Braunschweig, Alemanha
• Vinculado à bolsa: 22/13435-4 - Algoritmos Parametrizados para o Freeze-Tag Problem sobre Diferentes Domínios, BP.MS
• Assunto(s): Algoritmos de aproximação Análise de algoritmos Geometria computacional Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | análise de algoritmos | Geometria Computacional | Robótica de Enxame | teoria dos grafos | análise de algoritmos

Resumo

A robótica de enxame é um tópico de interesse crescente, impulsionado principalmente por várias aplicações práticas bem-sucedidas, desde o escalonamento de maquinário agrícola até o controle de satélites ao redor da Terra. A necessidade de controlar ou escalonar operações com robôs frequentemente leva a problemas de otimização intratáveis do ponto de vista computacional. Até agora no mestrado, concentramos nossos esforços em estudar a complexidade e a parametrização do Freeze-Tag Problem (FTP), que consiste em ativar um enxame de robôs no menor tempo possível. No que diz respeito ao FTP, temos dois trabalhos aceitos sobre sua complexidade, o primeiro apresentado no VII Encontro de Teoria da Computação (ETC 23) e o segundo a ser apresentado no XII Simpósio Latino-Americano de Algoritmos, Gráficos e Otimização (LAGOS 23). Além disso, outros resultados algorítmicos estão em andamento. Nesta nova pesquisa, temos como objetivo complementar nosso projeto atual estudando e desenvolvendo algoritmos para problemas relacionados, principalmente ao controle de enxames de satélites, um tópico com muitas questões em aberto e direções de pesquisa promissoras. Como exemplo, gostaríamos de estudar o problema de distribuir dados de missões espaciais entre satélites, problema que se assemelha ao FTP, mas cujas operações correspondem a rotações com custos angulares. Enquanto o FTP se concentra na ativação, ele é apenas um passo na coordenação de enxames de robôs. Portanto, ao expandir nosso escopo para incluir esses outros problemas de robótica em enxames, com este estágio e a experiência adicional do Dr. Fekete, podemos produzir um trabalho muito mais completo. (AU)