技术领域
本发明属于室内移动机器人环境拓扑地图构建方法,在增长神经气(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算法节点个数对比
机译: 基于开放流无线网状网络环境中基于开放流的拓扑发现和对等检测的控制器装置和方法
机译: 基于WPAN和WLAN的集成网络环境中的WPAN设备有效网络的构建方法及其存储方法
机译: 用于基于提供的管理员拓扑GUI在网络环境中引导目标设备的方法和系统