本申请实施例涉及计算机技术领域，特别涉及路径规划方法、电子设备、计算机可读存储介质。
背景技术：
移动机器人的路径规划问题是目前关于机器人的研究方向中的一个热门领域，也是基础问题。在路径规划问题中，要求移动机器人依据一定的标准(如时间最短、或功耗最低、或距离最短等)，在所给定的具有障碍物的环境中寻找出一条从起始点到目标点的无碰撞最优或接近最优的路径。目前的路径规划智能算法计算复杂度高，迭代速度慢。
公开内容
本申请实施例提供一种路径规划方法、电子设备、计算机可读存储介质。
第一方面，本申请实施例提供一种路径规划方法，包括：
对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置；其中，t为当前迭代次数，所述蝠鲼个体的位置表示所述智能移动体从起点到终点之间的一条移动轨迹上的序列点的第二坐标值的集合；
根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置；
在t等于总迭代次数的情况下，输出所述第t代群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，在t小于所述总迭代次数的情况下，该方法还包括：
将t加1，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
在一些示例性实施例中，所述根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置后，该方法还包括：
对于每一个所述蝠鲼个体，采用蝠鲼翻滚觅食方法计算所述蝠鲼个体的第t代位置的镜像位置作为新的蝠鲼个体的第t代位置；
根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置；
所述输出所述第t代群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合包括：
输出所述第t代新的群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，在t小于所述总迭代次数的情况下，该方法还包括：
将t加1，将所有所述新的蝠鲼个体加入所述蝠鲼种群中，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
在一些示例性实施例中，所述采用蝠鲼翻滚觅食方法计算所述蝠鲼个体的第t代位置的镜像位置作为新的蝠鲼个体的第t代位置包括：
按照公式x′j(t)＝xj(t) s(r1xbest(t)-r2xj(t))计算第j个所述新的蝠鲼个体的第t代位置；
其中，x′j(t)为第j个所述新的蝠鲼个体的第t代位置，s为翻滚系数，r1为0到1之间第一随机数，r2为0-1之间的第二随机数，xj(t)为第j个所述蝠鲼个体的第t代位置，xbest(t)为第t代群体最优位置。
在一些示例性实施例中，所述根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置包括：
对于每一个所述新的蝠鲼个体，根据所述新的蝠鲼个体的第t代位置计算所述新的蝠鲼个体的第t代适应度值；
根据所述第t代群体最优位置计算所述第t代群体最优位置的适应度值；
确定所述第t代新的群体最优位置为所有所述新的蝠鲼个体的第t代适应度值和所述第t代群体最优位置的适应度值中，最小适应度值对应的位置。
在一些示例性实施例中，所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置包括：
生成第三随机数r3；
在所述第三随机数r3小于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼螺旋觅食方法计算所述蝠鲼个体的第t代位置。
在一些示例性实施例中，所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置包括：
生成第三随机数r3；
在所述第三随机数r3大于或等于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼链式觅食方法计算所述蝠鲼个体的第t代位置。
第二方面，本申请实施例提供一种电子设备，包括：
至少一个处理器；
存储器，所述存储器上存储有至少一个程序，当所述至少一个程序被所述至少一个处理器执行时，使得所述至少一个处理器实现上述任意一种路径规划方法。
第三方面，本申请实施例提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现上述任意一种路径规划方法。
本申请实施例提供的路径规划方法，在每一次迭代过程中，仅对蝠鲼个体采用蝠鲼觅食方法进行位置更新，无需对蝠鲼个体进行速度更新，即可获得群体最优位置，即得到智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合，计算复杂度低，收敛速度也更快，该方法不仅适用于低维度的个体搜索，也适用于高维度的个体搜索。
在一些示例性实施例中，采用蝠鲼翻滚觅食方法来计算新的蝠鲼个体的位置，即生成新的蝠鲼个体，增加了蝠鲼种群的个体多样性，缩小了搜索空间，进一步提高了收敛速度，同时也避免了个体陷入局部最优陷阱。
附图说明
图1为以第一坐标轴为纵轴为例的移动轨迹的示意图；
图2为本申请一个实施例提供的路径规划方法的流程图；
图3为本申请实施例提供的群体最优位置的适应度值随迭代次数的变化曲线图；
图4为本申请实施例提供的路径规划示意图一；
图5为本申请实施例提供的路径规划示意图二；
图6为本申请另一个实施例提供的路径规划装置的组成框图。
具体实施方式
为使本领域的技术人员更好地理解本申请的技术方案，下面结合附图对本申请提供的路径规划方法、电子设备、计算机可读存储介质进行详细描述。
在下文中将参考附图更充分地描述示例实施例，但是所述示例实施例可以以不同形式来体现且不应当被解释为限于本文阐述的实施例。反之，提供这些实施例的目的在于使本申请透彻和完整，并将使本领域技术人员充分理解本申请的范围。
在不冲突的情况下，本申请各实施例及实施例中的各特征可相互组合。
如本文所使用的，术语“和/或”包括至少一个相关列举条目的任何和所有组合。
本文所使用的术语仅用于描述特定实施例，且不意欲限制本申请。如本文所使用的，单数形式“一个”和“该”也意欲包括复数形式，除非上下文另外清楚指出。还将理解的是，当本说明书中使用术语“包括”和/或“由……制成”时，指定存在所述特征、整体、步骤、操作、元件和/或组件，但不排除存在或添加至少一个其它特征、整体、步骤、操作、元件、组件和/或其群组。
除非另外限定，否则本文所用的所有术语(包括技术和科学术语)的含义与本领域普通技术人员通常理解的含义相同。还将理解，诸如那些在常用字典中限定的那些术语应当被解释为具有与其在相关技术以及本申请的背景下的含义一致的含义，且将不解释为具有理想化或过度形式上的含义，除非本文明确如此限定。
目前的路径规划智能算法基本思想都是模拟自然界生物群体行为来构造随机优化算法，如粒子群算法、蚁群算法、神经网络算法、遗传算法、萤火虫算法、天牛须算法、蝙蝠算法、布谷鸟搜索算法，等等。
其中，粒子群算法在迭代过程中需要每次更新个体的位置和速度两个变量，计算相对复杂，仅仅适用于低纬度空间搜索，收敛速度也比较慢。
神经网络算法本质上为梯度下降法，优化的目标函数的复杂性导致该算法收敛速度慢。
萤火虫算法必须要求感知范围内有优秀个体向其提供信息，否则个体将停止搜索，该算法对优秀个体的依赖程度太高，从而降低了收敛速度。
天牛须算法仅仅适用于低维度最优解搜索，收敛速度慢。
总之，目前的路径规划智能算法计算复杂度高，迭代速度慢。
本申请实施例基于蝠鲼觅食优化(mrfo，mantarayforagingoptimization)算法进行路径规划，蝠鲼觅食优化算法是由赵维国等人在2019年提出的新型智能仿生群体算法。蝠鲼是海洋中的一种大型鱼类，体型硕大仅次于鲸鱼，常结成庞大的群体一同觅食，蝠鲼的食物通常是浮游在海洋中的藻类，具有寻优能力强，收敛快的特点。蝠鲼觅食优化算法是模仿蝠鲼在海洋中的觅食过程，针对不同的捕食策略进行数学建模，对蝠鲼个体位置更新的方式进行数学描述，从而实现在复杂的空间中对最优解的搜索。由于位置更新方式的独特性，蝠鲼觅食优化算法的求解精度与鲁棒性相比传统的群体智能仿生算法也有显著的提升。蝠鲼觅食优化算法可描述为3种觅食行为，包括链式觅食、螺旋觅食以及翻滚觅食。
本申请实施例的路径规划方法虽然是基于移动机器人提出的，但是本申请实施例的路径规划方法同样适用于其他需要进行路径规划的智能移动体，如实现自动驾驶的汽车、玩具汽车等。
本申请实施例的路径规划方法中，假设智能移动体的移动轨迹位于二维平面内，并且智能移动体的移动环境中的障碍物是静止不动的。
如图1所示，对智能移动体的移动轨迹所在的二维平面建立二维坐标系，平面上的任何点都可以采用二维坐标(x，y)来表示，例如，智能移动体的起点s0的坐标为(x0，y0)，智能移动体的终点sn的坐标为(xn，yn)。
本申请实施例的路径规划方法中，将智能移动体的起点的第一坐标值和终点的第一坐标值之差的绝对值分成n等分，n为大于或等于1的整数，即在二维坐标系上可以画出n 1条平行于第一坐标轴的等分线{l0，l1，…，ln}，那么，智能移动体的路径规划可以转换为在每一条等分线上寻找一个点si，将所有等分线上的点连起来即为智能移动体的移动轨迹，即可以表示为{s0，s1，……，sn}，如果n足够大，则移动轨迹是一条连续的曲线。也就是说，路径规划的过程也就是搜索以下序列点的坐标值的集合：
s＝{s0,s1,…,sn}＝{(x0,y0)，(x1,y1)，(x2,y2)，…，(xn,yn)}(1)
序列点的坐标值包括第一坐标值和第二坐标值，由于每一个序列点对应一条等分线，因此，序列点的第一坐标值即为对应的等分线的第一坐标值，而等分线的第一坐标值可以根据起点的第一坐标值和终点的第一坐标值计算得到，序列点的第二坐标值即为需要搜索的坐标值，也就是说，路径规划的过程也就是搜索公式(1)中的序列点的第二坐标值的集合。
其中，第一坐标值可以是横坐标的坐标值，也可以是纵坐标的坐标值，第一坐标轴可以是横轴(即x轴)，也可以是纵轴(即y轴)。当第一坐标值为横坐标的坐标值时，第二坐标值为纵坐标的坐标值，第一坐标轴为纵轴；当第一坐标值为纵坐标的坐标值时，第二坐标值为横坐标的坐标值，第一坐标轴为横轴。
其中，相邻两条等分线的第一坐标值之差的绝对值等于起点的第一坐标值和终点的第一坐标值之差的绝对值的n分之一，那么第i条等分线的第一坐标值为：起点的第一坐标值加上起点的第一坐标值和终点的第一坐标值之差的绝对值的n分之i，i为0到n之间的整数。
图1中以第一坐标轴为纵轴为例给出了移动轨迹的一个示意图。如图1所示，将智能移动体的起点的y坐标的坐标值和终点的y坐标的坐标值之差的绝对值分成n等分，即在二维坐标系上可以画出n 1条平行于x轴的等分线{l0，l1，…，ln}，那么，智能移动体的路径规划可以转换为搜索公式(1)中的序列点的x坐标的坐标值的集合。
其中，第i条等分线的y坐标的坐标值yi为：
图2为本申请一个实施例提供的路径规划方法的流程图。
第一方面，参照图2，本申请一个实施例提供一种路径规划方法，包括：
步骤200、对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置；其中，t为当前迭代次数，所述蝠鲼个体的位置表示所述智能移动体从起点到终点之间的一条移动轨迹上的序列点的第二坐标值的集合。
在本申请实施例中，蝠鲼个体的第t代位置是一个d维向量，表示所述智能移动体从起点到终点之间的一条移动轨迹上的序列点的第二坐标值的集合。例如，在第二坐标值为横坐标的坐标值的情况下，第i个蝠鲼个体的第t代位置可以表示为xi(t)＝(xi，0(t),xi，1(t),xi，2(t)...xi，n(t))；在第二坐标值为纵坐标的坐标值的情况下，第i个蝠鲼个体的第t代位置可以表示为yi(t)＝(yi，0(t),yi，1(t),yi，2(t)...yi，n(t))。
其中，d＝n 1，n为将智能移动体的起点的第一坐标值和终点的第一坐标值之差的绝对值进行划分的等分参数，即如前所述，将智能移动体的起点的第一坐标值和终点的第一坐标值之差的绝对值分成n等分。
在本申请实施例中，在进行第一次迭代之前，将t初始化为1。
在本申请实施例中，在t等于1的情况下，蝠鲼个体的第(t－1)代位置为蝠鲼个体的位置初始值，第(t－1)代群体最优位置为群体最优位置初始值。
在一些示例性实施例中，在第二坐标值为横坐标的坐标值的情况下，第i个蝠鲼个体的位置初始值为：
xi(0)＝lb r4(ub-lb)(2)
其中，xi(0)为第i个蝠鲼个体的位置初始值，lb为蝠鲼个体的位置的下边界值，ub为蝠鲼个体的位置的上边界值，r4为0到1之间的第四随机数。
在一些示例性实施例中，在第二坐标值为纵坐标的坐标值的情况下，第i个蝠鲼个体的位置初始值为：
yi(0)＝lb r4(ub-lb)(3)
其中，yi(0)为第i个蝠鲼个体的位置初始值，lb为蝠鲼个体的位置的下边界值，ub为蝠鲼个体的位置的上边界值，r4为0到1之间的第四随机数。
其中，lb和ub均为d维向量，lb中的每一个元素均为第二坐标值的最小值，即起点的第二坐标值和终点的第二坐标值的最小值，ub中的每一个元素均为第二坐标值的最大值，即起点的第二坐标值和终点的第二坐标值的最大值。
在本申请实施例中，路径规划的目的是寻求一条与障碍物没有发生碰撞、且路径最短、且没有出现急转弯的最优移动轨迹，基于此目的构建适应度函数，如下述公式(4)和公式(5)，所构建的适应度函数应满足适应度函数值越小的移动轨迹越优。
在一些示例性实施例中，群体最优位置初始值根据所有蝠鲼个体的位置初始值计算得到。具体的，分别计算每一个蝠鲼个体的适应度初始值，确定群体最优位置初始值为适应度初始值最小的蝠鲼个体的位置初始值。
在一些示例性实施例中，在第二坐标值为横坐标的坐标值的情况下，按照公式(4)计算第i个蝠鲼个体的适应度初始值。
f(xi(0))＝k1×l(xi(0)) k2×ψ(xi(0)) p(xi(0))(4)
其中，f(xi(0))为第i个蝠鲼个体的适应度初始值，l(xi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的距离，ψ(xi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的所有夹角之和，p(xi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的惩罚函数值，k1 k2＝1，k1，k2为调节因子。
在一些示例性实施例中，在第二坐标值为纵坐标的坐标值的情况下，按照公式(5)计算第i个蝠鲼个体的适应度初始值。
f(yi(0))＝k1×l(yi(0)) k2×ψ(yi(0)) p(yi(0))(5)
其中，f(yi(0))为第i个蝠鲼个体的适应度初始值，l(yi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的距离，ψ(yi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的所有夹角之和，p(yi(0))为第i个蝠鲼个体的位置初始值所表示的移动轨迹的惩罚函数值，k1 k2＝1，k1，k2为调节因子。
下面以第二坐标值为横坐标的坐标值为例说明l(xi(0))，ψ(xi(0))，p(xi(0))的计算方式，第二坐标值为纵坐标的坐标值的情况下l(yi(0))，ψ(yi(0))，p(yi(0))的计算方式与第二坐标值为横坐标的坐标值的情况类似，这里不再赘述。
(1)l(xi(0))的计算方式
按照公式(6)计算l(xi(0))。
其中，xi，k 1(0)为第i个蝠鲼个体的位置初始值的第(k 1)维取值，xi，k(0)为第i个蝠鲼个体的位置初始值的第k维取值，d为第i个蝠鲼个体的位置初始值所表示的移动轨迹上相邻两个序列点的第一坐标值之差，具体取值为智能移动体的终点的第一坐标值和起点的第一坐标值之差和n的比值。
(2)ψ(xi(0))的计算方式
由于没有出现急转弯的移动轨迹由于出现急转弯的移动轨迹，根据运动学原理，智能移动体的移动轨迹相邻三个点之间的夹角越大，相邻三个点组成的移动轨迹越平滑，因此，相邻三个点之间的夹角之和越大，移动轨迹越优，为了满足适应度函数值越小的移动轨迹越优，所构建的适应度函数应该取相邻三个点之间的夹角的补角之和，如公式(7)。
也就是说，可以按照公式(7)计算ψ(xi(0))。
其中，
(3)p(xi(0))的计算方式
为了满足适应度函数值越小的移动轨迹越优，对与障碍物发生碰撞的移动轨迹进行惩罚，从而构建惩罚函数，具体的，根据第i个蝠鲼个体的位置初始值所表示的移动轨迹上的所有序列点与所有障碍物相交的次数计算p(xi(0))，如公式(8)。
p(xi(0))＝g×m(0)(8)
其中，g为惩罚因子，g>0，m(0)为第i个蝠鲼个体的位置初始值所表示的移动轨迹上的所有序列点与所有障碍物相交的次数。
其中，m可以采用以下方式来计算：
计算第k个序列点和第m个障碍物的质心的距离；
在第k个序列点和第m个障碍物的质心的距离小于或等于第m个障碍物的轮廓半径的情况下，将n加1；
在第k个序列点和第m个障碍物的质心的距离大于第m个障碍物的轮廓半径的情况下，将m加1，继续执行计算第k个序列点和第m个障碍物的质心的距离的步骤；
在所有障碍物计算完成的情况下，将m替换为1，将k加1，继续执行计算第k个序列点和第m个障碍物的质心的距离的步骤，直到所有序列点计算完成。
其中，按照公式(9)计算第k个序列点和第m个障碍物的质心的距离。
其中，di，k，m(0)为第k个序列点和第m个障碍物的质心的距离，xi，k(0)为第i个蝠鲼个体的位置初始值的第k维取值，xobsm为第m个障碍物的质心的横坐标的坐标值，yi，k(0)为第i个蝠鲼个体的位置初始值所表示的移动轨迹上的第k个序列点的纵坐标的坐标值，yobsm为第m个障碍物的质心的纵坐标的坐标值。
其中，第m个障碍物的轮廓半径为第m个障碍物的最小外接圆的半径。
在一些示例性实施例中，所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置包括：
生成第三随机数r3；
在所述第三随机数r3小于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼螺旋觅食方法计算所述蝠鲼个体的第t代位置。
在一些示例性实施例中，第三随机数r3为0到1之间的随机数。
本申请实施例对预设阈值不作限定，例如，预设阈值可以取为0.5。
下面以第二坐标值为横坐标的坐标值为例说明蝠鲼个体的位置更新，第二坐标值为纵坐标的坐标值的情况的蝠鲼个体是位置更新与第二坐标值为横坐标的坐标值的情况类似，这里不再赘述。
在一些示例性实施例中，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼螺旋觅食方法计算所述蝠鲼个体的第t代位置包括：
在(t-1)和总迭代次数t的比值大于第三随机数r3的情况下，按照公式(10)计算第i个蝠鲼个体的第t代位置。
其中，xi(t)为第i个蝠鲼个体的第t代位置，xbest(t-1)为第(t－1)代群体最优位置，r5为0到1之间的第五随机数，xi(t-1)为第i个蝠鲼个体的第(t－1)代位置，
在一些示例性实施例中，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼螺旋觅食方法计算所述蝠鲼个体的第t代位置包括：
在(t-1)和总迭代次数t的比值小于或等于第三随机数r3的情况下，按照公式(11)计算第i个蝠鲼个体的第t代位置。
其中，xi(t)为第i个蝠鲼个体的第t代位置，xrand(t-1)＝lb r7(ub-lb)，r7为0到1之间的第七随机数，r5为0到1之间的第五随机数，xi(t-1)为第i个蝠鲼个体的第(t－1)代位置，
在一些示例性实施例中，所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置包括：
生成第三随机数r3；
在所述第三随机数r3大于或等于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼链式觅食方法计算所述蝠鲼个体的第t代位置。
在一些示例性实施例中，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼链式觅食方法计算所述蝠鲼个体的第t代位置包括：
按照公式(12)计算第i个蝠鲼个体的第t代位置。
其中，xi(t)为第i个蝠鲼个体的第t代位置，xbest(t-1)为第(t－1)代群体最优位置，r5为0到1之间的第五随机数，xi(t-1)为第i个蝠鲼个体的第(t－1)代位置，
步骤201、根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置。
在一些示例性实施例中，根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置包括：
分别计算每一个蝠鲼个体的第t代适应度值；
计算第(t－1)代群体最优位置的适应度值；
确定第t代群体最优位置为所有蝠鲼个体的第t代适应度值和第(t－1)代群体最优位置的适应度值中，最小适应度值对应的位置。
在某一个蝠鲼个体的第t代适应度值最小的情况下，最小适应度值对应的位置为该某一个蝠鲼个体的第t代位置；在第(t－1)代群体最优位置的适应度值最小的情况下，最小适应度值对应的位置为第(t－1)代群体最优位置。
在一些示例性实施例中，在第二坐标值为横坐标的坐标值的情况下，按照公式(13)计算第i个蝠鲼个体的第t代适应度值。
f(xi(t))＝k1×l(xi(t)) k2×ψ(xi(t)) p(xi(t))(13)
其中，f(xi(t))为第i个蝠鲼个体的第t代适应度值，l(xi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的距离，ψ(xi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的所有夹角之和，p(xi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的惩罚函数值，k1 k2＝1，k1，k2为调节因子。
在一些示例性实施例中，在第二坐标值为纵坐标的坐标值的情况下，按照公式(14)计算第i个蝠鲼个体的第t代适应度值；
f(yi(t))＝k1×l(yi(t)) k2×ψ(yi(t)) p(yi(t))(14)
其中，f(yi(t))为第i个蝠鲼个体的第t代适应度值，l(yi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的距离，ψ(yi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的所有夹角之和，p(yi(t))为第i个蝠鲼个体的第t代位置所表示的移动轨迹的惩罚函数值，k1 k2＝1，k1，k2为调节因子。
下面以第二坐标值为横坐标的坐标值为例说明l(xi(t))，ψ(xi(t))，p(xi(t))的计算方式，第二坐标值为纵坐标的坐标值的情况下l(yi(t))，ψ(yi(t))，p(yi(t))的计算方式与第二坐标值为横坐标的坐标值的情况类似，这里不再赘述。
(1)l(xi(t))的计算方式
按照公式(15)计算l(xi(t))。
其中，xi，k 1(t)为第i个蝠鲼个体的第t代位置的第(k 1)维取值，xi，k(t)为第i个蝠鲼个体的第t代位置的第k维取值，d为第i个蝠鲼个体的第t代位置所表示的移动轨迹上相邻两个序列点的第一坐标值之差，具体取值为智能移动体的终点的第一坐标值和起点的第一坐标值之差和n的比值。
(2)ψ(xi(t))的计算方式
由于没有出现急转弯的移动轨迹由于出现急转弯的移动轨迹，根据运动学原理，智能移动体的移动轨迹相邻三个点之间的夹角越大，相邻三个点组成的移动轨迹越平滑，因此，相邻三个点之间的夹角之和越大，移动轨迹越优，为了满足适应度函数值越小的移动轨迹越优，所构建的适应度函数应该取相邻三个点之间的夹角的补角之和，如公式(16)。
也就是说，可以按照公式(16)计算ψ(xi(t))。
其中，
(3)p(xi(t))的计算方式
为了满足适应度函数值越小的移动轨迹越优，对与障碍物发生碰撞的移动轨迹进行惩罚，从而构建惩罚函数，具体的，根据第i个蝠鲼个体的位置初始值所表示的移动轨迹上的所有序列点与所有障碍物相交的次数计算p(xi(t))，如公式(17)。
p(xi(t))＝g×m(t)(17)
其中，g为惩罚因子，g>0，m(t)为第i个蝠鲼个体的第t代位置所表示的移动轨迹上的所有序列点与所有障碍物相交的次数。
其中，m可以采用以下方式来计算：
计算第k个序列点和第m个障碍物的质心的距离；
在第k个序列点和第m个障碍物的质心的距离小于或等于第m个障碍物的轮廓半径的情况下，将n加1；
在第k个序列点和第m个障碍物的质心的距离大于第m个障碍物的轮廓半径的情况下，将m加1，继续执行计算第k个序列点和第m个障碍物的质心的距离的步骤；
在所有障碍物计算完成的情况下，将m替换为1，将k加1，继续执行计算第k个序列点和第m个障碍物的质心的距离的步骤，直到所有序列点计算完成。
其中，按照公式(18)计算第k个序列点和第m个障碍物的质心的距离。
其中，di，k，m(t)为第k个序列点和第m个障碍物的质心的距离，xi，k(t)为第i个蝠鲼个体的第t代位置的第k维取值，xobsm为第m个障碍物的质心的横坐标的坐标值，yi，k(t)为第i个蝠鲼个体的第t代位置所表示的移动轨迹上的第k个序列点的纵坐标的坐标值，yobsm为第m个障碍物的质心的纵坐标的坐标值。
其中，第m个障碍物的轮廓半径为第m个障碍物的最小外接圆的半径。
在本申请实施例中，第(t－1)代群体最优位置的适应度值的计算方式与蝠鲼个体的第t代适应度值的计算方式类似，仅需要将公式(13)到公式(18)中的xi(t)替换为xbest(t-1)即可，xbest(t-1)为第(t－1)代群体最优位置。
步骤202、在t等于总迭代次数的情况下，输出所述第t代群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，在t小于所述总迭代次数的情况下，将t加1，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
本申请实施例提供的路径规划方法，在每一次迭代过程中，仅对蝠鲼个体采用蝠鲼觅食方法进行位置更新，无需对蝠鲼个体进行速度更新，即可获得群体最优位置，即得到智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合，计算复杂度低，收敛速度也更快，该方法不仅适用于低维度的个体搜索，也适用于高维度的个体搜索。
在一些示例性实施例中，所述根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置后，该方法还包括：
对于每一个所述蝠鲼个体，采用蝠鲼翻滚觅食方法计算所述蝠鲼个体的第t代位置的镜像位置作为新的蝠鲼个体的第t代位置；
根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置；
所述输出所述第t代群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合包括：
输出所述第t代新的群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，在t小于所述总迭代次数的情况下，将t加1，将所有所述新的蝠鲼个体加入所述蝠鲼种群中，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
在一些示例性实施例中，所述采用蝠鲼翻滚觅食方法计算所述蝠鲼个体的第t代位置的镜像位置作为新的蝠鲼个体的第t代位置包括：
按照公式x′j(t)＝xj(t) s(r1xbest(t)-r2xj(t))计算第j个所述新的蝠鲼个体的第t代位置；
其中，x′j(t)为第j个所述新的蝠鲼个体的第t代位置，s为翻滚系数，r1为0到1之间第一随机数，r2为0-1之间的第二随机数，xj(t)为第j个所述蝠鲼个体的第t代位置，xbest(t)为第t代群体最优位置。
在一些示例性实施例中，所述根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置包括：
对于每一个所述新的蝠鲼个体，根据所述新的蝠鲼个体的第t代位置计算所述新的蝠鲼个体的第t代适应度值；
根据所述第t代群体最优位置计算所述第t代群体最优位置的适应度值；
确定所述第t代新的群体最优位置为所有所述新的蝠鲼个体的第t代适应度值和所述第t代群体最优位置的适应度值中，最小适应度值对应的位置。
在某一个新的蝠鲼个体的第t代适应度值最小的情况下，最小适应度值对应的位置为该某一个新的蝠鲼个体的第t代位置；在第t代群体最优位置的适应度值最小的情况下，最小适应度值对应的位置为第t代群体最优位置。
在本申请实施例中，新的蝠鲼个体的第t代适应度值的计算方式与蝠鲼个体的第t代适应度值的计算方式类似，仅需要将公式(13)到公式(18)中的xi(t)替换为x′j(t)即可，x′j(t)为第j个新的蝠鲼个体的第t代位置。
在本申请实施例中，第t代群体最优位置的适应度值的计算方式与蝠鲼个体的第t代适应度值的计算方式类似，仅需要将公式(13)到公式(18)中的xi(t)替换为xbest(t)即可，xbest(t)为第t代群体最优位置。
在一些示例性实施例中，采用蝠鲼翻滚觅食方法来计算新的蝠鲼个体的位置，即生成新的蝠鲼个体，增加了蝠鲼种群的个体多样性，缩小了搜索空间，进一步提高了收敛速度，同时也避免了个体陷入局部最优陷阱。
图3为本申请实施例提供的群体最优位置的适应度值随迭代次数的变化曲线图。如图3所示，随着迭代次数的增加，群体最优位置的适应度值逐渐减小，减小到一定数值后保持不变，当群体最优位置的适应度值不变时，次数的群体最优位置所表示的移动轨迹即为最优移动轨迹。
图4和图5给出了路径规划的两个示意图。如图4和图5所示，最终得到的移动轨迹均没有与障碍物相交，该计算复杂度低，收敛速度也更快，该方法不仅适用于低维度的个体搜索，也适用于高维度的个体搜索，同时也避免了个体陷入局部最优陷阱。
第二方面，本申请实施例提供一种电子设备，其包括：
至少一个处理器；
存储器，存储器上存储有至少一个程序，当至少一个程序被至少一个处理器执行时，使得至少一个处理器实现上述任意一种路径规划方法。
其中，处理器为具有数据处理能力的器件，其包括但不限于中央处理器(cpu)等；存储器为具有数据存储能力的器件，其包括但不限于随机存取存储器(ram，更具体如sdram、ddr等)、只读存储器(rom)、带电可擦可编程只读存储器(eeprom)、闪存(flash)。
在一些实施例中，处理器、存储器通过总线相互连接，进而与计算设备的其它组件连接。
第三方面，本申请实施例提供一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现上述任意一种路径规划方法。
图6为本申请另一个实施例提供的路径规划装置的组成框图。
第四方面，参照图6，本申请另一个实施例提供一种路径规划装置，包括：
位置更新模块601，用于对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置；其中，t为当前迭代次数，所述蝠鲼个体的位置表示所述智能移动体从起点到终点之间的一条移动轨迹上的序列点的第二坐标值的集合；
群体最优位置计算模块602，用于根据所述蝠鲼种群中的所有所述蝠鲼个体的第t代位置和所述第(t－1)代群体最优位置计算第t代群体最优位置；
输出模块603，用于在t等于总迭代次数的情况下，输出所述第t代群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，位置更新模块601还用于：
在t小于所述总迭代次数的情况下，将t加1，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
在一些示例性实施例中，还包括：
新个体生成模块604，用于对于每一个所述蝠鲼个体，采用蝠鲼翻滚觅食方法计算所述蝠鲼个体的第t代位置的镜像位置作为新的蝠鲼个体的第t代位置；
群体最优位置计算模块602还用于：根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置；
输出模块603具体用于：
在t等于总迭代次数的情况下，输出所述第t代新的群体最优位置作为所述智能移动体从起点到终点之间的最优移动轨迹上的序列点的第二坐标值的集合。
在一些示例性实施例中，位置更新模块601还用于：
在t小于所述总迭代次数的情况下，将t加1，将所有所述新的蝠鲼个体加入所述蝠鲼种群中，继续执行所述对于蝠鲼种群中的每一个蝠鲼个体，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置的步骤。
在一些示例性实施例中，新个体生成模块604具体用于：
按照公式x′j(t)＝xj(t) s(r1xbest(t)-r2xj(t))计算第j个所述新的蝠鲼个体的第t代位置；
其中，x′j(t)为第j个所述新的蝠鲼个体的第t代位置，s为翻滚系数，r1为0到1之间第一随机数，r2为0-1之间的第二随机数，xj(t)为第j个所述蝠鲼个体的第t代位置，xbest(t)为第t代群体最优位置。
在一些示例性实施例中，群体最优位置计算模块602具体用于采用以下方式实现所述根据所有所述新的蝠鲼个体的第t代位置和所述第t代群体最优位置计算第t代新的群体最优位置：
对于每一个所述新的蝠鲼个体，根据所述新的蝠鲼个体的第t代位置计算所述新的蝠鲼个体的第t代适应度值；
根据所述第t代群体最优位置计算所述第t代群体最优位置的适应度值；
确定所述第t代新的群体最优位置为所有所述新的蝠鲼个体的第t代适应度值和所述第t代群体最优位置的适应度值中，最小适应度值对应的位置。
在一些示例性实施例中，位置更新模块601具体用于采用以下方式实现所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置：
生成第三随机数r3；
在所述第三随机数r3小于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼螺旋觅食方法计算所述蝠鲼个体的第t代位置。
在一些示例性实施例中，位置更新模块601具体用于采用以下方式实现所述根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼觅食方法计算所述蝠鲼个体的第t代位置：
生成第三随机数r3；
在所述第三随机数r3大于或等于预设阈值的情况下，根据所述蝠鲼个体的第(t－1)代位置和第(t－1)代群体最优位置，采用蝠鲼链式觅食方法计算所述蝠鲼个体的第t代位置。
本申请实施例的路径规划装置的具体实现过程与前述实施例的路径规划方法的具体实现过程相同，这里不再赘述。
本领域普通技术人员可以理解，上文中所公开方法中的全部或某些步骤、系统、装置中的功能模块/单元可以被实施为软件、固件、硬件及其适当的组合。在硬件实施方式中，在以上描述中提及的功能模块/单元之间的划分不一定对应于物理组件的划分；例如，一个物理组件可以具有多个功能，或者一个功能或步骤可以由若干物理组件合作执行。某些物理组件或所有物理组件可以被实施为由处理器，如中央处理器、数字信号处理器或微处理器执行的软件，或者被实施为硬件，或者被实施为集成电路，如专用集成电路。这样的软件可以分布在计算机可读介质上，计算机可读介质可以包括计算机存储介质(或非暂时性介质)和通信介质(或暂时性介质)。如本领域普通技术人员公知的，术语计算机存储介质包括在用于存储信息(诸如计算机可读指令、数据结构、程序模块或其它数据)的任何方法或技术中实施的易失性和非易失性、可移除和不可移除介质。计算机存储介质包括但不限于ram、rom、eeprom、闪存或其它存储器技术、cd-rom、数字多功能盘(dvd)或其它光盘存储、磁盒、磁带、磁盘存储或其它磁存储器、或者可以用于存储期望的信息并且可以被计算机访问的任何其它的介质。此外，本领域普通技术人员公知的是，通信介质通常包含计算机可读指令、数据结构、程序模块或者诸如载波或其它传输机制之类的调制数据信号中的其它数据，并且可包括任何信息递送介质。
本文已经公开了示例实施例，并且虽然采用了具体术语，但它们仅用于并仅应当被解释为一般说明性含义，并且不用于限制的目的。在一些实例中，对本领域技术人员显而易见的是，除非另外明确指出，否则可单独使用与特定实施例相结合描述的特征、特性和/或元素，或可与其它实施例相结合描述的特征、特性和/或元件组合使用。因此，本领域技术人员将理解，在不脱离由所附的权利要求阐明的本申请的范围的情况下，可进行各种形式和细节上的改变。
