Distributed Task Allocation for Multi-Agent Systems: A Submodular Optimization Approach

作     者：Liu, Jing Li, Fangfei Jin, Xin Tang, Yang 

作者机构：School of Mathematics East China University of Science and Technology Shanghai200237 China School of Mathematics Key Laboratory of Smart Manufacturing in Energy Chemical Process Ministry of Education East China University of Science and Technology Shanghai200237 China Research Institute of Intelligent Complex Systems Fudan University Shanghai200433 China Key Laboratory of Smart Manufacturing in Energy Chemical Process Ministry of Education East China University of Science and Technology Shanghai200237 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Micro satellites 

摘      要：This paper investigates dynamic task allocation for multi-agent systems (MASs) under resource constraints, with a focus on maximizing the global utility of agents while ensuring a conflict-free allocation of targets. We present a more adaptable submodular maximization framework for the MAS task allocation under resource constraints. Our proposed distributed greedy bundles algorithm (DGBA) is specifically designed to address communication limitations in MASs and provides rigorous approximation guarantees for submodular maximization under q-independent systems, with low computational complexity. Specifically, DGBA can generate a feasible task allocation policy within polynomial time complexity, significantly reducing space complexity compared to existing methods. To demonstrate practical viability of our approach, we apply DGBA to the scenario of active observation information acquisition within a micro-satellite constellation, transforming the NP-hard task allocation problem into a tractable submodular maximization problem under a q-independent system constraint. Our method not only provides a specific performance bound but also surpasses benchmark algorithms in metrics such as utility, cost, communication time, and running time. Copyright © 2024, The Authors. All rights reserved.