机器人对未知环境的自主探索是机器人智能化的关键技术。为了更好的提高搜索效率，作者提出了一种基于边...
机器人对未知环境的自主探索是机器人智能化的关键技术。为了更好的提高搜索效率，作者提出了一种基于边界点优化和多步路径规划的搜索策略。他们主要对边界点优化、边界点选择、路径规划三个方面对路径规划算法进行改进。在边界点优化部分，提出了一种随机边界点优化(RFPO)算法，选择评价值最高的边界点作为目标边界点。考虑信息增益、导航成本和机器人定位精度，来确定边界点的评价函数。在路径规划部分，提出了一个多步探索策略。没有直接规划从机器人当前位置到目标边界点的全局路径，而是设置了局部探索路径步长。当机器人的运动距离达到局部探索路径步长时，重新选择当前最优边界点进行路径规划，以减少机器人走一些重复路径的可能性。最后，通过相关实验验证了该策略的有效性。
机器人自主探索是机器人领域的一个重要研究课题。主要目标是让机器人在有限时间且无需人工干预的情况下，获得最完整、最准确的环境地图。许多现有的地图探索策略都是基于边界，边界定义为未知空间与已知空间的分界线。基于边界的探索策略的思想是引导机器人到未知区域完成探索任务，因此自主探索任务大体上分为三个步骤:生成边界点、选择评价值最高的边界点、规划前往所选边界点的路径。
边界点的生成以基于边界的探索策略为前提。在现有的研究中，常见地边界点生成算法有：
基于数字图像处理的边缘检测和区域提取技术：为了提取边界边缘，必须对整个地图做处理，随着地图的扩展，处理它将消耗慢慢的变多的计算资源。
Keidar和Kaminka后来提出了一种只处理新的激光读取数据的边界检测算法，加快了计算速度，降低了计算资源的消耗。
快速探索随机树(rapid-exploration Random Tree, RRT)算法：由于RRT算法的随机性，生成的边界点分布不均匀。
基于广度优先搜索(BFS)的方法：这种方法简单便捷，不重不漏，但在大地图环境下，相对于其他算法可能计算速度稍慢
目标边界点的选择是有效探索的关键。以边界为基础的战略是由Yamauchi首先提出的。所使用的探索策略是识别当前地图中的所有边界区域，然后驱动机器人前往最近的边界点。这种方法对于探索任务有两个缺点。首先，它平等对待所有边界。其次，它仅限于一个信息源自:寻找新边界区域。因此很多研究者提出了多种不同的边界点选择算法，来改善这一情况。这篇文章是考虑信息增益、导航成本和机器人定位精度，来确定边界点的评价函数。
最后是机器人的路径规划部分，对于机器人自主探索中路径规划的研究已经存在很多高效的算法：
文中采用ROS平台下常见的SLAM算法--GMapping构建二维占用网格图，然后使用RRT算法在地图中生成边界点，如果新生成的点位于未知区域，则认为该点为边界点。它会被标记在地图上，然后我们停止这棵树的生长。将当前机器人的位置作为新的根节点，我们构建一个新的快速探索随机树来生成边界点。边界点生成示例如下图所示。
文章从边界点的信息增益、导航成本和机器人定位精度三个方面对边界点进行评估。
信息增益被定义为对于一个给定边界点预期被探索的未知区域面积。本文采取直接测量目标边界点可见区域内未检测到的空间大小的方法计算信息增益。以边界点为圆心，以激光雷达探测距离为半径形成圆。边界点检测圈如下图所示。通过计算圆圈中未知单元格的数量来量化信息增益。
导航成本定义为机器人到达边界点的预期距离，使用机器人当前位置到目标边界点的欧氏距离来表示。
在目标边界点的探测范围内，如果能检测到更多的直线特征或其他特征(如断点、拐角、折线)，机器人就能更准确地定位自己。文章用边界点检测圈内障碍物的面积来表示定位精度。通过计算圆圈中被占用的单元数来量化。边界点评价函数定义如下所示：
其中α、β、γ分别为信息增益、导航成本与障碍物面积的权重。这些权重用于调整不同因素的重要性,可根据不同的任务和环境进行设置。如果探索任务要求尽快完成探索，则增加α，降低γ;如果探索任务更注重地图的准确性，则减少α，增加γ。β通常取1表示单位导航成本下的增益值。利用边界点评价函数对所有边界点进行评价。选取值最大的点作为目标边界点。
PS：在计算导航成本时，如果环境地图过于复杂，可以再一次进行选择使用A*规划出的路径长度作为导航成本项，但会造成过大的资源计算消耗；另外，作者提出的这种计算模型是是合理的的，导航成本在分母上，也就是说距离越大得分越低，信息增益与障碍物面积在分子上，机器人在选择目标点时，肯定倾向于选择信息增益高、导航精度高的目标点。
由于边界点的生成部分始终运行在整个探测过程中，因此随着探测任务的执行，将得到许多边界点。然而，由于RRT算法的随机性，这些边界点的分布是不均匀的。因此，需要对生成的边界点来优化。文中借鉴GSO算法的思想，提出RFPO算法。GSO算法是一种新型的仿生群体智能优化算法。它模拟了高亮度萤火虫会吸引低亮度萤火虫向其移动的自然现象，使所有萤火虫集中在一个更好的位置，以此来实现问题的优化。在RFPO算法中，将每个边界点视为一只萤火虫，并将边界点评价函数的值E作为其绝对亮度值L：
萤火虫会被绝对亮度值更大的萤火虫所吸引，并向其移动。这种吸引力的大小由萤火虫对萤火虫的相对亮度值决定，萤火虫在萤火虫所在位置的亮度强度定义为萤火虫对萤火虫的相对亮度，相对亮度值越大，吸引力越大。然后对相对亮度进行建模。对于每个边界点，都有一个感知半径。它的值应根据感知传感器的范围来设置。在这个范围内，每一个边界点都会找到绝对亮度值大于自己的其他边界点，形成自己的邻域集。在邻域集中使用轮盘赌的方法，选择下一个要移动的目标点。
PS：这里的建模过程不是文章主要内容，就不过多展开，感兴趣可以在原文查看详细推导过程。
采用多步探索的原因：在机器人运动的过程中，会产生一些新的边界点，一些旧的边界点会失效，而新生成的边界点可能会优于当前的最优目标边界点。这有几率会使机器人选择一些重复的路径。
文中解决办法：定义了一个局部探索路径步长。每次当机器人的运动距离达到步长时，就清除无效点，并对所有剩余的边界点进行重新优化和重新选择。在每个局部探索路径步长内，采用动态窗口法进行机器人避障局部路径规划。
PS：动态窗口法是ROS中常见地局部路径规划方法，主要思想是在速度空间中进行采样，生成下一时间步的模拟轨迹，然后根据评估函数选择得分最高的路径，驱动机器人移动。
如下图所示，黄色点为目标边界点。作者在不同的速度集上模拟了许多轨迹。根据他们定义的轨迹评价函数，选取得分最高的轨迹（下图中用红色标记的路径）。能够准确的看出，机器人执行红色轨迹能够迅速到达目标边界点。同时，轨迹与墙体有一定的安全距离，墙体边界能够在一定程度上帮助机器人更准确地定位自身。
*博客内容为网友个人发布，仅代表博主个人自己的观点，如有侵权请联系工作人员删除。
