机器学习方法在无人机室内导航中的应用与实现

宋雅娟，冯 萍，张洪刚

(1.苏州市职业大学 计算机工程学院，江苏 苏州 215104；2.马萨诸塞大学波士顿分校 工程系，马萨诸塞州 波士顿 02125；3.长春大学 计算机科学技术学院，吉林 长春 130022)

无人机的一个主要研究领域是无人机的环境感知、路径规划及控制系统的开发。这些能力对部署无人机辅助人们进行诸如营救、搜索及运输等任务非常必要[1]。在无线传感网中，不知道事件发生的确切位置，获得的传感器数据就没有价值，因此节点的定位就显得尤为重要[2]。确定无人机的位置可以用来实现基于位置信息的服务。局部地图算法的目标是根据探测到的障碍物确定空间中何处有障碍，在探索到障碍时可以依据无人机的位置信息生成障碍地图，从而可以进行室内空间导航及其他相关服务[3]。定位算法是通过使用传感器间的节点测量值，如距离或角度的知识并参考局部或全局坐标系统估计移动目标的位置。无线传感网中的多数定位方法集中于一部分称为锚点的传感节点，可以通过GPS或手工配置获取自己的确切位置，其他的节点使用定位算法从这些锚点计算出自己的位置，从而可完成对移动节点的位置追踪[4]。为提高基于近似数据的定位算法性能，应用基于距离、角度或者这些方法混合的额外方法进行距离度量。距离度量主要使用RSSI、TWR、TOA和TDOA，更进一步可以通过使用指南针或专门智能天线对接收信号的角度进行测量[5-6]。目前，很多方法开始采用机器学习领域的知识推导传感节点的位置。可以假定一组锚节点并且使用它们与目标节点的距离作为训练数据，过程的结果即为一个可以用来预测其他节点位置的模型[7-11]。本文是研究室内无人机的定位算法，实验中将室内空间人为划分成大小相同的立体网格，使用基于锚节点的室内定位系统计算与无人机的距离，并分别使用不同的机器学习算法确定无人机所在的网格。主要对决策树[12]、支持向量机[13]和贝叶斯[14]等三种方法进行对比。通过实验对比三种算法的分类准确率后选择基于贝叶斯的分类方法用于定位，并以此对无人机进行导航。实验中无人机可以根据贝叶斯预测结果进行比较准确的定位，在飞行过程中通过激光传感器实时探测环境中的障碍，同时更新网格地图，使无人机可以避障飞行。

1 实验环境

实验所用的无人机型号是crazyflie 2.0，见图1。配装在无人机上的Flow Deck，见图2。其中使用的VL53L0x激光传感器能够测量无人机与地面的高度，PMW3901光学流传感器可以用来给出其相对于地面的运动信息，但缺乏长期的位置感知。外部的系统可提供其当前位置的信息，室外可以借助GPS进行定位，但室内环境往往受限制，更复杂、或造价更高。本实验使用的是bitcraze公司的局部定位系统。

图1 实验所用无人机crazyflie 2.0

图2 配装在无人机上的Flow Deck

局部定位系统可被用来获得物体在空间中的3D位置。系统中主要涉及两部分：①一组锚节点传感器集合，他们被定位在房间中用来做位置参考，坐标根据实际部署位置手工测量后给出；②一个或更多的标签，被放置在无人机上，系统可以测量标签和多个锚节点之间的距离。有了这些距离值，可以通过计算获得无人机的定位信息。

实验中，在房间里放置6个锚节点，分布位置见图3。其中0号为第1个锚节点，在地面上，一般作为原点坐标使用。0、1、2号分别部署在地面上，3、4、5号部署在高层上，这样可形成一个立体空间，覆盖区域为阴影部分立体空间。

图3 局部定位系统锚节点传感器分布位置

为了能够确认无人机在空间中的位置，需要在无人机上安装相应局部定位系统的标签，见图4。标签可以与图3中的6个锚节点进行双方式测距方法(TWR)通信[14]，获取与它们的距离数据。

为了后续的路线规划及避障算法需要，将立体空间划分成固定大小的网格空间，见图5。将局部定位系统的6个锚节点按如图3所示位置安置在立体网格空间的相应位置。

无人机导航所用地图依赖于此网格空间，每个网格为地图中的一个点。

图4 安装在无人机上的局部定位系统标签

图5 室内空间网格划分示意图

2 机器学习方法在无人机定位中的应用

在每个网格空间不同位置分别采集与6个锚节点的距离数据d0：0.968 86；d1：2.431 061；d2：0.926 044；d3：1.406 135；d4：1.738 959；d5：2.292 752。

实验中使用局部定位系统获取的距离可以计算出3D坐标，但由于传感器数据存在的噪声问题，计算出的坐标存在一定的不确定性。为了增加定位的准确率，将定位问题建模成为分类问题。一般情况下，最初两个步骤是：①类别定义。将空间划分成大小相同的网格，Gm=(i，j，k)，其中类别Gm是锚节点覆盖区域中的一个网格。②训练数据。由于锚节点坐标是已知的，每个锚节点与网格中位置的距离作为特征值。当运行分类程序时就会获得一个预测模型，用于预测无人机位置属于哪个网格，为后续的导航算法提供网格定位信息。

为了解决分类问题，可以使用机器学习中的各种分类方法，本研究主要使用决策树、SVM和贝叶斯方法进行分类测试，并根据测试结果和问题的需要选择适合的分类方法。

实验中，将无人机放置在不同网格中，使用自行设计的数据采集程序，收集来自锚节点的距离数据，将6个距离数据直接作为特征值来训练分类模型。为了选择合适的机器学习方法用于定位，验证训练数据量对分类准确率的影响，使用规模不同的两种数据集，分别为每个网格采集148组不同数据；每个网格采集351组不同数据，训练时使用十折交叉验证来计算分类准确率。训练后再次采集新的数据验证不同方法的泛化误差。

图6 三种机器学习方法在两种规模数据集训练准确率对比

图7 三种机器学习方法在两种规模数据集训练实测准确率对比

三种机器学习方法对应不同规模数据量的准确率对比图，见图6。由图6可看出：SVM和贝叶斯两种分类准确率相近，都明显高于决策树分类。三种机器学习方法在不同规模数据量训练模型下实际数据测试的泛化准确率，见图7。由图7可看出：贝叶斯方法在实际分类中准确率较高。无人机在飞行过程中需要不断根据传感数据判断所在位置，准确率对后续的寻路算法及避障有重要作用，因此本文选取贝叶斯方法作为位置判断的方法。在训练数据时，数据量规模对测试准确率的提高有重要作用，可通过线下采集大量训练数据集的办法进一步提高分类准确率。

3 室内导航及避障

3.1 室内寻路算法

路径搜索的目标是找到一条避免障碍物好的路径，并把代价(距离、转向)最小化。运动的目标是找到一条路径并且沿着它行进。A*是路径搜索中最受欢迎的选择，因为它相当灵活，并且能用于多种多样的情形之中。图8为实验中使用A*算法根据新的启发函数计算的从S到E的最优路径。

无人机在起点S使用A*算法，以E为终点寻找一条最优路径。飞行时不断采集与锚节点的距离数据并使用贝叶斯方法确定自己位置，并按规划路径向终点方向飞行。同时，使用激光传感器探测前方相邻网格障碍物，更新地图后再次调用A*算法重新寻路，避开障碍物。

考虑到无人机在飞行过程中网格交叉位置定位准确率低的情况，在本文的A*算法中不支持无人机选取对角线的路径，所以在选取当前格子的相邻格子时，只考虑前后左右四个方向的直行路线。又因为无人机按原方向直行的代价较低，所以在计算G值的过程中对与无人机当前运行方向不同的相邻格子的G值适当提高了代价，从而可在寻路时优先选择与无人机同方向的下一格子。

图8 改进A*算法规划的从S到E的一条飞行路径

3.2 室内避障及地图更新

无人机避障地图更新及新路径如图9所示。为了能够探测环境中的障碍及障碍的位置，在无人机上装备Multiranger板，在4个方向上(前、后、左、右)分别装备激光传感器，在飞行过程中收集4个传感器传送回的距离数据，根据障碍探测算法确定相邻格子出现的障碍，根据方向将地图中的相邻位置填上障碍标记。

图9中的虚线位置为从未探测到障碍时从S到E的规划路径，实线为在S'网格探测到前方存在障碍后，将障碍标记更新到地图中，重新调用A*算法规划出的新路线。无人机在S'格需要进行转向，按新路径飞行到E。

图9 无人机避障地图更新及新路径

3.3 基于规划路线的贝叶斯定位准确率的进一步提升

由于网格空间是人为划分的，两个网格相交处没有明显的界限。在实验中发现，出现分类错误往往是在两个网格交界的地方。在实验过程中总结出两种有关定位与飞行路线不吻合的情况：

①无人机飞行路线正确，但贝叶斯预测为相邻网格，解决方法是通过使无人机在此处上飞，下飞n次，取与飞行路线吻合的那次判断；②无人机受动作噪声影响，偏离路径。

如果①中所有n次都与飞行路线所定网格不同，按投票方法选取预测多的那个网格对无人机进行定位，重新规划飞行路线。

由于选取的贝叶斯方法的泛化准确率比较高，再以规划路线及实际飞行情况辅助提高准确率，实验中可以完成无人机的室内飞行精确定位，正确导航其从起点飞行到终点，并可准确避障飞行。

4 结论

1) 在室内环境中，通过无人机定位完成室内导航研究中，使用锚节点作为已知节点，将其信号覆盖空间划分成网格。根据无人机在不同网格中接收到与各个锚节点的距离信息，分别使用三种机器学习方法进行训练分析后，选定贝叶斯方法作为定位方法。无人机在飞行过程中不断通过预测方法获得自己所在位置后使用A*算法进行寻路，并利用装备的激光传感器来探测周围障碍情况，根据位置、障碍实时更新网格地图，调整导航路线直至到达终点。

2) 为了简化操作，本研究中的地图只使用了地面一层的平面地图，A*算法是在平面地图中进行的。后续可以将算法扩充为立体地图并基于立体地图进行3D导航的研究。贝叶斯方法的训练过程需要事先采集各个网格的数据，这个过程费时而且高空不容易进行，所以需要进一步研究合适的采集方法从而简化空间数据的训练过程，增强方法的实用性。