拓扑地图及拓扑导航

机器人学中的传统导航方法，通过利用在给定地图中定位、轨迹规划以及运动控制等途径让机器人完成导航任务，如SLAM（Simultaneous Localization And Mapping：同步定位与建图）。然而，SLAM 方法存在许多局限性。例如，在特定的情况下，SLAM 方法需要耗费很大精力来获得一张几何上非常精 确的环境地图。这往往需要与高精度的计量学或全球导航卫星系统传感器相结合，并且需要专家级的地图修改和参数调整，实际应用成本较为高昂。

2010 年代以来，伴随着深度学习的蓬勃发展，基于学习（learning-based）的导航方法逐渐得到了广泛的应用，成为机器人在复杂三维环境中学习导航的有效途径。

基于深度学习的导航方法主要可以划分为三类：1）纯粹反应性的（reactive），例如基于深度强化学习的目标驱动导航；2）基于非结构化通用记忆的，例如LSTM（Long Short-Term Memory，长短期记忆）；3）基于特定于导航场景的结构化记忆的，例如度量地图（metric map）。

n  度量地图：

度量地图是指以数学度量方式描述环境的地图，通常使用二维或三维网格地图来表示。度量地图通常包含环境中的物体、障碍物、地形等信息，以及机器人的位姿信息。机器人在使用度量地图进行导航时，通常采用自我定位（self-localization）方法来确定自身的位置和方向，然后使用路径规划算法（如A* 算法、Dijkstra 算法等）来寻找从当前位置到目标位置的最短路径。机器人在移动过程中，会不断更新自身的位置和方向，并根据更新后的信息重新规划路径，以保证能够到达目标位置。

度量地图的优点是能够提供精 确的环境信息，能够在机器人移动时实时更新，且适用于多种导航算法。然而，度量地图也有一些缺点，比如它需要较大的存储空间和计算资源，且对环境变化敏感，需要不断更新地图信息。

n  拓扑地图：

事实上，动物和人类主要依赖的便是基于地标的导航策略，这一策略以对环境的定性拓扑知识为基础，即环境的拓扑地图（topological map）

作为另一类基于结构化记忆的主流导航方法，拓扑导航基于拓扑学的原理，使用节点和边的连接关系来描述环境，构建拓扑地图。

拓扑地图是一种抽象化的地图表示方法，它不需要记录精 确的物理坐标和尺寸，只需记录节点以及节点之间的拓扑关系。在拓扑地图中，节点代表环境中的关键位置，即地标，例如房间、门、走廊等，而边代表节点之间的邻接关系，例如门连接两个房间、走廊连接两个节点等。在基于拓扑地图的机器人导航中，机器人通过特定的传感器获取环境信息，并将这一信息与拓扑地图进行匹配，以确定自身所处的位置。完成定位后，再利用拓扑地图上的节点和边计算到达目标位置的最短路径，并根据特定的控制算法沿着路径移动。

相比于度量地图，基于拓扑地图的导航具有许多优势，包括：

1）地图的简洁性：拓扑地图通过表示环境中的关键点和它们之间的连接来简化了地图表示。相较于度量地图，拓扑地图通常较小，更容易存储和处理。

2）抽象级别：拓扑地图提供了一种对环境进行高层次抽象的方法，这使得机器人能够更好地理解环境中的结构和关系。这种抽象级别有助于机器人规划路径和避免障碍物。

3）地图更新和维护：拓扑地图中的节点和边可以轻松地添加、删除或更新，这使得地图的维护和更新变得相对容易。这对于机器人在动态环境中导航尤为重要。

4）可扩展性：拓扑地图可以轻松地扩展以包含更多的节点和边，使其能够适应不断变化的环境。此外，拓扑地图可以与其他地图类型（如度量地图）结合使用，以提供更丰富的导航信息。

5）鲁棒性：拓扑地图对于环境中的变化具有较好的鲁棒性，因为它们只关注关键点之间的连接关系。这使得机器人能够在环境中的部分变化或不精 确的传感器数据的情况下继续进行导航。

6）路径规划和优化：基于拓扑地图的导航可以利用图搜索算法（如A* 算法）来快速找到从起点到终点的最优路径。通过优化这些算法，可以提高路径规划的速度和效率。

7）多机器人协作：拓扑地图为多机器人系统提供了有效的通信和协作机制。机器人可以共享地图信息，并通过拓扑地图来协同规划路径和任务分配。

n  拓扑导航-感知相似性

拓扑导航关注于如何构建环境的拓扑地图作为一种空间记忆的表征形式，以利用环境中的拓扑几何信息进行导航。一般地，在拓扑地图中，节点代表环境中的某一空间位置，有时还会存储该位置的观测信息；而节点之间的边则反映了节点所代表的空间位置间的邻接关系（或者说机器人在空间位置间的可达性），节点之间有边相连，代表空间位置相邻，反之则代表空间位置不相邻。当前拓扑导航领域的研究，一方面研究拓扑地图（拓扑记忆）构建的问题，另一方面研究基于感知信息的拓扑定位的问题，并常与路点预测、底层局部控制等相结合。

在拓扑导航中，定位模块主要基于感知相似性（perceptual similarity）来构建定位网络（或检索网络）。由此可知，感知相似性是拓扑导航系统的核心。感知相似性能够衡量不同视觉观测之间的相似程度，进而反映视觉观测所处地点在空间位置上的关系。相似程度越高，代表越接近；相似程度越低，代表越远离。这一逻辑与动物和人类的直觉相契合。

感知相似性与这些功能的实现息息相关：1）拓扑节点定位。通过判断机器人当前位置观测与拓扑记忆中节点的相似性，可将机器人当前位置定位到拓扑图的最邻近节点中。2）拓扑地图构建。感知相似，则节点融合；感知不相似，则节点远离。从而将机器人探索轨迹所形成的连续观测序列稀疏化，把环境抽象为离散的拓扑地图。

计算机视觉领域感知相似性的研究可以分为两个方向：基于特征提取的方法和基于深度学习的方法。

§  基于特征提取的方法通常使用传统的计算机视觉算法（如SIFT、HOG等）来提取图像的局部特征，并将这些特征映射到低维空间中。在低维空间中，可以使用欧氏距离、余弦相似度度量方式来计算相似性。这种方法的优点是具有良好的可解释性、计算效率高，但往往在处理复杂场景和大规模数据时表现不佳。

§  基于深度学习的方法则是使用卷积神经网络（CNN）或循环神经网络（RNN） 等深度学习模型来直接学习图像、视频等数据的嵌入向量（embedding），并使用这些向量计算相似度。这种方法的优点是能够自动学习特征表示，适用于处理复杂的场景和大规模数据，但是需要大量的标注数据和计算资源。

感知相似性研究工作中基于深度学习的方法也被称作深度度量学习（Deep Metric Learning，DML）方法。深度度量学习的目标是学习一个能够表征特征嵌入空间的函数（通过深度神经网络实现），使其能够将高维视觉数据（image pixels）映射到低维特征嵌入向量（feature embedding vector），再通过计算嵌入向量之间的距离，来衡量不同图像间的相似程度。

基于感知相似性的拓扑地图在线构建

把观测间的空间几何信息融入到深度度量学习框架中，使得深度网络能够学习到一种有效的深度特征空间，其输出的嵌入特征之间的距离既能表征观测图像本身的相似性，又能反映其在环境中的空间位置关系，从而实现拓扑节点定位的效果；

有机结合机器人当前观测和拓扑记忆，在拓扑记忆中定位机器人当前位置，并融合相似节点、分离不相似节点，实现机器人在探索环境过程中在线生成并更新拓扑地图，从而构建精 确度高、信息冗余度低的环境拓扑地图。