一种基于多目标萤火虫算法的路径规划方法

摘要

本发明提出一种基于多目标萤火虫算法的路径规划方法，属于路径规划技术领域，包括：对路径规划问题进行建模、初始化多目标萤火虫算法、更新萤火虫位置并确定非劣解集、更新外部档案文件、判断是否达到预先设定的最大迭代次数和确定Pareto最优路径。本发明基于Pareto支配的概念对基本萤火虫算法进行改进，很好地利用了萤火虫算法的全局搜索与并行计算能力。在规划中同时考虑多个路径性能指标，一次规划就能够得到一组Pareto最优解集，具有很大的灵活性。这种路径规划方法异于传统的针对单一目标的路径规划方法和采用加权法把多目标转化为单目标的路径规划方法，能更好地满足路径规划的实际需要。

主权项

1.一种基于多目标萤火虫算法的路径规划方法，其特征在于：具体包括以下几个步骤： 步骤一：对路径规划问题进行数学建模： （1）对路径规划的环境进行数学建模： 在二维平面中进行路径规划，S为机器人的出发点，G为终点，在路径规划范围内建立全局坐标系O-XY，若n个路径点组成一个路径，则路径表示为P＝{S,p₁,p₂,...,p_n,G}，其中(p₁,p₂,...,p_n)为全局地图中的路径点的序列，为路径规划的目标； 在全局坐标系O-XY中，路径点序列的坐标为二维的，为减小编码的长度，建立一个坐标系S-X'Y'，以出发点S为坐标系原点，以作X'轴，垂直于X'且经过S点的射线作为Y'轴，对应的坐标变换为：其中(x,y),(x',y')分别为地图中某一点在坐标系O-XY和S-X'Y'下的坐标，θ为坐标轴X与坐标轴X'之间的夹角，(x_s,y_s)为S点在坐标系O-XY下的坐标； 将线段SG进行n+1等分，在每一个等分点作垂线，得到平行直线族(l₁,l₂,...,l_n)，平行直线族与待确定的路径P的交点为目标路径点序列(p₁,p₂,...,p_n)；定义S为起始路径点p₀，G为终止路径点p_n+1，一条候选路径表示成一系列可用路径点的集合P＝(p₀,p₁,p₂,...,p_n,p_n+1)，路径规划的目的为找到起始点和终止点之外的n个路径点(p₁,p₂,...,p_n)； 由于平行直线族(l₁,l₂,...,l_n)相邻直线之间的距离相同，所以根据这些路径点在路径点集合中的序号确定其在S-X'Y'坐标系中的横坐标，纵坐标初始化为工作区域中的随机数，为待优化部分，因此，对于某一序号为i的路径点，其在S-X'Y'坐标系中的横坐标x′_i和纵坐标 _y′_i分别表示为： 其中，x′_i、_y′_i分别表示序号为i的路径点在S-X'Y'坐标系中的横坐标值和纵坐标值；L_SG是起始点S和目标点G之间的距离，Y′_min和Y′_max分别为纵坐标的最小值和最大值，rand(Y′_min,Y′_max)表示在(Y′_min,Y′_max)内服从均匀分布的随机数； （2）确定路径的三个评价函数，分别衡量路径长度、路径平滑度和路径安全性： 设任意一条可行路径为P＝(p₀,p₁,p₂,...,p_n,p_n+1)，则多目标路径规划问题的3个性能指标定义如下： （1）路径长度f₁(P) 对于一条路径P＝(p₀,p₁,p₂,...,p_n,p_n+1)，由n+1条路径段组成，该路径的长度即n+1条 路径段的长度之和； 其中i表示路径点的下标；|p_ip_i+1|表示路径点i和路径点i+1之间的路径段的长度；x′_i+1和y′_i+1分别表示序号为i+1的路径点在S-X'Y'坐标系中的横坐标值和纵坐标值；x′_i和_y′_i分别表示序号为i的路径点在S-X'Y'坐标系中的横坐标值和纵坐标值，|p₀p₁|表示路径点p₀和路径点p₁之间的路径段的长度； （2）路径平滑度f₂(P) 将每个路径段看成一个矢量，根据斜率计算出其与X'轴的夹角，为路径方向角，计算相邻两段路径段的方向角的差值，得到偏转角度α_i，用偏转角度大小描述路径的平滑程度： f₂(P)为路径P的平均拐角值，α_i(i＝1,2,...n)表示两向量p_i-1p_i和p_ip_i+1的夹角（0≤α_i＜π）；n为n+1条路径段中相邻路径段向量之间夹角的个数；k为α_i中大于或等于π/2的个数，当某一夹角大于或等于π/2时，对目标值进行惩罚； （3）路径安全距离f₃(P) 安全度是指机器人与障碍物之间的距离大小，如果移动机器人尺寸较大，则不能被视为一个质点，为了防止其某一部位与障碍物发生碰撞，使其与障碍物保持一定的路径安全距离f₃(P)： 其中，d表示路径P距离所有障碍物的最短距离； （4）对不可行路径进行惩罚 根据路径是否会碰撞障碍物，把路径分为可行路径和不可行路径，判断一条路径是否为可行路径，给定一条路径判断它与环境的相交信息，障碍物设定为多边形，由一组顶点坐标描述出来，因此，计算每条路径段与障碍物每条边的相交信息，得出整条路径与障碍物的相交信息； 为保证每条不可行路径的目标函数值比所有可行路径的适应度值大，在计算不可行路径目标函数值时，加上一个惩罚值，对于不可行路径，以上三个目标函数值的计算如下： f_i(P)＝W_i+m×C_i,i＝1,2,3 其中，W_i为所有可行路径在目标函数f_i上的最差值；m为不可行路径P中不可行路径段的个数；C_i为惩罚因子； 步骤二：初始化多目标萤火虫算法： 首先，初始化多目标萤火虫算法的参数：种群大小N、外部档案文件大小N_a和最大迭代 次数T_max；初始化萤火虫的位置，每只萤火虫代表一条备选路径，经过步骤一对路径编码的简化，萤火虫位置向量的每一维分量依次代表备选路径上各个路径点的纵坐标，在搜索空间内随机初始化萤火虫的初始位置，如果要确定n个路径点，则萤火虫的位置向量为n维向量； 步骤三：更新萤火虫的位置，并确定非劣解集： 在FA中，萤火虫通过发光实现信息共享，采用亮度来区分萤火虫所代表的解的优劣，亮度大的萤火虫吸引亮度小的萤火虫向它移动，从而使得整个种群向着更好的区域移动，把萤火虫所在位置的目标函数值定义为其亮度，采用Pareto支配的概念区分FA中的萤火虫的亮度大小，同时结合FA的信息共享机制，引导萤火虫不断地移动； 更新萤火虫位置和确定非劣解集的具体方法为： 首先，依次把各个萤火虫的位置向量代入到路径长度、路径平滑度和路径安全性这三个目标函数，并判断路径是否可行，对不可行路径进行惩罚，得到每只萤火虫对应的目标函数向量； 对种群中的任意两只萤火虫，基于Pareto支配的概念，判断萤火虫之间的Pareto支配关系，如果某萤火虫iPareto支配萤火虫j，则表示i所代表的路径更优，j会被i吸引而更新自己的位置，其位置更新公式为： 其中t为迭代次数；为萤火虫i和j所处的空间位置；α为常数，取α∈[0,1]，为随机数向量；β_ij(r_ij)为萤火虫i对萤火虫j的吸引力，定义为： 其中β₀为最大吸引力，_γ为光吸收系数，r_ij为萤火虫i到萤火虫j的距离；n为萤火虫位置向量的维数，x_i,k为萤火虫i位置向量的第k维分量，x_j,k为萤火虫j位置向量的第k维分量，在实现上述迭代的过程中，保存不受任何其他萤火虫支配的萤火虫为本次迭代的非劣解集；步骤四：更新外部档案文件： 采用外部档案文件用来保存在迭代过程中获得的所有性能都较好的路径，最初外部档案文件是空的，随着迭代的进行，用步骤三中每一代产生的非劣解集更新外部档案文件，档案文件的更新策略为：对于非劣解集中的每个非劣解，如果非劣解受档案成员支配，则拒绝非劣解加入档案中；如果非劣解支配了部分档案成员，则移除那些受支配的成员，同时将非劣解加入档案中；如果非劣解和档案中的所有成员彼此不受支配，则直接将非劣解加入档案中； 限定档案文件的大小，当档案文件的规模事先设定的上限，存在有删除档案文件中部分 非劣解的准则，当档案文件的大小超过设定的最大规模N_a时，删除档案文件中多出的非劣解的方法为：计算所有档案成员个体邻域的密度，并从小到大排序，保留其中邻域密度最小的N_a个档案成员，其他成员从档案文件中删除； 对于个体邻域密度的定义，PAES算法采用自适应网格法定义个体邻域的密度，具体的为：将搜索空间划分为若干个网格，个体邻域密度定义为和它处于同一网格中的所有个体的数目，网格的划分随着外部档案文件成员的变化而自适应地改变，当插入到档案中的个体位于网格的现有边界之外，则重新划分网格； 步骤五：判断是否达到预先设定的最大迭代次数： 如果已经达到步骤二中设定的最大迭代次数，则转到步骤六；否则，转到步骤三；步骤六：确定Pareto最优路径，路径规划结束： 输出外部档案文件中的非劣解集，则得到一组Pareto最优路径的集合，根据实际问题需要，从中选择一条Pareto最优路径作为路径规划的结果。