Discrete Optimal Transport for Robot Swarms

Sammanfattning

There is a growing interest in applications where swarms of agents - i.e., robots or drones -collaborate to solve complex tasks, such as search-and-rescue missions, environmentalmonitoring, automated delivery systems etc. Traditional control approaches, like modelpredictive control, typically design strategies for each agent individually. However, in swarmsettings, it is often more effective to coordinate agents collectively, enabling globally optimaltask assignment and execution. A powerful recent approach to this challenge is the optimaltransport problem, a classical mathematical theory with strong foundations and wide-rangingapplications in logistics, economics, computer vision, machine learning, and control theory. This thesis focuses on discrete optimal transport to solve anonymous multi-agent path finding (AMAPF), i.e. finding optimal paths from a set of agents to a set of targets, building on previouswork by A. Khan et al. and their proposed method for model predictive optimal transport. Itimplicitly handles collisions via a formulation that guarantees non-overlapping trajectories, which is shown to cause infeasibility or suboptimality in some relevantedge cases. A possible solution is proposed, extending the optimal transport formulation forAMAPF through a time-discretization approach with arbitrarily many margins.