Efficient task assignment algorithm for coal mine underground group robots
-
摘要: 松散型合作群机器人系统在现阶段煤矿辅助机器人作业中具有广泛应用前景。但松散型合作群机器人系统的任务分配过程未向划分过程进行反馈，导致任务划分与分配过程高效性与合理性不足。针对该问题，提出一种基于改进型鲁宾斯坦协商策略的煤矿井下群机器人高效任务分配算法。根据群机器人系统任务划分与分配过程的多方博弈特点，将鲁宾斯坦协商策略由双方博弈向多方共同博弈方向延伸，提出多方协商博弈的“出价−讨价−还价”规则。从机器人个体执行能力与任务执行情况差异的角度出发，提出基于机器人个体单位时间任务完成量的折扣因子计算方法，以及基于各分配周期任务执行情况的任务完成状态反馈参数模型，以实现任务的动态划分与分配。通过3组机器人合作执行煤矿矿区的整体监测任务，对算法性能开展实验验证，结果表明：① 算法3（采用改进型鲁宾斯坦协商策略）的任务划分与分配效率较算法1（将每组无人机数量与运行速度乘积的比例直接作为3组无人机任务划分与分配的标准）、算法2（使用多方共同协商的鲁宾斯坦协商策略，但不考虑任务完成状态反馈参数）分别提升了30.10%，18.29%。② 基于算法3的3组无人机执行任务的平均最大时间差为42 s，较算法1、算法2分别优化了77.66%，65.29%，这是由于算法3通过引入任务完成状态反馈参数，及时对任务参与方的任务执行过程进行评估，将任务的分配和执行过程向任务的划分阶段进行反馈，使任务的划分与分配更加准确。Abstract: The loose cooperative group robot system has broad application prospects in the current coal mine auxiliary robot operation. However, the task assignment process of the loose cooperative group robot system did not provide feedback to the division process, resulting in insufficient efficiency and rationality of the task division and assignment process. To address this issue, an efficient task assignment algorithm for coal mine underground group robots based on an improved Rubinstein negotiation strategy is proposed. Based on the multi-party game features of task division and assignment in group robot systems, the Rubinstein negotiation strategy is extended from a bipartite game to a multi-party joint game. A "bid-bargain-counteroffer" rule for multi-party negotiation games is proposed. From the perspective of the difference between the execution capability and task execution status of individual robots, a discount factor calculation method based on the task completion quantity per unit time of robot individuals is proposed. A task completion status feedback parameter model based on the task execution status of each assignment cycle is also proposed to achieve dynamic task division and assignment. By collaborating with three groups of robots to perform overall monitoring tasks in coal mining areas, experimental verification is conducted on the performance of the algorithm. The results show the following points. ① Algorithm 3 uses an improved Rubinstein negotiation strategy. Algorithm 1 directly uses the ratio of the number of unmanned aerial vehicles in each group multiplied by their running speed as the standard for task division and assignment in three groups of unmanned aerial vehicles. Algorithm 2 uses the Rubinstein negotiation strategy of multi-party negotiation without considering the feedback parameters of task completion status. Algorithm 3 has a higher efficiency in task division and assignment than Algorithm 1 and Algorithm 2 by 30.10% and 18.29% respectively. ② The average maximum time difference for the three groups of unmanned aerial vehicles based on Algorithm 3 to execute tasks is 42 seconds. It is 77.66% and 65.29% optimized compared to Algorithm 1 and Algorithm 2, respectively. This is because Algorithm 3 introduces task completion status feedback parameters to timely evaluate the task execution process of the task participants. Algorithm 3 provides feedback on the task assignment and execution process to the task division stages, making the task division and assignment more accurate.
-
图 2 理论博弈平衡点建立过程
Figure 2. The establishment process of theoretical game equilibrium point
图 5 影响因素与折扣因子的关系
Figure 5. Relationship between influencing factors and discount factor
图 6 3种典型增长类型的影响因素对比
Figure 6. Comparison of influencing factors for three typical growth types
图 7 3种典型增长类型的计算与理论结果对比
Figure 7. Comparison of calculation and theoretical results of the three typical growth types
图 8 $ n $个参与方进行博弈的理论协商博弈平衡点计算过程
Figure 8. Calculation process of theoretical negotiation game equilibrium point of game played by n participants
图 10 第1个分配周期中3组无人机的博弈过程
Figure 10. Game process of three groups of unmanned aerial vehicle in the first assignmen cycle
图 11 3组无人机在不同分配周期的任务完成情况
Figure 11. Task completion of three groups of unmanned aerial vehicle in different assignment cycles
图 12 不同分配周期的反馈参数$ k $、折扣因子$ \delta $、划分比例h变化情况
Figure 12. Changes of feedback parameter $ k $, discount factor $ \delta $ and division proportion h in different assignment cycles
表 1 无人机技术参数
Table 1. Technical parameters of unmanned aerial vehicles
机体尺寸/m 直径1.4，高0.6 最大飞行速度/(km·h−1) 21 空载质量/kg 7 最大抗风能力/级 7 满载续航时间/min 45 
下载: 导出CSV
表 2 3组无人机数量及飞行速度
Table 2. Number and running speed of three groups of unmanned aerial vehicles
组别 无人机数量/架 最大飞行速度/(km·h−1) 1 3 8.9 2 6 4.2 3 4 3.8
下载: 导出CSV
表 3 第1个分配周期的任务完成情况与状态反馈参数
Table 3. Task completion and status feedback parameters in the first assignment cycle
无人机组别 1 2 3 分配任务面积/ km2 1.311 1.175 1.012 完成任务面积/ km2 0.0906 0.0643 0.0401 任务执行度参数/% 6.91 5.47 3.96 任务完成状态反馈参数 1.2685 1.0042 0.7270
下载: 导出CSV
表 4 3种任务划分与分配算法实验时间
Table 4. Experiment time of three task partition division and assignment algorithms
s 时间 实验1 实验2 实验3 平均值 算法1 1 344 1 458 1 394 1 399 算法2 1 238 1 152 1 202 1 197 算法3 986 945 1 003 978
下载: 导出CSV
表 5 每组无人机的任务执行时间
Table 5. Task execution time of each group of unmanned aerial vehicle
s 平均作业时间 最大组别时间差 机组1 机组2 机组3 算法1 1337 1482 1294 188 算法2 1 262 1141 1189 121 算法3 993 979 1 035 42
下载: 导出CSV
-
[1] 张鹏. 智能矿山机器人协同管控[J]. 工矿自动化,2021,47(增刊2):43-44.ZHANG Peng. Collaborative control of robots in intelligent mine[J]. Industry and Mine Automation,2021,47(S2):43-44. [2] 王宏,宋智瀛,贾瑞清. 基于模块化异构多机器人的煤矿灾害处置系统[J]. 煤炭科学技术,2011,39(10):93-95,111.WANG Hong,SONG Zhiying,JIA Ruiqing. Mine disaster control system based on module heteromerous multi robot[J]. Coal Science and Technology,2011,39(10):93-95,111. [3] GAUTHAM D,THOMAS M,SONYA C,et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J]. Journal of Intelligent & Robotic Systems,2015,80(1):33-58. [4] 彭凡彬,杨俊杰,叶波. 改进蚁群算法的变电站群机器人路径规划研究[J]. 仪表技术,2018(3):9-13,35.PENG Fanbin,YANG Junjie,YE Bo. Research on robot path planning of substation group based on improved ant colony algorithm[J]. Instrumentation Technology,2018(3):9-13,35. [5] 王伟嘉,郑雅婷,林国政,等. 集群机器人研究综述[J]. 机器人,2020,42(2):232-256.WANG Weijia,ZHENG Yating,LIN Guozheng,et al. Swarm robotics:a review[J]. Robot,2020,42(2):232-256. [6] XIAO Renbin,WU Husheng,HU Liang,et al. A swarm intelligence labour division approach to solving complex area coverage problems of swarm robots[J]. International Journal of Bio-Inspired Computation,2020,15(4):224-238. doi: 10.1504/IJBIC.2020.108598 [7] 邱靖廷. 基于群体智能的多机器人任务分配[D]. 哈尔滨: 哈尔滨工程大学, 2020.QIU Jingting. Multi-robot task assignment based on group intelligence[D]. Harbin: Harbin Engineering University, 2020. [8] YEUNG W L. Efficiency of task allocation based on contract net protocol with audience restriction in a manufacturing control application[J]. International Journal of Computer Integrated Manufacturing,2018,31(10):1005-1017. doi: 10.1080/0951192X.2018.1493227 [9] 梁志伟,吴海健. RoboCup标准平台组中基于改进合同网协议的任务分配算法[J]. 计算机工程与科学,2022,44(1):176-183.LIANG Zhiwei,WU Haijian. A task allocation algorithm based on the improved contract network protocol in RoboCup standard platform league[J]. Computer Engineering & Science,2022,44(1):176-183. [10] 黄柳强,秦丽娟,商云龙. 电力市场双边协商交易模型设计研究[J]. 广西电力,2021,44(2):14-19.HUANG Liuqiang,QIN Lijuan,SHANG Yunlong. Research on a design of bilateral negotiation and transaction model in electricity market[J]. Guangxi Electric Power,2021,44(2):14-19. [11] 马金龙. 基于博弈论的国际工程承包合同纠纷研究[D]. 北京: 北京交通大学, 2020.MA Jinlong. Research on the disputes of international engineering contracts based on game theory[D]. Beijing: Beijing Jiaotong University, 2020. [12] 罗震环. 基于VCG和鲁宾斯坦模型的数据定价方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2021.LUO Zhenhuan. Research on data pricing methods based on VCG and rubinstein models[D]. Harbin: Harbin Institute of Technology, 2021. [13] JAEHWI S,HOUNG S. Bargaining model-based coverage area subdivision of multiple UAVs in remote sensing[J]. Journal of Biosystems Engineering,2021,45(3):133-144. [14] 张梦颖,王蒙一,王晓东,等. 基于改进合同网的无人机群协同实时任务分配问题研究[J]. 航空兵器,2019,26(4):38-46. doi: 10.12132/ISSN.1673-5048.2019.0153ZHANG Mengying,WANG Mengyi,WANG Xiaodong,et al. Cooperative real-time task assignment of UAV group based on improved contract net[J]. Aero Weaponry,2019,26(4):38-46. doi: 10.12132/ISSN.1673-5048.2019.0153 [15] 马洪宽. 博弈论[M]. 上海: 同济大学出版社, 2015: 78-91.MA Hongkuan. Game theory[M]. Shanghai: Tongji University Press, 2015: 78-91. [16] 王磊. 动态合作博弈中解的策略稳定性[D]. 青岛: 青岛大学, 2016.WANG Lei. Strategic stability of solutions in dynamic cooperative games[D]. Qingdao: Qingdao University, 2016. [17] 郭超,熊伟,刘呈祥. 合同网协议改进研究现状与展望[J]. 装备学院学报,2016,27(6):82-89.GUO Chao,XIONG Wei,LIU Chengxiang. Prospects and current researches on improvement of contract net protocol[J]. Journal of Equipment Academy,2016,27(6):82-89. [18] SZCZERBA R J,GALKOWSKI P,GLICKSTEIN I S,et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems,2000,36(3):869-878. doi: 10.1109/7.869506 [19] 刘刚,王瑛,张发,等. 合同网协议协商机制收敛性与收敛速率分析[J]. 控制与决策,2014,29(6):1027-1034.LIU Gang,WANG Ying,ZHANG Fa,et al. Convergence and convergent rate analysis of contract net protocol negotiation mechanism[J]. Control and Decision,2014,29(6):1027-1034. [20] 李娟,张昆玉. 基于改进合同网算法的异构多AUV协同任务分配[J]. 水下无人系统学报,2017,25(6):418-423.LI Juan,ZHANG Kunyu. Heterogeneous multi-AUV cooperative task allocation based on improved contract net algorithm[J]. Journal of Unmanned Undersea Systems,2017,25(6):418-423. [21] 吴江,赵世钰,周锐,等. 基于面向服务的多无人机辅助决策仿真集成方法[J]. 系统仿真学报,2012,24(12):2525-2529.WU Jiang,ZHAO Shiyu,ZHOU Rui,et al. Simulation integration of decision aiding based on service-oriented for multiple UAVs[J]. Journal of System Simulation,2012,24(12):2525-2529. [22] CHEN Kaiwen, REICHARD G, AKANMU A, et al. Geo-registering UAV-captured close-range images to GIS-based spatial model for building facade inspections[J]. Automation in Construction, 2021, 122（1）. DOI: 10.1016/j.autcon.2020.103503. -
点击查看大图
计量
- 文章访问数: 143
- HTML全文浏览量: 24
- PDF下载量: 22
- 被引次数: 0
