基于多目标人工蜂群算法的多机器人路径规划方法

摘要

本发明提出一种基于多目标人工蜂群算法的多机器人路径规划方法，属于路径规划技术领域，包括：路径规划问题的环境建模、多目标人工蜂群算法的参数初始化、三种蜜蜂迭代优化路径并确定非劣解集、排序保留优良路径和输出最优路径集合。本发明基于Pareto支配和拥挤距离的非支配排序的概念对标准人工蜂群算法进行改进，提出了适用于求解多目标优化问题的多目标人工蜂群算法。在路径规划过程中本算法可以考虑路径长度、平滑性和安全性等多个性能指标，并且一次路径规划可以获得一组Pareto最优路径。本发明提出的路径规划方法属于元启发式智能优化方法，不同于传统的单目标路径规划方法，能够更好的适应复杂环境中的路径规划任务。

主权项

一种基于多目标人工蜂群算法的多机器人路径规划方法，其特征在于，包含以下优化步骤：步骤一：环境建模一，路径规划问题的环境建模路径规划的环境设置为二维平面，建立环境地图的全局坐标系O‑XY；Start为机器人的出发点，Target为机器人的目标点；机器人的路径在环境地图中可以表示为起点、目标点和中间经过的n个路径点组成的集合：Path＝{Start,Step₁,Step₂,…,Step_n,Target}；其中，集合P＝{Step₁,Step₂,…,Step_n}即为路径规划的优化目标，Step为机器人的路径点，每个Step路径点含有机器人运动的横纵坐标为简化环境地图、优化机器人路径点的表示方法，将机器人的步长值设置为定值StepLen，其运动路径通过机器人起点坐标(Start^x,Start^y)和机器人每一个当前位置相对于上一个位置的夹角θ_i来确定，具体如下式：$\left\{\begin{array}{c}{\mathrm{Step}}_k^x={\mathrm{Start}}^x+\underset{i=1}{\overset{k}{\Sigma }}\mathrm{StepLen}\times \cos \left({\theta }_i\right)\\ {\mathrm{Step}}_k^y={\mathrm{Start}}^y+\underset{i=1}{\overset{k}{\Sigma }}\mathrm{StepLen}\times \sin \left({\theta }_i\right)\end{array}\right.$其中，k表示机器人行走的第k步，为路径点的x坐标值，为路径点的y坐标值；Start^x为起点的x坐标值，Start^y为起点的y坐标值；StepLen为机器人的步长值，θ_i为机器人路径点对应的夹角；路径规划目标由集合P转化为集合θ＝{θ₁,θ₂,…,θ_n,θ_n+1}；其中，θ₁为路径点Start和路径点Step₁之间对应的夹角；θ_n+1为路径点Step_n和Target之间对应的夹角；夹角θ_i的初始化是通过随机数生成的，生成方式为如下式：θ_i＝rand(0,1)×(max_i‑min_i)+min_i其中，rand(0,1)表示0到1之间的随机数，max_i为夹角θ_i可以取得的最大值，min_i为夹角θ_i可以取得的最小值；二，路径规划问题的三个目标函数路径规划中，性能指标有很多；本发明考虑最重要的三个目标函数：路径长度函数、路径安全性函数和路径平滑性函数；其定义分别是如下：路径长度函数f₁(θ)：对于路径Path＝{Start,Step₁,Step₂,…,Step_n,Target}＝{p₀,p₁,…,p_n,p_n+1}的优化转化为对θ＝{θ₁,θ₂,…,θ_n,θ_n+1}的优化；本发明中机器人的步长值为定值，因此机器人路径长度为机器人的行走步数和最后一步到目标点的距离，可以表示为如下式：f₁(θ)＝f₁(p)＝n×StepLen+|p_np_n+1|其中，n表示机器人行走的步数，StepLen为机器人的步长值；|p_np_n+1|表示路径目标点Target和机器人第n步的位置Step_n之间的距离；路径安全性函数f₂(θ)：机器人在运动过程中不能与障碍物或者其他机器人相撞，路径安全性函数是避免碰撞的关键函数，本发明设计的路径安全性函数为如下式：$f_2\left(\theta \right)=f_2\left(p\right)=\left\{\begin{array}{cc}-\min \left(\mathrm{disObst}\right)& \min \left(\mathrm{disObst}\right)\le \mathrm{Dist}\\ \mathrm{const}& \min \left(\mathrm{disObst}\right)>\mathrm{Dist}\end{array}\right.$其中，min为最小值求取函数，disObst为机器人的路径点到障碍物的距离，min(disObst)为机器人的路径点到各个障碍物的距离的最小值；Dist为设定的阈值，表示机器人的安全度；const为常数，表示当机器人的路径点到障碍物的距离大于此值时，机器人的路径是安全的，不需要进行优化；路径平滑性函数f₃(θ)：通过路径点之间对应的夹角计算路径的方式简化了路径平滑性函数的设计，本发明的路径平滑性函数为如下式：$f_3\left(\theta \right)=\max \left(\underset{i=1}{\overset{n}{\Sigma }}({\theta }_{i+1}-{\theta }_i)\right)$其中，max为最大值求取函数，θ_i为机器人的路径点集合θ中机器人路径点之间的夹角，n表示夹角的数目；步骤二：路径规划参数、多目标人工蜂群算法参数初始化多目标人工蜂群算法需要初始化的参数：首先设置食物源数目Fs、最大迭代次数MaxCycle、食物源的取值范围[min,max]；然后进行食物源的初始化，食物源即代表路径规划中的优化目标——路径点之间的夹角集合θ；食物源的数目等于雇佣蜂和观察蜂总量的二分之一，通常每个食物源会对应一只雇佣蜂，雇佣蜂会对食物源进行优化；需要初始化的路径规划参数为机器人步长值StepLen；步骤三：三种蜜蜂分别对路径进行优化算法初始化之后，进入算法的主体迭代优化过程；多目标人工蜂群算法的优化是通过蜂群的自组织能力实现的；蜂群的自组织能力体现在其具有正反馈、负反馈、波动和交互的属性；在多目标人工蜂群算法中，食物源最初在解空间中的分布是无序的、随机的，经过一次次优化，逐步走向有序，得到最优解；三种蜜蜂分别对路径进行优化是算法的主体循环部分之一；首先，雇佣蜂采蜜，产生新的路径，得到路径点对应的夹角的集合θ_i'；其路径的更新方式为如下式：${{\theta }_{\mathrm{ij}}}^{\prime }=\left\{\begin{array}{cc}{\mathrm{ub}}_j& {\theta }_{\mathrm{ij}}+{ϵ}_{\mathrm{ij}}({\theta }_{\mathrm{ij}}-{\theta }_{\mathrm{kj}})>{\mathrm{ub}}_j\\ {\mathrm{lb}}_j& {\theta }_{\mathrm{ij}}+{ϵ}_{\mathrm{ij}}({\theta }_{\mathrm{ij}}-{\theta }_{\mathrm{kj}})<{\mathrm{lb}}_j\\ {\theta }_{\mathrm{ij}}+{ϵ}_{\mathrm{ij}}({\theta }_{\mathrm{ij}}-{\theta }_{\mathrm{kj}})& \mathrm{otherwise}\end{array}\right.$其中，ub_j和lb_j分别是路径点对应的夹角的最大值和最小值；ε_ij代表的是波动系数，决定雇佣蜂觅食的范围；θ_ij′为新产生的路径点之间的夹角；θ_ij为集合θ_i'中的一个元素，θ_kj为集合θ中随机选择的一个子集θ_k中的对应元素；然后雇佣蜂会判断新得到的θ'和当前的θ之间的Pareto支配关系，如果则用θ'取代θ作为当前的路径集合；如果则不进行更新操作；观察蜂会根据自己的喜好进行采蜜，之后同样会进行路径更新；最后，侦察蜂会根据当前的排序状态选择放弃不可行路径，并重新生成新的路径；步骤四：基于Pareto支配和拥挤距离排序，保留优良路径基于Pareto支配和拥挤距离的排序是等雇佣蜂、观察蜂和侦察蜂路径优化结束之后才总体进行的；此方法运行效率明显优于每种蜜蜂路径优化结束之后就进行一次排序；排序之后，根据排序的次序保留优良路径，舍弃不可行路径，维持种群大小的恒定；此步骤也是算法的主体循环部分之一；此步结束之后，会判断是否已经达到最大迭代次数，如果达到最大迭代次数则进入下一步；否则，算法的迭代次数加1，继续进行下一步优化过程；步骤五：输出最优路径当算法达到最大迭代次数时便会终止；此时得到机器人路径规划的路径点之间的夹角的集合；此集合是一个Pareto最优解集；算法的最后一步是把路径点的夹角关系集合θ转化为路径点的集合Path；然后，将集合Path输出，路径规划结束；最后，机器人运动的路径是从输出的Pareto最优解集中选取的一条适合当时机器人所在环境要求的路径。