Algorithms for the freeze-tag and related swarm robotics problems

• Grant number: 23/12529-8
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: January 31, 2024
• End date: July 30, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Lehilton Lelis Chaves Pedrosa
• Grantee: Lucas de Oliveira Silva
• Supervisor: Sandor P. Fekete
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Technology Braunschweig, Germany
• Associated to the scholarship: 22/13435-4 - Parameterized Algorithms for the Freeze-Tag Problem over Different Domains, BP.MS

Abstract

Swarm robotics is a topic of ever-growing interest mainly driven by several successful practical applications, from scheduling agriculture machinery to controlling satellites around Earth. The need to control or schedule robot operations often leads to intractable optimization problems. The candidate's Master's research project focuses on studying the complexity and parameterization of the Freeze-Tag Problem (FTP), which is the task of activating a robot swarm within minimum time. For FTP, we have two accepted works about its complexity, the first presented in the VII Encontro de Teoria da Computação (ETC 23), and the second to be presented in the XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 23). Also, other algorithmic results are in progress. In this internship proposal, we aim to complement the Master's project by studying and designing algorithms for related problems, mainly controlling satellite swarms, a topic with many open questions and exciting research directions. For one example, we would like to study the problem of distributing mission data among satellites, which resembles FTP but whose operations correspond to rotations with corresponding angular costs. While FTP concentrates on activation, it is only one step in robot swarm coordination. Thus, by expanding our scope to include these other swarm robotics problems, with this internship and the added expertise of Dr. Fekete, we can produce a much more complete work. (AU)