10 Mar 2025
10:00 Master's Defense Room 85 of IC2
Topic
Algorithms for Freeze-Tag and Related Swarm Robotics Problems
Student
Lucas de Oliveira Silva
Advisor / Teacher
Lehilton Lelis Chaves Pedrosa
Brief summary
Swarm robotics is the study of systems composed of autonomous agents, with diverse applications, ranging from the organization of agricultural machinery to the coordination of satellites. The need to control or schedule agents' operations often leads to NP-hard optimization problems. An example is the Freeze-Tag Problem (FTP), in which one wants to activate a set of robots in a metric space starting from a single active robot. Each active robot can activate an inactive robot by moving towards it, which takes time proportional to the distance traveled. The goal is to find an activation strategy that minimizes the total time to activate all robots. In this dissertation, we study the complexity and present algorithms for several subcases of FTP and related problems.
Although FPT has been extensively studied in several metric spaces, determining whether the problem is NP-hard for the metric L₁ in each Euclidean space Rᵈ is a question that has remained open for more than twenty years. In this work, we partially resolve this issue and demonstrate that the problem is strongly NP-hard for the metric L₁ on Rᵈ when d ≥ 3. Furthermore, we show that the problem remains hard even if we restrict it to instances with metrics induced by bounded-degree trees. For the case of graphs without edge weights, we show that it is NP-hard to approximate the FTP by a factor less than or equal to 3/2, even if the graph has diameter two and the instance contains exactly one robot per vertex.
From a practical point of view, 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 guaranteed approximation quality that can be executed in practice.
Finally, we explore satellite swarm coordination problems that aim at data transmission via peer-to-peer communication. First, we investigate the Angular Freeze-Tag Problem (AFTP), a variation of FTP. In AFTP, activation of an inactive satellite occurs when an active satellite points its antenna towards it, using only the rotation of its antenna, without physical displacement. Next, we consider Minimum Scan Cover (MSC), in which it is also desired to coordinate antenna rotation for data transmission between satellites, but in which data transmission is required only between a subset of satellite pairs corresponding to the edges of an input graph.
Examination Board
Headlines:
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Guilherme de Castro Mendes Gomes | DCC / UFMG |
| Orlando Lee | IC / UNICAMP |
Substitutes:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Carla Negri Lintzmayer | CMCC / UFABC |