Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2022, Vol. 56 Issue (9): 1806-1814    DOI: 10.3785/j.issn.1008-973X.2022.09.014
    
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
Download: HTML     PDF(1082KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 28 October 2021      Published: 28 September 2022
CLC:  TP 18  
Fund:  辽宁省自然科学基金资助项目（2019-ZD-0205）；辽宁省教育厅资助项目（LJKZ0130）
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Yong LI
Fu-qiang LIU
Bai-qing SUN
Qiu-hao ZHANG
Jun-you YANG
Cite this article:

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.

URL:

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


日常养老情境的异构多机器人动态多任务分配

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


关键词： 多智能体,  异构服务机器人,  满意度,  动态任务分配,  死锁 
Fig.1 Two types of executive agents
Fig.2 Flow chart of task allocation mechanism
Fig.3 Flow chart of negotiation algorithm between executing agents
Fig.4 Self locking detection algorithm
Fig.5 Virtual elderly care institution environment
子任务标号 所需技能 ${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 —
Tab.1 Subtask information of task T1 and 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)
Tab.2 Bidding value of executing agent for each subtask
Fig.6 Comparison of subtask satisfaction with multiple allocation mechanisms
Fig.7 Comparison of satisfaction for served
子任务标号 $ {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
Tab.3 Bidding value of executing agent for T3 sub task
子任务标号 所需技能 ${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 —
Tab.4 Subtask information of task T4 and 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] Gao-ping LIU,Zhi-huan SONG. Design method of electronic tag based on radio frequency energy acquisition[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(8): 1666-1675.
[2] Xiao-gao XU,Ying-jie XIA,Si-yu ZHU,Li KUANG. Cooperative control algorithm of multi-intersection variable-direction lanes based on reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(5): 987-994, 1005.
[3] Pan ZHANG,Hua DING,Ying-er ZHANG,Bing-ning LI,Jiang-tao HUANG-FU,Zhong-he JIN. Multi-agent autonomous electronic jamming system based on information sharing[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(1): 75-83.
[4] Lin-lin JI,Qing-wei WANG,Hao ZHOU,Mei-mei ZHENG. Optimization of cold chain fruit path considering customer satisfaction[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 307-317.
[5] Hang-lei SHAO,Dong-mei ZHANG. Synchronization of multi-agent systems based on static output feedback protocol[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(7): 1308-1315.
[6] Xia-sheng SHI,Rong-hao ZHENG,Zhi-yun LIN,Gang-feng YAN. Saddle dynamic based distributed algorithm for economic dispatch problem[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(4): 678-683.
[7] XU Shan-shan, DONG Li-da, ZHU Dan, ZHU Cheng-cheng. Method to compute minimal siphons in S4PR nets[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(3): 431-441.
[8] DU Rui-zhong, TIAN Jun-feng, ZHANG Huan-guo. Cloud service selection model based on trust and personality preferences[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(1): 53-61.
[9] AI Jie-qing, GAO Ji, PENG Yan-bin, ZHENG Zhi-jun. Negotiation decision model based on transductive
support vector machine[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(6): 967-973.
[10] YANG Hong-Yong, LI Xiao. Formation control of multiagent with diverse delays[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(7): 1355-1360.
[11] OU Li-Yong, DU Shu-Xin. Multi-agent based coordination of public detection resources[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(1): 81-86+123.
[12] ZHANG Bao-Jun, BO Xue-Ceng, WANG Jie-Bing, et al. Multi-agent based hybrid Intrusion detection system[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 987-993.
[13] HU Bin, GAO Ji, GUO Hang. Dynamic model of normative multi-agent system and its property verification mechanism[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 1014-1019.
[14] CHEN Meng-Liang. Agent-network:a fusion method for heterogeneous business intelligence technologies[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 1053-1059.
[15] XU Ping, GAO Ji, GUO Hang. Reliable reputation computing based on double-layer reputation and feedback mechanism[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(12): 2160-2164.