一种基于可变维粒子群膜算法的移动机器人路径规划方法

摘要

本发明属于智能机器人与控制技术领域，尤其涉及一种基于可变维粒子群膜算法的移动机器人路径规划方法。本发明步骤主要为：环境建模、输入路径参数、设置适应度函数、初始化有效路径母粒子和子粒子、路径粒子分类和重归类、对适应度函数进行评价、更新d维粒子的位置、判断当前粒子是否有无效维、对存在无效维的粒子进行修正和去除冗维信息等。本发明能利用复杂环境全局已知或者复杂环境局部位置的信息以及待定移动机器人的状态参数快速规划处适合此类机器人行走的最优路径。

主权项

一种基于可变维粒子群膜算法的移动机器人路径规划方法，其特征在于，包括以下步骤：S1、环境建模，具体为：S101、将物理环境信息映射为n·n的栅格型虚拟环境，对所述n·n个栅格进行标号，其中，n为不为零的自然数，所述栅格为正方形，所述栅格的边长SoG＝N×机器人直径，N≥2且N为自然数；S102、对S101所述带有标号的栅格进行分类，分为障碍物栅格和自由栅格；S103、对S102所述障碍物栅格的外凸顶点外围栅格进行标记，其中，外凸顶点外围栅格为自由栅格；S104、对S103所述外凸顶点外围栅格进行分类，分为对角顶点外围栅格和侧边外围栅格，定义所述对角顶点外围栅格的随机选择概率系数为γ₁，定义所述侧边外围栅格的随机选择概率系数为γ₂，其中，0≤γ₁≤1，0≤γ₂≤1，γ₁+γ₂＝1；S105、实际环境的物理坐标到虚拟环境栅格序号之间的映射关系表示为p＝u·Noc+v，$\left\{\begin{array}{c}v=\mathrm{fix}(x/\mathrm{SoG})\\ u=\mathrm{fix}(y/\mathrm{SoG})\end{array}\right.,$其中，p为序号数，x,y为物理坐标，SoG为单个栅格的边长，fix函数为低整位取整函数；S2、输入路径规划参数，具体包括：机器人状态参数，起止位置及安全范围；S3、设置适应度函数f＝K_d·Dis+K_f·S+K_s·SD，其中，K_d,K_f,K_s为权重系数，K_d用来调节最短距离Dis目标函数在最优路径中所占的比重，K_f用来调节平滑度S目标函数在最优路径中所占的比重，K_s用来调节安全度SD目标函数在最优路径中所占的比重，其中，Dis是从起始点到终止点的h个节点之间的距离之和；S4、初始化有效路径母粒子和子粒子，具体为：S401、在表层膜中创建m个子膜，在每个子膜中产生1个有效路径母粒子，共产生m个有效路径母粒子，对m个子膜进行标号，记作M_i,i＝1,2,...,m；S402、在S401所述m个有效路径母粒子的基础上利用随机和特殊方向指导相结合的方式在所述m个有效路径母粒子对应的子膜M_i中产生c个有效路径子粒子，共产生m·c个有效路径粒子的初始种群；S5、路径粒子分类与重归类，具体为：S501、根据S401所述每个子膜M_i中的粒子维度的不同，将粒子分为k_i组；S502、构建第i个子膜中的第j个基本膜将S501所述分类后的粒子放入所述基本膜中，其中，中粒子均为同维粒子，j＝1,2,...,k_i；S503、运用粒子运动方向重调整方法对粒子速度进行重新初始化；S6、对S502所述基本膜中路径粒子的适应度函数进行评价，具体为：S601、在S502所述基本膜中根据S3所述适应度函数f＝K_d·Dis+K_f·S+K_s·SD计算基本膜中每个粒子对应的适应度函数值，找到每个粒子的个体最优值S602、在S502所述基本膜中找到局部最优其中，j＝1,2,...,k_i，t为子粒子代数；S603、将第i个子膜里的局部最优送出到表层膜；S604、比较S603所述得出同维的全局最优解其中，d∈{1,2,...,D}；S605、将S604所述送回维数相匹配的基本膜中；S7、利用公式$\begin{array}{c}{V}_{\mathrm{id}}(t+1)={\delta }_1·(\rho ·V_{\mathrm{id}}\left(t\right)+c_1·r_1·(P_{\mathrm{best}}^{\mathrm{id}}\left(t\right)-X_{\mathrm{id}}\left(t\right))+c_2·r_2·(G_{\mathrm{ij}}^b\left(t\right)-X_{\mathrm{id}}\left(t\right))\\ +c_3·r_3·(G_d^b\left(t\right)-X_{\mathrm{id}}\left(t\right)))+{\delta }_2·V_{\mathrm{id}}^f\left(t\right)\end{array}$计算d维粒子的速度，利用公式X_id(t+1)＝V_id(t+1)+X_id(t)更新d维粒子的位置，其中，V_id(t)为粒子在第t代的速度，V_id(t+1)是粒子在t+1代的速度，是粒子在第t代的个体最优，X_id(t)是粒子在第t代的位置，是第t代同维数粒子的局部最优，是第t代同维粒子的全部最优，是第t代粒子经方向调整方法处理后的速度，δ₁和δ₂是比例系数，ρ是惯性权重系数，r₁,r₂,r₃是0和1间的随机数，c₁,c₂,c₃为加速度系数，X_id(t)是第t代粒子的位置，X_id(t+1)是第t+1代粒子的位置，V_id(t+1)第t+1代粒子的速度；S8、判断当前粒子是否有无效维，即对S7所述更新位置后的d维粒子进行判断，若所述更新位置后的d维粒子存在无效维则进入S9，若所述更新位置后的d维粒子不存在无效维则进入S10；S9、对S8所述存在无效维的粒子进行修正，修正后判断其无效性，直至不存在无效维转至S10；S10、判断当前粒子是否有冗维信息，如存在冗维信息则转入S11，如不存在冗维信息则转入S12；S11、去除冗维信息：S1101、对一条有效路径从起点到终点的所有节点依次排序并放入序列表L中，令起点为首节点，终点为尾节点；S1102、取出S1101所述首节点，从第3个节点开始，判断第3个节点是否与首节点能无障碍连接，如果能链接则依次取下一节点，继续判断此节点与首节点的无障碍连接性，直至找到与首节点不能直接相连接的节点a，如果首节点与第3个节点不能无障碍连接，则说明第2个节点不是冗余维节点，再令第2个为首节点；S1103、从序列表L中删除首节点和第a‑1个节点之间的所有节点；S1104、令第a‑1个节点为首节点，重复S1102依次取其后的节点进行判断并去除冗余信息，直至尾节点出现；S12、在基本膜中得到不同维数的最优路径粒子：各基本膜中的路径粒子经过S9的无效维路径粒子修正和S11的去冗余维信息处理后，每次得到的新路径粒子向较优或最优路径接近，其维数已经和初始状态的维数不同，同一子膜M_i内各基本膜溶解，去掉基本膜的封装，将新粒子重新释放回各自所属的子膜内，等待下一次迭代的分类；S13、判断算法满足终止条件：如果循环次数t≥T，则循环结束，输出包含最优路径的解集Φ，否则t＝t+1，算法跳转到S5。