辐射扫描算法在无人船航迹规划中的应用

2019-12-20路春晖尹美琳付振楷李兴盛张嘉琪

实验室研究与探索 2019年11期

路春晖, 尹美琳, 付振楷, 李兴盛, 张嘉琪

(天津理工大学环境科学与安全工程学院，天津 300380)

0 引言

目前，人们对海上无人船的研究越来越感兴趣。通过派遣无人船执行危险任务会大大降低人员受伤的风险[1]。在无人船应用中，一个部署是环境监控，在高度污染的湖泊中，可以通过无人船来有效地收集水样采集数据，而不会将人类暴露于有害元素之中;另一个潜在的应用是灾后场景中的搜救任务。在多次实验中已经证明，无人船可以有效缩短响应时间，增加救援任务的成功率[2]。而简单、有效、快速的航迹规划算法成为提高任务成功率的重要保障。目前，常用的航迹规划算法主要有A*算法[3-5]、人工势场算法[6-7]、粒子群算法[8-10]和蚁群算法[11-12]等。

本文针对传统路径算法的思路和现有缺陷进行研究，寻求一种新型路径规划方法。在起点和终点之间存在障碍物的情况下，向两侧扫描获取周围障碍物信息，用以获取最短路径。通过使用LabVIEW2017平台编写了算法仿真软件，进行仿真实验，最终确定路径规划算法的可靠性。

1 环境模型的建立

在规划无人船全局路径时，首先针对已知信息进行环境空间建模[13]，根据建模结果获得包含环境的搜索空间。本文采用栅格法作为建模方法表示障碍物，将规划路径的区域划分成大小相同的栅格，原本有障碍物的栅格标记为不可行区域；剩下的栅格就是正常情况下的可行区域。

1.1 栅格粒度的确定

在利用栅格法进行空间环境建模过程中，栅格粒度的确定影响着路径规划的准确性[14]。栅格粒度的取值如果过小，将会造成环境空间的信息量过大，使系统负担过大；栅格粒度的取值如果过大，当障碍物较多时，将导致无法找到有效路径。

将栅格粒度的确定与环境中障碍物的疏密程度相结合，粒度的大小可以通过计算各障碍物面积的总和与计算整体环境的面积来获得。计算障碍物的面积时，对于不是矩形的障碍区域，对障碍物边缘进行扩充，以构成矩形区域，并将扩充部分一并算为障碍物进行考虑。

确定栅格粒度的具体方法：通过将各个障碍物矩形化，确定各个障碍物的面积，利用Sz=∑Sn计算障碍物总面积,其中：Sn为第n个障碍物的面积；Sz为障碍物总面积。确定栅格粒度：

式中：S总为需规划二维空间的面积；lmax为栅格坐标系的长度；lmin为人为限定的栅格最小边长；l为经计算所得的栅格边长(栅格粒度)。

1.2 栅格空间布局

在二维路径规划空间中，将水平右方向设置为正x轴方向，水平向上方向设置为正y轴方向。以这种方式构造了二维空间直角坐标系。栅格分为两种类型，第1种类型在其覆盖范围内不含任何障碍物；第2种类型在其覆盖范围内含有障碍物。将第1种栅格称之为自由栅格，用白色表示；第2种栅格称为障碍栅格，用黑色表示(见图1、2)。

图1 未处理前栅格障碍物形状

图2 处理后栅格障碍物形状

2 辐射扫描算法原理、模型及优化

2.1 辐射扫描路径规划原理

在起点与终点之间存在障碍物的情况下，起点沿障碍物向两侧进行扫描，得出子节点。再由子节点向终点方向进行扫描，若存在障碍物，则继续沿起点之前的扫描方向扫描，得出下一代的子节点。子节点再扫描下一代子节点时，已经被扫描过的子节点将不会再被定义为子节点。扫描到终点为最后一代节点，扫描过程终止，每代子节点依次反选，最后反选回起点，得出最短路径。

2.2 算法实现

Step1建立环境模型，确定栅格粒度，设置障碍栅格、可行栅格、起始栅格、目标栅格。

Step2从起点向终点方向发射射线，扫描路上有没有障碍(注意：射线真实宽度不是1，而是单个栅格的边长)。

Step3碰到障碍物后，生成两条射线向两侧扫点，以原向量角度沿障碍物边界前进，为起点到该点的新向量。

Step5比较该方向扫描新向量的长度与旧向量长度，当差值超过单位栅格粒度时，则判断当前位置存在可走空间。

Step6此时，在判断有可走空间的位置，被阻挡的可行栅格向射线方向下一个栅格建立子节点。

Step7子节点只需向外发射一条射线，新扫描的栅格需要不断判断是否超过了上级起点的扫描范围。如果超过，则上级起点也需要继续扫描(防止出现迷宫里的死胡同问题，同时防止所走路线并非最短路径)。

Step8如果沿障碍物前进所更新向量位置坐标的栅格不是障碍栅格的话，则需要该点到起点方向的向量的下一个栅格建立子节点。

Step9当沿障碍物扫描方向又出现不可行栅格时，则判断遇到内拐点，此时由原向量向逻辑扫描方向(一条射线为顺时针；另一条为逆时针)转动90°，继续扫描。

Step10重复当前所有步骤进行扫描。

Step11到达终点后，从终点开始反向连接父节点，直至回到起点，寻路完成。

2.3 辐射扫描算法模型

建立环境栅格，在环境模型中，设点(13,17)为要规划路径的起点，目标为(13,4)点。从起点(13,17)出发，向终点(13,4)发射射线，发现中间有障碍物(见图3)。由于起点(13,17)到终点(13,4)中发现障碍物，那么程序将生成两条射线向两侧扫描(见图4)。

扫描过程中发现在点(15,11)处，扫描射线的新向量与旧向量长度差超过1栅格宽度，判断此处有缺口。点(15,11)为射线中心遇到障碍物前的最后一个栅格。这时在点(15,11)向射线方向下一个栅格点(15,10)建立子起点(见图5)。

图5 建立一级子节点图

点(15,10)只向外发射1条射线，首先判断此点与终点之间是否存在障碍物，若存在则按上级点(这里的上级点是起点)扫描方向继续扫描，并且不断判断是否超过了上级起点范围，如果超过则上级起点也需要扫描。点(15,10)扫描到障碍物点(17,9)时，开始超过起点(13,17)的扫描范围，那么起点也继续扫描(见图6)。

起点(13,17)扫描过程中至点(21,12)处由不可行栅格变为可行栅格，判断该点到起点方向的向量的下一个栅格(21,13)建立子节点(见图7)。而点(15,10)由于扫描角度变化一周后无子节点而被舍弃。重复上述步骤，依次在点(21,13)、(23,11)、(23,8)、(21,6)、(18,4)、(16,2)、(13,2)建立子节点，点(13,2)向终点(13,4)发射射线，发现无障碍物。可直接到达终点，则扫描过程结束(见图8)。

图6 起点与一级子节点同时扫描图

图7 建立二级子节点图

图8 扫描终止后路线图

最终程序寻找出的路径为：起点(13,17)至(21,13)至(23,11)至(23,8)至(21,6)至(18,4)至(16,2)至(13,2)至终点(13,4)(见图9)。

图9 扫描算法所寻路线图

2.4 辐射扫描算法的优化

通过实例分析不难看出，障碍物分布与子节点的位置关系为左上、左下、右上、右下4种位置关系。当寻找的路径通过了子节点和其周边障碍物方格所夹方格时，则可忽略子节点，直接将两个所夹方格相连。如图10所示，点(21,13)为黄色子节点栅格，点(20,12)为其周边障碍物栅格，并在其右上位置。点(21,13)与点(20,12)相夹栅格为(21,12)和(20,13)，通过图10不难看出所规划路线需经过(21,12)和(20,13)两点。那么当寻路完毕后，从起点沿着所寻路径发射信号，当到达点(20,13)时，跳过子节点(21,13)直接走到点(21,12)。最终规划路径(见图10)。

图10 射线扫描算法最终规划路线图

3 仿真实验

为了验证辐射扫描算法的正确性，用C++实现了算法，并将其封装到动态链接库中，在LabVIEW 2017开发环境下做程序主界面并调用C++库。仿真软件主界面如图11所示，左侧用来显示无人船工作环境，图中显示的是天津于桥水库。路径规划的结果会直接绘制在地图上，并且在右侧显示规划的路径中包含的GPS坐标和算法耗时。为了方便使用，软件在内部对GPS坐标和栅格模型的序号之间做转换，所以软件的输入和输出均是GPS坐标，不需要用户手动输入起点和目标所在栅格的序号。