Algorithm for Predicting the Trajectory of Road Users to Automate Control of an Autonomous Vehicle* [0000-0003-4570-4442] [0000-0003-0702-3662] Andrey Azarchenkov , Maxim Lyubimov Bryansk State Technical University, Bryansk, Russia azarchenkovaa@gmail.com, max32@inbox.ru Abstract. One of the problems faced by developers of artificial intelligence al- gorithms when creating car control systems is that the actions of other road users are difficult to predict and have a large variability. Even if we assume that all actions comply with traffic rules and participants do not make mistakes, that is, to bring the actual environment closer to the ideal, the task of automating vehicle control still contains many difficulties. This paper describes what difficulties ex- ist in the field of predicting the trajectory of objects, shows concepts that will help in solving this problem, and also describes a particular method of forecast- ing, which allows you to make a forecast for cars moving along traffic lanes. The main forecasting stages and the results of testing the method collected by using a ready-made data set are given. The results presented in the form of a set of met- rics, are compared with another algorithm for predicting trajectories. As a result, the advantages and disadvantages of the created solution were identified. Keywords: Trajectory Prediction, Autonomous Driving Car, Regression Model, NuScenes Dataset 1 Introduction Driving a car is a complex process that requires drivers to understand the situation and control many dynamic processes in real time, as well as making decisions to react to these processes in seconds. Unfortunately, we can say that not all people cope with this task, which is confirmed by negative statistics. In 2019, 164,318 accidents were com- mitted on the territory of Russia, in which 16,981 people were killed [1]. Despite all the measures taken to minimize the number of accidents, there is no decreasing trend in these indicators. In addition, human errors are the cause of up to 94% of accidents [2]. Based on this fact, it can be assumed that eliminating the unreliable human factor could potentially save thousands of lives. Recent advances in artificial intelligence and high-performance computing allow to develop in this direction. Creating a fully autonomous car requires solving many of the problems faced by a Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) 2 A. Azarchenkov, M. Lyubimov person driving a car. One of these tasks is to assess the trajectory of other road users. If we consider the solution of this problem as a separate subsystem, different types of information can be fed to its input. In the simplest case, this is different information about the physical properties of the object, such as speed, acceleration, orientation, and others [3]. The methods that use this information are the simplest to implementing, but they can't be said to have high accuracy. The most popular group of methods for predicting the trajectory of movement, in terms of the number of scientific papers, is based on the use of the trajectory of move- ment from the past. In most cases, this problem is solved using neural networks. This is because they are good at identifying patterns, in this case patterns from the trajectory of movement. In addition, a popular solution for this method is to use recurrent layers [4], especially such recurrent layers as LSTM [5], [6], [7], [8]. There is also a large number of publicly available data sets containing motion paths that can be used for neural network training [9], [10]. The disadvantage of these methods is that they consider the trajectory of a single object, without taking into account others. The solution to this problem is to use the input representation [11] (Fig 1). The principles of generating such an image may differ, but the general points are the presence of layers with objects, as well as the presence of roads in the image [12], [13], [14]. Fig. 1. An example of input representation A number of methods based on using images from the camera should be singled out separately. The idea is that the object is detected in the image, then the neural network predicts its position on the same frame. Most often, recurrent layers are also used for this purpose. [15], [16], [17]. Then, having the calibration parameters of the camera, we can understand the position of the object in space [18]. Algorithm for Predicting the Trajectory of Road Users to Automate Control 3 In addition, it is important to separate the task of trajectory planning for an autono- mous driving car and predicting traffic paths for other objects. Although the input and output data for this problem are similar, the methods for solving it are different. The subsystem based on input data returns the expected position of an object or objects. The position can be specified exactly, or it can be a sequence of points or a motion vector. As part of the task, it is planned to determine the sequence of points. The selected time for making the forecast is 6 seconds. nuScenes set was chosen as the data set for testing the developed method [19]. A special feature of this set is the amount of information marked up. In addition to the classic object detection and segmentation tasks, the data set provides physical charac- teristics of each object, its exact position in space, and tracking. Special attention is paid to information storage. To work with a data set, a library provided by developers is used that not only provides access to objects, but also allows to filter them by various criteria. The data set is divided into 1000 scenes, each lasting 20 seconds. The vehicle collecting data was equipped with an omnidirectional lidar, cameras, radars, GPS and IMU sensors. In total, the set contains 1,400,000 images, and 390,000 lidar images. It is important to have marked maps for all the sections where data were collected. This allows to define the traffic lane for each object that it moves along. 2 Approach to predict the trajectory 2.1 Description of prediction method After analyzing existing scientific papers, as well as industrial solutions in the field of trajectory forecasting, several concepts were identified that can improve the results of the work: • Application of algorithms depending on the class of the object. Since the tra- jectory is predicted for objects that have different behavior and the class is known in advance, it is possible to predict the trajectory of their movement in different ways. • Division of algorithms depending on the position of the object. Objects of the same class may have different behaviors depending on their location. • Use of maps prepared in advance. The main task for which using the module under development is needed is related to predicting the trajectory of the car along the traffic lanes. Information about the position of roads can be consid- ered static, since changes to existing roads are rare. At the same time, while driving on the road, the absolute majority of cars move along the lane. This applies to both straight sections and turns of the road. In this regard, infor- mation about the position of lanes can be used to predict the trajectory of traf- fic in cases where the orientation of the car differs slightly from the direction of the road. To do this, the current position of the car is projected to the middle of the lane, and from this position an angular coordinate is defined, equal to the distance that the car will travel according to the forecast. The resulting road section is shifted to the current position of the car, and an adjustment is made for its orientation. 4 A. Azarchenkov, M. Lyubimov • Building a regression model for speed prediction. To implement the previous idea, we need to know the position of the road lane in space and the predicted distance of car movement. Since it is planned to use a static time interval when predicting the trajectory, the distance traveled can be determined by knowing the speed and acceleration of the object. However, for a long period of time, the acceleration that we know before making the forecast cannot be considered constant for the entire forecast section. In addition, drivers often adjust the speed of the vehicle using similar models. In this regard, to increase the accu- racy, it was decided to use the predicted final speed, which can be obtained using a regression model. To train the model, it was decided to use the initial speed and acceleration of the object, as well as changing the orientation of the object, in comparison with the state from the past. • Calculating the probabilities of predicted trajectories. Firstly, we can use prob- abilities to make a decision about using trajectories. Secondly, using a single algorithm, we can get a number of trajectories that also need to be compared. Finally, the obtained probabilities can be used with subsequent modules or the prediction module itself for further calculation. • Using recurrent layers to predict the trajectory if there is no map. Based on the analysis of existing approaches, we can conclude that recurrent layers are used in most neural networks that perform trajectory prediction. 2.2. Trajectory prediction using maps prepared Initially, the prediction task was implemented for cars that move along traffic lanes. Within the task, a trajectory forecast is made for 6 seconds, with a frequency of 2 Hertz. Accordingly, the resulting trajectory includes 12 points. The algorithm consists of the following steps: • receiving data; • search for lanes; • calculation of the final speed; • calculation of angular coordinates for each suitable lane; • calculation of trajectory points. Figure 1 shows examples of the obtained trajectories. Here and further the following rules will be applied when making up drawings: the blue trajectory represents the real trajectory of the object, while the red one is predicted using the algorithm being devel- oped. The green one is predicted using a third-party algorithm where the latter is pre- sent. When implementing the algorithm, the following complications were identified: • Within the selected data set the current lane ends at the moment when there is an alternative path. This raises the problem of choosing a new lane. This prob- lem was solved by constructing a function between the angle of orientation change and the speed. This angle was calculated as the difference between the current orientation and the direction of the alternate lane. This method is ef- fective when the choice is limited to two options, for example, moving straight and turning. However, there is a high probability of error in lanes where mul- tiple turns are possible. In real life, this task is also difficult and is solved by determining the speed of the car by the driver, as well as using turn signals, Algorithm for Predicting the Trajectory of Road Users to Automate Control 5 which is a more effective way. In this regard, in situations where multiple choices are possible, it was decided to consider both trajectories. First, these trajectories have a partial intersection as a part of the current lane, and second, in the case when the turn signal is not visible, the driver in reality also allows both versions of trajectories. However, it should be noted that we are talking about situations when the car is moving along the lane, and is not making a lane change. • In areas where there is a large number of lanes, the starting lane selection may not be correct, due to the car being too far off-center. It was decided to calcu- late paths using several lanes within a given radius, with the probability of each of them inversely proportional to the distance from the object to the lane center. Fig. 2. An example of trajectory prediction 2.3 Prediction of the final speed of objects The training part of the dataset was used to train the regression model, but since nuScenes test dataset contains many objects, including inanimate objects which loca- tion and physical parameters are also different, a number of filters were applied to the entire training sample: • filtering by class, only transport was used; • speed filtering, many objects have zero speed; • filtering by tracking time. For training, the object speed was used after 6 sec- onds, relative to the prediction; • filtering by acceleration and direction of the object. As a result, 65,000 training objects were obtained. 90% percent for training, 10% for accuracy testing. Several regression models with the selected parameters were tested (Table 1). The speed of the models was also taken into account, but all the models under consideration showed acceptable results at the specified parameter values, so the speed comparison was not performed. The standard error between the predicted speed value and the correct one (1) was used to estimate accuracy. This metric allows to evaluate errors with different signs, in addition, its feature is that large errors are taken into ac- count to a greater extent, due to using the square of difference in values. 6 A. Azarchenkov, M. Lyubimov 1 𝑀𝑆𝐸 = ∑𝑛𝑖=1(𝑋𝑖 − 𝑋̌𝑖 )2 (1) 𝑛 Table 1. Prediction of final speed by various methods Root mean square er- Regression model ror Linear regression 9.246 The method of minimum angles 9.246 The method of orthogonal matching pursuit 9.398 Bayesian linear regression 9.246 Lasso regression method 9.245 RANSAC method 10.404 Theil–Sen estimator 9.899 Huber loss 9.276 Multilayer perceptron 8.2885 k-nearest neighbors algorithm 8.937 Support vector machine 8.368 Elastic map 9.367 Random forests 7.860 Neural network of 10 linear layers and ReLU. 8.26 Having the results obtained, it was decided to use the method of random forests. The resulting model was used to predict the final speed of the object. 2.4 Evaluation of trajectory prediction As part of the work, the accuracy of the object trajectory prediction algorithm de- scribed earlier is estimated. The current position of the object is input into the subsys- tem, as well as its speed, acceleration, and direction of movement. The subsystem re- turns a future trajectory consisting of 12 points. The following metrics were used to evaluate the accuracy: • average displacement error (ADE) is the average distance between two sepa- rate points of the trajectory in meters; • final displacement error (FDE) is the distance between two endpoints in me- ters; • minimum displacement error (MDE) is the minimum distance between the endpoint and the path in meters. To calculate this metric, we used 8 trajectory points instead of 12. This was done in order to reduce the impact of the trajec- tory length on the metric results, in cases where the predicted trajectory is longer. The first two metrics are classical for the problem under consideration, but they do not have very accurate results, since they strongly depend on the correct definition of the trajectory length. To compare the results, we used one of the standard algorithms for this problem, which means generation of trajectory points depending on the current speed and orientation Algorithm for Predicting the Trajectory of Road Users to Automate Control 7 of the object. The algorithm returns an exceptionally straight trajectory. This method was considered as a basic one. In addition, to demonstrate the advantages of the regression model and show the rela- tionship between metrics and the trajectory length, the results for the algorithm under development were considered, by replacing the regression model with the constant speed, as well as changing the speed based on the initial acceleration. In accordance with the Euler method, integration was performed, that is, half of the object's accelera- tion was added to the initial speed, since the time between two steps is 0.5 seconds. This operation was carried out for two and for 12 steps. As a result, the following indi- cators were obtained for 7,600 objects (Table 2). Table 2. Comparison of metrics for the full test set Basic Constant 2 integration 12 integration Regression method speed steps steps model ADE 4.52 4.1449 4.1169 4.089 4.0695 FDE 10.787 9.7575 9.701 9.620 9.5575 MDE 3.613 2.8455 2.841 2.832 2.848 Analyzing the examples, we can conclude that the main reason that negatively affects the accuracy is errors in predicting the length of the trajectory. However, it should be noted that despite its impact on metrics, this problem is less significant in real condi- tions. In addition, it is important to note the following fact: most of the considered trajectories are straight. Often, the prediction of such trajectories is not problematic and the base method copes with this well. However, the main difficulty is represented by curved paths. Figure 3 shows examples of such paths. Most of the methods of trajectory prediction aim at curved trajectories. At the same time, due to different number of cases of linear motion, the effect of the developed algorithm, in terms of predicting a curved trajectory, is lost in comparison with the basic one. Therefore, it was decided to calcu- late the metrics considered earlier not on all available objects, but on objects which orientation change is greater than 0.1 radian, that is, the angle of rotation of the object changed by 0.1 radian between the current position and the previous one in the training sample. According to the results of this filtering, 1,772 objects were obtained. Table 3 shows the results. It can be seen that the difference between the two methods has in- creased significantly. Table 3. Comparison of metrics for the full test set with curved trajectory Basic Constant 2 integration 12 integration Regression method speed steps steps model ADE 5.221 4.2217 4.2038 4.1816 4.1369 FDE 12.3774 9.7505 9.7122 9.6467 9.5215 MDE 4.6327 2.8947 2.9 2.8961 2.8162 8 A. Azarchenkov, M. Lyubimov Fig. 3. Curved trajectory samples 3 Conclusion At this stage, the feasibility of the concept was tested by predicting the trajectory of cars based on the use of maps prepared in advance. Analyzing the results of the algo- rithm on the selected data set, we can conclude that this method allows to predict the direction of the car movement with high accuracy. First of all, the predicted trajectory length has a negative impact on metrics. However, in real-world problems, the accuracy of the trajectory length is less important. The resulting algorithm can be used to predict car trajectories in unmanned control systems. In such systems, it is necessary to implement this task, since it is not enough for an unmanned vehicle to simply detect an object in order to perform maneuvers. Without information about further movement of the object, it is impossible to move, because the danger of a particular maneuver is not clear. In the future, it is planned to implement a trajectory prediction method for cars that make changes or move off the road, as well as for other objects, such as pedestrians and two-wheeled transport. The implemented set of algorithms will be tested on nuScenes dataset. References 1. Road safety indicators, http://stat.gibdd.ru/, last accesses 19/07/2020. 2. Singh, S. Critical reasons for crashes investigated in the national motor vehicle crash causation survey. Technical Report DOT HS 812 115, National Highway Traffic Safety Administration (2015). 3. Scholler, C., Aravantinos, V., Lay, F., Knoll, A. What the Constant Velocity Model Can Teach Us About Pedestrian Motion Prediction. arXiv:1903.07933v3 (2020). 4. Wenjing, Z., Yuan, L., Tingting, L., Chenyang, Y. Trajectory Prediction with Re- current Neural Networks for Predictive Resource Allocation. 14th IEEE Interna- tional Conference on Signal Processing (ICSP) pp. 1-8. (2018). 5. Alahi, A. Goel, K., Ramanathan, V., Robicquet, A., Fei-Fei, L., Savares, S. Social Algorithm for Predicting the Trajectory of Road Users to Automate Control 9 LSTM: Human Trajectory Prediction in Crowded Spaces IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2-6. (2016). 6. The Autoware Foundatiion, https://www.autoware.org/, last accessed 19/06/2020. 7. Vemula, A., Muelling, K., Oh, J. Social Attention: Modeling Attention in Human Crowds arXiv:1710.04689v2 (2018). 8. Deo N., Trivedi, M. Convolutional Social Pooling for Vehicle Trajectory Predic- tion arXiv:1805.06771v1, 2018. – 9 p. 9. US Highway 101 Dataset, https://www.fhwa.dot.gov/publications/research/oper- ations/07030/index.cfm, last accesses 19/07/2020. 10. Interstate 80 Freeway Dataset. https://www.fhwa.dot.gov/publications/re- search/operations/06137/, last accesses 19/07/2020. 11. Djuric, N., Radosavljevic, V., Cui, H., Nguyen, T., Chou, F. C., Lin, T. H., Nitin, S., Schneider, J.: Uncertainty-aware Short-term Motion Prediction of Traffic Ac- tors for Autonomous Driving. CoRR abs/1808.05819, https://arxiv.org/abs/1808.05819 (2020). 12. Cui, H. Radosavljevic, V., Chou, F., Lin, T., Nguyen, T., Huang, T., Schneider J., Djuric, N. Multimodal Trajectory Predictions for Autonomous Driving using Deep Convolutional Networks 2019 International Conference on Robotics and Automation (ICRA), pp. 1-5 (2019). 13. Grigore, E., Boulton, F., Beijbom, O., Wolff, E. CoverNet: Multimodal Behavior Prediction using Trajectory arXiv:1911.10298v1 (2019). 14. GTC 2020: PredictionNet: Predicting the Future in Multi-Agent Environments for Autonomous Vehicle Applications, https://devel- oper.nvidia.com/gtc/2020/video/s21899-vid, last accessed 06/20. 15. Ma, Y., Zhu, X., Zhang, S., Yang, R., Wang, W., Manocha, D. TrafficPredict: Trajectory Prediction for Heterogeneous Traffic. arXiv:1811.02146v5 (2019). 16. Rasouli, A., Kotseruba, I., Kunic, T., Tsotso, K. PIE: A Large-Scale Dataset and Models for Pedestrian Intention Estimation andTrajectory Prediction. IEEE/CVF International Conference on Computer Vision (ICCV), p. 10 (2019). 17. Yau, Y., Xuo, M., Choi, C., Crandall, D. J., Atkins, E. M., Dariush, B. Egocentric Vision-based Future Vehicle Localization for Intelligent Driving Assistance Sys- tems. arXiv:1809.07408v2 (2019). 18. Siswantoro, J., Prabuwono, A., Abdullah, A. Real World Coordinate from Image Coordinate Using Single Calibrated Camera Based on Analytic Geometry. Inter- national Multi-Conference on Artificial Intelligence Technology, pp. 1-11 (2013). 19. Nuscenes dataset, https://www.nuscenes.org, last accesed 19/06/20.