Application Research of an Intelligent Detection Algorithm for Vehicle Trajectory Route Deviation ()
1. Introduction
The increasing availability of vehicle trajectory data is the core of vehicle networking solutions [1] [2] . These data provide unprecedented information for the development of applications based on trajectory data mining [3] [4] . An important task of trajectory analysis is to use efficient and accurate methods to compare trajectories.
Vehicle trajectory route deviation detection is often used to assist drivers in driving, and most of them use mobile terminal navigation software to complete vehicle route planning [5] [6] . However, in the case that some managers need to monitor the driving route of the vehicle in real-time, this method cannot achieve the desired effect [7] [8] . At present, there are some driving route deviation detection under monitoring scenarios [9] [10] . The specific method is to extract the starting point, end point, and inflection point from the historical driving track of a vehicle as the key position, and then match the similarity with the planned route. Most of these methods are analyzed offline afterward [11] [12] [13] [14] , and it is difficult to achieve the purpose of real-time monitoring.
Through the analysis and comparison of two different real-time trajectory deviation detection methods, this paper finally proposed a trajectory deviation detection method, which can achieve the purpose of real-time monitoring of vehicles based on big data related technology.
2. System Design
2.1. System Architecture Diagram
The architecture design of the system is shown in the Figure 1. The manager plans the route of the vehicle to be driven in advance through the page, and the route planning can be completed through the commonly used Baidu API, or it can be completed in a custom way.
In Figure 1, the external module interface is provided to store the route defined by the manager and query the final route deviation warning results; The planned routes stored in the relational database are synchronized to the dimension table for real-time big data analysis in HBase by data synchronization.
The real-time analysis and processing module in Figure 1, specifically storm stream processing analysis code will read real-time location data reported by the vehicle from the message queue in real time, and combined with the route rules in the HBase dimension table, determine whether the vehicle currently deviates from the planned route, and send the corresponding warning result to the message queue. The message queue here is used for decoupling the result data. To prevent too much and too fast result data, affecting downstream applications.
2.2. Route Planning
Route planning can be achieved through the manager’s custom and Baidu API interface two ways.
In the customized mode of the manager, users operate on the map, record the characteristic inflection points of the planned path from A to M (such as A, B, C, D, etc.), and then call the system interface to complete the storage of the planned route information, as shown in Figure 2.
All the fix points in the planned path can be obtained through Baidu API interface, as shown in Figure 3, but there are too many track points of the entire route. In order to reduce the storage of the entire data and the consumption of computing resources, route extraction is required. For N path points on the same line, only the path points of the first and last two endpoints need to be obtained. Then each characteristic inflection point is obtained to complete the route planning Settings.
2.3. Monitoring Period
The monitoring cycle of the whole route planning is the period from the driver’s click to execute the start task to the driver’s click to end the task, and the rest period is not required for monitoring.
2.4. Algorithm Analysis
2.4.1. Fence Discrimination Algorithm
The planned path AB can be regarded as the sum of AC, CD, and DB paths. Both AC and CD segments are straight lines, as shown in Figure 4.
The curve path of DB segment can be approximately decomposed into multiple straight-line segment paths, as shown in Figure 5. Therefore, the problem of curve route deviation can be approximately regarded as the problem of vehicle offset straight-line driving path.
Take the AC segment route for analysis, the longitude and latitude coordinates of the AC segment are known (LngA, LatA, LngC, LatC), and the road width is assumed to be 5 meters, then the problem is converted to determine whether the current location point of the vehicle is in the AC, CD, DE… If the problem is in multiple rectangular areas of the center line (similar to MNPQ, as shown in Figure 6), it is judged that the vehicle deviates from the specified route if the vehicle appears to have an area phenomenon.
The advantages of this algorithm are simple and fast to realize deviation judgment, but there are three disadvantages. Firstly, for each anchor point, N fence areas need to be judged, and the time consumption increases. Secondly, the line segment AB needs to be converted into a rectangle of 4 points for storage, which requires more storage space. Finally, there is no order for the path.
![]()
Figure 4. Route planning for section AB.
![]()
Figure 5. Route decomposition of DB segment.
![]()
Figure 6. Fence discrimination algorithm.
2.4.2. Segmentation Analysis Algorithm
In order to solve the three shortcomings of the fence discrimination algorithm, we re-consider the adoption of segmented analysis algorithm, each time only for the vehicle’s current driving path segment, when the vehicle enters the end of the road section, the analysis section will be updated, so repeated until all calculations are completed. The specific analysis process is shown in Figure 7.
For each route segment in the entire planned route, the specific analysis process is as follows.
Assume that A planned path is A → B → C, where point B is the intersection, and there are two branching roads BD and BE at point B, as shown in Figure 8. The normal driving route is P0 → P1 → P2 → P3 → P4;
Points P0, P2 and P4 are located in A circle with three points A, B and C as the center radius and the road width respectively. According to the flow chart, they are located near the feature points of the path, that is, the path is determined to be unchanged.
For the driving section from P0 to P2, there are two cases of P1 and P5 in the extracted analysis path AB. Since the distance from P5 to AB is greater than the road width, it is judged as path deviation; while the distance from P1 to AB is less than the road width, it is judged as path no deviation.
![]()
Figure 7. Flow chart of the segmented analysis.
When the vehicle tracks near point B, the current analyzed path is updated from section AB to section BC. For the driving section from point P2 to point P4, there are three cases: P3, P6 and P7. The analysis of P3 and P7 points is the same as that of P1 and P5 points described above. For P6, when the vehicle exceeds the range near point B, it can be seen from the obtuse Angle of P6BC that the vehicle does not advance in the prescribed BC direction, but in the opposite direction, so it is judged as path deviation.
In addition, in the real scenario, due to the excessive speed of the vehicle, the obtained fixed points are sparse. When the vehicle is driving along the ABC path, it does not appear near the B point, resulting in the failure to update the analysis path when the vehicle has driven from segment AB to segment BC, resulting in misjudgment. Therefore, three segment paths will be judged continuously. When the three consecutive paths are considered to be deviations, it is determined that the vehicle has a path deviation.
3. Experimental Verification
The segmentation analysis algorithm is verified by experiments on real vehicle trajectories.
3.1. Experimental Preparation
Firstly, route planning was carried out for the experimental vehicle. A total of 12 route sections from A to L were planned, and the road width was set at 5 m, as shown in Figure 9.
The latitude and longitude information of each segment is shown in Table 1, and the latitude and longitude coordinates are reserved for 4 decimal places.
3.2. Experimental Results
The actual driving path of the vehicle is shown in Figure 10.
![]()
Table 1. Path segmentation information table.
The vehicle trajectory is analyzed in real time through the whole system, and the vehicle deviation alarm results stored in the relational database are shown in Table 2.
The starting and ending positions of the first warning are shown in Figure 11.
The reason for this alarm is that the difference between the starting point of path planning and the starting point of vehicle start-up is more than 5 m of the set road width. When the vehicle travels near the starting point of the path planning, the warning ends. The starting point of path planning is shown in Figure 12.
![]()
(a) ![]()
(b)
Figure 11. First warning. (a) Starting point; (b) End point.
![]()
Table 2. Vehicle trajectory deviation warning results table.
The starting and ending positions of the second alert generation are shown in Figure 13.
The starting position of the alarm is located at the starting point of the planned route F, and the end position of the alarm is located at the starting point of the planned route L. Because the vehicle fails to follow the planned route E → F → G → H → I → J → K → L, but travels from route E to route L (E → L), this alarm is consistent with the actual situation.
3.3. Algorithm Comparison
In view of this experiment, we analyze and compare the fence discrimination algorithm and the segmentation analysis algorithm from two aspects of resource storage consumption and execution time.
In terms of resource storage consumption, the longitude and latitude coordinates of feature points in the planned path are stored using Float type, Float occupies 4 bytes, and a group of latitude and longitude occupies 8 bytes. The segmentation analysis algorithm only needs to store each feature point, and the fence discrimination algorithm needs to convert every 2 feature points into 4 fence coordinates for storage.
In terms of execution time, for each route segment in the planned path, the segmented analysis algorithm needs to perform circular region judgment at least once, and secondary circular region judgment and distance judgment at most. Assuming that all judgment times are m, the analysis execution time of each route segment is m ≤ t ≤ 3m. The fence discrimination algorithm makes N fence judgments for each route segment, that is,
,
where N represents the number of route segments.
The storage and execution time of the algorithm in this experiment are shown in Table 3.
![]()
(a) ![]()
(b)
Figure 13. Second warning. (a) Starting point; (b) End point.
![]()
Table 3. Comparison of algorithm storage usage and execution time.
Through the theoretical analysis and the comparison of the actual results, it can be seen that the segmentation analysis algorithm is better than the fence discrimination algorithm. At the same time, with the increase of the planned path segment, the difference in storage occupancy and execution time will become more obvious.
4. Conclusion
In some vehicle business application systems, there has been a lack of effective methods for real-time monitoring of drivers’ traffic paths [15] [16] . Based on this, this paper proposes a vehicle trajectory route deviation detection method. The experimental results show that, after the manager’s path planning is completed, the corresponding path feature points are extracted, and the path deviation analysis method is combined with the real-time analysis technology of big data. It can realize the real-time early warning function of vehicle path deviation and achieve the management goal of driver behavior norms.