RoboCup标准平台组中基于改进合同网协议的任务分配算法

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (01): 176-183.

RoboCup标准平台组中基于改进合同网协议的任务分配算法

梁志伟，吴海健

（南京邮电大学自动化学院、人工智能学院，江苏南京 210023）

收稿日期:2020-06-12 修回日期:2020-11-10 接受日期:2022-01-25 出版日期:2022-01-25 发布日期:2022-01-13
基金资助:
国家自然科学基金(61104216)；南京邮电大学基金(NY219123)

A task allocation algorithm based on the improved contract network protocol in RoboCup standard platform league

LIANG Zhi-wei,WU Hai-jian

（College of Automation & Artificial Intelligence,Nanjing University of Posts and Telecommunications，Nanjing 210023,China）

Received:2020-06-12 Revised:2020-11-10 Accepted:2022-01-25 Online:2022-01-25 Published:2022-01-13

摘要/Abstract

摘要： 针对RoboCup标准平台组SPL中多机器人之间的协同问题，提出了基于改进合同网协议的任务分配算法。首先对RoboCup多机器人系统建立层次结构分解模型和单体机器人行为任务树模型，并采用AHP层次分析法确定各个任务权重。其次，提出基于改进合同网协议的任务分配策略，相对于传统合同网协议，改进的合同网协议将标书公示机制引入任务分配模型；同时，提出了优先招标策略并对合同网协议流程和评价函数进行了改进和扩展。

关键词: 任务分配, 合同网协议, 任务分解, RoboCup

Abstract: Aiming at the cooperation problem among multiple robots in RoboCup Standard Platform League (SPL), a task allocation algorithm based on the improved contract network protocol is proposed. Firstly, a hierarchical structure decomposition model and a single robot behavior task tree model are established for the RoboCup multi-robot system, and the analytic hierarchy process (AHP) is used to determine the weight of each task. Secondly, a task allocation strategy based on the improved contract network agreement is proposed. Compared with the traditional contract network agreement, the improved contract network agreement introduces the bid announcement mechanism into the task allocation model. At the same time, the priority bidding strategy is proposed and the contract network protocol process and evaluation function are improved and expanded.

Key words: task allocation, contract network protocol, task decomposition, RoboCup

梁志伟, 吴海健. RoboCup标准平台组中基于改进合同网协议的任务分配算法[J]. 计算机工程与科学, 2022, 44(01): 176-183.

LIANG Zhi-wei, WU Hai-jian. A task allocation algorithm based on the improved contract network protocol in RoboCup standard platform league[J]. Computer Engineering & Science, 2022, 44(01): 176-183.

参考文献［14］

［1］	Wang Y K,Jia S H,Chen C X,et al. Multi-agent collaboration for feasible collaborative behavior construction and evaluation ［C］∥Proc of 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO),2019:1158-1165.
［2］	Gadelrab A A,Noaman A Y. A two-tier bipartite graph task allocation approach based on fuzzy clustering in cloud-fog environment［J］. Future Generation Computer Systems,2020,103:79-90.
［3］	Chen X Y,Zhang P,Du G L,et al. A distributed method for dynamic multi-robot task allocation problems with critical time constraints［J］. Robotics and Autonomous Systems,2019,118:31-46.
［4］	Qin Jiu-feng, Zeng Fan-ming, Chen Yu-tao, et al. Research on cooperation mechanism of multi-agent system based on improved contract network［J］. Journal of Wuhan University of Technology（Transportation Science Engineering），2014, 38(5):1065-1069.(in Chinese)
［5］	Chen Ming, Jian Yu-mei.Research on mental coefficient-based multi-agent contract net collaborative model
［J］	Computer Applications and Software,2013,30(6):46-51.(in Chinese)
［6］	Zhang J R,Wang G,Song Y F,et al. Task assignment of the improved contract net protocol under a multi-agent system［J］. Algorithms,2019,12(4):70.
［7］	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.
［8］	He Li-jian. Research on trust and reputation model in multi-agent system［D］. Beijing:Beijing Jiaotong University,2011.(in Chinese)
［9］	Rob C. Mobility as a service:A valuecentric approach to design［C］∥Proc of The Web Conference 2019—Companion of the World Wide Web Conference,2019:83-92.
［10］	Qian Yan-ping, Xia Jie, Liu Tian-yu. Task assignment scheme based on contract net［J］. Journal of System Simulation,2011,23(8):1672-1676.(in Chinese)
［11］	Zhou Kun. Research on resource service aggregation model based on multi-agent system［D］. Xi’an:Xidian University,2014.(in Chinese)
［12］	Zhang C, Jin P, Li Y B, et al. Virtual constellation task planning technology for emergency observation［J］. Systems Engineering and Electronics,2019,41(4):819-825.
［13］	Hu Y,Li C,Zhang K,et al. Task allocation based on modified contract net protocol under generalized cluster［J］. Journal of Computational Methods in Sciences and Engineering,2019,19(3):1-20.
［14］	Hao Hui-cheng. Research on mission planning problem modeling and solving method of agile earth obsevertion satellite ［D］.
	Harbin:Harbin Institute of Technology,2013.(in Chinese)
［15］	Du B,Li S. A new multi-satellite autonomous mission allocation and planning method［J］. Acta Astronautica,2019,163(10):287-298.
［16］	Gao Y. Shortest path problem with uncertain arc lengths［J］. Computers and Mathematics with Applications,2011,62(6):2591-2600.
［17］	Elgibreen H,Youceftoumi K. Dynamic task allocation in an uncertain environment with heterogeneous multi-agents［J］. Autonomous Robots,2019,43(7):1639-1664.
［18］	Huang H Q,Zhuo T. Multi-model cooperative task assignment and path planning of multiple UCAV formation［J］. Multimedia Tools and Applications,2019,78(1):415-436.
［19］	Muender T, Rofer T. Model-based fall detection and fall prevention for humanoid robots［M］∥RoboCup2017:Robot World Cup XXI.New York:Springer, Cham,2017:312-324.
［20］	Schwartz T,Feld M,Burckert C,et al. Hybrid teams of humans,robots,and virtual agents in a production setting［C］∥Proc of 2016 12th International Conference on Intelligent Environments,2016:234-237.
［21］	Rofer T,Laue T. On B-Human’s code releases in the stan- dard platform league-software architecture and impact［M］∥RoboCup2013:Robot World Cup XVII.New York:Springer, Cham,2013:648-655.
	附中文参考文献：
［4］	秦久峰，曾凡明，陈于涛，等.基于改进合同网的多Agent系统协作机理研究［J］.武汉理工大学学报（交通科学与工程版），2014，38（5）:1065-1069.
［5］	陈明,简玉梅.基于心智系数的多Agent合同网协作模型研究［J］.计算机应用与软件,2013,30(6):46-51.
［8］	贺利坚. 多Agent系统中信任和信誉模型的研究［D］.北京:北京交通大学,2011.
［10］	钱艳平,夏洁,刘天宇.基于合同网的无人机协同目标分配方法［J］.系统仿真学报,2011,23(8):1672-1676.
［11］	周坤.基于多Agent系统的资源服务聚合模型研究［D］.西安:西安电子科技大学，2014.
［14］	郝会成. 敏捷卫星任务规划问题建模及求解方法研究［D］.哈尔滨:哈尔滨工业大学,2013.

[1]	侯占伟, 李鑫, 王辉, 申自浩, 刘琨, 刘沛骞. 面向路网的空间众包隐私保护任务分配算法[J]. 计算机工程与科学, 2023, 45(08): 1424-1432.
[2]	李小玲, 方建滨, 马俊, 谭霜, 谭郁松. 基于监督学习的稀疏矩阵自动任务分配[J]. 计算机工程与科学, 2023, 45(05): 782-789.
[3]	申晓宁, 许笛, 宋丽妍, 姚铖滨, 王玉芳, . 采用离散烟花算法的移动群智感知异构任务分配[J]. 计算机工程与科学, 2023, 45(02): 321-331.
[4]	郭嘉宇, 付晓东, 岳昆, 刘骊, 冯勇, 刘利军. 偏好匹配满意度最大化的众包任务分配[J]. 计算机工程与科学, 2022, 44(01): 16-26.
[5]	薛建彬,安亚宁. 基于边缘计算的新型任务卸载与资源分配策略[J]. 计算机工程与科学, 2020, 42(06): 959-965.
[6]	何世添，谭德立. 课内外协同的《计算机组成原理》课程教学模式探索与实践[J]. 计算机工程与科学, 2019, 41(增刊S1): 144-148.
[7]	付慧敏1,2,徐扬2，何星星2,宁欣然1,2. 基于任务分配与调度的GSAT算法求解3-SAT问题[J]. 计算机工程与科学, 2018, 40(08): 1366-1374.
[8]	陈振1，朱海滨2，盛寅3，高海波1. 基于E-CARGO模型的多任务分配算法[J]. 计算机工程与科学, 2016, 38(12): 2542-2551.
[9]	王艳春1，尚晓丽2，李会1. FCM-AFSA的无线传感器网络多目标跟踪节点任务分配方法[J]. J4, 2014, 36(07): 1262-1267.
[10]	孙海梦[1] 李咏梅[2] 陈海洋[1]. 基于视觉噪声的粒子滤波定位法在RoboCup中的应用[J]. J4, 2008, 30(12): 41-42.
[11]	冯玉才刘冉冉. 基于任务分配的数据库集群模型[J]. J4, 2007, 29(12): 114-116.
[12]	王罡陈木彬梁福鸿郑淑梅. Robocup仿真比赛传球策略研究[J]. J4, 2007, 29(10): 101-104.
[13]	程显毅王军张俊. RoboCup 3D Server分析[J]. J4, 2006, 28(3): 119-122.
[14]	王慧华朱娜. 多用户协作环境下的递归建模及合理决策[J]. J4, 2004, 26(12): 94-96.