基于遗传算法的目标追踪过程中路径规划研究*

鞠成恩， 赵晓侠， 王明兴， 黎振红

0 引 言

在目标追踪过程中，路径规划[1，2]是关键问题之一，其目的是在具有障碍物的环境里，根据一定的规则，寻找一条从起始点到目标的无碰撞路径，以较短的行程在较少的时间内追踪目标。路径规划常用的方法有人工势场法、可视图法和蚁群算法[3～5]等，但均存在着一定的缺点, 如算法计算量大 、自适应能力差以及易陷入局部最优解等。本文提出了路径规划方法，在遗传算法[6，7]的基础之上，应用简单几何避障方式产生遗传编码，通过仿真证明了方法能在障碍物环境下，实现追踪目标过程中的路径规划。

1 基于遗传算法的追踪路径规划

1.1 追踪区域及路径编码的表示方法

整个环境区域用二维栅格表示，以二维坐标(x，y)表示位置如图1所示。图中的空白区域表示无障碍物阻挡，目标及追踪器在该区域内可以自由移动；阴影部分表示有障碍。追踪器的行进路径由一串二维坐标点连接而成，本文采用浮点数编码。图中，S和D为路径的起点和目标点，v1(x1，y1)，v2(x2，y2)，…，vn(xn，yn)为路径上的点，路径长度可变，目标D沿序号1，2，3，4，5，6运动。

图1 追踪区域及路径

1.2 初始种群的产生

1.2.1 当前随机方式产生初始种群存在的问题

当前遗传算法产生种群一般采用随机方式，产生的种群中有很多非连通路径，虽然在迭代运算中可能转化为连通路径，但转化效果一般并不理想，使得过程解的覆盖空间具有很大的不确定性，可能在有限的进化代数内过早收敛，影响最终解的质量。所以，在确保初始种群的多样性的前提下尽可能保证所产生的路径连通，有助于改善算法的求解速度和全局收敛性。

1.2.2 基于切线方向方式的几何避障方法

本文提出了一种沿切线方向拉开的避障方法，基本思想为遇到障碍时沿切线方向作规避动作远离障碍，如图2所示 ，具体实现步骤为：

1)连接起始节点S和目标点D，得线段SD。

2)判断线段SD间是否被障碍物隔开。如果未隔开，则线段SD为最短路径；否则，继续。

3)若障碍区和线段SD相交于点A，以A为起点作障碍物在A点处边缘的切线，该直线交无障碍区域F于任一点B，若相交处为障碍物顶点，则在该点处作垂直于路径的垂线，同样该垂线交无障碍区域F于任一点B。

4)连接线段SB，BD。

5)在线段SB，BD中重复步骤(1)～步骤(4)直至线段不与障碍区域相交为止。

6)将各条分线段组合，形成一条由S到D的连通路径。

注意在通过各障碍区时每次直线避开障碍物的拉开方向应保持在最短连线的一侧，避免路径迂回。

图2 障碍物

1.2.3 初始种群生成

采用沿切线方向拉开的避障方法生成初始种群，当出现一个或多个障碍区域时，其产生初始路径的方法相似。以多个障碍区为例：1)作一条连接起点和目标点的连线；2)根据自由区域对区域进行分割，对不同的障碍区域生成各自的避障路径, 最后将各段路径连成一条完整的初始路径，如图3所示，(S-v1-v2-c3-v4-D)为生成的一条路径。

图3 初始路径

1.3 适应度函数确定

采用的适应度函数为总路径S最短，pi为路径中间点

(1)

1.4 交叉算子

本文利用切线方向拉开的特点，采用分区同侧交叉方式改进传统交叉算子不利于收敛的特点。根据产生种群时的划分区域，随机选择一个区域，在此区域内若交叉线段位于障碍物一侧，则在此线段上进行单点交叉；若交叉线段位于障碍物两侧，则放弃。如图4所示,路径S-B1-C1-D与S-B2-C1-D在障碍物一侧可以进行单点交差，而S-B3-D在障碍物另一侧不与前两条路径进行单点交差。

图4 交叉算子

1.5 变异方式

采用多点变异方式，根据产生种群时对区域的划分随机选择多个区域，每个区域内选择一个点，对该点横坐标及纵坐标进行高斯小范围变异

(2)

2 仿 真

设整个区域由50×50栅格组成，每个栅格表示一个二维位置坐标(x,y)，如图5(a)所示。S点方块表示追踪器位置，D点实心圆表示目标位置，追踪器的速度为目标的1.5倍。假设整个区域内布置有固定探测器[8,9]，每隔一段时间对目标进行探测以获得目标的当前位置。目标计划的侵入路线如图所示，由1号点位置侵入顺序经过2,3,4,5号点由6号点逃逸出区域。假设追踪器与目标若相距5个栅格即视为追踪到目标。

图5 目标追踪过程

当探测器侦测到目标出现在1号位置时追踪器启动，追踪的路线如图5(b)所示。

当经过一段时间后对目标进行第二次探测，此时追踪器已经到达S1点位置，而此时目标已经到达2号点位置，重新对目标追踪路线进行规划。如图5(c)所示。

再经过一段时间后对目标进行第三次、第四次探测，追踪器经过S2点已到达S3点位置，目标则到达了4号点位置。目标与追踪器间距已经小于5栅格距离，完成了追捕如图5(d)所示。

3 结束语

基于切线方向的几何避障方法，不仅保证了遗传算法产生种群时路径的连通性，而且避免了传统遗传算法的随机性对结果产生的不利影响，仿真结果表明本文方法正确可行。

参考文献:

[1] 山 丹，胡玉兰．移动机器人动态目标规划研究[J]．沈阳理工大学学报,2011,30(3)：13-16．

[2] Deepak B L，Parhi D R，Kundu S．Innate immune based path planner of an autonomous mobile robot[J]．Procedia Engineering，2012，38：2663-2671．

[3] 顾幸方，陈晋音．移动机器人未知环境避障研究[J]．传感器与微系统,2011,30(5)：16-20．

[4] 白金柯，陈立家，金 何,等．动态未知环境下一种新的机器人路径规划方法[J]．传感器与微系统,2011,30(10)：33-36．

[5] 张 琦，马家辰，谢 玮,等．基于改进蚁群算法的移动机器人路径规划[J]．东北大学学报:自然科学版,2013,34(11)：1521-1524．

[6] 邹细勇．自主移动机器人的智能导航研究 [D]．杭州： 浙江大学,2004：48-58.

[7] 姜明洋．基于遗传算法的移动机器人路径规划方法的研究[D]．沈阳：沈阳理工大学, 2008：6-45.

[8] 王 雪．无线传感网络测量系统[M]．北京：机械工业出版社，2007：307-360.

[9] 吕淑芳．无线传感器网络节点定位研究综述[J]．传感器与微系统，2016，35(5)：1-3,8．