Multi-root dynmic tsk lloction nd pth plnning considering fult fctors

He Zhou'†，He Pengyang（a.Colegeoficalamp;tllallEiUesiegy，Xi'an 710021，China）

Abstract：Toaddress therobustness problem of multiplerobots incomplex tasks，，this paper proposedacoupled task llcationand path planning method to adressthetrajectoryrequirementsundersuchtasks.Firstly，the Dijkstraalgorithmpreprocesed the shortestpathsand distances between task grids inenvironments.Secondly，whenthecentral controlermonitored the robotenteringthedangerzoneandfailure，itwasresponsibleforreal-timetask assignmentandenvironmentupdates toensuretask completion.Inaddition，it proposedanimproved northern goshawkoptimizationalgorithm（INGO）withlocaladjustment strategies inconjunction withaneighbourhoodsearchtoimprovethesolutionquality，andanauctionmethod incorporatingmarginalcosthandledtherootfailurereassignmentproblem.Finally，itconductedrandomtestsunderdiferentmapsizes and numbers of tasks. In 1OO-grid environment，the proposed method saved 19.63% of the total traveled distance compared to the auction method，andthesolutiontime wasshorter thanthatoftheothermethods.Theresultsdemonstratethatthe method beterbalances the travellingdistanceand solution time，whilealsooutperforming existing methods interms ofscalabilityand system robustness.

Key words：multi-robot system；task planning；system robustness； robot failure；path planning

0引言

多机器人系统（multi-robotsystem，MRS），由于其相对于单机器人系统在工作效率、灵活性等方面的优势而受到广泛关注[1，2]。目前MRS已被广泛应用于仓储、救援、巡检监测等领域[3-5]。作为MRS 的核心，任务分配和路径规划等问题已受到广泛关注。将系统的高级任务分解成子任务再分配给机器人的过程称为多机器人任务分配（multi-robottaskallocation，MRTA）。在大多数MRTA问题中，仅考虑避开障碍物的同时最小化系统的目标函数，如移动距离、求解时间等[6＼～8]。现实中，机器人对环境的感知可能是不准确的，会存在一定的危险性，从而对机器人产生影响，因此动态任务分配问题就变得具有挑战性。Dai等人[9研究了MRTA下的军事对抗问题，机器人收到任务指令后，对环境搜索的同时要摧毁隐藏在环境中的目标，而目标也可能对机器人造成损坏，系统需要重新考虑下发任务，并开发出基于竞拍、空缺链和DeepQ-leaming的方法。

针对在执行任务过程中机器人损坏的情况，Huang等人[1]在有限个机器人损坏的假设下，通过构建过渡系统和自动机，提出一种有效的任务分配策略，在满足故障机器人数量上限的情况下，保证任务的鲁棒性要求。进一步考虑到运动不确定的情况，Cai等人[]将机器人的运动建模为具有未知转移概率的马尔可夫决策过程，结合强化学习方法，提出一种最大化概率满足任务的策略。

近几年，随着问题的日益复杂，点对点的单机器人规划方法早已无法支持多机器人系统对复杂行为的需求[12.13]，具有高规格MRS的任务分配已经成为重要的研究课题。……