一种不确定环境下多机器人协同搜索的路径规划方法

摘要

本发明公开的不确定环境下多机器人协同搜索的路径规划方法，S1：将不确定环境地图进行栅格化，基于不确定环境的先验信息将不确定环境的栅格化地图转化为目标搜索概率图；S2：初始化多机器人的数量、优先级、初始位置和最大步长；S3：判断机器人所在栅格是否为高概率区域，如果是则采用滚动优化遗传算法进行路径规划，否则采用人工势场法进行路径规划；S4：多机器人根据路径规划结果进行搜索，并对目标搜索概率图进行更新；S5：当机器人行驶步长达到最大步长时，搜索结束，完成多机器人在不确定环境中的协同搜索，否则返回步骤S3。能够使多机器人在不确定环境下的限定步长内发现尽可能多的目标，保证障碍物避碰和机器人之间避碰，减少重复探测。

说明书

技术领域

本公开属于机器人路径规划技术领域，特别是涉及到一种不确定环境下多机器人协同搜索的路径规划方法。

背景技术

在机器人去往野外区域执行任务前，往往仅知道区域的地理位置以及目标在区域中可能存在的位置信息，区域内目标点的具体位置、环境地形以及移动障碍均为未知信息，仅在接近时能够探测到。同时，传感器的探测存在不确定性。机器人携带的燃料或装载的电池电力有限，往往不能够支撑机器人完成对整个区域的搜索。考虑以上实际因素，机器人对目标区域的搜索往往是在环境信息与传感器探测均存在较大不确定性的场景下进行的。受燃料限制，考虑环境信息，机器人应优先探测那些目标存在可能性较大的区域，以最大化发现目标的概率，在有限路程内发现尽可能多的目标。多机器人通过彼此间的信息共享进行协同搜索，避免重复探测。相比于单机器人，多机器人能够更加高效地完成对目标的搜索任务。对于未知且动态变化的环境，机器人的路径规划还要求能够实时避障，且避免多机器人之间的碰撞。

路径规划问题已有多种规划算法，包括人工势场法、RRT算法、A*算法、粒子群算法、蚁群算法、遗传算法等。每个算法具备各自独特的优缺点，将不同算法结合使用能够取长补短，融合算法优势，克服单一算法所存在的缺点。针对不确定环境下的地面机器人协同搜索路径规划，采用单一算法难以在未知环境的各种情况下均保持较高的搜索效率。根据各路径规划算法的特点，将人工势场法与遗传算法结合使用，能够在解决协同搜索路径规划问题时取得更高的搜索效率。

发明内容

有鉴于此，本公开提出了一种不确定环境下多机器人协同搜索的路径规划方法，能够使多机器人在不确定环境下的限定步长内发现尽可能多的目标，实时性强，保证了障碍物避碰和机器人之间避碰，减少重复探测。

根据本公开的一方面，提出了一种不确定环境下多机器人协同搜索的路径规划方法，所述方法包括：

S1：将所述不确定环境地图进行栅格化，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图；

S2：初始化多机器人的数量、优先级、初始位置和最大步长；

S3：针对每个机器人，判断所述机器人所在栅格是否为高概率区域，如果是高概率区域，则采用滚动优化方法结合遗传算法进行路径规划，否则，采用人工势场法进行路径规划；

S4：所述多机器人根据路径规划结果进行搜索，并对所述目标搜索概率图进行更新；

S5：当所述机器人行驶步长达到所述最大步长时，搜索结束，完成所述多机器人在不确定环境中的协同搜索的路径规划，否则，返回步骤S3。

在一种可能的实现方式中，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图，包括：

设定所述目标存在的最大概率值p

根据所述不确定环境的先验信息确定目标在所述不确定环境的栅格地图中的位置，并将所述位置的目标搜索概率设为最大概率值p

采用二维正态分布函数，初始化所述栅格地图中每个栅格的目标搜索概率，进而得到所述目标搜索概率图。

在一种可能的实现方式中，所述判断所述机器人所在栅格是否为高概率区域包括：所述机器人所在栅格与其相邻栅格的最大目标搜索概率大于预设概率阈值时，所属机器人所在栅格为高概率区域。

在一种可能的实现方式中，采用滚动优化遗传算法进行路径规划，包括：

S311：初始化机器人向前移动路径步数q，滚动优化遗传算法的最大迭代次数G、种群大小NIND、交叉概率P

S312：定义所述机器人的行动集编码，利用所述行动集编码对所述机器人的行动路径进行表征；

S313：初始化遗传算法的种群，所述种群包括以所述行动集编码随机生成NIND个长度为q*n

S314：根据Deb可行性法则，计算每个染色体的适应度；

S315：基于轮盘赌的选择策略，根据所述染色体的适应度设置所述染色体被选择的概率；

S316：采用单点交叉的交叉方式，将所述种群内的染色体随机两两配对并按照所述交叉概率P

S317：采用单点变异的变异方式，按照所述变异概率P

S318：判断是否满足迭代条件，如果是，则选择适应度最高的染色体作为最终规划结果，否则，返回S314；

S319：根据所述最终规划结果，对所述多机器人执行q步行动路径中的第一部。

在一种可能的实现方式中，采用人工势场法进行路径规划，包括：

S321：根据所述目标搜索概率图为每个栅格生成人工势场矢量；

S322：将所述机器人所在栅格的人工势场矢量与其相邻的八个搜索方向的人工势场矢量进行对比，当所述机器人所在栅格内不存在障碍物时，选择夹角最小的方向作为所述机器人的下一步行动方向。

在一种可能的实现方式中，将所述机器人所在栅格的人工势场矢量与其相邻的八个搜索方向的人工势场矢量进行对比，还包括：当所述机器人所在栅格内存在障碍物时，选择第二小夹角的方向作为所述机器人的下一步行动方向。

在一种可能的实现方式中，所述目标搜索概率图进行更新，包括：

初始化所述目标搜索概率图的每个栅格的目标搜索概率为p(x,y)；

所述目标搜索概率图的每个栅格存在目标且被所述机器人探测到的概率为α，则所述每个栅格被机器人探测后的目标搜索概率为p’(x,y)＝p(x,y)(1-α)，根据目标搜索概率p’(x,y)更新所述目标搜索概率地图。

在一种可能的实现方式中，根据Deb可行性法则，计算每个染色体的适应度，包括：

当所述种群的染色体为不可行个体时，所述每个染色体的适应度g

在一种可能的实现方式中，根据Deb可行性法则，计算每个染色体的适应度，还包括：

当所述种群的染色体为可行个体时，对所述染色体进行解码得到所述机器人在目标搜索过程中的路径S

本公开的不确定环境下多机器人协同搜索的路径规划方法，通过S1：将所述不确定环境地图进行栅格化，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图；S2：初始化多机器人的数量、优先级、初始位置和最大步长；S3：针对每个机器人，判断所述机器人所在栅格是否为高概率区域，如果是高概率区域，则采用滚动优化方法结合遗传算法进行路径规划，否则，采用人工势场法进行路径规划；S4：所述多机器人根据路径规划结果进行搜索，并对所述目标搜索概率图进行更新；S5：当所述机器人行驶步长达到所述最大步长时，搜索结束，完成所述多机器人在不确定环境中的协同搜索的路径规划，否则，返回步骤S3。能够使多机器人在不确定环境下的限定步长内发现尽可能多的目标，实时性强，保证了障碍物避碰和机器人之间避碰，减少重复探测。

根据下面参考附图对示例性实施例的详细说明，本公开的其它特征及方面将变得清楚。

附图说明

包含在说明书中并且构成说明书的一部分的附图与说明书一起示出了本公开的示例性实施例、特征和方面，并且用于解释本公开的原理。

图1示出了根据本公开一实施例的不确定环境下多机器人协同搜索的路径规划方法流程图；

图2示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的目标搜索概率分布图；

图3示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的当前栅格与相邻栅格的目标搜索概率示意图；

图4示出了根据本公开一实施例的步骤S3的进一步限定流程图；

图5示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的目标搜索方向示意图；

图6示出了根据本公开一实施例的滚动优化遗传算法的种群染色体编码示意图；

图7示出了根据本公开一实施例的多机器人间的不可行路径规划示意图；

图8示出了根据本公开另一实施例的步骤S3的进一步限定流程图；

图9示出了根据本公开另一实施例的目标搜索概率图生成的人工示势场矢量示意图；

图10示出了根据本公开另一实施例的根据目标搜索概率图生成的人工示势场矢量的搜索方向示意图；

具体实施方式

以下将参考附图详细说明本公开的各种示例性实施例、特征和方面。附图中相同的附图标记表示功能相同或相似的元件。尽管在附图中示出了实施例的各种方面，但是除非特别指出，不必按比例绘制附图。

在这里专用的词“示例性”意为“用作例子、实施例或说明性”。这里作为“示例性”所说明的任何实施例不必解释为优于或好于其它实施例。

另外，为了更好的说明本公开，在下文的具体实施方式中给出了众多的具体细节。本领域技术人员应当理解，没有某些具体细节，本公开同样可以实施。在一些实例中，对于本领域技术人员熟知的方法、手段、元件和电路未作详细描述，以便于凸显本公开的主旨。

图1示出了根据本公开一实施例的不确定环境下多机器人协同搜索的路径规划方法流程图。如图1所示，该方法可以包括：

S1：将所述不确定环境地图进行栅格化，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图。

可以根据机器人的探测半径大小将不确定环境地图的目标搜索区域进行栅格化为栅格地图，例如，可以以机器人探测半径的

图2示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的目标搜索概率分布图。

在执行目标搜索任务前能够获得目标搜索区域的先验信息，例如包含目标可能存在的栅格位置，以此为基础建立搜索概率地图等。

在一示例中，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图，可以包括：设定所述目标存在的最大概率值p

S2：初始化多机器人的数量、优先级、初始位置和最大步长。

可以初始化多机器人的数量为n、优先级为r、初始位置为s

S3：针对每个机器人，判断所述机器人所在栅格是否为高概率区域，如果是高概率区域，则采用滚动优化方法结合遗传算法进行路径规划，否则，采用人工势场法进行路径规划。

图3示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的当前栅格与相邻栅格的目标搜索概率示意图。

其中，当机器人所在栅格与其相邻栅格的最大目标搜索概率大于预设概率阈值时，该机器人所在栅格为高概率区域。

例如，预设概率阈值为ρ，则ρ＝βp

图4示出了根据本公开一实施例的步骤S3的进一步限定流程图。

当机器人所在栅格为高概率区域时，采用滚动优化遗传算法(滚动优化方法结合遗传算法)进行路径规划。采用滚动优化遗传算法的思想，即在每个时刻，为机器人向前规划多步路径，但是只执行路径规划的第一步。

在一示例中，如图4所示，采用滚动优化遗传算法进行路径规划可以包括：

S311：初始化机器人向前移动路径步数q，滚动优化遗传算法的最大迭代次数G、种群大小NIND、交叉概率P

S312：定义所述机器人的行动集编码，利用所述行动集编码对所述机器人的行动路径进行表征。

图5示出了根据本公开一实施例的不确定环境下多机器人协同搜索目标区域的目标搜索方向示意图。

可以定义机器人的行动集编码A＝{1,2,3,4,5,6,7,8}，如图5所示，分别代表机器人所在栅格和其相邻栅格的8个不同搜索方向。

假设机器人i在执行了t步规划后的状态为s

S313：初始化遗传算法的种群，所述种群包括以所述行动集编码随机生成NIND个长度为q*n

图6示出了根据本公开一实施例的滚动优化遗传算法的种群染色体编码示意图。如图6所示，满足滚动优化遗传算法规划条件的机器人个数为n

S314：根据Deb可行性法则，计算每个染色体的适应度。

图7示出了根据本公开一实施例的多机器人间的不可行路径规划示意图。

种群中的个体(染色体)并不都是可行解，存在机器人与障碍物的碰撞以及多机器人间的碰撞约束。如图7所示，在多机器人路径编码解码过程中，优先级较高的机器人路径先被解码，优先级较低的机器人将优先级较高的机器人所处栅格视作障碍物栅格。若将染色体解码后存在机器人所处栅格与障碍物栅格重合的情况，即s

在一示例中，当所述种群的染色体为不可行个体时，所述每个染色体的适应度g

当所述种群的染色体为可行个体时，其适应度大小与所在栅格的目标存在概率相关，目标搜索概率大的栅格将获得更大收益，染色体的适应度值也更高。对所述染色体进行解码得到所述机器人在目标搜索过程中的路径S

S315：基于轮盘赌的选择策略，根据所述染色体的适应度设置所述染色体被选择的概率。

可以根据染色体的适应度大小设置各个染色体被选择的概率，其中，适应度大的染色体将被复制到下一代。每个染色体被选择的概率为

S316：采用单点交叉的交叉方式，将种群内的染色体随机两两配对并按照交叉概率P

S317：采用单点变异的变异方式，按照变异概率P

S318：判断是否满足迭代条件，如果是，则选择适应度最高的染色体作为最终规划结果，否则，返回S314。

S319：根据最终规划结果，对多机器人执行q步行动路径中的第一步。

当机器人所在栅格不是高概率区域此时，采用人工势场法进行路径规划。

图8示出了根据本公开另一实施例的步骤S3的进一步限定流程图。图9示出了根据本公开另一实施例的目标搜索概率图生成的人工示势场矢量示意图。

在一示例中，如图8所示，采用人工势场法进行路径规划，可以包括：

S321：根据所述目标搜索概率图为每个栅格生成人工势场矢量。

如图9所示，根据目标搜索概率图为每个栅格生成人工势场矢量，为了避免重心偏移，每个栅格生成人工势场矢量的值为目标搜索区域内所有目标搜索概率大于预设概率阈值ρ的栅格对该栅格中心点产生的人工势场矢量之和。

比如，目标搜索区域内，目标搜索概率值大于预设概率阈值ρ的栅格(m，n)对该栅格(x，y)中心产生的人工势场矢量

然后，优先为优先级更高的机器人规划下一步路径，且在为机器人做决策时，将已完成规划的机器人所在栅格视作障碍物栅格，避免多机器人间的碰撞。

图10示出了根据本公开另一实施例的根据目标搜索概率图生成的人工示势场矢量的搜索方向示意图。

S322：将机器人所在栅格的人工势场矢量与其相邻的八个搜索方向的人工势场矢量进行对比，当所述机器人所在栅格内不存在障碍物时，选择夹角最小的方向作为所述机器人的下一步行动方向；当所述机器人所在栅格内存在障碍物时，选择第二小夹角的方向作为所述机器人的下一步行动方向。

如图10所示，对于机器人所在的中间栅格来说，相邻栅格中，栅格2与其人工势场矢量间的夹角θ

S4：所述多机器人根据路径规划结果进行搜索，并对所述目标搜索概率图进行更新。

在一示例中，初始化目标搜索概率图的每个栅格的目标搜索概率为p(x,y)；目标搜索概率图的每个栅格存在目标且被机器人探测到的概率为α，则每个栅格被机器人探测后的目标搜索概率为p’(x,y)＝p(x,y)(1-α)，根据目标搜索概率p’(x,y)更新目标搜索概率地图，并更新机器人新探测到的障碍物信息，以实现多机器人间的信息共享。

S5：当所述机器人行驶步长达到所述最大步长时，搜索结束，完成所述多机器人在不确定环境中的协同搜索的路径规划，否则，返回步骤S3。

本公开的不确定环境下多机器人协同搜索的路径规划方法，通过S1：将所述不确定环境地图进行栅格化，基于所述不确定环境的先验信息将所述不确定环境的栅格化地图转化为目标搜索概率图；S2：初始化多机器人的数量、优先级、初始位置和最大步长；S3：针对每个机器人，判断所述机器人所在栅格是否为高概率区域，如果是高概率区域，则采用滚动优化方法结合遗传算法进行路径规划，否则，采用人工势场法进行路径规划；S4：所述多机器人根据路径规划结果进行搜索，并对所述目标搜索概率图进行更新；S5：当所述机器人行驶步长达到所述最大步长时，搜索结束，完成所述多机器人在不确定环境中的协同搜索的路径规划，否则，返回步骤S3。能够使多机器人在不确定环境下的限定步长内发现尽可能多的目标，实时性强，保证了障碍物避碰和机器人之间避碰，减少重复探测。

以上已经描述了本公开的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。