10 mar 2025
10:00 Defesa de Mestrado Sala 85 do IC2
Tema
Algoritmos para o Freeze-Tag e Problemas de Robótica de Enxame Relacionados
Aluno
Lucas de Oliveira Silva
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve resumo
Robótica de enxame é o estudo de sistemas compostos por agentes autônomos, com diversas aplicações, que vão desde a organização de maquinário agrícola até a coordenação de satélites. A necessidade de controlar ou agendar operações dos agentes frequentemente leva a problemas de otimização NP-difíceis. Um exemplo é o Problema do Freeze-Tag (FTP), em que se deseja ativar um conjunto de robôs em um espaço métrico partindo-se de um único robô ativo. Cada robô ativo pode ativar um robô inativo movendo-se até ele, o que leva tempo proporcional à distância percorrida. O objetivo é encontrar uma estratégia de ativação que minimize o tempo total para ativar todos os robôs. Nesta dissertação, estudamos a complexidade e apresentamos algoritmos para vários subcasos do FTP e problemas relacionados.
Embora o FPT tenha sido amplamente estudado em diversos espaços métricos, determinar se o problema é NP-difícil para a métrica L₁ em cada espaço euclideano Rᵈ é uma questão que permanece em aberto há mais de vinte anos. Neste trabalho, resolvemos essa questão parcialmente e demonstramos que o problema é fortemente NP-difícil para a métrica L₁ em Rᵈ quando d ≥ 3. Além disso, mostramos que o problema permanece difícil mesmo se o restringirmos às instâncias com métricas induzidas por árvores com graus limitados. Para o caso de grafos sem pesos nas arestas, mostramos que é NP-difícil aproximar o FTP por um fator menor ou igual a 3/2, mesmo que o grafo tenha diâmetro dois e a instância contenha exatamente um robô por vértice.
Do ponto de vista prático, apresentamos duas formulações de programação linear inteira mista e uma formulação de programação por restrições. Nós testamos essas formulações com resolvedores existentes e comparamos os resultados com uma estratégia gulosa utilizada na literatura. Adicionalmente, adaptamos o esquema de aproximação de tempo polinomial (PTAS) para espaço euclidiano de Arkin et al., convertendo-o em um algoritmo com garantia de qualidade de aproximação e que pode ser executado na prática.
Finalmente, exploramos problemas de coordenação de enxame de satélites que têm por objetivo a transmissão de dados via comunicação par-a-par. Primeiramente, investigamos o Problema do Freeze-Tag Angular (AFTP), uma variação do FTP. No AFTP, a ativação de um satélite inativo ocorre quando um satélite ativo direciona sua antena para ele, utilizando apenas a rotação de sua antena, sem deslocamento físico. Depois, consideramos o Minimum Scan Cover (MSC), em que também se deseja coordenar a rotação de antenas para transmissão de dados entre satélites, mas em que é necessária transmissão de dados apenas entre um subconjunto de pares de satélites correspondentes às arestas de um grafo de entrada. Nesta dissertação, iniciamos os estudo de complexidade parametrizada desses problemas, identificando dificuldades inerentes aos custos angulares e introduzindo parâmetros adequados que permitem a obtenção de algoritmos parametrizados, ou algoritmos de aproximação parametrizados.
Banca examinadora
Titulares:
Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
Guilherme de Castro Mendes Gomes | DCC/UFMG |
Orlando Lee | IC/UNICAMP |
Suplentes:
Flávio Keidi Miyazawa | IC/UNICAMP |
Carla Negri Lintzmayer | CMCC/UFABC |