论文部分内容阅读
【摘 要】本论文主要任务是针对移动机器人技术领域中的动态环境下路径规划问题进行深入研究。在动态结构化环境中，通过设计不同的控制策略（算法），避开运动的障碍物，最终为移动机器人规划出一条从起始点到目标点的可行路径。然后基于MATLAB和VC++可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。
【关键词】移动机器人；动态环境；遗传算法；路径规划
移动机器人路径规划就是移动机器人从初始出发点，在一个有障碍物的环境中，找到一条从初始点到目标点的无碰撞最优路径。本文在分析了目前各种路径规划方法优缺点的基础上，采用遗传算法来解决动态环境下移动机器人的路径规划问题。首先针对路径规划问题的特点，对遗传算法的各个环节进行了细致的分析，包括地图环境的建立，染色体的表示和编码、适应度函数的设计，遗传操作算子的设计，算法参数的分析和选取等。然后基于MATLAB和VC++可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。
一、遗传算法
遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。
二、移动机器人路径规划建模
本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：将环境空间划分为独立的栅格空间；首先将环境空间的每个栅格初始化为0；探测障碍物所占据的部分栅格；把1赋给障碍物所占据的栅格；在障碍物地图中，被占栅格上、下、左、右的四个相邻栅格的值neighbor通过规定的减函数decrease来计算，直到计算值小于或等于0，即neighbor [Edirection]=decrease（s，dtreclion），其中direction为0，1，2，3，表示赋值为0的左右四个相邻栅格，s为当前栅格的值，在屏幕上显示的仿真效果图如图1～2所示：
三、基于遗传算法的路径规划实现
（1）问题定义。本文研究的移动机器人运动环境为二维平面空间，环境中的静态障碍物已知，动态障碍物可以探测。这样使得问题便于着手，有利于把重点放在探索遗传算法在这类问题的实际应用上来，为今后研究三维空间内机器人的运动路径规划打下基础。本文将移动机器人视作一个质点，即不考虑机器人的尺寸。本文的目标是要在静态环境和具有少量动态障碍物出现或运动的环境里，为机器人找到一条从当前位置到目标位置的行动路线，要求这条路径满足以下条件：该路径不与任何障碍物发生冲突；该路径应尽可能短；该路径应与障碍物保持一定的安全距离；该路径应尽可能平滑。（2）遗传算子设计。优胜劣汰是设计遗传算法的基本思想，它应在选择、交叉和变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。一是轮盘赌法选择。轮盘赌法是把种群中所有个体适应度的总和比作一个轮子的圆周，每一个个体按其适应度的大小占轮子不同大小的扇区。轮子随即旋转后停在哪个扇区，对应的个体就被选中。具体步骤如下：计算每一个个体的适应度值f（xi）；累加所有个体的适应度值SUM=∑f（xi），并记录每一个个体的中间累加值S_mid；产生一个随机数N，0 三是变异算子。变异运算模拟生物在自然界中因各种偶然因素而引起的基因突变。它提供了种群中遗传基因类型的多样性，当交叉操作产生的适应度值不再进化且没有达到最优时，就意味着算法的早熟收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度上克服了这种情况，有利于增加种群的多样性。
其程序如下所示：Mutate（vector &vecBits）；{for（int curBit=0；curBit 四、路径规划仿真研究
移动机器人的动态环境路径规划是个相当困难的问题。本文所研究的动态环境限于机器人运动空间里一直存在一个或多个不断移动的障碍物。与A*算法进行比较图4（a）为A*算法的仿真结果。图4（b）为本文所用的遗传路径规划方法的仿真结果。由图4和表1数据可得，本文所研究的路径规划方法具有时间短，路程优，可视性强的特点，并能有效的实现路径规划。
本文在分析比较目前各种移动机器人路径规划算法的优缺点的基础上，对采用遗传算法解决静态和动态环境里路径规划问题的方法作了进一步的分析研究。通过在多个复杂程度不同的环境下，分别进行静态和动态情况下的仿真，仿真结果表明，该算法能够成功地规划出近似最优的路径。
参 考 文 献
[1]徐国华，谭民．移动机器人的发展现状及其趋势[J]．机器人技术与应用．2001，20（2）：45～51
[2]龚进峰．数字势场和遗传算法的机器人路径规划的方法[J]．天津大学学报．2002，10（2）：75～78
[3][美]Mat Buckland.Ai Techniques for Game Programming[J]．北京：清华大学出版社，2006
[4]赵翊捷，陈卫东．基于地图的移动机器人定位技术研究[D]．上海：上海交通大学．2002
[5]王仲民，岳宏．一种移动机器人全局路径规划新型算法[J]．机器人．2003（2）：152～155
[6]王醒策，张汝波，顾国昌．基于势场栅格法的机器人全局路径规划[J]．哈尔滨工程大学学报．2003，24（4）：170～172
[7]李智军，吕恬生．遗传算法在自主移动机器人局部路径规划中的应用[J]．机械设计．2000，12（7）： 27～28
[8]杨正华，张秋生．Visual C++游戏编程导学[J]．北京：清华大学出版社，2004
[9]吴涛．移动机器人避障与路径规划研究[D]．武汉：华中科技大学．2004
【关键词】移动机器人；动态环境；遗传算法；路径规划
移动机器人路径规划就是移动机器人从初始出发点，在一个有障碍物的环境中，找到一条从初始点到目标点的无碰撞最优路径。本文在分析了目前各种路径规划方法优缺点的基础上，采用遗传算法来解决动态环境下移动机器人的路径规划问题。首先针对路径规划问题的特点，对遗传算法的各个环节进行了细致的分析，包括地图环境的建立，染色体的表示和编码、适应度函数的设计，遗传操作算子的设计，算法参数的分析和选取等。然后基于MATLAB和VC++可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。
一、遗传算法
遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。
二、移动机器人路径规划建模
本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：将环境空间划分为独立的栅格空间；首先将环境空间的每个栅格初始化为0；探测障碍物所占据的部分栅格；把1赋给障碍物所占据的栅格；在障碍物地图中，被占栅格上、下、左、右的四个相邻栅格的值neighbor通过规定的减函数decrease来计算，直到计算值小于或等于0，即neighbor [Edirection]=decrease（s，dtreclion），其中direction为0，1，2，3，表示赋值为0的左右四个相邻栅格，s为当前栅格的值，在屏幕上显示的仿真效果图如图1～2所示：
三、基于遗传算法的路径规划实现
（1）问题定义。本文研究的移动机器人运动环境为二维平面空间，环境中的静态障碍物已知，动态障碍物可以探测。这样使得问题便于着手，有利于把重点放在探索遗传算法在这类问题的实际应用上来，为今后研究三维空间内机器人的运动路径规划打下基础。本文将移动机器人视作一个质点，即不考虑机器人的尺寸。本文的目标是要在静态环境和具有少量动态障碍物出现或运动的环境里，为机器人找到一条从当前位置到目标位置的行动路线，要求这条路径满足以下条件：该路径不与任何障碍物发生冲突；该路径应尽可能短；该路径应与障碍物保持一定的安全距离；该路径应尽可能平滑。（2）遗传算子设计。优胜劣汰是设计遗传算法的基本思想，它应在选择、交叉和变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。一是轮盘赌法选择。轮盘赌法是把种群中所有个体适应度的总和比作一个轮子的圆周，每一个个体按其适应度的大小占轮子不同大小的扇区。轮子随即旋转后停在哪个扇区，对应的个体就被选中。具体步骤如下：计算每一个个体的适应度值f（xi）；累加所有个体的适应度值SUM=∑f（xi），并记录每一个个体的中间累加值S_mid；产生一个随机数N，0
其程序如下所示：Mutate（vector
移动机器人的动态环境路径规划是个相当困难的问题。本文所研究的动态环境限于机器人运动空间里一直存在一个或多个不断移动的障碍物。与A*算法进行比较图4（a）为A*算法的仿真结果。图4（b）为本文所用的遗传路径规划方法的仿真结果。由图4和表1数据可得，本文所研究的路径规划方法具有时间短，路程优，可视性强的特点，并能有效的实现路径规划。
本文在分析比较目前各种移动机器人路径规划算法的优缺点的基础上，对采用遗传算法解决静态和动态环境里路径规划问题的方法作了进一步的分析研究。通过在多个复杂程度不同的环境下，分别进行静态和动态情况下的仿真，仿真结果表明，该算法能够成功地规划出近似最优的路径。
参 考 文 献
[1]徐国华，谭民．移动机器人的发展现状及其趋势[J]．机器人技术与应用．2001，20（2）：45～51
[2]龚进峰．数字势场和遗传算法的机器人路径规划的方法[J]．天津大学学报．2002，10（2）：75～78
[3][美]Mat Buckland.Ai Techniques for Game Programming[J]．北京：清华大学出版社，2006
[4]赵翊捷，陈卫东．基于地图的移动机器人定位技术研究[D]．上海：上海交通大学．2002
[5]王仲民，岳宏．一种移动机器人全局路径规划新型算法[J]．机器人．2003（2）：152～155
[6]王醒策，张汝波，顾国昌．基于势场栅格法的机器人全局路径规划[J]．哈尔滨工程大学学报．2003，24（4）：170～172
[7]李智军，吕恬生．遗传算法在自主移动机器人局部路径规划中的应用[J]．机械设计．2000，12（7）： 27～28
[8]杨正华，张秋生．Visual C++游戏编程导学[J]．北京：清华大学出版社，2004
[9]吴涛．移动机器人避障与路径规划研究[D]．武汉：华中科技大学．2004