# Leveraging Untrustworthy Commands for Multi-Robot Coordination in Unpredictable Environments: A Bandit Submodular Maximization Approach

arXiv: https://arxiv.org/abs/2309.16161 · HTML: https://mlsanity.com/paper/2309.16161/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 40 references that are in the map.
- First posted on arXiv 28 Sep 2023.

## Builds on (most cited first, 21 of 21)

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [The Limits and Potentials of Deep Learning for Robotics](https://mlsanity.com/paper/1804.06557/) (2018)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Efficient Informative Sensing using Multiple Robots](https://mlsanity.com/paper/1401.3462/) (2014)
- [Distributed Submodular Maximization with Limited Information](https://mlsanity.com/paper/1706.04082/) (2017)
- [Black Box Submodular Maximization: Discrete and Continuous Settings](https://mlsanity.com/paper/1901.09515/) (2019)
- [Optimal Algorithms for Submodular Maximization with Distributed Constraints](https://mlsanity.com/paper/1909.13676/) (2019)
- [Resilient Active Information Acquisition with Teams of Robots](https://mlsanity.com/paper/2103.02733/) (2021)
- [Scalable Operator Allocation for Multi-Robot Assistance: A Restless Bandit Approach](https://mlsanity.com/paper/2111.06437/) (2021)
- [Distributed Resilient Submodular Action Selection in Adversarial Environments](https://mlsanity.com/paper/2105.07305/) (2021)
- [The Impact of Information in Greedy Submodular Maximization](https://mlsanity.com/paper/1807.10639/) (2018)
- [Execution Order Matters in Greedy Algorithms with Limited Information](https://mlsanity.com/paper/2111.09154/) (2021)
- [Scalable Distributed Planning for Multi-Robot, Multi-Target Tracking](https://mlsanity.com/paper/2107.08550/) (2021)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Active Inference for Autonomous Decision-Making with Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2209.09185/) (2022)
- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [An Upper Confidence Bound for Simultaneous Exploration and Exploitation in Heterogeneous Multi-Robot Systems](https://mlsanity.com/paper/2105.06118/) (2021)

## Abstract (arXiv)

We study the problem of multi-agent coordination in unpredictable and partially-observable environments with untrustworthy external commands. The commands are actions suggested to the robots, and are untrustworthy in that their performance guarantees, if any, are unknown. Such commands may be generated by human operators or machine learning algorithms and, although untrustworthy, can often increase the robots' performance in complex multi-robot tasks. We are motivated by complex multi-robot tasks such as target tracking, environmental mapping, and area monitoring. Such tasks are often modeled as submodular maximization problems due to the information overlap among the robots. We provide an algorithm, Meta Bandit Sequential Greedy (MetaBSG), which enjoys performance guarantees even when the external commands are arbitrarily bad. MetaBSG leverages a meta-algorithm to learn whether the robots should follow the commands or a recently developed submodular coordination algorithm, Bandit Sequential Greedy (BSG) [1], which has performance guarantees even in unpredictable and partially-observable environments. Particularly, MetaBSG asymptotically can achieve the better performance out of the commands and the BSG algorithm, quantifying its suboptimality against the optimal time-varying multi-robot actions in hindsight. Thus, MetaBSG can be interpreted as robustifying the untrustworthy commands. We validate our algorithm in simulated scenarios of multi-target tracking.