Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2022, Vol. 56 Issue (9): 1806-1814    DOI: 10.3785/j.issn.1008-973X.2022.09.014
计算机与控制工程     
日常养老情境的异构多机器人动态多任务分配
李勇(),柳富强,孙柏青,张秋豪,杨俊友
沈阳工业大学 电气工程学院，辽宁 沈阳 110870
Dynamic multi-task allocation of heterogeneous multi-robots for daily elderly care scenarios
Yong LI(),Fu-qiang LIU,Bai-qing SUN,Qiu-hao ZHANG,Jun-you YANG
School of Electrical Engineering, Shenyang University of Technology, Shenyang 110870, China
 全文: PDF(1082 KB)   HTML
摘要：

针对异构多机器人系统动态任务分配问题，基于多智能体技术，利用符合养老情境特点的多智能体组织结构，提出处理养老情境下任务类型相对固定的异构多机器人多任务动态分配机制. 建立基于被服务对象满意度函数的投标值计算模型，兼顾多任务的动态分配与被服务对象的满意度. 根据拓扑排序算法，提出多智能体系统死锁的检测及处理方法，解决执行智能体自锁、各执行智能体间互锁的问题. 对不同任务情况在不同分配机制下的被服务对象满意度进行仿真. 仿真结果表明，在避免死锁的情况下，所提机制能够兼顾养老情景下的动态任务分配和被服务对象的满意度.
关键词： 多智能体;  异构服务机器人;  满意度;  动态任务分配;  死锁    
Abstract:

Aiming at the dynamic task assignment of heterogeneous multi-robot systems for elderly care scenarios, a dynamic multi-task allocation mechanism for the nursing home scenario was proposed with relatively fixed types of tasks, using the multi-agent organizational structure that conformed to the characteristics of the elderly care situation, based on multi-agent technology. A bid value calculation model based on the satisfaction function of the served was established, which not only completed the dynamic multi-tasks allocation, but also improved the satisfaction of the served. According to the topological sorting algorithm, a method of deadlock detection and remedy for multi-agent system was proposed, and the problems of self-locking and interlocking among agents were solved. The satisfaction of the served object under different task conditions and different allocation mechanisms was simulated. Simulation results shows the proposed dynamic task assignment mechanism for heterogeneous multi-service robot system can complete the dynamic task assignment without deadlock, and at the same time take into account the satisfaction of the served.
Key words: multi-agent    heterogeneous service robot    satisfaction    dynamic task allocation    deadlock
收稿日期: 2021-10-28 出版日期: 2022-09-28
CLC:  TP 18  
基金资助: 辽宁省自然科学基金资助项目（2019-ZD-0205）；辽宁省教育厅资助项目（LJKZ0130）
作者简介: 李勇（1980—），男，副教授，博士，从事系统建模与多目标优化和机器学习研究. orcid.org/0000-0002-3098-6363.E-mail： liyong@sut.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
李勇
柳富强
孙柏青
张秋豪
杨俊友

引用本文:

李勇,柳富强,孙柏青,张秋豪,杨俊友. 日常养老情境的异构多机器人动态多任务分配[J]. 浙江大学学报(工学版), 2022, 56(9): 1806-1814.

Yong LI,Fu-qiang LIU,Bai-qing SUN,Qiu-hao ZHANG,Jun-you YANG. Dynamic multi-task allocation of heterogeneous multi-robots for daily elderly care scenarios. Journal of ZheJiang University (Engineering Science), 2022, 56(9): 1806-1814.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2022.09.014    或    https://www.zjujournals.com/eng/CN/Y2022/V56/I9/1806

图 1  2类执行智能体
图 2  任务分配机制流程图
图 3  执行智能体间协商算法的流程图
图 4  自锁检测算法
图 5  虚拟养老机构环境
子任务标号 所需技能 ${t}_{\rm{e}}$/s ${v}$/(m·s?1)
T1_1 拉/放 18 —
T1_2 运送 — 0.6
T1_3 拉/放 15 —
T2_1 拉/放 20 —
T2_2 运送 — 0.7
T2_3 拉/放 17 —
表 1  服务任务T1和T2的子任务信息
子任务标号 $ {b}_{i,j} $
AR1 AR2 WR1 WR2
T1_1 0.087 0 (7.074×10?5) 0.112 0 (0.073) 0(0) 0(0)
T1_2 0(0) 0(0) 0.054 (3.002×10?5) 0.056 0 (0.602)
T1_3 0.0006 (6.833×10?5) 0.0005 (?1.261) 0(0) 0(0)
T2_1 0.0001 (8.187×10?5) 0.018 0 (0.012) 0(0) 0(0)
T2_2 0(0) 0(0) 0.010 (3.680×10?5) 0.0004 (3.679×10?5)
T2_3 0.0002 (7.947×10?4) 0.0006 (?1.214) 0(0) 0(0)
表 2  执行智能体对各子任务的投标值
图 6  多种分配机制的子任务满意度对比折线图
图 7  被服务对象满意度对比条状图
子任务标号 $ {b}_{i,j} $
AR1 AR2 WR1 WR2
T3_1 0 6.523×10?3 0 0
T3_2 0 0 0 8.566×10?4
T3_3 0 6.983×10?4 0 0
表 3  执行智能体对T3中子任务的投标值
子任务标号 所需技能 ${t}_{\rm{e}}$/s ${v}$/(m·s?1)
T4_1 拉/放 19 —
T4_2 运送 — 0.5
T4_3 拉/放 18 —
T5_1 拉/放 16 —
T5_2 运送 — 0.7
T5_3 拉/放 15 —
表 4  服务任务T4和T5的子任务信息
1 郭冉, 王俊 世界人口发展趋势和人口转变——理论与现实[J]. 人口与社会, 2019, 35 (3): 52- 63
GUO Ran, WANG Jun World population trends and demographic transition: theory and reality[J]. Population and Society, 2019, 35 (3): 52- 63
doi: 10.14132/j.2095-7963.2019.03.005
2 雷莹 我国人口老龄化发展趋势问题及对策研究[J]. 农村经济与科技, 2019, 30 (16): 207- 208
LEI Ying Research on the development trend, problems and countermeasures of population aging in China[J]. Rural Economy and Science, 2019, 30 (16): 207- 208
doi: 10.3969/j.issn.1007-7103.2019.16.124
3 郑健, 陈建, 朱琨 基于多智能体强化学习的无人集群协同设计[J]. 指挥信息系统与技术, 2020, 11 (6): 26- 31
ZHENG Jian, CHEN Jian, ZHU Kun Unmanned swarm cooperative design based on multi-agent reinforcement learning[J]. Command Information System and Technology, 2020, 11 (6): 26- 31
doi: 10.15908/j.cnki.cist.2020.06.005
4 张思锋, 张泽滈 中国养老服务机器人的市场需求与产业发展[J]. 西安交通大学学报:社会科学版, 2017, 37 (5): 49- 58
ZHANG Si-feng, ZHANG Ze-hao Market demand, industrial base and development of aged service robot[J]. Journal of Xi'an Jiaotong University: Social Sciences, 2017, 37 (5): 49- 58
5 洪奕光, 翟超 多智能体系统动态协调与分布式控制设计[J]. 控制理论与应用, 2011, 28 (10): 1506- 1512
HONG Yi-guang, ZHAI Chao Dynamic coordination and distributed control design of multi-agent systems[J]. Control Theory and Applications, 2011, 28 (10): 1506- 1512
6 DAS G P, MCGINNITY T M, COLEMAN S A, et al A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J]. Journal of Intelligent and Robotic Systems, 2015, 80: 33- 58
doi: 10.1007/s10846-014-0154-2
7 HUNT S, MENG Q, HINDE C, et al. Consensus-based grouping algorithm for multi-agent cooperative task allocation with complex requirements [J] Cognitive Computation, 2014, 6(3): 338–350.
8 LEE D H Resource-based task allocation for multi-robot systems[J]. Robotics and Autonomous Systems, 2018, 103: 151- 161
doi: 10.1016/j.robot.2018.02.016
9 TERESHCHUK V, STEWART J, BYKOV N, et al An efficient scheduling algorithm for multi-robot task allocation in assembling aircraft structures[J]. IEEE Robotics and Automation Letters, 2019, 4 (4): 3844- 3851
doi: 10.1109/LRA.2019.2929983
10 李勇, 李坤成, 孙柏青, 等 智能体Petri网融合的多机器人-多任务协调框架[J]. 自动化学报, 2021, 47 (8): 2029- 2049
LI Yong, LI Kun-cheng, SUN Bai-qing, et al Multi-robot-multi-task coordination framework based on the integration of intelligent agent and Petri net[J]. Acta Automatica Sinica, 2021, 47 (8): 2029- 2049
doi: 10.16383/j.aas.c190400
11 KARAMAN S, RASMUSSEN S, KINGSTON D, et al. Specification and planning of UAV missions: a process algebra approach [C]// 2009 American Control Conference. St. Louis: IEEE, 2009: 1442–1447.
12 WEINSTEIN A L, SCHUMACHER C. UAV scheduling via the vehicle routing problem with time windows [C]// AIAA Infotech@Aerospace 2007 Conference and Exhibit. Rohnert Park: [s.n.], 2007: 1324–1337.
13 DENG Q, YU J, WANG N Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26 (5): 1238- 1250
doi: 10.1016/j.cja.2013.07.009
14 NAGARAJAN T, THONDIYATH A An algorithm for cooperative task allocation in scalable, constrained multiple robot systems[J]. Intelligent Service Robotics, 2014, 7 (4): 221- 233
doi: 10.1007/s11370-014-0154-x
15 SHI J, YANG Z, ZHU J An auction-based rescue task allocation approach for heterogeneous multi-robot system[J]. Multimedia Tools and Applications, 2020, 79: 14529- 14538
doi: 10.1007/s11042-018-7080-4
16 OTTE M, KUHLMAN M J, SOFGE D Auctions for multi-robot task allocation in communication limited environments[J]. Autonomous Robots, 2020, 44: 547- 584
doi: 10.1007/s10514-019-09828-5
17 COFFMANN E G J, ELPHICK M J, SOSHANI A System deadlocks[J]. Computing Surveys, 1971, 3 (2): 67- 78
doi: 10.1145/356586.356588
[1] 刘高平,宋执环. 基于射频能量采集的电子标签设计方法[J]. 浙江大学学报(工学版), 2022, 56(8): 1666-1675.
[2] 徐小高,夏莹杰,朱思雨,邝砾. 基于强化学习的多路口可变车道协同控制方法[J]. 浙江大学学报(工学版), 2022, 56(5): 987-994, 1005.
[3] 张盼,丁华,张颖而,李冰凝,皇甫江涛,金仲和. 基于信息共享的多智能体自主电子干扰系统[J]. 浙江大学学报(工学版), 2022, 56(1): 75-83.
[4] 季琳琳,王清威,周豪,郑美妹. 考虑顾客满意度的冷链水果路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 307-317.
[5] 邵杭蕾,张冬梅. 基于静态输出反馈协议的多智能体系统同步[J]. 浙江大学学报(工学版), 2020, 54(7): 1308-1315.
[6] 董如良, 杨强, 颜文俊. 多智能体协同寻优的主动配网动态拓扑重构[J]. 浙江大学学报(工学版), 2015, 49(10): 1982-1989.
[7] 徐姗姗, 董利达, 朱丹, 朱承丞. S4PR网的极小信标计算方法[J]. J4, 2013, 47(3): 431-441.
[8] 娄柯, 齐斌, 穆文英, 崔宝同. 基于反馈控制策略的多智能体蜂拥控制[J]. J4, 2013, 47(10): 1758-1763.
[9] 杜瑞忠, 田俊峰, 张焕国. 基于信任和个性偏好的云服务选择模型[J]. J4, 2013, 47(1): 53-61.
[10] 杨洪勇, 李晓. 时延多智能体系统的编队控制[J]. J4, 2010, 44(7): 1355-1360.
[11] 欧立勇, 杜树新. 基于多智能体的公共检测资源协调方法[J]. J4, 2010, 44(1): 81-86+123.
[12] 刘海强, 纪杨建, 祁国宁, 等. 支持多学科设计优化的产品集成设计知识模型研究[J]. J4, 2009, 43(10): 1841-1847.
[13] 李国阳 邬盈盈 韦巍. 一种基于等级有序竞争的群集控制[J]. J4, 2009, 43(1): 73-76.
[14] 沈国江 许卫明. 交通干线动态双向绿波带控制技术研究[J]. J4, 2008, 42(9): 1625-1630.
[15] 胡敏 李艳君 吴铁军. 基于多边协商的分布式网格资源调度[J]. J4, 2007, 41(7): 1073-1077.