Texto completo
| |
| Autor(es): |
Lucas de Oliveira Silva
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2025-03-10 |
| Membros da banca: |
Lehilton Lelis Chaves Pedrosa;
Guilherme de Castro Mendes Gomes;
Orlando Lee
|
| Orientador: | Lehilton Lelis Chaves Pedrosa |
| 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 FTP tenha sido amplamente estudado em diversos espaços métricos, determinar se o problema é NP-difícil para a métrica L1 em cada espaço euclidiano R^d é 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 L1 em R^d 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 ao menos 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 estudos 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 (AU) | |
| Processo FAPESP: | 22/13435-4 - Algoritmos Parametrizados para o Freeze-Tag Problem sobre Diferentes Domínios |
| Beneficiário: | Lucas de Oliveira Silva |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |