4.7 Article

Distributed Attack-Robust Submodular Maximization for Multirobot Planning

Journal

IEEE TRANSACTIONS ON ROBOTICS
Volume 38, Issue 5, Pages 3097-3112

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TRO.2022.3161765

Keywords

Robot sensing systems; Robot kinematics; Planning; Approximation algorithms; Multi-robot systems; Task analysis; Target tracking; Adversarial attacks; approximation algorithm; distributed optimization; multirobot planning; robust optimization; submodular optimization; target tracking

Categories

Funding

  1. National Science Foundation [1943368]
  2. Office of Naval Research [N000141812829]
  3. ARL CRA DCIST
  4. U.S. Department of Defense (DOD) [N000141812829] Funding Source: U.S. Department of Defense (DOD)
  5. Direct For Computer & Info Scie & Enginr
  6. Div Of Information & Intelligent Systems [1943368] Funding Source: National Science Foundation

Ask authors/readers for more resources

In this article, algorithms are designed to protect swarm-robotics applications against sensor denial-of-service attacks, and a distributed robust maximization algorithm is proposed. The distributed approach improves computational speed and achieves tracking performance comparable to centralized algorithms in simulations. Additionally, an improved distributed robust maximization algorithm is introduced to infer attack quantities more accurately.
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 distributed robust maximization (DRM). DRM 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 DRM achieves a close-to-optimal performance. We demonstrate DRM's performance in Gazebo and MATLAB simulations, in scenarios of active target tracking with swarms of robots. In the simulations, DRM achieves computational speed-ups, being 1 to 2 orders faster than the centralized algorithms. Yet, it nearly matches the tracking performance of the centralized counterparts. Since, DRM overestimates the number of attacks in each clique, in this article, we also introduce an improved distributed robust maximization (IDRM) algorithm. IDRM infers the number of attacks in each clique less conservatively than DRM by leveraging three-hop neighboring communications. We verify IDRM improves DRM's performance in simulations.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available