机器人路径规划要点.doc

基于 Floyd 算法的机器人最短路径规划摘要:最短路径规划是一种点对点的路径规划方式,移动机器人最短路径规划研究即是实现始点和终点间最短路径规划问题的研究。首先采用栅格地图的方式对移动机器人工作环境建模,在建模的基础上,以垂线法方式选择移动机器人路径中的关键节点,确定关键节点的位置和权值关系,并根据所选节点,基于 Floyd 算法进行移动机器人的最短路径规划, 以及对规划的路径算法进行简化改进,通过实验证明,改进的 Floyd 算法能实现移动机器人路径的最短和用时的相对减少。关键词:路径规划; Floyd 算法;垂线法;最短路径 1引言路径规划是移动机器人研究过程中的一个热门话题,如何降低移动机器人路径规划的时间复杂度和空间复杂度,是研究者积极探索的问题。移动机器人最短路径规划问题也就是寻找两点之间最短路径的问题,通常采用的路径规划方法有:平行最短路径搜寻算法[1]、蚁群算法[2]、基于矩阵负载平衡的启发算法[3]、EBSP* 算法[4]、Dijkstra 算法[5-7] 等,其中 Dijkstr a 算法在最短路径规划中应用比较多,但Dijkstra 算法的实现形式比较复杂,Floyd 算法是一种容易理解、设计方便的解决最短路径规划算法,然而,多数研究者对 Floyd 算法的研究主要集中在算法的应用问题上,而对 Floyd 算法中节点的研究和对 Floyd 算法改进的文献比较少。因此本文基于 Floyd 算法对移动机器人的最短路径规划问题进行研究,主要对移动机器人路径规划所需节点如何选择、有向图权值大小如何确定、Floyd 算法的实现,以及对 Floy d 算法的优化改进研究作详细的介绍,并通过实验证明了 Floyd 算法改进的优越性以及移动机器人最短路径选择的正确性。 2 环境的建模 栅格地图的建立首先对移动机器人及工作环境作以下假设: 1) 工作环境是在一个面积大小为 100 的正方形区域; 2)移动机器人形状大小为 1 ?1的正方形; 3)障碍物形状不作限定,所占面积为 1~n,n取值范围[1,100] ; 将移动机器人的工作环境以栅格地图的形式进行分块,每个栅格形状大小为 1 ?1,并对每个栅格进行编号,从坐标原点开始,沿 X轴编号,编号形式如图 1所示,图中灰色部分为障碍物位置。图1栅格地图模型 移动机器人在栅格地图中的移动方向假定移动机器人所在位置为点(x s,y s),移动机器人的移动方向有 8个,方向表示如图 2 所示,移动一个单元格后机器人的位置分别为(x s+1, y s+1) 、(x s,y s+1) 、(x s–1,y s+1) 、(x s –1,y s)、(x s–1,y s–1)、(x,y s–1)、(x s+1, y s–1)、(x s+1, y s),需要移动的距离分别是( 2,1, 2,1, 2,1, 2,1) 。图2移动机器人移动方向和移动距离图 3 移动机器人最短路径规划算法的实现 Floyd 算法的基本思想 Floyd 算法的基本思想是:假设求从节点 v i到v j的最短路径。如果从 v i到v j有弧,则从 v i到v j存在一条长度为 A ij的路径,该路径不一定是最短路径,尚需进行 n次试探。首先考虑路径<v i,v 1,v j>是否存在,如果存在,则比较<v i,v j>