A Competitive Algorithm for Online Multi-Robot Exploration of a Translating Plume
Yoonchang Sung, Pratap Tokekar
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 2(Sr + Sp)(R+⌊log R⌋)/(Sr + Sp)(R+⌊log R⌋) where R is the number of robots, and Sr and Sp 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 2(Sr + Sp)(18 R+⌊log R⌋)/(Sr + Sp)(1+⌊log R⌋) competitive ratio under the fat condition. We empirically verify our algorithm using simulations.
BibTeX
@inproceedings{icra2019_acompetitivealgo,
title = {A Competitive Algorithm for Online Multi-Robot Exploration of a Translating Plume},
author = {Yoonchang Sung and Pratap Tokekar},
booktitle = {ICRA 2019},
year = {2019}
}