为了降低人员的伤亡风险和提升任务的执行效率，具备独立感知和自主决策能力的群组机器人常常被应用于未知探索、灾难救援、军事战争等动态场景中代替人类完成一些危险复杂的工作任务。在该场景中群组机器人系统资源有限且分布不均衡，机器人之间需要通过交互和竞争来分配系统中的资源，因此设计有效的机器人交互方式是实现系统资源高效分配的关键所在。针对动态场景中群组机器人系统资源的分配问题，本文使用拍卖机制从任务优先级和资源偏好度两个角度进行了研究，主要工作如下：

针对资源有限且分布不均衡的动态场景中群组机器人系统的资源分配问题，建立了一种真实的组合双向拍卖模型，并提出了一种基于任务优先级的拍卖机制。首先，根据资源的供求关系把群组机器人划分为资源消费机器人和资源提供机器人。再将资源消费机器人和资源提供机器人之间的资源交易问题抽象为一个组合双向拍卖模型，并综合考虑了资源消费机器人计算任务时间敏感性、资源需求量以及能源消耗，定义了计算任务的优先级函数。其次，在拍卖模型的基础上定义了资源供需双方的收益函数，将系统资源的分配问题定义为一个线性整数规划模型。为了克服组合拍卖系统资源分配结果的计算复杂度，提出了一种基于任务优先级的资源分配算法。为了防止虚假报价降低系统的整体收益，设计了一种真实的定价机制。最后，通过仿真实验从社会福利、资源利用率以及用户满意度等多个角度验证了本文提出的拍卖算法的有效性。

针对群组机器人系统资源拍卖过程中的信息不平衡问题，利用贝叶斯博弈框架对供需双方的报价策略进行了分析与求解，并提出了一种基于资源偏好度的拍卖机制。首先，建立一种组合双向拍卖模型来模拟群组机器人系统中资源消费机器人和资源提供机器人的交易过程。由于系统中机器人的隐私信息不能相互共享，所以又利用贝叶斯博弈框架对资源供需双方的报价策略进行分析与求解。当资源消费机器人和资源提供机器人都采用均衡报价策略参与拍卖时，系统资源难以在多项式时间内求出最优的分配结果，因此本文提出了一种基于资源偏好度的分配算法实现了系统资源的近似最优分配。为了保证资源交易的的公平性，将匹配成功双方报价的平均值作为最终的交易价格。最后，通过仿真实验从社会福利、计算效率以及资源利用率等多个角度证明了本文所提出的拍卖算法更适用于群组机器人系统。

In order to reduce the risk of human casualties and improve the efficiency of task execution, swarm robots with independent perception and autonomous decision-making capabilities are often applied to replace humans to complete some dangerous and complex work tasks in unknown exploration, disaster rescue, military war and other dynamic scenarios. In this scenario, the resources of the swarm robot system are limited and unevenly distributed, and the robots need to interact and compete with each other to allocate the resources in the system. Therefore, designing an effective robot interaction method is the key to realize the efficient allocation of system resources. Aiming at the resource allocation problem of swarm robot system in dynamic scenes, this paper uses auction mechanism to study from two perspectives of task priority and resource preference. The main work is as follows:

For the problem of resource allocation in swarm robot system in the environment of limited and unevenly distributed resources, a real combinatorial double auction model is established, and a priority-based auction mechanism is proposed. Firstly, the swarm robots are divided into resource consuming robots and resource providing robots according to the relationship between supply and demand of resources. Then, the resource trading problem between resource consumer robots and resource provider robots is abstracted as a combinatorial double auction model, and the priority function of computing tasks is defined by considering the time sensitivity, resource demand and energy consumption of computing tasks of resource consumer robots. Then, based on the auction model, the revenue function of resource supply and demand is defined, and the system resource allocation problem is defined as a linear integer programming model. In order to overcome the computational complexity of resource allocation results in combinatorial auction system, this thesis proposed a resource allocation algorithm based on task priority. In order to prevent false offers from reducing the overall revenue of the system, an incentive compatible pricing mechanism is designed. Finally, through simulation experiments, the effectiveness of the proposed auction algorithm was validated from multiple perspectives, including social welfare, resource utilization, and user satisfaction.

Aiming at the problem of information imbalance in the resource auction process of the swarm robot system, we use the Bayesian game framework to analyze and solve the bidding strategies of the supply and demand sides, and propose an auction mechanism based on resource preference degree. Firstly, a combinatorial double auction model was established to simulate the transaction process of resource consumer robots and resource provider robots in the swarm robot system. Since the private information of the robots in the system cannot be shared with each other, the Bayesian game framework is used to analyze and solve the bidding strategy of the resource supply and demand sides. When both resource consuming robots and resource providing robots adopt the equilibrium bidding strategy to participate in the auction, it is difficult to find the optimal allocation result of system resources in polynomial time. Therefore, this thesis proposes an allocation algorithm based on resource preference degree to realize the approximate optimal allocation of system resources. In order to ensure the fairness of the resource transaction, the average value of the two successful matching offers is taken as the final transaction price. Finally, the simulation results show that the auction algorithm proposed in this thesis is more suitable for the swarm robot system from the perspectives of social welfare, computational efficiency and resource utilization.

[1]徐天添,黄晨阳,刘佳等.磁驱动微型机器人的智能控制发展现状[J].机器人,2023,45(05):603-625.

[2]Osaba E, Del Ser J, Iglesias A, et al. Soft computing for swarm robotics: new trends and applications[J]. Journal of Computational Science, 2020, 39: 101049.

[3]范衠,孙福赞,马培立等.基于共识主动性的群体机器人目标搜索与围捕[J].北京理工大学学报,2022,42(02):158-167.

[4]Kondoyanni M, Loukatos D, Maraveas C, et al. Bio-inspired robots and structures toward fostering the modernization of agriculture[J]. Biomimetics, 2022, 7(2): 69..

[5]Akter M, Keya J J, Kayano K, et al. Cooperative cargo transportation by a swarm of molecular machines[J]. Science Robotics, 2022, 7(65): eabm0677.

[6]Keung K L, Chan Y Y, Ng K K H, et al. Edge intelligence and agnostic robotic paradigm in resource synchronisation and sharing in flexible robotic and facility control system[J]. Advanced Engineering Informatics, 2022, 52: 101530.

[7]杨桂松,白高磊,何杏宇,等.面向依赖关系约束的移动群智感知任务协作[J].计算机应用研究,2023,40(09):2626-2632.

[8]雷耀麟,丁文锐,罗祎喆等.无人机数据采集任务中的航迹与资源优化[J/OL].北京航空航天大学学报:1-14[2024-03-27].

[9]孙彦景,李林,王博文等.灾后无人机自组网高动态多信道TDMA调度算法[J/OL].西安电子科技大学学报,1-12[2024-03-27].

[10]Li T, Leng S, Wang Z, et al. Intelligent resource allocation schemes for uav-swarm-based cooperative sensing[J]. IEEE Internet of Things Journal, 2022, 9(21): 21570-21582.

[11]Liu H, Liu S, Zheng K. A reinforcement learning-based resource allocation scheme for cloud robotics[J]. IEEE Access, 2018, 6: 17215-17222.

[12]Afrin M, Jin J, Rahman A, et al. Multi-objective resource allocation for edge cloud based robotic workflow in smart factory[J]. Future generation computer systems, 2019, 97: 119-130.

[13]Tang Q, Zhang J, Yu F, et al. A resource management algorithm for real-time response of mobile ad hoc cloud in swarm robotic system[C]//2018 IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2018: 1171-1176.

[14]孙弋,宋冬冬.群组机器人系统资源分配策略研究[J].西安科技大学学报,2022,42(04):818-825.

[15]Afrin M, Jin J, Rahman A, et al. Robotic edge resource allocation for agricultural cyber-physical system[J]. IEEE Transactions on Network Science and Engineering, 2021, 9(6): 3979-3990.

[16]Chen J, Chen P, Wu Q, et al. A game-theoretic perspective on resource management for large-scale UAV communication networks[J]. China Communications, 2021, 18(1): 70-87.

[17]Xu F, Yang W, Li H. Computation offloading algorithm for cloud robot based on improved game theory[J]. Computers & Electrical Engineering, 2020, 87: 106764.

[18]吕晔,周锐,李兴,等.基于多轮次分布式拍卖的异构多任务分配算法[J/OL].北京航空航天大学学报,1-14[2024-04-04].

[19]刘奔.移动边缘网络中基于拍卖理论的资源分配研究[D].南京:南京邮电大学,2020.

[20]Reza Dibaj S M, Miri A, Mostafavi S A. A cloud priority-based dynamic online double auction mechanism (PB-DODAM)[J]. Journal of Cloud Computing, 2020, 9: 1-26.

[21]Peng X, Ota K, Dong M. Multiattribute-based double auction toward resource allocation in vehicular fog computing[J]. IEEE Internet of Things Journal, 2020, 7(4): 3094-3103.

[22]Zhang M, Kong Z. A multi-attribute double auction and bargaining model for emergency material procurement[J]. International Journal of Production Economics, 2022, 254: 108635.

[23]颜超英,张紫仪,曲映楠等.基于联盟链的双向拍卖碳交易[J/OL].计算机应用:1-8[2024-03-26].

[24]Haggi H, Sun W. Multi-round double auction-enabled peer-to-peer energy exchange in active distribution networks[J]. IEEE Transactions on Smart Grid, 2021, 12(5): 4403-4414.

[25]闫先国,孙碧颖,录鹏东等.智能电网中基于填充方法的双向拍卖电力资源再分配[J/OL].西安交通大学学报:1-10[2024-03-26].

[26]李斌.基于社交网络的拍卖机制设计理论研究[D].成都:电子科技大学,2021.

[27]Li Z, Jiang C, Kuang L. Double auction mechanism for resource allocation in satellite MEC[J]. IEEE Transactions on Cognitive Communications and Networking, 2021, 7(4): 1112-1125.

[28]Alahdadi A, Safaei A A, Ebadi M J. A truthful and budget-balanced double auction model for resource allocation in cloud computing[J].Soft Computing,2023,27(23): 18263-18284.

[29]郑阳超,李珍妮.面向资源最优分配的深度学习双边拍卖算法[J].控制理论与应用,2023,40(10):1863-1872.

[30]Ng J S, Lim W Y B, Xiong Z, et al. A double auction mechanism for resource allocation in coded vehicular edge computing[J]. IEEE Transactions on Vehicular Technology, 2021, 71(2): 1832-1845.

[31]Liu X, Liu J. A truthful double auction mechanism for multi-resource allocation in crowd sensing systems[J]. IEEE Transactions on Services Computing, 2021, 15(5): 2579-2590.

[32]Zhong W, Xie K, Liu Y, et al. Multi-resource allocation of shared energy storage: A distributed combinatorial auction approach[J]. IEEE transactions on smart grid, 2020, 11(5): 4105-4115.

[33]吴雄,麻淞,何雯雯等.具有激励相容和能源共享特性的混合储能组合拍卖[J].西安交通大学学报,2023,57(09):162-173.

[34]Liu Y, Sun S, Wang X V, et al. An iterative combinatorial auction mechanism for multi-agent parallel machine scheduling[J]. International Journal of Production Research, 2022, 60(1): 361-380.

[35]李颖浩,嵩天,杨雅婷.面向边缘计算的组合拍卖式任务卸载机制[J].计算机科学与探索,2021,15(01):73-83.

[36]Yang S. A task offloading solution for internet of vehicles using combination auction matching model based on mobile edge computing[J]. IEEE Access, 2020, 8: 53261-53273.

[37]Guo J, Ding X, Wang T, et al. Combinatorial resources auction in decentralized edge-thing systems using blockchain and differential privacy[J]. Information Sciences, 2022, 607: 211-229.

[38]Cacchiani V, Iori M, Locatelli A, et al. Knapsack problems-An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems[J]. Computers & Operations Research, 2022: 105693.

[39]Fu H, Liaw C, Randhawa S. The Vickrey auction with a single duplicate bidder approximates the optimal revenue[C]//Proceedings of the 2019 ACM Conference on Economics and Computation. 2019: 419-420.

[40]Zaman S, Grosu D. Combinatorial auction-based allocation of virtual machine instances in clouds[J]. Journal of parallel and distributed computing, 2013, 73(4): 495-508.

[41]Samimi P, Teimouri Y, Mukhtar M. A combinatorial double auction resource allocation model in cloud computing[J]. Information Sciences, 2016, 357: 201-216.

[42]李姗.基于层次化拍卖的移动区块链计算资源分配机制研究[D].南京:南京航空航天大学,2020.

[43]池来新,杨旭涛,谢宁等.边缘计算系统中资源分配防策略拍卖机制设计[J].计算机工程与科学,2021,43(10):1720-1729.

[44]Kumar D, Baranwal G, Raza Z, et al. A truthful combinatorial double auction-based marketplace mechanism for cloud computing[J]. Journal of Systems and Software, 2018, 140: 91-108.

[45]Zhang J, Yang X, Xie N, et al. An online auction mechanism for time-varying multidimensional resource allocation in clouds[J]. Future Generation Computer Systems, 2020, 111: 27-38.

[46]Li Q, Jia X, Huang C, et al. A dynamic combinatorial double auction model for cloud resource allocation[J]. IEEE Transactions on Cloud Computing, 2022.

[47]Jones S, Milner E, Sooriyabandara M, et al. Distributed situational awareness in robot swarms[J]. Advanced Intelligent Systems, 2020, 2(11): 2000110.

[48]王伟嘉,郑雅婷,林国政,等.集群机器人研究综述[J].机器人,2020,42(02):232-256.

[49]de Croon G C H E, Dupeyroux J J G, Fuller S B, et al. Insect-inspired AI for autonomous robots[J]. Science robotics, 2022, 7(67): eabl6334.

[50]Tang Q, Zhang J, Yu F, et al. A resource management algorithm for real-time response of mobile ad hoc cloud in swarm robotic system[C]//2018 IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2018: 1171-1176.

[51]陈建先.博弈理论框架:一个理论体系的建构[J].重庆理工大学学报(社会科学),2018,32(01):88-95.

[52]Ratliff L J, Burden S A, Sastry S S. On the characterization of local Nash equilibria in continuous games[J]. IEEE transactions on automatic control, 2016, 61(8): 2301-2307.

[53]Zamir S. Bayesian games: Games with incomplete information[M]. Springer US, 2020.

[54]Narahari Y. Game theory and mechanism design[M]. World Scientific, 2014.

[55]Danz D, Vesterlund L, Wilson A J. Belief elicitation and behavioral incentive compatibility[J]. American Economic Review, 2022, 112(9): 2851-288.

[56]肖涛.机制设计[D].上海:上海交通大学,2020.

[57]陆瑾洋.社交网络中的资源分配机制研究与实现[D].镇江市:江苏科技大学,2020.

[58]Khezr P, Cumpston A. A review of multiunit auctions with homogeneous goods[J]. Journal of Economic Surveys, 2022, 36(4): 1225-1247.

[59]Hong Y, Wang C, Pavlou P A. Comparing open and sealed bid auctions: Evidence from online labor markets[J]. Information Systems Research, 2016, 27(1): 49-69.