一种基于粒子群优化算法的移动机器人路径规划方法

摘要

本发明涉及一种基于粒子群优化算法的移动机器人路径规划方法。目前移动机器人路径规划方法对于路径的选择比较单一、容易走入死胡同。本发明的具体步骤是：首先对环境进行建模；用多边形表示障碍物，用点表示机器人，用小方框表示机器人的起始位置，用表示目标点。机器人开始点标记为S，目标点标记为G；然后对机器人路径利用粒子群优化算法进行规划；最后对规划的路径进行深度优先搜索。本发明在极坐标粒子群中加入了深度优先搜索。用这种方法，机器人可以在大多数复杂环境中有效地找到一个无碰撞的路径，最终到达目标点。

主权项

1、一种基于粒子群优化算法的移动机器人路径规划方法，其特征在于该方法的步骤包括：步骤(1)设机器人的当前位置为Si，机器人传感器感应圆的半径为R，Si与目标点之间的距离为D；以Si为圆心做圆C，如果R≤D，则圆C的半径为R，如果R＞D，则圆C的半径为D；以Si为射线出发点，做平行于x轴的射线，射线与圆C相交于Q点，并将此射线作为极坐标轴；步骤(2)将Si点与Q点间线段进行K等分，得到长度为||SiQ||/K的K段线段，以各个等分点到Si点的距离为半径，以Si为圆心做圆，得到K个同心圆；步骤(3)可行路径是一条从起点Si到圆C上点的若干线段组成的折线，用这些折线的端点即路径关键点的序列表示，机器人移动过的路径就是这些点的连线，定义为P＝{Si，P1，...，Pj，...，Pm}，1≤j≤m，m＜K；其中P1，...，Pj，...，Pm都是非障碍物点，即相邻的两点之间的连线上没有障碍物；步骤(4)在当前非障碍物点上将传感器感应到的半径为R的圆等分为n个扇形区域{d1，d2，...，dj，dj+1，...，dn}，每个扇形的角度为360/n度；步骤(5)每次选择一个扇形区域作为探索区域：扇形区域dj被选择，用粒子群优化算法探索dj，如果在扇形区域dj中找到可行路径，移动机器人至下一个非障碍物点；如果找不到路径，探索下一个扇形区域dj+1；对每一个扇形区域探索利用PSO算法对机器人路径进行规划，最终找到无障碍物的路径；步骤(6)如果在传感器感应到的半径为R的圆的范围内找不到可行路径，则返回到前一点，探索在前一点中没有探索过的扇形区域；把机器人每次走过的路径存储在一个链表中；步骤(7)当圆C的半径为D时，目标点即在圆周C上，机器人利用PSO算法所做的移动即可到达目标点；当圆C的半径小于D时，机器人移动pm到后，将pm的极坐标值赋值给Si，重复步骤(1)到(7)，直到找到一条无碰撞路径，到达目标点。