Robust Multi-Robot Active Target Tracking Against Sensing and Communication Attacks

Abstract

The problem of multi-robot target tracking asks for actively planning the joint motion of robots to track targets. In this article, we focus on such target tracking problems in adversarial environments, where attacks or failures may deactivate robots' sensors and communications. In contrast to the previous works that consider no attacks or sensing attacks only, we formalize the first robust multi-robot tracking framework that accounts for any fixed numbers of worst-case sensing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">and</i> communication attacks. To secure against such attacks, we design the first robust planning algorithm, named <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Robust Active Target Tracking</i> ( <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> ), which approximates the communication attacks to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">equivalent</i> sensing attacks and then optimizes against the approximated and original sensing attacks. We show that <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> provides provable suboptimality bounds on the tracking quality for any non-decreasing objective function. Our analysis utilizes the notations of curvature for set functions introduced in combinatorial optimization. In addition, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> runs in polynomial time and terminates with the same running time as state-of-the-art algorithms for (non-robust) target tracking. Finally, we evaluate <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> with both the qualitative and quantitative simulations across various scenarios. In the evaluations, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> exhibits a tracking quality that is near-optimal and superior to varying non-robust heuristics. We also demonstrate <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">RATT</monospace> ’s superiority and robustness against varying attack models (e.g., worst-case and bounded rational attacks) and with over- and under-estimated numbers of attacks.