【作者】 季秀才；

【导师】 郑志强；

【作者基本信息】 国防科学技术大学 ， 控制科学与工程， 2008， 博士

【摘要】 移动机器人同步定位与建图(SLAM)问题是移动机器人在未知环境中实现真正自主必须解决的关键问题,是当前移动机器人学界的研究重点和热点之一。SLAM包含状态估计和数据关联两部分。其中,状态估计是指对环境特征的位置以及机器人定位的估计过程;数据关联是指建立在不同时间、不同地点获得的传感器测量之间、传感器测量与地图特征之间或者地图特征与地图特征之间的对应关系,以确定它们是否源于环境中同一物理实体的过程。数据关联为状态估计提供输入,正确的数据关联是实现正确的状态估计的前提。随着机器人运行环境的日益复杂和非结构化,SLAM中数据关联相关问题研究的重要性日益突显。SLAM中主要有以下三个子问题涉及数据关联:递增建图与定位,循环闭合和多机器人SLAM中的地图合并。递增建图与定位中的数据关联研究如何确定当前连续的传感器观测之间或者当前时刻的观测与最近所创建的局部地图中特征间的关联关系,该问题即为通常意义下的数据关联问题,本文称其为局部数据关联;循环闭合中的数据关联研究机器人沿不同的路径回到某一循环的起点时,如何确定当前创建的局部地图中的特征与以前所创建的循环起点处地图中特征之间的关联关系,本文称其为循环数据关联;地图合并中的数据关联研究多个局部地图中的特征间的关联关系,本文称其为多机器人数据关联。这三类数据关联的差别在于问题解空间大小不同。本论主要文针对上述三类数据关联问题展开了研究,取得了以下成果:(1)在分析现有的描述数据关联问题的数学模型局限性的基础上,根据SLAM中数据关联问题的特点,应用关联树模型描述SLAM中数据关联问题的解空间,将数据关联问题建模为针对关联树的图搜索过程,提出了一种更为清晰直观的图模型结构。在适当的节点耗散值定义下,证明了关联树节点耗散值随深度增加的单调递增性。根据关联树模型,应用人工智能中的图搜索理论对主要的数据关联算法进行了分类,并从算法的时间复杂度、空间复杂度和最优性等方面对这些算法进行了分析比较。(2)应用示例分析了SLAM中修正过去“错误的”1数据关联的必要性。利用针对关联树“好的优先”回溯搜索,并结合基于最小二乘的完全SLAM状态估计方法,提出了一种基于关联树有限深度回溯搜索数据关联的递增式完全SLAM算法(Incremental Full SLAM with Limited Backtracking Search Data Association—BTK_SLAM)。该算法将状态估计的最小二乘残差作为关联树节点耗散值,并实现了该耗散值的递增式计算,从而引入了由状态估计到数据关联的直接反馈。算法可以在线检测并修正过去错误的数据关联,因此在系统误差较大时依然可以获得较好的状态估计。另外,设计了合理的关联树剪枝方法以减少计算量。(3)针对闭环问题始终存在的根本原因一直未得到完善的理论分析解答这一问题,本文以线性高斯SLAM问题为研究对象,对机器人定位估计的收敛特性进行了详细的理论分析,证明了SLAM本质上是航迹推算式(Dead-reckoning alike)的自定位过程:随着机器人对未知区域的不断探索,其定位估计误差总体上递增且不收敛,即无上界。闭环问题始终存在的根本原因正是源于机器人定位估计的不收敛性。当机器人沿不同路径回到某一循环起点时,其定位误差可能会非常大,递增建图和定位技术难以获得相容一致的地图估计,必须采取其他方法单独处理闭环过程。(4)以使得机器人尽早检测到循环地形,并尽快实现循环闭合为目的,本文将机器人探索策略与闭环过程相结合提出了一种在线主动闭环方法。该方法将闭环过程与增量式SLAM过程相分离,并应用多阶段决策对主动闭环过程进行建模。自主机器人根据相互承接的多个决策过程的决策结果选择合适的行为,并应用改进的非完整地图中的粒子滤波定位实现闭环确定。该方法将循环数据关联问题转化为机器人在闭环处的全局定位问题,并应用粒子滤波实现定位估计,从而将高维关联空间中的搜索问题转化为多个连续低维空间当中的搜索问题。由于该主动闭环方法不受具体的递增建图和定位方法的限制,所以它实际上是一个实现机器人未知环境探索过程中在线自主闭环的模型框架,具有通用性。(5)多机器人SLAM中,当局部地图间的相对位置已知时,可以应用局部数据关联技术解决多机器人数据关联问题,此时地图合并问题的难度将大大降低。为此,本文提出了一种基于粒子簇滤波定位的地图合并算法,主要解决局部地图相对位置未知时如何正确计算局部地图间的相对位置关系问题。该算法通过实现一个机器人的探索路径在另外一个机器人建立的局部地图中的全局定位确定局部地图间的相对位置关系,这种相对位置关系称为合并假设。算法主要采取两方面措施保证生成正确的合并假设:一是将机器人路径分段并分别确定每段路径的全局定位,每段路径的一个定位估计称为一个局部合并假设,然后通过多个局部合并假设间的相容性检验确定全局合并假设;二是应用粒子簇滤波定位算法获得每段路径的多个定位估计,从而减少丢失正确的局部假设的可能。更多还原

【Abstract】 The simultaneous localization and mapping (SLAM) problem is one of the key problems for a mobile robot to be truly autonomous in an unknown environment, and has been an important and active research topic in mobile robotics community. The SLAM problem consists of two components: state estimation and data association. State estimation is the problem of estimating the location of the robot and individual features in the environment. And data association is the problem of determining whether or not two sensor measurements observed at different places and time, two features in different partial maps, or one sensor measurement and one map feature correspond to the same object in the physical world. Since the data association process provides inputs for the state estimation process, correct data association is the precondition to achieve correct state estimation. It is becoming necessary to study the data association problem in depth, as the environments in which mobile robots operate are becoming more and more complex and unstructured.There are three sub-problems in SLAM that involve data association: incremental localization and mapping, loop closing and map merging in multi-robot SLAM. In this dissertation, the data association problem in the incremental localization and mapping process is called local data association, which pertains to the correspondence relationships among sensor measurements obtained sequentially in time. The data association problem in the loop closing process is called loop data association, which pertains to the correspondences between features in the map built at present and features in the map built formerly at the point where the loop is closed. The data association problem in map merging process is called multi-robot data association, which pertains to the correspondences between features in the partial maps built by different robots. The three kinds of data association problems differ in the volume of their respective solution spaces. This dissertation is dedicated to the three sub-problems, and the three kinds of data association problems involved in them are mainly studied.Firstly, the dissertation analyses the character of the data association problem in SLAM and the limitations of its popular mathematical models, and then a concise and intuitionistic tree model, which is called correspondence tree (CT), is presented to describe the solution space of the data association problem in SLAM. The process to solve the data association problem is modeled as the tree searching process in CT. With an appropriate node cost defined, it is proven that the node cost in a path of CT is monotonically increasing with depth. Based on the CT model and using the tree searching theory of AI, the dissertation compares popular data association algorithms in terms of time complexity, space complexity and optimality. Secondly, the dissertation analyzes the necessity to revise past“false”1 data associations, and puts forward an incremental full SLAM algorithm with limited backtracking search data association (BTK_SLAM), which combines the“best-first”backtracking search strategy of CT with the least-squares state estimation method. The BTK_SLAM algorithm takes the least-squares residual produced by the state estimation process as CT’s node cost, which can be calculated incrementally, so a direct feedback is introduced from the state estimation process to the data association process. Since the BTK_SLAM algorithm can evaluate data associations and revise those false data associations on line, it can achieve good state estimation even when the system errors are large. In addition, practical pruning methods for the expanding of CT are proposed to reduce the computational complexity further.Thirdly, since the main reason why the loop closing problem in SLAM is unavoidable is still undiscorvered, the dissertation analyzes the convergent character of the robot localization estimation in SLAM, based on the linear Gaussian SLAM problem. It is proven that SLAM is a dead-reckoning alike self-localization process: when the robot continuously explores an unknown environment, the error of the robot self-localization estimation is generally increasing and divergent, that is the error has no upper limit. The divergency of the robot self-localization estimation is the essential reason why the loop closing is an issue at all. When the robot comes back to the start point of a big loop following a different path, its localization estimation error may be very large, and it might be impossible for incremental SLAM approaches to build a consistent map, so additional techniques beyond incremental SLAM methods must be adopted to deal with the loop closing problem.Fourthly, aiming at detecting and closing loops as soon as possible to reduce the mapping errors, the dissertation presents an on-line active loop closing method, which incorporates the exploration strategy into the loop closing process. In this method, the loop closing process is separated from the incremental SLAM process, and is modeled as a multi-stage decision problem. The robot decides its actions according to sequential decisions, and uses an adapted version of particle filters to validate loops. The method actually translate the loop data association problem into a robot global localization problem at the loop closing point, and obtains the localization estimation by particle filter, so it translate this searching problem in a high-dimensional space into a searching problem in multiple low-dimensional spaces. Since the active loop closing method is independent to the incremental SLAM process, it’s actually a general framework for the robot to autonomously implements loop closing during its exploring and mapping an unknown environment. Finally, in multi-robot SLAM, when the relative locations between partial maps are known, the map merging is much easier, because the multi-robot data association problem can be solved by local data association approaches. So the dissertation presents a map merging algorithm based on cluttered particle filter, which tries to properly calculate the relative locations between partial maps when their relative locations are unknown. The relative locations between partial maps are called map merging hypotheses. The algorithm gains the map merging hypothesis between two partial maps through localizing one robot’s trajectory in the other robot’s partial map. Two techniques are applied to ensure the correct merging hypothesis is achieved. The first technique is that the robot’s trajectory is divided into many segments, and the localization of every segment is estimated separately. One localization estimation of every trajectory segment is called a local map merging hypothesis. The global map merging hypothesis is obtained by the joint compatibility test of multiple local map merging hypotheses of these trajectory segments. The second technique is that the cluttered particle filter is used to generate multiple localization estimations for every trajectory segment to further avoid the risk of missing the proper local map merging hypothesis in a partial map with many similar local areas.更多还原