一种移动机器人路径规划方法

doi: 10.3969/j.issn.1006-1576.2009.12.021

一种移动机器人路径规划方法

温瑞，王航宇，谢君

（海军工程大学 电子工程学院，湖北 武汉 430033）

摘要：路径规划的目标是根据具体任务为机器人寻找一条最优无碰撞路径，其主要内容包括：运动建模，环境建模和路径搜索。对机器人的运动模型进行分析，基于Voronoi理论，采用近似构造法，构造一般环境的Voronoi图，通过将移动机器人起始点和目标点连入Voronoi图，形成移动机器人运动的无碰撞路径网络。利用Dijkstra算法，寻找一条从起点到终点的最短路径。仿真结果表明，该方法简单、有效。

关键词：路径规划；Voronoi图；Dijkstra算法 中图分类号：TP242 文献标识码：A

Path Planning Method for Mobile Robot

WEN Rui, WANG Hang-yu, XIE Jun

(Electronic Engineering College, Naval University of Engineering, Wuhan 430033, China)

Abstract: The target of path planning is to finding an optimal non-collision path according to task. Its main content is movement modeling, environment modeling and path searching. Analyze the movement model of mobile robot. The method of Voronoi diagrams for general figures by approximation structuring is utilized and the origin and terminal are joined into it to construct the non-collision road map. Dijkstra algorithm is applied to search the shortest path between origin and terminal. Simulation results demonstrate that the method is simple and effective.

Keywords: Path planning; Voronoi diagram; Dijkstra algorithm

0 引言

路径规划是移动机器人重要研究内容，目标是根据任务为机器人寻找最优的无碰撞路径。Voronoi图是表示点或实体集合近似信息的几何结构。由于Voronoi图具有独特的几何特性，在计算机辅助设计、地理信息系统、模式识别、机械加工等获得广泛应用。由于Voronoi图在机器人路径规划中是全路线图的方法，倾向于使图中机器人与障碍物间的距离最大化，且Voronoi图方法具有超越其他避障技术的可执行性[1]。故基于Voronoi图及Dijkstra算法，对移动机器人路径规划方法进行研究。

动模式，通过改变两轮的速度获得不同的运动方式。

先假设移动机器人由刚性框架和刚性轮组成，并假设机器人在水平面上运动，轮子与地面为点接触，并且接触点只有纯滚动而不发生对滑动（包括侧向和纵向滑动），且机器人小车的质心A在小车

-的中心[23]。机器人在平面上的位姿描述如图1。

机器人的质心坐标为(x,y)，代表机器人的位置，机器人正方向与坐标系的夹角θ为机器人的姿态，可得机器人的位姿P和机器人的位置Pd：

P=[x,y,θ]T

，

Pd=[x,y]T

。

1 机器人运动模型

Y θ y A 机器人的运动包括2个部分：小车中心点平移和绕中心轴的旋转，机器人满足刚体运动规律。有下列运动学方程成立：

vl=riωlvr=rωr

v=

(1) (2)

(vl+vr)2 (3)

0.5 cm, ω=

x X(vr−vl)l (4)

图1 位姿描述

在移动机器人系统中，机器人采用两轮驱

式中，ωr和ωl分别标识左右论的角速度，ω表示质心的角速度，v为质心的线速度。当vr=vl时，小车走直线，质心角速度为0，当vl=-vr时小车的

收稿日期：2009-06-26；修回日期：2009-07-22 作者简介：温瑞（1982-），男，黑龙江人，硕士研究生，从事装备系统分析研究。

·60·

温瑞，等：一种移动机器人路径规划方法

线速度为0，小车实现原地转动。

为方便研究，补充如下假设：

1) 机器人在转弯时都是先停止运动，然后转向到下一路径，开始运动；2) 机器人在停止当前运动和从静止到加速到规定运行速度的时间很短，近似为零；3) 机器人在各点转向时候，角速度ω相同。

个数与生成元边界长度成正比。具体做法如下：

1) 在各生成元的边界上设置母点；

2) 将设置的母点作为生成元，按点Voronoi图的做法做出Voronoi图；

3) 保留不同生成元之间的Voronoi边，消去同一生成元上的母点之间的Voronoi边；

图3为采用一般图形近似构造法构造的以矩形、三角形、直线、点为生成元的Voronoi图。

2 Voronoi图的基本概念

设平面A是一个已确定了尺度的量度平面，设P是一离散点集合P1, P2, …, Pn∈P，定义Pi的Voronoi区域V(Pi)为所有到Pi距离最小点的集合：V(Pi){Pd(P,Pi)≤d(P,Pj),j≠i,j=1,2,󰀢,n}。

P

1

的

2

Voronoi

n

图V(P)为

V(P)=

{V(P),V(P),󰀢V(P)}，Pi称为Voronoi图生成元[4]。

图2为7个生成元构造的Voronoi图。

P1 P2 图3 近似构造法构造的Voronoi图

4 建立完整路径网络模型

P3 P4 P5P6 P7 图2 普通的Voronoi图

3 一般图形的Voronoi图

从Voronoi图的基本概念可以发现，普通Voronoi图是建立在生成元为点的基础上的。但在机器人路径规划问题中，障碍物的外形多种多样，不能简单地将其用外接圆包裹后当作点生成元来处理，故采取一般图形的Voronoi图近似构造法，构建一般图型的Voronoi图[4]。

构造Voronoi图就是对于给定的生成元构造Voronoi边。采用近似构造法来生成一般图形的Voronoi图。近似构造法是在各生成元（多边型，线段，点等）边界上选择具有代表性的点，称为母点，以这些母点作为生成元构造点Voronoi图，进而得到一般图形的Voronoi图的近似图。近似构造法的关键问题是如何设置母点，现阶段一般采用均匀设置的方法，如线段的端点，折线的拐点。多边形的顶点都必须设置成母点，受时间空间等方面因素的，适当选择少量具有代表性的母点来构造Voronoi图，生成元的分布要均匀，生成元上的母点

利用Voronoi图进行路径规划，其核心在于Voronoi图的构建。在路径规划环境中包含多种类型的实体，如直线、多边形、圆等一般图形。对于一般障碍物的处理，文献[5]作出障碍物的外接圆，取圆形区域的圆心作为障碍物的近似质心，并以此为生成元构造Voronoi图进行路径规划。文献[6]根据障碍物的大小，在障碍物内部提取若干个点作为建模的生成元，再以这些生成元作若干个圆包络障碍物区域，构造Voronoi图进行路径规划。文献[5]这种处理方式忽略了障碍物的大小及形状，所构建的环境地图不能很好地表达出障碍物信息，浪费许多可行区域，造成Voronoi图构建的低效性。文献[6]包含了更准确的障碍物信息及可行路径，但不适用于障碍物比较密的环境。

基于Voronoi图中图形的近似构造法[7]构造障碍物的Voronoi图，并进行路径规划。可根据需要增加或降低生成元中母点的数量以提高或降低相似程度，尽可能少占用可行区域，较适合在密集障碍物环境中应用。同时，对机器人的转向进行分析，将机器人的转向幅度计算，并与路线长度进行综合。

对生成的Voronoi图进行处理。由于采用搜索算法进行最短路径搜索，首先必须建立路径图，并计算出路径图中个边的权值。显然，由近似构造算法构造的Voronoi图得出的无碰撞路径网络中，并不一定包含给定的起始点和目标点。为实现路径的

·61·

兵工自动化

自主搜索，对已建立的无碰撞路径网络按一定规则生成包含起始点和目标点的路径图。

如果起始点和目标点都在无碰撞路径网络中，则不需要处理。

如果起始点和目标点都不在无碰撞路径网络中，则在起始点和目标点附近取适当距离做一点称为虚起点和虚终点，从该点开始，分别做与环境边界平行的直线，与Voronoi边相交，形成新结点。然后分别把起始点和目标点与虚起点和虚终点相连接，称该连接线为虚路径，以此搜索由固定路径和虚路径组成的包含起始点和目标点的图，即可找到一条从起始点到目标点的路径，如图4。

起点 虚起点 寻找下一个要给予P标号的节点。

对{(vi,vj)vi∈I,vj∈J}中的弧，计算

min{Sij=li+cij,∀cij∈{(vi,vj)vi∈I,vj∈J}}，cij为该弧的

权数。给此弧的终点以P标号(Scd,c)，返回步骤2。

重复步骤2和3，直到满足下列任一条件止： 1)

{(v

i

,v

j

)v

i

∈I,vj∈J

}=φ；

2) 终点vt获得P标号。

从终点vt的P标号(lt, kt)开始，反向追踪至起点vs，从而找出从起点到终点的最短路。

若在步骤3中，使得Sij最小的弧不止一条，则可任选一条的终点予以标定。若这些弧中某些弧的终点为同一点，则该点应给予多个标号，以便找到多条最短路。

6 仿真实现

7060母点 504030虚终点 终点 201000 10 20 30 40 50 60 70 80

(a) 不考虑转向的仿真运行结果

图4 路径规划图

5 Dijkstra最短路径搜索算法

路径规划的目标是为机器人寻找一条无碰撞路径，无碰撞路径网络建立后，就必须按给定的起始点和目标点，为机器人找出一条行走路径。

Dijkstra算法的基本思想是：从起点出发，逐步向外探寻，且每向外延伸一步都要求路径最短。执行过程中，对应每个点都记录一个数（该数称为此点的标号），它或者表示从vs到该点的最短路的权（称为P标号），或者表示从vs到该点的最短路的权的上界（称为T标号）；方法的每一步是去修改T标号，并且将某一个具有T标号的点改变为具有P标号的点，从而使具有P标号的顶点数比上一步多一个。假定在途中，顶点个数为ρ，最多经过P-1步，就能求出从vs到vt的最短路。Dijkstra方法的具体步骤如下[8]：

1) 起点vs以P标号(0,s)。0表示从起点到该点的距离，s表示该点前一个节点的下标。

2) 已标号点集合I和未标号集合J，弧的集合

7060504030201000 10 20 30 40 50 60 70 80

(b) 考虑转向的仿真运行结果

图5 仿真结果

当机器人到达某节点时，需转动φ到达下一路径，所需时间t=ϕω，机器人在路径上运动的速度为v，在t时间内可以行进的距离为s=v⋅t，将S加入所选择路径的长度上，得到ss=ss+s。改变该路径的权值，可以将转向的幅度与所选择路径的长度进行综合计算。

把机器人视为一个质点，采用Matlab编程仿真，仿真路径如图5。其中，(a) 图为不考虑转向的

'

{(vi,vj)vi∈I,vj∈J}。若该集合为空集，则计算结束。

3) 若节点vi被赋予P标号(li, ki)，按如下方法

·62·

温瑞，等：一种移动机器人路径规划方法

仿真运行结果，(b) 图为考虑转向的仿真运行结果。

[4] 张有会, 浅野哲夫, 小保方幸次. 关于一般图形Voronoi

图的近似构造法研究[J]. 数值计算与计算机应用, 2002(9): 217-225.

[5] 许松清, 吴海彬, 林宜, 等. 基于Voronoi图法的移动机

器人路径规划[J]. 中国工程机械学报, 2005(7): 336-340.

[6] 吴海彬, 林宜. 基于改进Voronoi图法的移动机器人在

线路径规划[J]. 中国工程机械学报, 2007(1): 117-3121. [7] 邓俊辉, 译. 计算几何-算法与应用（第2版）[M]. 北

京: 清华大学出版社, 2005.

[8] 张宏斌. 运筹学方法及其应用[M]. 北京: 清华大学出

版社 北京交通大学出版社, 2008.

[9] 蔡自兴, 贺汉根, 陈虹. 未知环境中移动机器人导航控

制理论与方法[M]. 北京: 科学出版社, 2009.

7 结论

该方法简单方便，易于实现，仿真计算结果验证了其有效性。

参考文献：

[1] 李人厚, 译. 自主移动机器人导论[M]. 西安: 西安交

通大学出版社, 2006.

[2] 宋伟刚. 机器人学-运动学、动力学与控制[M]. 北京:

科学出版社, 2007.

[3] 张洪宁, 张鹏程, 刘春明, 等. 基于动力学模型的轮式

移动机器人运动控制[J]. 兵工自动化, 2008, 27(11): 79-82.

**********************************************************************************************************

（上接第45页）

1) 采用Delphi法确定影响导弹保障人员可靠性的因素为：生理状况、心理素质、知识水平、专业技能、工作态度等，作为神经网络的输入元素；

2) 采用模糊数学中的隶属函数方法对各因素进行数字化处理；

3) 把数值输入神经网络训练，使误差满足要求；选定新的数据对模型验证，确定模型的可信性；

4) 对输入因素进行幅度调整，并进行仿真，通过敏感性分析判断因素重要程度。 2.2 实例

以导弹的制导系统为例分析，得到保障人员可靠性影响因素的实际数据，再利用建立的隶属度函数，得到实际数据对于影响因素的隶属度，如表1。

表1 实际数据对于影响因素的隶属度

生理状况 心理素质 知识水平 专业技能 工作态度 可靠度1 0.69 0.462 0.618 0.606 0.678 0.555 62 0.2 0.294 0.282 0.366 0.13 0.354 3 0.81 0.582 0.522 0.486 0.222 0.552 4 0.93 0.366 0.438 0.846 0.678 0.4 45 0.81 0.702 0.69 0.702 0.45 0.654 6 0.81 0.702 0.858 0.954 0.87 0.84 7 0.4 0.366 0.726 0.93 0.87 0.765 68 0.774 0.462 0.2 0.606 0.222 0.521 69 0.93 0.582 0.822 0.4 0.678 0.782 410 0.81 0.702 0.354 0.786 0.45 0.626 4

3组进行仿真，在该模型下得到的仿真结果为： 0.576 5，0.351 2，0.533 9。进一步对仿真数据的各项分别进行幅度变化，得到结果如表3。显然，对保障人的可靠性影响程度由大到小依次为：专业技能、生理状况、知识水平、心理素质、工作态度。

表3 模型验证数据分析表2

生理状况心理素质知识水平 专业技能工作态度变化幅度±10% ±10% ±10% ±10% ±10% 1 2 3

2.46%

2.46% 3.87% 3.90% 3.14% 3.14%

0.83% 0.83% 0.88% 0.91% 1.14% 1.12%

3.08% 3.08% 2.39% 2.39% 2.84% 2.84%

3.81% 3.81% 3.90% 3.92% 3.33% 3.33%

0.22% 0.12% 0.05% 0.08% 0.09% 0.07%

3 结论

分析结果表明：专业技能、生理状况、知识水平3个因素相对重要。在保障人员选择、培训过程中，可有针对性地选拔和学习，以提高保障能力。

参考文献：

[1] 李青, 潘旭峰, 杨威. 基于神经网络的导弹系统保障可

靠性分析[J]. 军事运筹与系统工程, 2003(4): 48-51. [2] 迪隆BS. 人的可靠性[M]. 牟致忠, 谢秀玲, 吴福邦,

译. 上海: 上海科学技术出版社, 1990: 1-5.

[3] 周保生, 林江, 于海学, 等. 人工神经网络在煤矿巷道

围岩移近量预测中的应用[J]. 系统工程理论与实践, 2000(1): 136-139.

[4] 张金春, 翟景春, 姜晨. 用神经网络组合预测法估算反

舰导弹研制费用[J]. 系统工程与电子技术, 2002(9): 111-113.

[5] Martin T, Hagan Howard B, Demuth Mark H, Beale. 神经

网络设计[M]. 北京: 机械工业出版社, 2002.

[6] 薛雪东, 程旭德, 徐兵, 等. 基于BP神经网络的导弹

故障诊断专家系统设计[J]. 四川兵工学报, 2008(4): 54-56.

·63·

利用Matlab编制神经网络程序进行计算，选取前面7组作为训练数据，后3组作为仿真数据。训练后，对模型进行验证，结果如表2。

表2 模型验证数据分析表1

样本编号

1 2 3

原始数据 0.521 6 0.782 4 0.626 4

仿真数据 0.595 5 0.794 5 0.612 9

误差 0.073 9 0.012 1 0.013 5

由表2可知，该模型可用。选取原始数据的前