Title: A Competitive Algorithm for Online Multi-Robot Exploration of a Translating Plume,
Abstract: In this paper, we study the problem of exploring a translating plume with a
team of aerial robots. The shape and the size of the plume are unknown to the
robots. The objective is to find a tour for each robot such that they
collectively explore the plume. Specifically, the tours must be such that each
point in the plume must be visible from the field-of-view of some robot along
its tour. We propose a recursive Depth-First Search (DFS)-based algorithm that
yields a constant competitive ratio for the exploration problem. The
competitive ratio is
$\frac{2(S_r+S_p)(R+\lfloor\log{R}\rfloor)}{(S_r-S_p)(1+\lfloor\log{R}\rfloor)}$
where $R$ is the number of robots, and $S_r$ and $S_p$ are the robot speed and
the plume speed, respectively. We also consider a more realistic scenario where
the plume shape is not restricted to grid cells but an arbitrary shape. We show
our algorithm has
$\frac{2(S_r+S_p)(18R+\lfloor\log{R}\rfloor)}{(S_r-S_p)(1+\lfloor\log{R}\rfloor)}$
competitive ratio under the fat condition. We empirically verify our algorithm
using simulations.