takeaway
Map software has now become a necessary and important auxiliary tool for people to travel. In order to achieve accurate navigation, the current position of the person or vehicle must first be determined accurately. Therefore, positioning technology is the cornerstone of navigation function.
This paper systematically introduces the key technologies used in mobile phone, vehicle and machine navigation and positioning, as well as the progress of AmAP in these key technologies. Finally, the evolution path of localization technology in the evolution from traditional navigation to autonomous driving is discussed.
1. Navigation and positioning framework
The core business objective of navigation positioning is to provide continuous and reliable positioning basis for navigation services, including: which road is on, whether it deviates from the route, how far it is from the next intersection, and so on.
In order to achieve this goal, the first need to receive positioning signal input. The most common positioning signal is GPS, which can provide location information with a full-field accuracy of 5 to 10 meters. On top of this, most phones are equipped with both inertial sensors (gyroscopes, accelerometers) and magnetometers, and some phones are equipped with barometers that can sense changes in position in the direction of elevation.
For the vehicle, the speed pulse, steering wheel Angle and other information obtained through CAN bus are another kind of important positioning input. Based on the above positioning signals, attitude fusion and dead reckoning are used to calculate the continuous and reliable position and attitude. Then, according to the map data, the actual position of the person/vehicle is associated with the map road, so as to judge whether the current navigation route has deviated in real time, or update the current relative position in the navigation route.
In the above positioning framework, the configuration of the input positioning signal is different according to the configuration of different terminals (mobile phone/vehicle), and the positioning technology used and the positioning scenes covered are also different.
For mobile phones, there are multiple use scenarios such as walking, cycling and driving, and user behaviors need to be identified. In the walking scenario, due to the low speed and inaccurate GPS direction, the mobile phone posture is realized by integrating inertial navigation and magnetometer calculation. In driving scenarios, position and attitude are mainly provided by GPS. Designing reliable map matching algorithm for GPS jumping, drift and other complex situations is the key problem to be solved in mobile phone positioning.
For vehicles, only driving scenarios exist. At the same time, because the vehicle has a stable installation state and CAN provide more abundant vehicle CAN bus information, based on this information, the design of dead count and fusion algorithm to solve the continuous positioning problem of tunnel, elevated, parallel road and other complex scenes is the focus of vehicle vehicle positioning.
2. Mobile navigation and positioning
2.1. Pose fusion technology
The commonly used Attitude fusion technology is also called AHRS (Attitude and Heading Reference System). For six-axis inertial sensor fusion, including gyroscope and accelerometer, its AHRS algorithm is shown in the figure below. Gyroscopes measure angular velocity, which can be integrated to obtain the change in Angle over a certain period of time. An accelerometer measures the acceleration of an object, including the acceleration of gravity. When at rest, the relative tilt Angle can be calculated by obtaining the components of the acceleration of gravity along the three axes. AHRS algorithm uses filtering methods, such as complementary filtering and Kalman filtering, to fuse different sensor attitudes.
For the nine-axis sensor, three additional axial magnetometer directions are provided, and the algorithm framework above is also used for fusion.
2.2. Map matching technology
The traditional map matching method is to find the road which is most likely to be the road of the car according to some judgment criteria such as distance and direction proximity among roads near the registration point. This method is simple to implement, but usually GPS positioning error is ten meters, in the case of signal interference, occlusion can reach tens of meters or even hundreds of meters, and map mapping error, map simplification error can also reach ten to dozens of meters. Under various error conditions, it is very unstable to do strategy matching only by judging geometric features such as distance and direction.
For a good map matching algorithm, in order to determine the matching road stably and accurately, it is necessary to make comprehensive use of various input data of location source and map, do fusion calculation, and process various special scenes according to the characteristics of car driving. For multi-source information fusion, hidden Markov model (HMM) is a common and effective method, so we use HMM as the core of matching algorithm, supplemented by scene strategy algorithm, to achieve map matching.
In the HMM map matching algorithm, the matching path is unknown as the hidden variable Zn. The GPS positioning information observed at each moment is the observation variable Xn. The objective of map matching is to estimate the matched road with known location information:
The core of establishing map matching model under HMM framework is to determine emission probability model and transition probability model. Emission probability model is determined according to location and direction.
1) For the positioning position, the closer the distance is to the road, the greater the probability is; otherwise, the smaller the probability is. It is also considered that the selection of matching road is sensitive to transverse distance error and insensitive to longitudinal distance error. Normal distribution was used to establish the model.
2) For the positioning direction, the closer it is to the road direction, the greater the probability is; otherwise, the smaller the probability is. And the probability is related to the speed, and the higher the speed, the more credible it is. The model was established by using Von Mises distribution and velocity as hyperparameter.
The transition probability model is established according to the constraints of road distance and road Angle on vehicle driving.
The greater the Angle at which the road turns, the lower the probability of high speed. The model was established by using Von Mises distribution and velocity as hyperparameter. The travel distance is calculated according to the speed and time difference. The closer the distance is to the path, the greater the probability is. Exponential distribution was used to establish the model.
The algorithm mentioned above has been implemented on amap mobile APP, providing accurate positioning and matching results for driving navigation, and used for navigation guidance and broadcasting. Compared with the original map matching method using strategy, HMM algorithm has significantly improved the matching accuracy and stability.
3. Vehicle and machine navigation and positioning
3.1. Vehicle-machine positioning scheme
For vehicle-vehicle navigation, how to make full use of vehicle sensors and bus information and optimize the experience of various complex scenes in driving navigation is the core problem to be solved. Among them, complex scenes include: tunnel, underground parking lot location failure, urban canyon area location drift, etc.
The key to solve the problem is multi-sensor fusion technology. For example, when GPS drifts or fails, the navigation dead reckoning technology integrating speed pulse and INERTIAL navigation can be used for continuous positioning, but the navigation dead reckoning will produce cumulative errors, which need to be corrected by feedback from map data. At the same time, map data and GPS can calibrate the navigation parameters and improve the accuracy of navigation dead reckoning.
In actual vehicle-vehicle navigation projects, different sensor configurations will lead to different positioning schemes, as shown in the following table.
3.2. Sensor fusion technology
For example, the sensor fusion algorithm framework is as follows.
The fusion algorithm has two purposes: first, the navigation information of different technologies is fused into a unique navigation information, so that its reliability is higher than before the fusion; Second, the device error is estimated (gyroscope zero deviation, velocimeter scale error, etc.).
The fusion algorithm is based on Kalman filter, and the key lies in model building and model parameter setting. Kalman filter model is composed of state transition equation and observation equation. The state transition equation represents the transition relation between adjacent navigation states, which is realized by constructing navigation error differential equation. Model parameters refer to state transition noise and observation noise, and the setting of observation noise is related to GPS quality assessment module. After Kalman filtering, the optimal estimation of navigation error is obtained.
The sensor fusion technology with complete information fusion can achieve or even exceed the positioning effect of high-cost professional INERTIAL navigation equipment under the condition of using low-cost sensors.
The following figure shows the vehicle-vehicle navigation and positioning effect of the back-end fusion scheme. In the figure, the blue is the GPS position, the red is the positioning track of the high-precision reference equipment, and the green is the vehicle-machine navigation and positioning track. It can be seen that in the parking lot where GPS is blocked or in the area where GPS is interfered, vehicle-vehicle navigation and positioning can continuously and stably output high-precision positioning position, ensuring the reliable operation of vehicle-vehicle navigation function.
4. High-precision positioning evolution
Traditional navigation and positioning only need to solve the problem of road level positioning, positioning accuracy is not high. However, with the emergence of more and more application scenarios such as assisted driving and automatic driving, the requirements for positioning accuracy are also increasing, as shown in the figure below.
For lane-level navigation, positioning needs to be able to distinguish the lane where the car is currently located, which requires positioning accuracy of meters or even sub-meters. For more advanced intelligent driving applications, positioning accuracy of centimeters is required to ensure safety.
In order to achieve higher precision positioning capability, it is necessary to upgrade the existing positioning means. One upgrade method is to directly upgrade the existing positioning input sources, such as general GPS upgrade to higher precision RTK-GPS, low-cost MEMS inertial navigation upgrade to high precision inertial navigation. In this way, the high precision positioning ability can be directly obtained without changing the original algorithm framework. However, the disadvantage is that the defects of the original algorithm, such as the cumulative error of the long time GPS loss scenario, still exist, and the cost is high. Another method is to introduce new location sources, such as lidar, millimeter-wave radar, camera and so on. It is necessary to develop new fusion localization algorithms for these new sensors. The following table compares different high-precision positioning schemes.
Among the relative positioning schemes based on environmental feature matching, lidar scheme is relatively mature and reliable, and it is also the most widely used positioning scheme in the early prototype stage of autonomous driving. However, the cost and reliability of lidar still pose risks to mass production. The vision-based relative positioning scheme has lower cost and benefits from the rapid development of visual algorithms and computing chips in recent years. It has gradually become the mainstream positioning scheme in the current mass production of autonomous driving. Based on autonavi’s own image and positioning capacity building, the business practice of high-precision positioning will be carried out in three business directions.
1) System-level positioning for L3 automatic driving: Based on external input visual semantic information (such as the shape and type of lane lines sent by Mobileye, etc.), it is matched with HD Map data, combined with other location sources such as GPS/RTK and IMU, real-time lane-level high-precision location results are calculated, and the high-precision data transmission engine (EHP) is driven to send high-precision data. Provide location and data services for autonomous driving functions.
2) Lane-level navigation and positioning: based on the self-developed visual algorithm and cloud image positioning capability, the lane-level positioning capability with full coverage can be realized, driving the upgrade of traditional road-level navigation to lane-level navigation.
3) Integrated soft and hard precision positioning for high-precision data crowdsourcing: Based on self-developed low-cost vision +RTK+IMU hardware, high-precision absolute positioning based on vSlam technology is realized, which provides support for high-precision data collection, reconstruction and rapid update and iteration.
summary
Traditional navigation and positioning is based on GPS positioning with 10m accuracy. Sensor fusion algorithm, behavior judgment algorithm and map matching algorithm are designed for different ends of mobile phone/vehicle, considering their unique motion characteristics and input signal configuration, and finally meet the accuracy requirements of navigation for the road level positioning of the whole scene. In the future, for semi-automatic and fully automatic driving applications, positioning accuracy is required to evolve to lane-level or even centimeter-level, which requires sensor and algorithm iteration on the basis of considering the actual landing scene, which is an important direction of positioning technology evolution in the next stage.
