How can a robot locate, map and move in an unknown environment?

1. Foreword With the rapid development of computer technology, with the deepening of robot research and the expansion of people's demand for robots, robots that can move intelligently and navigate autonomously have become the focus of research. There are some practical solutions for robot autonomous localization in known environment and map creation of known robot position. However, in many environments, the robot can not use the global positioning system for positioning, and it is difficult to obtain the map of the robot's working environment in advance. At this time, the robot needs to create a map in a completely unknown environment under the condition of uncertain position, and use the map for autonomous positioning and navigation. Slam (synchronous positioning and map building) technology is considered to be the core and key technology to realize truly autonomous mobile robot. The robot starts to move from an unknown position in an unknown environment. In the process of moving, it locates itself according to the position estimation and sensor data, and gradually improves and constructs a complete map. This is a slam process. In slam, the robot uses its own sensor to identify the feature mark in the unknown environment, and then estimates the global coordinates of the robot and the feature mark according to the relative position between the robot and the feature mark and the odometer reading. This online positioning and map creation needs to maintain the detailed information between the robot and the feature mark. In recent years, the research of slam has made great progress and has been applied to various environments, such as robot, AR, VR, UAV, autopilot and so on. 2. Key issues of slam 2.1 representation of map At present, the common map representation methods can be roughly divided into three categories: grid representation, geometric information representation and topology representation. Each method has its own advantages and disadvantages. (1) Geometric information map Geometric information map representation means that the robot collects the perception information of the environment, extracts more abstract geometric features, such as line segments or curves, and uses these geometric information to describe the environment. advantage: It is more compact and convenient for position estimation and target recognition; The geometric method uses Kalman filter to obtain high accuracy and small amount of calculation in local area; Disadvantages: The extraction of geometric information requires additional processing of perceptual information, and a certain amount of perceptual data is required to obtain the results; It is difficult to maintain accurate coordinate information in wide area environment; (2) Grid map Grid map is to divide the whole environment into several grids of the same size, and point out whether there are obstacles for each grid. advantage: Easy to create and maintain, and try to retain all kinds of information of the whole environment; With the help of the map, self positioning and path planning can be carried out conveniently; Disadvantages: When the number of grids increases (in large-scale environment or when the environment is divided in detail), it will become difficult to maintain the map. At the same time, there is a large search space in the positioning process. If there is no good simplified algorithm, it is difficult to realize real-time application. (3) Topological map Topological maps are highly abstract, especially when the environment is large and simple. In this method, the environment is represented as a graph in the sense of topology, and the nodes in the graph correspond to a characteristic state and location in the environment. If there is a direct connection path between nodes, it is equivalent to the arc connecting nodes in the figure. advantage: Conducive to further path and task planning; The storage and search space are relatively small and the computing efficiency is high; Many mature and efficient search and reasoning algorithms can be used; Disadvantages: When using, it should be based on the identification and matching of topology nodes. For example, when there are two very similar places in the environment, it will be difficult for the topology map method to determine whether they are the same point; 2.2 description of uncertain information When the environment is completely unknown, if the robot wants to build a map and walk, it must get information with the help of other sensors, such as odometer, sonar, laser rangefinder, vision and so on. Due to the limitations of the sensor itself, there are varying degrees of uncertainty in the sensing information. For example, the uncertainty of the laser rangefinder mainly comes from the measurement error of the distance and the measurement angle error caused by the rotation of the reflector and laser scattering. As shown in the above figure, the uncertainty of perceived information will inevitably lead to the impossibility that the constructed environment model is completely accurate. Similarly, when making decisions based on model and perception, there is uncertainty, that is, uncertainty is transitive. The methods to measure uncertainty mainly include probability measurement, trust measurement, possibility measurement, fuzzy measurement and evidence theory. At present, probability measure and fuzzy measure are widely used in AMR map construction. There are two main forms of probability measurement: (1) The uncertain information is described by probability characteristics such as mean, variance and covariance. The advantage of this measurement method is that the probability characteristics such as mean have clear geometric significance, but the disadvantage is that the discrete calculation formula of probability characteristics has not been determined; (2) Probability model is used to describe uncertain information, mainly using Bayes rule and Markov hypothesis. The advantage of this measurement method is that the position, attitude and environmental information of the robot are described by the random probability model, and the robustness is very good. The disadvantage is that the amount of calculation of the probability model is very large, and the prior probability of the model must be known in advance, which makes it difficult for practical application. 2.3 location and environmental feature extraction Mobile robot self localization is closely related to environmental modeling. The accuracy of the environment model depends on the positioning accuracy, and the implementation of positioning is inseparable from the environment model. In the unknown environment, the robot has no reference and can only rely on its own inaccurate sensors to obtain external information, just like a blind man groping in an unfamiliar environment. In this case, positioning is difficult. Both map positioning and map creation with positioning are easy to solve, but positioning without map and map creation without positioning are like the "chicken egg" problem. In the existing research, the solutions to such problems can be divided into two categories: (1) While relying on internal sensors to estimate their own motion, external sensors (such as laser rangefinder, vision, etc.) are used to perceive the environment, analyze the obtained information, extract environmental features and save them. In the next step, their own position is corrected by comparing environmental features. But this method depends on the ability to obtain environmental characteristics. (2) Using a variety of internal sensors (including odometer, compass, accelerometer, etc.) carried by itself, the positioning error is reduced through the fusion of a variety of sensor information. Most of the fusion algorithms used are based on Kalman filter. Because these methods do not refer to external information, the error accumulation will be large after long-time roaming. Environmental feature extraction methods include: 1) . Hough transform is a kind of method to detect lines and other curves based on gray image. This method requires a cluster of pre prepared specific curves that can be searched, and generates curve parameters according to a cluster of curves in the displayed gray image. 2) . clustering analysis is a data detection tool, which is effective for unclassified samples. At the same time, its goal is to divide the targeted objects into natural categories or cluster classes based on similarity or distance. When the category of the extracted object is unknown, clustering technology is a more effective technology compared with houghtransform. Cluster classes should be centered on "cohesion", rather than fragmented and disjoint. Environmental features are sometimes difficult to extract. For example, when the environmental features are not obvious enough or there is little sensor information, it is difficult to obtain environmental features from one-time perception information. 2.4 Data Association Data association is to match two feature marks to determine whether they correspond to the same object in the environment. Data association in slam mainly needs to complete three tasks: (1) Matching between maps; (2) Matching of feature marks; (3) Detection of new feature marks; Although data association has been well solved in the fields of target tracking and sensor fusion, these methods have a large amount of calculation and can not meet the real-time requirements of slam. The complexity of data association between M signs and maps with n signs is exponential with M. assuming that each observed sign I has a possible match, for M signs, it is necessary to search for the correct match in the exponential space =. The search space of data association is related to the complexity of the environment and the positioning error of the robot. The increase of the complexity of the environment will increase m, and the increase of the error will increase Ni. 2.5 cumulative error The errors in slam mainly come from three aspects: (1) Observation error; (2) Error of odometer; (3) Errors caused by incorrect data association; When the robot locates in the environment of known map, the robot can compensate the odometer error by observing the feature mark with known position. Each observation makes the robot's position error tend to the sum of the observation error and the position error of the feature mark. However, in slam, because the position of the robot and the position of the feature mark in the environment are unknown, the observation information can not effectively correct the error of the odometer, and the position error of the robot increases with the moving distance of the robot. The increase of the position error of the robot will lead to wrong data association, which will increase the position error of the feature mark; in turn, the error of the feature mark will increase the position error of the robot. Therefore, the position error of the robot is closely related to the position error of the feature mark. The interaction between them makes the position estimation of robot and feature mark produce cumulative error, which is difficult to ensure the consistency of map. 3. Implementation method of slam At present, slam methods can be roughly divided into two categories: (1) Methods based on probability model: complete slam based on Kalman filter, compression filter, FastSLAM, etc (2) Non probabilistic model methods: sm-slam, scan matching, data association, based on fuzzy logic, etc. 3.1 implementation method based on Kalman filter From the statistical point of view, slam is a filtering problem, that is to estimate the current state of the system according to the initial state of the system and the observation information and control information (odometer reading) from 0 to t. In slam, the state of the system is composed of robot pose R and map information m (including the position information of each feature mark). Assuming that the motion model and observation model of the system are linear models with Gaussian noise, and the state of the system obeys Gaussian distribution, slam can be realized by Kalman filter. SLAM Based on Kalman filter includes two steps: system state prediction and update. At the same time, it also needs to manage map information, such as the addition of new feature marks and the deletion of feature marks. Kalman filter assumes that the system is a linear system, but in practice, the motion model and observation model of the robot are nonlinear. Therefore, the extended Kalman filter is usually used. The extended Kalman filter approximately represents the nonlinear model through the first-order Taylor expansion. Another Kalman filter suitable for nonlinear models is UKF (unscented Kalman filter). UKF uses conditional Gaussian distribution to approximate a posteriori probability distribution. Compared with EKF, UKF has higher linearization accuracy and does not need to calculate Jacobian matrix. Kalman filter has become the basic method to realize slam. Its covariance matrix contains the uncertain information of robot position and map. When the robot continuously observes the characteristic signs in the environment, the determinant of any sub matrix of the covariance matrix decreases monotonically. Theoretically, when the number of observations tends to infinity, the covariance of each feature mark is only related to the covariance of the starting position of the robot. The time complexity of Kalman filter is O (). Because the robot can only observe a few feature marks at each time, the time complexity of SLAM Based on Kalman filter can be optimized as O (), and N represents the number of feature marks in the map. 3.2 local sub map method The local sub map method decomposes slam into some smaller sub problems from the perspective of space. The following problems should be considered in the sub map method: (1) How to divide sub maps; (2) How to represent the relationship between sub maps; (3) How to transfer the information of the sub map to the global map and whether the consistency of the global map can be guaranteed; The simplest local sub map method is to divide the global map into independent sub maps including a fixed number of feature markers without considering the relationship between sub maps, and implement slam in each sub map respectively. The time complexity of this method is O (1). However, due to the loss of useful information representing the correlation between different sub maps, this method can not ensure the global consistency of the map. In this regard, Leonard et al. Proposed DSM (decoupled stochastic mapping) method. Each sub map in DSM saves its own robot position estimation. When the robot enters another sub map B from one sub map a, EKF based method is used to transmit the information in sub map a to sub map B; B. Williams et al. Proposed a slam method based on CLSF (constrained local submap filter). CLSF creates a sub map with known global coordinates in the map. During the robot's progress, only the observation information is used to update the position of the feature marks in the robot and the local sub map, and the local sub map information is transmitted to the global map at a certain time interval. Although experiments show that the two algorithms have good performance, they have not been proved theoretically that they can maintain the consistency of maps. J. Guivant et al. Proposed a slam optimization algorithm cekf (compressed extended Kalman filter) without any information loss. Cekf divides the observed feature marks into parts A and B. A represents the area adjacent to the current position of the robot, which is called the active sub map. When the robot moves in the active sub map a, the position of the robot and sub map a are updated in real time by using the observation information, and the influence of the observation information on sub map B is recorded by recursive method; When the robot leaves the active sub map a, the observation information is transmitted to the sub map B without loss, so as to update the sub map B at one time and create a new active sub map at the same time. The calculation time of this method consists of two parts: slam in activity sub map, whose time complexity is O (), which is the number of feature marks in activity sub map a; The time complexity of updating sub map B is O (), which is the number of feature marks in map B. When the time interval of sub map merging is large, cekf can effectively reduce the amount of slam calculation. 3.3 decorrelation method Another way to reduce the complexity of slam is to ignore some elements with smaller values in the covariance matrix representing the correlation relationship and turn it into a sparse matrix. However, it will also lose the consistency of the map due to the loss of information. However, if the representation of covariance matrix can be changed so that many of its elements are close to or equal to zero, it can be safely ignored. SLAM Based on extended information filter (EIF) is based on this idea. EIF is the information-based expression of EKF. The difference between them is that they represent information in different forms. EIF uses the inverse matrix of covariance matrix to represent the uncertain information in slam, which is called information matrix. The fusion of two unrelated information matrices can be simply expressed as the addition of two matrices. Each non diagonal element in the information matrix represents a constraint relationship between the robot and the feature mark or between the feature mark and the feature mark. These constraint relationships can be updated locally through the signal relationship of the system state. This local update makes the information matrix approximate to the sparse matrix, and the error caused by thinning it is very small. According to this, S. Thrun et al. Proposed a slam method based on sparse information filter seif (sparse extended information filter), and proved that the time complexity of slam using sparse information matrix is O (1). Although EIF can effectively reduce the time complexity of slam, there are still some problems in the representation and management of map information. Firstly, the mean value of the system state can only be approximately calculated in constant time; Secondly, in the slam method based on EIF, the addition and deletion of feature marks is inconvenient.