Full text
| |
| Author(s): |
Lucas de Oliveira Silva
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2025-03-10 |
| Examining board members: |
Lehilton Lelis Chaves Pedrosa;
Guilherme de Castro Mendes Gomes;
Orlando Lee
|
| Advisor: | Lehilton Lelis Chaves Pedrosa |
| Abstract | |
Swarm robotics is the study of systems composed of autonomous agents, with various applications ranging from the organization of agricultural machinery to satellite coordination. The need to control or schedule the agents' operations often leads to NP-hard optimization problems. One example is the Freeze-Tag Problem (FTP), whose goal is to activate a set of robots in a metric space starting with a single active robot. Each active robot can activate an inactive robot by moving to it, which takes time proportional to the distance traveled. The objective is to find an activation strategy that minimizes the total time to activate all robots. In this thesis, we study the complexity and present algorithms for several subcases of FTP and related problems. Although FTP has been widely studied in various metric spaces, determining whether the problem is NP-hard for the L1 metric in each Euclidean space R^d has remained an open question for over twenty years. In this work, we partially answer this question and show that the problem is strongly NP-hard for the L1 metric in R^d when d = 3. Furthermore, we show that the problem remains hard even if we restrict it to instances with metrics induced by trees with bounded degrees. For the case of unweighted graphs, we show that it is NP-hard to approximate FTP by a factor of at most 3/2, even if the graph has diameter two and the instance contains at least one robot per vertex. From a practical standpoint, we present two mixed-integer linear programming formulations and one constraint programming formulation. We tested these formulations with existing solvers and compared the results with a greedy strategy used in the literature. Additionally, we adapt the polynomial-time approximation scheme (PTAS) for Euclidean space by Arkin et al., converting it into an algorithm with an approximation quality guarantee that can run in practice. Finally, we explore satellite swarm coordination problems aimed at data transmission via peer-to-peer communication. First, we investigated the Angular Freeze-Tag Problem (AFTP), a variation of FTP. In AFTP, the activation of an inactive satellite occurs when an active satellite points its antenna toward it, using only the rotation of its antenna without any physical movement. Next, we consider the Minimum Scan Cover (MSC), where we also aim to coordinate antenna rotation for data transmission between satellites, but data transmission is required only between a subset of pairs of satellites corresponding to the edges of an input graph. In this thesis, we begin the study of the parameterized complexity of these problems, identifying inherent difficulties related to angular costs and introducing suitable parameters that allow the design of parameterized algorithms or parameterized approximation algorithms (AU) | |
| FAPESP's process: | 22/13435-4 - Parameterized Algorithms for the Freeze-Tag Problem over Different Domains |
| Grantee: | Lucas de Oliveira Silva |
| Support Opportunities: | Scholarships in Brazil - Master |