基于分治法的同步定位与环境采样地图创建

Simultaneous Localization and Sampled Environment Mapping Based on a Divide-and-conquer Ideology

在不使用几何参数描述大规模环境的前提下,提出了基于分治法的同步定位与环境采样地图创建(Simultaneous localization and sampled environment mapping,SLASEM)算法来同时进行定位与地图创建.该算法采用环境采样地图(Sampled environment map,SEM)描述环境,使算法不局限于用几何参数描述的规则环境.同时该算法实时地创建局部地图,并基于分治法合并局部地图,保证了算法的实时性.在合并两个子地图时,算法首先从环境采样地图中提取出角点,利用角点约束初步更新子地图;然后利用符号正交距离函数作为虚拟测量函数,再次细微地更新子地图;最后将两个子地图合并到一个大地图,约简冗余的环境采样粒子,以提高地图的紧凑性.两个实验的结果验证了所提算法的有效性和实时性.

This paper presents an algorithm of simultaneous localization and sampled environment mapping（SLASEM） with a divide-and-conquer ideology to localize a robot and map large scale environments without using the environments geometric parameters.The usage of sampled environment map（SEM） prevents the algorithm from being limited to structured environments which can be described by geometric parameters.The algorithm builds local maps in real-time firstly,then combines them by the means of divide and conquer.This enables the proposed algorithm to be an on-line algorithm.To combine two local maps,firstly the algorithm extracts corner points from the maps and uses them to update the maps.Then,the algorithm takes the signed orthogonal distance function as the virtual measurement function to update the local maps in detail.Finally,the two local maps are combined into one and the redundant environment samples are removed to make the map compact.The results of two real experiments validate the efficiency and the real-time capability of the proposed algorithm.