一种基于GNG网络的可删减环境拓扑地图构建方法

摘要

本发明公开了一种基于GNG网络的可删减环境拓扑地图构建方法，本发明提出PGNG拓扑地图构建方法，在原有的GNG算法基础上引入了节点修剪算法，使得原有地图中冗余的拓扑节点得到删除和替换。同时新节点的建立采用了“平均”思想，使得生成的拓扑地图中的节点分布更加均匀，地图表达更为简洁，可以有效应用在移动机器人拓扑地图的建立中。实验结果表明，应用本发明所提出的基于GNG网络的可删减环境拓扑地图构建方法，其拓扑节点个数约为传统GNG算法个数的3/4，有效地简化了拓扑地图的复杂程度，同时为路径规划任务奠定了较为良好的基础。

说明书

技术领域

本发明属于室内移动机器人环境拓扑地图构建方法，在增长神经气(GrowingNeural Gas，简称GNG)算法的基础上提出一种可删减的环境拓扑地图构建方法PGNG(Prunable Growing Neural Gas)，对GNG网络所生成的冗余拓扑节点进行替换及删除，并将原有拓扑节点周围的连接关系加入到新生成的节点上。该算法可以有效地解决拓扑节点冗余的问题，可在机器人拓扑地图的优化中发挥重要作用。

背景技术

随着人工智能行业与机器人技术的不断发展，如何在一定空间中为机器人建立更加简洁、有效的环境地图得到了人们越来越多的关注。常见的环境地图表示方法大致分为：栅格地图、拓扑地图、稀疏地图、稠密地图。栅格地图虽然有利于进行建模、更新，但随着环境的扩大及栅格精度的提升，该方法所造成的存储资源浪费是十分明显的。稀疏地图只包含了环境中人为设定的一些特征点，不能十分精准地表达环境，造成了已有信息的浪费。而稠密地图则需要大量的存储资源以保存完整的环境地图，不适用于动态环境，且存在着很多冗余信息。拓扑地图具有较低的空间复杂度，且不需要机器人的精确位置信息，是一种更为紧凑的环境表达方式。

增长神经气(GNG)算法能够在环境中不断增加神经气网络节点以表征地图，并进行信息的抽取与表示，且能够保持输入空间的拓扑特征不变，是一种具有自学习，自适应能力的智能环境拓扑地图构建方法。然而，传统的GNG算法中，其神经气节点的增长具有一定的局部性，所生成的拓扑环境地图中存在节点冗余问题。

针对上述情况，本发明提出一种基于GNG网络的可删减环境拓扑地图构建方法PGNG，该方法可对生成的拓扑地图中存在的冗余节点进行替换及删除，并生成较为简洁的环境拓扑结构。

发明内容

本发明依据对GNG网络在环境中生成的拓扑连接关系进行统计分析，设定长度删减阈值，设计了PGNG算法。在不破坏地图准确性的条件下有效减少了其的冗余性，所生成的拓扑地图更加适用于移动机器人的路径规划任务。通过与原有地图进行对比可知，PGNG算法生成的拓扑节点个数更少，节点分布更加均匀，地图表达更为简洁。

本发明是通过以下技术方案实现的，一种基于GNG网络的可删减环境拓扑地图构建方法，本发明包括以下步骤：

第一步、初始化输入空间N；

第二步、初始化网络A；

第三步、更新输入空间N；

第四步、执行GNG算法。通过不断增加节点个数及调整网络内节点所在位置，用GNG网络对机器人所在环境进行拓扑描述，生成机器人导航所用的拓扑地图。

第五步、执行网络修剪算法。对已经生成的拓扑地图中的冗余点进行替换及删除，得到更为简洁的拓扑地图。

具体而言，

第一步中：依据输入空间N的大小获得添加一个新的输入信号的概率p

第二步中包括：

步骤2-1：初始化GNG网络结构A。在空间中任意选取两个点a与b并设定为机器人所在环境拓扑结构的原始状态，则A＝{a,b}；

步骤2-2：依概率p

第三步中包括：

步骤3-1：更新输入空间N。随机添加一个新的输入信号的概率为p

步骤3-2：计算信号ξ与节点空间中每个节点的欧氏距离，并找出信号ξ的最近邻节点及次近邻节点。假设c

其中，c

第四步中包括：

步骤4-1：如果c

C＝CU{(s

步骤4-2：更新最近邻节点c

其中，

步骤4-3：更新最近邻节点c

其中ε

步骤4-4：

步骤4-5：若输入信号产生的次数为λ的整数倍，且当前网络中拓扑节点个数小于最大节点个数，则插入新的节点N

4-5-1：在节点空间N中找出具有最大累计误差的节点N

4-5-2：找到与N

4-5-3：新节点向量

4-5-4：将与节点N

4-5-5通过乘以常数α来减小N

步骤4-6：对所有节点的误差乘以常数d，以减小所有节点的累计误差。

步骤4-7：如果程序未到达停止条件，则返回第三步。

步骤5：当GNG网络到达停止条件，依次检查网络中的每一个神经节点，若某一节点N

改进算法的流程图如图1所示。

附图说明

图1、PGNG算法流程图。

图2、移动机器人室内仿真环境。

图3、不同学习轮次的拓扑结构图。图3a为第1轮；图3b为第20轮；图3c为第40轮；图3d为第60轮；图3e为第80轮。

图4、经删减后的拓扑地图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例在本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例：

一种可删减GNG网络的环境拓扑地图构建方法步骤如下：

第一步、初始化输入空间N。依据输入空间N的大小获得添加一个新的输入信号的概率p

第二步、初始化GNG网络结构A。在空间中任意选取两个点a与b并设定为机器人所在环境拓扑结构的原始状态，则A＝{a,b}。依概率p

第三步、更新输入空间N。随机添加一个新的输入信号的概率为p

其中，c

第四步、执行GNG算法。通过不断增加节点个数及调整网络内节点所在位置，用GNG网络对机器人所在环境进行拓扑描述，生成机器人导航所用的拓扑地图。

如果c

C＝CU{(s

更新最近邻节点c

其中，

更新最近邻节点c

其中ε

若输入信号产生的次数为λ的整数倍，此处取λ＝100，且当前网络中拓扑节点个数小于最大节点个数，则插入新的节点N

1、在节点空间N中找出具有最大累计误差的节点N

2、找到与N

3、新节点向量

4、将与节点N

5、通过乘以常数α来减小N

对所有节点的误差乘以常数d＝0.0005，以减小所有节点的累计误差。

如果程序未到达停止条件，则返回第三步。

第五步、执行网络修剪算法。当GNG网络到达停止条件，依次检查网络中的每一个神经节点，若某一节点N

实施效果

为了验证本发明的可行性及精确性，搭建了移动机器人的室内环境图，如图2所示。图3为不同轮次时，GNG网络产生的环境拓扑地图。图4为经修剪后的拓扑地图。图3、图4两种地图的节点个数如表1所示。结果表明：在对原有地图进行修剪之后，拓扑图中的节点个数减少至原来的4/5，降低了环境的冗余性，使拓扑地图更加简洁有效。

表1.GNG算法与PGNG算法节点个数对比