【专家点评】： 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。本论文采用遗传算法对深海集矿车的避障路径进行规划，思路和过程表达清晰。结果通过了计算机仿真测试初步证明了其可行性。应该说本论文论述的内容是在自动化领域使用先进控制算法的一次有益和有效的尝试。
摘要：
本文主要研究了利用遗传算法实现深海集矿车避障路径规划的方法与途径。将连续的路径离散化，并用随机数模拟各路径种群。把二维的路径转化为一维，生成简单的路径基因。提出了物理意义明确的适应度函数和相应的变异算子，从而引导遗传算法快速收敛于最优解。实验仿真表明，该算法能够快速，稳定的搜寻到所需的最佳路径。
关键词:
移动机器人，遗传算法, 避障路径规划
Abstract:
A kind of path planning method based on genetic algorithm for mobile robot with the consideration of the obstacles in the environment is analyzed and worked out. In this paper the continuous path is simulated by scatter point, and uses the random number to represent the path. The path of two dimensions is reduced into one dimension to produce simple path gene. In the method, the fitness function contains explicit physic means and corresponding mutation operator is provided, so that GA can be lead to an optimized result rapidly. The experiment shows that: this algorithm can get a optimal path fast and steadily.
Key word:
Mobile Robot, Genetic Algorithm, Path Planning;
1.引言
在深海集矿车的导航控制中, 路径规划是一个很关键的问题。深海集矿车路径规划的主要任务是在具有障碍物的环境中, 按照一定的评价标准, 寻找一条从起始状态到达目标状态的无碰撞路径。 一般来说有许多路径可供集矿车行走,可事实上需要集矿车必须找到一个最优路径,既能避开障碍物，又能以最小的消耗(如时间)返回预定路径。 集矿车路径规划是一个困难的非线性问题,传统的寻优策略因复杂而费时[1],难以用于集矿车的实时导航。 本文提出的路径规划算法, 应用简单的遗传编码, 并有明确物理意义的适应度函数。 通过计算机仿真证明该方法能解决动态环境中的深海集矿车路径规划问题。
2.基于遗传算法的深海集矿车路径规划方法
2.1路径编码方式
如何将问题的解转换为编码表达的染色体，并利于后续约束条件下的优化操作是遗传算法的关键问题。在遗传算法中，编码串的长度以及查找空间对于系统的运行速度是非常重要的[2], 因此必须设计一种简洁实用的编码技术,才能缩短规划时间，实现实时控制。在现实运动中，路径点是二维的，如果能对路径坐标点进行降维处理，必将大大提高计算速度。本文中，令当前坐标系为XOY,其中原点与起始点重合，X轴位于起始点与目标点的连线上。将连接起点与目标点的线段 等分,取等分点Xj(j=1,2,…n-2),过Xj点作直线Lj与X轴正交，在每个Lj上随机地选择一点Pj ,共得到n-2个点,再令Po, Pn-1分别为起点，终点，如下图所示：
路径编码示意图
记各点纵坐标为yi,j,从而形成一条随机路径Rj。这样路径就转化为一维的Y坐标编码。具体编码采用浮点数方式，如下图所示：
图中的yi,o即移动机器人的当前位置纵坐标,yi,n-1即是机器人的目标点纵坐标,路径就是：
2.2适应度函数的确定
适应值函数的选取直接影响到遗传算法收敛速度的快慢和算法的成败。结合具体问题的特征,该适应度函数应考虑以下因素：
2.2.1 路径长度
本文的路径长度指标函数定义如下：
2.2.2 路径的光滑度
本文的路径光滑度指标函数定义
规划时必须考虑路径光滑性对机器人运动性能的影响。机器人转弯时，角度应尽可能的小，因而要求生成的路径尽可能变化均匀。故路径的转角差累积值φ(vi)较小的基因较为优越。
2.3 路径的安全性及相应的惩罚策略
在设计安全保障策略前，首先假设障碍物的个数,位置信息已由安装在机器人上的声纳传感器获得。那么惩罚策略的目的是在机器人规划路径与障碍物覆盖范围进行比较的基础上, 形成安全、无碰撞可行路径。一条可行的路径必须保证机器人任何部位都不与障碍物发生碰撞, 即机器人与障碍物边缘的距离必须大于最小安全距离，即： Mi∩O=0
其中：Mi为机器人的某条运动轨迹； O指考虑安全距离条件时所有障碍物覆盖范围的集合。
对于进入障碍物覆盖范围的随机点，如下图所示：
（注：图中阴影部分为障碍物范围，Pi,j为随机路径点, P,i,j为该点对应的障碍物边缘点；）
本文设计了一个罚函数φ(vi)令：
2.2.4 适应度函数的选取
综合以上几点，可得到适应度函数为：
其中α,β,γ为相应的加权系数。
该适应度函数把3个约束条件有机的结合到一起，物理意义明了，计算简单。
2.3 交叉方法
采用算术交叉法产生新的个体。这里将两个染色体中的各元素以如下的方式组合，得到新染色体的相应元素，方法如下：
2.4 变异操作算子的选择
2.4.1 修复操作算子：
移动一个点。依照一定的概率，对位于障碍区域内的点重新取值，使其获得避开障碍物的机会。
2.4.2 优化操作算子：
删除一个点。同样，在一定的概率下，如果三个连续点皆在障碍物覆盖范围外部，且首尾点连线的中间点还位于障碍物覆盖范围外部，则删除中间点。
两种变异操作分别如下图所示：
2.5遗传算法操作步骤
综上所述，该算法可描述如下：
1.编码：生成一组随机数，以一维数组的形式转化成染色体vi。
2.评估及选择：
3.以一定的概率，对新种群进行交叉，变异。
4.进行遗传迭代操作，经过若干代的搜索，即可得到一条最佳路径。
3. 仿真实验
本文在VC++6.0环境下进行了仿真，用两个椭圆物体代表障碍物，用遗传算法求得避障路径，效果图如下：
（注：P o为起点，P n-1为目标点，障碍物的标记分别为BLOCK1,BLOCK2）
4. 结论
本文设计了一套基于遗传算法的路径
规划的方法，通过适当的适应度函数引导遗传搜索，得到了集矿车避障的最佳路径。仿真实验证明了该方法的稳定性和有效性。它的应用将使深海集矿车具备一定的自主导航、避障的能力，为其智能化研究提供了一条有益的思路。
参考文献：
[1]孙明，孙树栋。遗传算法原理及应用。国防工业出版社,1999: 45-47.
[2]玄光男(日)，程润伟。遗传算法与工程设计。科学出版社, 2000: 64-66.
[3]仲欣,吕恬生。基于遗传算法的汽车式移动机器人路径规划方法。上海交通大学学报，1999年7月。
[4]Bauer,R. Genetic Algorithms and Investment Strategies. John Wiley&Sons,New York. 1994: 102-105.
[5]Allbrecht,R.,C. Reeves, and N. Steele,editors, Artificial Neural Nets and Genetic Algorithms. Springer-Verlag,New York,1993: 88-91.
