Title: Min-Time Coverage in Constricted Environments

Date: November 21, 2025

Time: 2:00 pm – 4:00 pm (EST)

Location: Groseclose 304 

Zoom link: https://gatech.zoom.us/j/91872907695

Young-In Kim

Ph.D. Candidate in Industrial Engineering

School of Industrial and Systems Engineering

Georgia Institute of Technology

Committee:

1. Dr. Spyros Reveliotis(Advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology
2. Dr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
3. Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
4. Dr. Alejandro Toriello, School of Industrial and Systems Engineering, Georgia Institute of Technology
5. Dr. Seth Hutchinson, College of Computer Sciences and Department of Electrical and Computer Engineering, Northeastern University

Abstract:

We address a new set of time-optimal coverage problems in the area of networked robotic systems, where a fleet of mobile robots must execute a set of inspection tasks in a constricted operational environment. The robots are separated from each other by adhering to a zoning policy, and furthermore, they must maintain a multi-hop wireless communication network connecting them with each other and with a command and control center that supervises the entire operation. These requirements give rise to resource allocation structures and traffic dynamics that transcend the state of the art of the corresponding theory and challenge our current understandings and insights for these dynamics and their effective management. We provide a systematic introduction of the considered problems and of the elements that differentiate them from similar task allocations and traffic scheduling problems already studied in the literature. The presented developments and the results for the considered problems are organized into three main stages.

The first stage (Chapters 2 - 4) addresses the special cases of the considered problems where the robot fleets are homogeneous in terms of their operational capabilities and they operate in tree-structured guidepath networks. More specifically, in Chapter 2, we provide a complete characterization of these special problem versions in the form of mathematical programming (MP) formulations, and a formal analysis of their worst-case computational complexity. In Chapter 3, we establish some structural results for these problem versions that are useful for the strengthening of the aforementioned MP formulations. Furthermore, we introduce strong combinatorial relaxations of the aforementioned MP formulations for the considered problem versions and an efficient post-processing algorithm that constructs an optimal solution for the original formulation from an optimal solution of these relaxations. In Chapter 4, we employ the insights and the results of the previous chapters towards the development of an efficient heuristic algorithm for addressing larger problem instances.

In the second stage (Chapters 5 and 6), we extend our investigation to the more general cases of the considered problems where the underlying guidepath networks have arbitrary topologies. In Chapter 5, we provide a detailed characterization of the considered MMRS operations and the ensuing traffic management problems in this new setting, and formulate these new problems as integer programs (IPs). Furthermore, we establish that it is possible to relax the integrality requirement for a large subset of the decision variables in these IPs without compromising the feasibility and the optimality of the obtained solutions. In Chapter 6, we develop a heuristic algorithm for the general problem versions. The development of the heuristic capitalizes on the insights and the results for the special versions in the first stage: the heuristic (i) constructs systematically a pertinently selected subtree that is rooted at the command and control center and contains all target locations, and then (ii) solves the induced restriction by adapting the computation procedures of the heuristic for the special problem versions in Chapter 4. This approach enables the computation of good-quality solutions for large-scale problem instances that remain intractable for the relaxations developed in Chapter 5.

In the third stage (Chapter 7), we address the problem versions where the robotic fleet is heterogeneous. In this setting, the tasks at the target locations must be executed by specific robot types equipped with the required capabilities. We provide a detailed characterization of the corresponding MMRS operations under heterogeneous robotic fleets, and the ensuing traffic-management problems. We formulate these problems as dynamic, integer multi-commodity flow problems. Furthermore, we develop strong combinatorial relaxations of the derived IP formulations that reduce the number of integer variables involved while maintaining the feasibility of the obtained solutions.