Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918349809647616 |
|---|---|
| author | Xu, Zirui Tzoumas, Vasileios |
| author_facet | Xu, Zirui Tzoumas, Vasileios |
| contents | Multi-robot decision-making is the process where multiple robots coordinate actions. In this paper, we aim for efficient and effective multi-robot decision-making despite the robots' limited on-board resources and the often resource-demanding complexity of their tasks. We introduce the first algorithm enabling the robots to choose with which few other robots to coordinate and provably balance the trade-off of centralized vs. decentralized coordination. Particularly, centralization favors globally near-optimal decision-making but at the cost of increased on-board resource requirements; whereas, decentralization favors minimal resource requirements but at a global suboptimality cost. All robots can thus afford our algorithm, irrespective of their resources. We are motivated by the future of autonomy that involves multiple robots coordinating actions to complete resource-demanding tasks, such as target tracking, area coverage, and monitoring. To provide closed-form guarantees, we focus on maximization problems involving monotone and 2nd-order submodular functions. To capture the cost of decentralization, we introduce the notion of Centralization Of Information among non-Neighbors (COIN). We validate our algorithm in simulated scenarios of image covering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_07520 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making Xu, Zirui Tzoumas, Vasileios Optimization and Control Artificial Intelligence Multiagent Systems Robotics Systems and Control Multi-robot decision-making is the process where multiple robots coordinate actions. In this paper, we aim for efficient and effective multi-robot decision-making despite the robots' limited on-board resources and the often resource-demanding complexity of their tasks. We introduce the first algorithm enabling the robots to choose with which few other robots to coordinate and provably balance the trade-off of centralized vs. decentralized coordination. Particularly, centralization favors globally near-optimal decision-making but at the cost of increased on-board resource requirements; whereas, decentralization favors minimal resource requirements but at a global suboptimality cost. All robots can thus afford our algorithm, irrespective of their resources. We are motivated by the future of autonomy that involves multiple robots coordinating actions to complete resource-demanding tasks, such as target tracking, area coverage, and monitoring. To provide closed-form guarantees, we focus on maximization problems involving monotone and 2nd-order submodular functions. To capture the cost of decentralization, we introduce the notion of Centralization Of Information among non-Neighbors (COIN). We validate our algorithm in simulated scenarios of image covering. |
| title | Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making |
| topic | Optimization and Control Artificial Intelligence Multiagent Systems Robotics Systems and Control |
| url | https://arxiv.org/abs/2204.07520 |