1. 引言

    自主机器人的路径规划是指:有一台机器人及其环境描述,要规划出一条从已知的起始位置出发、绕过障碍物、到达预先规定的终止位置、并满足某些优化条件的路径。仿真系统对于移动机器人路径规划的研究具有重要的作用，一般用来验证算法的最优性、安全性、可达性。很多学者对路径规划仿真做了大量的研究并提出一些方法，常用的有栅格法和人工势场法等，但这些算法都存在着一些算法本身的局限性。栅格法当空间增大时所需存储空间剧增，决策速度慢。人工势场法结构简单、便于底层实时控制，但它在障碍物前震荡，在狭窄通道中摆动，经常陷入陷阱区域，可使机器人在到达目标前就停车。而遗传算法是一种多点搜索算法，相对栅格法和人工势场法，更有可能搜索到全局最优解。

但传统的遗传算法也存在着早熟收敛和收敛速度慢这两个难题。早熟收敛导致产生局部最优值，而收敛速度慢是影响遗传算法应用在实时性要求比较高的环境中的一个瓶颈因素^[1]。本文针对上面提到的两个问题，将改进遗传算法和简单图搜索方法相结合，减少了搜索的盲目性，并且对遗传算法从改进选择方式和动态确定变异概率两个方面考虑，选择操作采用最优保存策略，局部出现相似个体之后实施灾变操作，并且根据个体适应度函数值的大小动态

确定变异概率，这样既不增加群体规模，避免运算时间过长，还能保证收敛到全局最优解，有效地克服了传统遗传算法的缺点。

2. 环境建模                                                       

首先根据任务和基本地图建立环境模型，即将现实世界的问题进行抽象后建立相关的模型。本文采用链接图法^[2]

(MAKLINK Graph)建模，它在构造规划空间时假设移动机器人在二维平面环境中运动；规划环境的边界及障碍物可用凸多边形描述；机器人用点来表示^[3]。在图1所示的环境中，黑色多边形表示环境中的障碍物。

                        图1  有障碍物的环境                       





图2  对环境的链接图表示

    链接图法对自由空间进行建模的过程为：取各障碍物顶点连线的中点为可能路径点，相互连接各可能路径点，并将机器人移动时的起点和终点分别连接到各个可能的路径点上。对图1所示含有障碍物的环境，经过上述算法处理后，可得到图2的链接图，其中P₁为起点，P₁₉为终点。所有可能路径点和之间连线形成的网络图即为机器人可自由行走的路线，即得到一个带权无向图，机器人的全局路径规划即转化为在网络图2中寻找从P₁点到P₁₉点的最短路径，采用E．W．Dijkstra(狄克斯特拉)算法可以在一个给定的带权无向图中去求连接起点和终点的最短路径和最短路径的长度，得到最短路径规划结果。

3. 应用于路径规划中的改进的遗传算法^[3,5,6]

3.1 路径编码方法

如图2 所示, 通过EW.Dijkstra(迪克斯特拉)算法得到了链接图中的最短路径为：P₁,P₂……P_n,P₁₉,其中P₁为路径的起点,P₁₉ 为路径的终点, 由于链接图法连接的是凸多边形的中点，基于上述方法通常得不到最短的规划路径，需要对P₁,P₂……P_n,P₁₉ 的位置进行调整, 从而得到机器人在工作空间的最优或近似最优的行走路径。用遗传算法优化时，我们让各路径点在相应障碍物端点连线上滑动。