Multi-Covering a Point Set by $m$ Disks with Minimum Total Area
Mariem Guitouni, Chek-Manh Loi, Sándor P. Fekete, Michael Perk, Aaron T. Becker
Abstract
A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$p$</tex> to be monitored by at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\kappa(p)$</tex> sen-sors. Given <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> assets that must be observed by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> sensors, each with a disk-shaped sensing region, where should the sensors be placed to minimize the total area observed? We provide and analyze a fast heuristic for this problem. We then use the heuristic to initialize an exact Integer Program-ming solution. Subsequently, we enforce separation constraints between the sensors by modifying the integer program formulation and by changing the disk candidate set.
BibTeX
@inproceedings{icra2025_multicoveringapo,
title = {Multi-Covering a Point Set by $m$ Disks with Minimum Total Area},
author = {Mariem Guitouni and Chek-Manh Loi and Sándor P. Fekete and Michael Perk and Aaron T. Becker},
booktitle = {ICRA 2025},
year = {2025}
}