Data Association Problem For Simultaneous Localization And Mapping Of Mobile Robots

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.