Distributed Attack-Robust Submodular Maximization for Multirobot Planning
Lifeng Zhou, Vasileios Tzoumas, George J. Pappas, Pratap Tokekar
Abstract
In this article, we design algorithms to protect swarm-robotics applications against sensor denial-of-service attacks on robots. We focus on applications requiring the robots to jointly select actions, e.g., which trajectory to follow, among a set of available actions. Such applications are central in large-scale robotic applications, such as multirobot motion planning for target tracking. But the current attack-robust algorithms are centralized. In this article, we propose a general-purpose distributed algorithm toward robust optimization at scale, with local communications only. We name it <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">distributed robust maximization</i> ( <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> ). <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> proposes a divide-and-conquer approach that distributively partitions the problem among cliques of robots. Then, the cliques optimize in parallel, independently of each other. We prove <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> achieves a close-to-optimal performance. We demonstrate <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> ’s performance in Gazebo and MATLAB simulations, in scenarios of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">active target tracking with swarms of robots</i> . In the simulations, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> achieves computational speed-ups, being 1 to 2 orders faster than the centralized algorithms. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Yet</i> , it nearly matches the tracking performance of the centralized counterparts. Since, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> overestimates the number of attacks in each clique, in this article, we also introduce an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">improved distributed robust maximization</i> ( <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">IDRM</monospace> ) algorithm. <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">IDRM</monospace> infers the number of attacks in each clique less conservatively than <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> by leveraging three-hop neighboring communications. We verify <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">IDRM</monospace> improves <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DRM</monospace> ’s performance in simulations.