Multi-robot decision-making is the process where multiple robots coordinate actions. In this paper, we aim for scalable and reliable multi-robot decision-making despite the robots' limited on-board resources and the resource-demanding complexity of their tasks. We introduce the first algorithm that enables robots to choose with which other robots to coordinate, balancing 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 and area covering. To provide closed-form characterizations, we focus on maximization problems involving monotone and "doubly" 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.
翻译:多机器人决策是多个机器人协调行动的过程。 在本文中,我们的目标是,尽管机器人在机上资源有限,而且任务要求很复杂,但仍进行可扩缩和可靠的多机器人决策。我们引入了第一个算法,使机器人能够选择与哪些其他机器人协调,平衡集中式与分散式协调的权衡。特别是,集中化有利于全球接近最佳的决策,但成本却增加了机上的资源需求;而分散化有利于最低的资源需求,但费用却低于全球。因此,所有机器人都能够负担得起我们的算法,而不管他们的资源如何。我们受到自主权的未来的驱动,它涉及多个机器人协调行动以完成资源需求任务,例如目标跟踪和覆盖的领域。为了提供封闭式的特征描述,我们把重点放在与单体和“摇晃动式”子功能有关的最大化问题上。为了了解分散化的成本,我们引入了非维里博托尔(COIN)中间信息集中化的概念。我们验证了我们模拟图像情景的算法。