Decentralized Game-based Auction Algorithm for Scheduling Robotic Chargers to Service EVs with Uncertain Demands

作     者：Fang, Qiuyang Zhang, Jianlei Wang, Chen Xie, Guangming Zhang, Chunyan 

作者机构：Department of Automation College of Computer and Control Engineering Nankai University Tianjin China National Engineering Research Center of Software Engineering Peking University Beijing China State Key Laboratory for Turbulence and Complex Systems Intelligent Biomimetic Design Lab College of Engineering Peking University Beijing China 

出 版 物：《IEEE Transactions on Intelligent Vehicles》 (IEEE Trans. Intell. Veh.)

年 卷 期：2024年

页      面：1-14页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0837[工学-安全科学与工程] 0811[工学-控制科学与工程] 0701[理学-数学] 

主　　题：Polynomial approximation 

摘      要：In this study, we introduce a novel auction-based algorithm modeled as a decentralized coalition formation game, designed for the complex requirements of large-scale multi-robot task allocation under uncertain demand. This context is particularly illustrative in scenarios where robots are tasked to charge electric vehicles. The algorithm begins by partitioning a composite task sequence into distinct subsets based on spatial similarity principles. Subsequently, we employ a coalition formation game paradigm to coordinate the assembly of robots into cooperative coalitions focused on these distinct subsets. To mitigate the impact of unpredictable task demands on allocations, our approach utilizes the conditional value-at-risk to assess the risk associated with task execution, along with computing the potential revenue of the coalition with an emphasis on risk-related outcomes. Additionally, integrating consensus auctions into the coalition formation framework allows our approach to accommodate assignments for individual robot-task pairings, thus preserving the stability of individual robotic decision autonomy within the coalition structure and assignment distribution. Simulative analyses on a prototypical parking facility layout confirm that our algorithm achieves Nash equilibrium within the coalition structure in polynomial time and demonstrates significant scalability. Compared to competing algorithms, our proposal exhibits superior performance in resilience, task execution efficiency, and reduced overall task completion times. The results demonstrate that our approach is an effective strategy for solving the scheduling challenges encountered by multi-robot systems operating in complex environments. IEEE