Soutenance de thèse : Xiao PENG

Planning Problems in a Multi-Tethered-Robot System

Doctorante : Xiao PENG

Laboratoire INSA : CITI
Ecole doctorale : ED512 : Infomaths

Multiple robot systems are widely applied in our real life. As a special type of mobile system, tethered robots play a crucial role in special contexts, particularly in challenging conditions, where cables provide stable access to power and network connectivity. However, constraints imposed by cables also introduce new challenges for motion planning in these applications. This thesis focuses on planning problems for a team of tethered robots, addressing two major problems: non-crossing Anonymous Multi-Agent Path Finding (AMAPF) and Multiple Tethered Coverage Path Planning (MTCPP).

The goal of non-crossing AMAPF is to find a set of non-crossing paths such that the makespan is minimal. The study is carried out in two cases, considering whether the robots are treated as point-sized or not. This hypothesis significantly influences the computation of makespan. The problem is abstracted to the Euclidean Bipartite Assignment problem and we show that bounds can be efficiently computed by solving linear assignment problems. We introduce a variable neighborhood search method to improve upper bounds, and a Constraint Programming model to compute optimal solutions. The approach is experimentally evaluated on three different kinds of instances.

The MTCPP problem is addressed by initially partitioning the workspace into equitable connected subregions, enabling each robot to operate independently in its assigned area. We propose an approach based on the additively weighted Voronoi diagram, ensuring an equitable partitioning that enforces relative star-convexity of each subregion to the associated anchor point, thereby avoiding cable entanglement. For the coverage path planning of each robot, the Spanning Tree Coverage method is shown to effectively solve the problem while respecting cable constraints.