University of Economics, Prague
Faculty of Informatics and Statistics
L
ONG-
TERM PREDICTION OF SURROUNDING AGENTS’
MOTION IN AN URBAN ENVIRONMENT FOR SELF-
DRIVING VEHICLESMASTER´S THESIS
Study programme: Applied Informatics (ISM) Field of study: Information Systems Management
Author: Bc. Bohdan Biesiedin Supervisor: Ing. Martin Potančok, Ph.D.
Prague, December 2020
Declaration
I hereby declare that I am the sole author of the thesis entitled “Long-term prediction of surrounding agents’ motion in an urban environment for self-driving vehicles “. I duly identified all citations. The used literature and sources are stated in the attached list of references.
Prague (Date)... Signature
Bohdan Biesiedin
Acknowledgement
I hereby wish to express my appreciation and gratitude to the supervisor of my thesis, Ing. Martin Potančok, Ph.D. for guiding when I had questions about the research, and for being open and encouraging when accepting the thesis topic.
I also want to thank Mgr. Veronika Brunerová , for always being responsive and for help with any questions.
Thanks to everyone who responded to my requests for an interview to advance my research.
And, of course, I have to thank all my family members for helping me to make all my goals come true.
Abstract
In the scope of this research, an investigation of the area of self-driving vehicles was done. As a result of the investigation a model which implements long-term prediction of surrounding agents motion in urban environment for self-driving vehicle was implemented. The proposed model is capable of capturing and recognizing the surrounding agents, tracking their motion, memorizing the history of their motion and making prediction about the future movements and maneuvers. The output of the proposed model is a set of trajectories for each of the surrounding vehicles.
At the beginning of the research, an investigation of the history and current state of the field was conducted. In the scope of the investigation, appropriate papers, books and articles were studied. Furthermore, a number of experts in the field of autonomous vehicles and movement prediction were consulted to gain more insight into the current state of the art and approaches in this field.
The results of the first part of research were used in order to design and construct a model which fulfils the main aim of the work.
In order to have a clear view on what should be done and how the final solution should look like at the result of the design process, a set of system and functional requirements were proposed and further realized in the design process.
The main components of the model were developed and described in the practical part of the work. Flowcharts were used in order to depict algorithms of main components of the model.
In conclusion, developed model is performing well for the tested time ranges and bypasses the system created on the basis of the state of art model in predicting the trajectories of agents. It can be used as it is in the result of the work or modified for a particular use case and integrated into a control system.
Keywords
Self-Driving Cars, Autonomous Driving, Neural Networks, Prediction, Autonomy, GPS, LIDAR, RADAR, AI, Trajectory, Machine Learning, Agents, Urban Environment, Localization, Algorithm, Model, Motion Prediction
JEL Classification
R0
Content
1. Introduction ... 12
1.1 History of Self-Driving Technology ... 12
1.1.1 Everything has a beginning ... 12
1.1.2 First developments in remote control ... 12
1.1.3 First developments in detection of surroundings on the streets ... 13
1.1.4 Introduction of Neural Networks in Self-Driving Vehicles ... 14
1.1.5 Recent Developments ... 14
1.1.6 Modern state ... 15
1.2 Topic Definition ... 16
1.2.1 Self-Driving Technology ... 16
1.2.2 Levels of autonomy ... 19
1.2.3 Benefits ... 20
1.2.4 Ego-vehicle ... 21
1.2.5 Surrounding agents ... 21
1.2.6 Prediction of surrounding agents motion ... 22
1.2.7 Urban environment ... 25
1.2.8 Prediction of surrounding agents’ motion in urban environment ... 25
1.2.9 Long-term prediction ... 26
1.3 Research objectives and aim ... 27
1.3.1 Problem statement ... 27
1.3.2 Aim ... 29
1.3.3 Objectives ... 29
1.3.4 Prerequisites and Limitations ... 30
1.4 Thesis Structure ... 31
1.5 Method of Approach ... 32
1.5.1 Conducted Interviews ... 33
1.5.2 Conducted interviews conclusion ... 36
1.6 Outputs and Expected Benefits ... 37
2 Literature review and current approaches ... 38
2.1 Description ... 38
2.2 Analyze approaches in long-term agents motion prediction ... 40
2.2.1 Long-term Vehicle Motion Prediction (Hermes et al., 2009) ... 40
2.2.2 A survey on motion prediction and risk assessment for intelligent vehicles (Lefèvre,
Vasquez and Laugier, 2014) ... 41
2.2.3 How would surround vehicles move? A Unified Framework for Maneuver Classification and Motion Prediction (Deo, Rangesh and Trivedi, 2018) ... 42
2.2.4 Probabilistic Prediction from Planning Perspective: Problem Formulation, Representation Simplification and Evaluation Metric (Zhan et al., 2018) ... 43
2.2.5 Multi-Modal Trajectory Prediction of Surrounding Vehicles with Maneuver based LSTMs (Deo and Trivedi, 2018) ... 43
2.2.6 Multimodal Trajectory Predictions for Autonomous Driving using Deep Convolutional Networks (Cui et al., 2019) ... 44
2.3 Analyze existing approaches in long-term prediction of surrounding agents motion in urban environment ... 44
2.3.1 Vehicle Tracking and Motion Prediction in Complex Urban Scenarios (Hermes et al., 2010) ... 44
2.3.2 Interaction-Aware Probabilistic Behavior Prediction in Urban Environments (Schulz et al., 2018) ... 45
2.4 Literature review summary ... 46
3 Relevance of Research ... 48
4 Problematic of Prediction of surrounding agents motion in urban environment ... 51
5 Long-term prediction of surrounding agents motion in urban environment and its advantages .. 52
6 Development of requirements for the model ... 53
6.1 Development of requirements for the model ... 53
6.1.1 System requirements ... 54
6.1.2 Functional requirements ... 55
7 Design a model based on conducted analyses ... 61
7.1 Describe technical design decisions ... 61
7.1.1 Tools ... 61
7.1.2 Programming Language ... 61
7.1.3 Libraries ... 61
7.1.3 Environment ... 62
7.2 Define crucial components of the model ... 63
7.2.1 Sequence to sequence module ... 63
7.2.2 Encoder - Decoder ... 65
7.2.3 Behavior ... 66
7.2.4 Localization ... 67
7.2.5 Object Detection ... 68
7.2.6 Object Tracking ... 73
7.2.7 Planning ... 74
7.2.8 Prediction ... 78
8 Testing and evaluation of the proposed model ... 86
8.1 Dataset and its description ... 86
8.2 Evaluation process ... 88
8.2.1 Prerequisites ... 88
8.2.2 Evaluation process description ... 89
8.2.3 Evaluation results description ... 94
9 Propose possible ways of application of proposed model ... 97
10 Conclusion ... 99
References ... 101 Annexes ... I Annex A: Interview Questions for Machine Learning Engineer Lead ... I Annex B: Interview Questions for Autonomous Driving Researcher ... I Annex C: Interview Questions for Senior Autonomous Vehicles Researcher ... I Annex D: Interview Questions for Principal Algorithms Developer ... I
9
List of Figures
Figure 1 – A self-driving car software flow-chart ... 16
Figure 2 - Design Science Research process (Peffers et al, 2007) ... 32
Figure 3 – A conceptual diagram of the model ... 56
Figure 4 – A decomposition of the conceptual diagram that represents the main functions of the model ... 57
Figure 5 – A decomposition of the function “Prediction” ... 59
Figure 6 – Sequence to sequence module based on Encoder and Decoder algorithm ... 64
Figure 7 – Behavior module algorithm ... 66
Figure 8 – Object Detection - YOLO algorithm ... 70
Figure 9 – Sparse scene flow module ... 72
Figure 10 – Object tracking module algorithm ... 73
Figure 11 – Planning module algorithm ... 75
Figure 12 – Lattice Planner algorithm ... 77
Figure 13 – Prediction module algorithm ... 78
Figure 14 – Longest Common Subsequence algorithm ... 82
Figure 15 – Trajectory classification algorithm ... 83
Figure 16 - Sample of dataset ... 87
Figure 17 - Data Processing Flow ... 87
Figure 18 – Algorithm of evaluation process ... 90
Figure 19 - Prediction root mean square deviation for 5 second time interval comparing to a state of the art model. ... 95
10
List of tables
Table 1 – System requirements ... 54 Table 2 - Localization modules ... 68 Table 3 - Prediction root mean square deviation for 1 second time interval comparing to a state of art model ... 95 Table 4 – Prediction root mean square deviation for 3 second time interval comparing to a state of art model ... 95 Table 5 – Prediction root mean square deviation for 5 second time interval comparing to a state of art model ... 96
11
List of abbreviations
MT Master´s Thesis
FIS Faculty of Informatics and Statistics
SDV Self-Driving Vehicle
LIDAR Light Detection and Ranging
RADAR Radio Detection and Ranging
AI Artificial Intelligence
RBF Radial Basis Function
LSTM Long-Short Term Memory
IMU Inertial Measurement Unit
HMM Hidden Markov Model
YOLO You Only Look Once
LCS Longest Common Subsequence
ADAS Advanced Driver Assistance Systems
DSR Design Science Research
12
1. Introduction
1.1 History of Self-Driving Technology
1.1.1 Everything has a beginning
The industry of self-driving cars is tightly dependent on the automotive industry and the industry of autonomous systems. The self-driving cars appeared rather as a synergy of two major fields than as a completely new field of technologies.
The very first concept of self-driving vehicle appeared in 1939 at the General Motors' automated highway plans in their Futurama ride. (History of the Autonomous Car, 2017) It was designed by Norman Bel Geddes and sponsored by General Motors and was demonstrating a probable model of the future world in around 20 years.
In 1958, the same General Motors made the design suggested in 1939 a full-size prototype. (History of the Autonomous Car, 2017) All the cars had attached a range of sensors through the wires to them. (History of the Autonomous Car, 2017) The cars were regulated by means of electromagnetic fields produced by magnetized metal spikes embedded in the road (History of the Autonomous Car, 2017)
1.1.2 First developments in remote control
After the first concepts appeared, professionals understood that this kind of technology can help in solving complex problems.
In 1961, James Adams, a Stanford engineering graduate student in Stanford wondered how to control vehicle on the moon when there is a delay in 2.5 seconds. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
13
They wanted to create the first self-driving car in the real world. It had cameras, and was programmed to detect a solid white line on the ground and follow it autonomously. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
1.1.3 First developments in detection of surroundings on the streets
In 1977, a Japanese-based company called "Tsukuba Mechanical Engineering"
developed a passenger vehicle capable of detecting road markings and driving through the streets at 20 miles per hour speed. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016) It used A camera device that transmits data to a machine to process road images. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
Another significant achievement was made by a German aerospace engineer Ernst Dickmann. His work, carried out within the walls of the Mercedes-Benz, was aimed at the capabilities of self-driving vehicles at high speeds.
In order to achieve that a Mercedes van was equipped with cameras and sensors to collect data from surrounding world and fed into a software that was capable of adjusting steering wheel, brake and throttle.
He created a car equipped with cameras and 60 micro-processing modules and an algorithm called "dynamic vision," aimed at focusing only on important objects and filtering out all the noise and less significant aspect. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
The VAMORS concept was successfully tested in 1986 and officially debuted on the autobahn a year later. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
14
1.1.4 Introduction of Neural Networks in Self-Driving Vehicles
As it was stated at the very beginning of the introduction, the field of self-driving cars is a synergy of achievements in the automotive industry and autonomous systems.
The last decades of the 20th century was marked by the rapid development of technologies related to robotics and artificial intelligence.
In the beginning of 1990s, a new milestone in development of self-driving technology has been accomplished.
In Carnegie Mellon a researcher Dean Pomerleau described in his paper how neural networks allow real-time steering control by using input images of the road and surroundings. (10 Major Milestones in the History of Self-Driving Cars, 2019)
In 1995, Pomerleau and fellow researcher Todd Jochem had already put their self-driving Navlab automotive device on the track. From Pittsburgh , Pennsylvania to San Diego , California on a journey of the pair of dubs, their bare-bones, autonomous minivan where they could control braking and speed of the vehicle. (10 Major Milestones in the History of Self-Driving Cars, 2019)
1.1.5 Recent Developments
In the 21st century, the number of institutions and companies that are involved in research and development in the field of self-driving technology has grown to such an extent that it was already possible to observe a high level of competition and the proposal of alternative solutions to the problem of unmanned control.
Probably one of the most important events in self-driving history took place from 2004 till 2013.
The DARPA challenges, organized and sponsored by US "Defense Advanced Research Projects Agency". (A Brief History of Autonomous Vehicle Technology | WIRED, 2016) The main aim of DARPA challenges was the competition between a number of teams in order to demonstrate whose self-driving vehicle will pass the
15
intended route faster. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
The very first challenge's task was to pass 150 miles of desert road to the finish point. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
Challenge role was modified in 2007 and moved to urban environment. The mission was to travel 60 miles to the finish point in urban surroundings. (A Brief History of Autonomous Vehicle Technology | WIRED, 2016)
One of the recent significant achievements was in 2015 when Tesla released its new update for autopilot which enables drivers to switch driving mode to auto-piloted and completely free from driving just keeping hands on the steering wheel when its required.
1.1.6 Modern state
Nowadays, most of the vehicles which include autonomous driving features are, basically, include advanced driver assistance systems which include blind spot monitoring, intersection assistance, pedestrian protection, auto parking, cruise control, collision warning and other basic features which enable safe and confident driving.
They rely on GPS data and data coming from the sensors, such as cameras, Sonar and Radar.
Obviously its not perfect yet and in most of the cases, it cannot perform a full self-driving. However, it does not stand still.
Many of the forecasts suggest that half of all assembling cars in the world will be autonomous by 2025 as it is being developed every day. (History of the Autonomous Car, 2017) Where this technology is prevalent, many states are already drafting laws and regulations for this. (History of the Autonomous Car, 2017)
16
1.2 Topic Definition
1.2.1 Self-Driving Technology
In general, when there is a talk about a Self-driving vehicle, it means a vehicle which is capable of driving itself with a little or even no human interaction.
Nowadays, a lot of cars, are already equipped with a range of autonomous- driving features, such as cruise control, self-parking, self-braking, lateral and longitudinal control, obstacle avoidance, and so on.
All of the features are based on the following technologies:
Computing Hardware - on-board computers, which are capable of making calculations and decisions on input data in order to leverage the software.Figure 1 – A self-driving car software flow-chart
17
● Software - a set of algorithms which allows the system process input data coming from sensors, assess the surrounding situation, predict, plan, decision making, and so on.
● Environment Representation - can be divided in three categories:
■ Localization of vehicle in the environment. As a result, a feature map is generated on this stage.
■ Path planning and eliminating obstacles is about finding the shortest and fastest routes to a destination. (How Do Self-Driving Cars Work? | The Zebra, 2019) Not only navigation but also static and mobile obstacles, as well as maneuvers such as lane changes and other vehicles driving by, a driverless car would have to remember. (How Do Self-Driving Cars Work? | The Zebra, 2019) Route planning begins with a long-range strategy when you put an address into a map application, something close to the directions you just received. (How Do Self-Driving Cars Work? | The Zebra, 2019) Then, as the car drives, short-range plans are created and continuous refinements are made. (How Do Self-Driving Cars Work? | The Zebra, 2019)
Avoiding static and moving obstacles, including pedestrians, is part of designing the map and planning the road. (How Do Self-Driving Cars Work? | The Zebra, 2019) They include both visible and expected obstacles, as driverless cars continuously draw maps of their world, and they use machine learning to determine the identity of such objects. (How Do Self-Driving Cars Work? | The Zebra, 2019) From here the computer learns its expected behaviour. For instance, a self-driving car's computer can discern a motorcycle from a bicycle, and thus decide how to avoid either. (How Do Self-Driving Cars Work? | The Zebra, 2019)
Map building and localization – a driverless car uses an inertial measurement unit, GPS and other sensors to build a map of its surroundings and localize itself within 1 cm of its actual position.
18
Perception of the self driving vehicle is done by applying different types of the sensors and creating what is called a “Sensor Fusion”. All of the sensors can be divided into exteroceptive and proprioceptive.
Exteroceptive sensors include:
LIDAR - sending a laser beam to get an information about surroundings after that beam returns.
RADAR - for getting a robust object detection and relative speed estimation. It is not affected by weather conditions or other conditions which can be harmful for perception using, for instance, a camera or LIDAR.
Land Radar-Penetration
One very special case that leverages the high-precision and focused characteristics of radar sensors is when these sensors are mounted and pointed down on the underside of the vehicle. (Perception: How Self-Driving Cars ‘See’
the World - Swarit Dholakia - Medium, 2019)
Radar sensors can be used to monitor a precise point cloud monitor of the ground immediately below road surfaces during periods of inclement weather (Perception:
How Self-Driving Cars ‘See’ the World - Swarit Dholakia - Medium, 2019) As the ground layout below is almost never going to change, when cameras and forward-facing sensors do not figure out where the car is headed, it serves as a good guide to follow.
(Perception: How Self-Driving Cars ‘See’ the World - Swarit Dholakia - Medium, 2019)
Camera - for getting information of surroundings in the visible range of light.
Stereo camera - for getting information about the shape and depth of surroundings
SONAR - for getting information at the short range, in any weather conditions, which makes them very useful for parking or other short range operation.
Proprioceptive sensors include:
19
GNSS (Global navigation satellite systems) – Global navigation satellite systems help vehicle to estimate its own position, velocity and direction. (Hofmann- Wellenhof, Lichtenegger and Wasle, 2007)
IMU – Inertial measurement unit is used to get a vehicle’s acceleration, angular rotation rate and provides a general three-dimensional orientation.
1.2.2 Levels of autonomy
Self-driving vehicles can be divided into autonomy levels based on their capabilities and degree of autonomy. According to Society of automotive engineers (SAE), they can be dived into 6 levels:
Level 0 - No Automation. The driver performs all the driving tasks on this level.
(SAE International, 2018)
Level 1 - Driver Assistance. The vehicle is driven by the driver at this stage, but it has either acceleration or steering power and some of the fundamental features of autonomy. (SAE International, 2018)
Level 2 - Partial Automation. This is the level where advanced driver assistance systems appear. The vehicle has combined automation features, such as acceleration and steering control. But still, the driver must retain engaged with the driving task. (SAE International, 2018)
Level 3 - Conditional Automation. The driver is a requirement on this level but is not necessary to control the environment. He / She has to be ready at any moment to take control of the car. (SAE International, 2018)
Level 4 - High Automation. On this level, the vehicle is capable under certain conditions of performing all the driving functions. It should have been necessary for the driver to take over. (SAE International, 2018)
Level 5 - Full Automation. Vehicles are capable of performing all driving functions under all conditions at this stage. The difference between this level and
20
level 4 is that there is no driver at all needed for the driving phase. It doesn't even need manual control systems, including steering wheel and pedals. (SAE International, 2018)
1.2.3 Benefits
The self-driving technology brings us a lot of benefits which cannot be achieved with a human-controlled vehicle.
First of all - sensor fusion.
When the car is fully equipped with different types of sensors, it enables the car to have a much broader view of surroundings and constantly monitoring everything around the car. It is able to see not only in front or behind the car, but also on the sides, on the corners, under the car, it is able to see any blind spot which cannot be spotted by human beings. In addition, a distance that can be seen by sensors is much longer than with human sight. It also can take into account much more details in bad-weather conditions than human beings.
The sensor fusion is observing the world from different perspectives: cameras - visible light, radar - radio waves, lidar - laser beams, sonar - ultrasonic waves, etc. This fact brings the possibility to get around the common problems related to the weather and road conditions. For example, if camera, which is based on the same principle of perception as human eyes cannot get enough information because of the mist, the lidar, or radar, can penetrate the mist without any obstacles and bring needed information immediately.
The autopilot system is constantly keeping in mind the whole situation on the road, including current rules, weather and road conditions, surrounding agents, buildings, level of brightness, etc.
In addition, to the physical advantages, the AI cannot be affected by any factor that can influence attention and involvement into the driving process. For instance, the autopilot cannot be angry, sleepy, or disturbed by phone conversation. It is not subject
21
to tiredness which means that the car can control itself as long as its needed without any pauses to rest.
As one of the biggest benefits - the autopilot system is capable of performing planning and prediction of the path and the situation on the road. Especially, the ability to make predictions of surrounding agents motion is very crucial in order to avoid or prevent collisions and to provide the safest and most effective way.
1.2.4 Ego-vehicle
This research aims to develop a model of long-term predictions for the ego- vehicle, which is controlled by an autonomous system. All the formulations and developments are done in order to utilize them in the ego-vehicle.
In this research, an ego-vehicle is a vehicle which plays the role of a reference point and a subject in contact with the environment.
Ego-vehicle is a regular vehicle equipped by all the required hardware for perception of surroundings, navigation, mapping and control. All the calculations and analyzes are done exclusively by the ego-vehicle on-board systems, using the power of its own hardware and software and by perceiving the surroundings by its own sensors.
For example, in their work on automated driving system architecture define ego- vehicle as a vehicle which is equipped with appropriate systems, such as ADS. (Yun, Nishimura, et al., 2016)
In addition, the ego-vehicle possesses software that describes the processes of planning, analysis, forecasting and decision-making based on past experience and environmental conditions.
1.2.5 Surrounding agents
As it is stated in the aim of this work, the research is done around the motion of surrounding agents.
22
By surrounding agents, this work assumes other drivable objects, vehicles, such as cars, motorcycles, buses, bicycles, etc.
The considered agent has various types, dynamics, and actions that vary and can be seen as an example of a heterogeneous system of multi-agents. (Ma et al, 2019)
All surrounding agent’s motions are assumed to be as similar to the real-world as it may be.
1.2.6 Prediction of surrounding agents motion
One of the biggest problems is identifying and responding to risky circumstances in order to prevent or minimize accidents. It involves projecting the potential development of the current traffic situation and evaluating how dangerous it could be in the future. (Lefèvre, Vasquez and Laugier, 2014)
With all of the set of sensors, its easy for a self-driving car to get information about static surroundings and make predictions regarding those surroundings.
The situation is much more complicated when it comes to prediction of surrounding agents which are moving at the same time with the self-driving vehicle.
The main goal in the scope of surrounding agents motion prediction is to avoid collisions with other participants, generate the most efficient path in order to reduce the pollution, time spent on the road and eliminate traffic congestion. In addition, vehicle motion should comply with driving comfort and safety.
In order to achieve this goal, the vehicle should obtain all relevant data about the current situation, such as traffic rules, other vehicles dynamics, environment conditions and its own dynamics feed the data into the predictive algorithm and use predictions in order to adjust the planned route. After that, the vehicle is able to perform its motion, while considering all mentioned conditions.
The task of tracking the vehicles’ motion is one of the most commonly tackled in the field of vehicle automation and self-driving cars.
23
The vehicle interaction module takes into account the mutual influences at the approval stage. (Lefèvre, Vasquez and Laugier, 2014) Most often, the paths that lead to an imminent collision are fined in the matching phase, so after this phase there is a ranked list of paths where the best of them are the best so as not to collide with other vehicles. In order to achieve that a probabilistic collision prediction is used. (Lefèvre, Vasquez and Laugier, 2014)
The key task for this module is to predict the potential future trajectories for all the moving entities in the scene, identify collisions with each possible pair of trajectories, and obtain an estimate of the risk resulting from the probability of collision.
(Lefèvre, Vasquez and Laugier, 2014)
The maneuver recognition module is responsible for recognizing different maneuvers that may occur while other vehicles are moving in the future based on their motion history.
At the very beginning an object detection is performed in order to get information about all the surrounding agents. A new tracker instance is created for each traffic participant which tracks all changes in the location and motion of the participant.
(Hermes, Einhaus, et al., 2018) Then the maneuver recognition module extracts motion patterns of moving scene and puts them into the motion-attributed stereo point cloud for further motion clusterization. The maneuver recognition module creates prototype trajectories by grouping vehicles trajectories.
The motion model, basically, is a pair of the object, which in our case is an agent on the road, and the trajectory along which it goes.
One of the most widely used algorithms for matching given trajectories is a Longest Common Subsequence (LCS) algorithm. The LCS metric originates from the field of matching string algorithms and returns the length of two strings corresponding to the longest common substring. (Hermes et al., 2018)
The trajectory prediction module derives from a linear combination of trajectories predicted by a traffic model using the projected instantaneous movement of the surrounding vehicles and a probabilistic trajectory prediction model from a series
24
of training freeways that studies the patterns of vehicles on the highways. (Deo, Rangesh and Trivedi, 2018)
In this point, it's easier to perform trajectory predictions for independent vehicles to get the most precise predictions. (Deo, Rangesh and Trivedi, 2018) In order to do that, with each class capturing a distinct pattern of motion that can be useful for future prediction, its advantageous to bin surround vehicle motion into maneuver classes.
The motion model becomes unreliable for long-term trajectory prediction, especially in cases involving a higher degree of decision-making by drivers such as overtakes, cut-ins or heavy traffic conditions. (Deo, Rangesh and Trivedi, 2018) These conditions are critical from a safety perspective.
There has been extensive analysis of the question of predicting trajectories for moving forces. Many conventional algorithms are based on models of motion, such as kinematic and dynamic models (Toledo-Moreo and Zamora-Izquierdo 2009), Bayesian filters (Kalman 1960), Gausian processes (Rasmussen and Williams 2006), etc. These approaches do not take into account interactions between traffic agents and the environment, which makes the study of complex scenarios or long-term forecasts difficult. With the success of LSTM networks in modeling non-linear time dependencies (Ma et al . 2017) in the study and sequence generation, these networks are increasingly being used to predict a crowd of people's trajectories (Alahi et al . 2016) and vehicle trajectories (Lee et al. 2017). The focus on predicting one type of group (for example, just pedestrians or cars) is a common limitation of these works. Such strategies can not operate in heterogeneous traffic, in which different vehicles and pedestrians coexist and communicate with one another.
25 1.2.7 Urban environment
Current is dedicated to the self-driving vehicles which are located and moving in the urban environment.
Considering that, there are several factors are constantly influencing the ego- vehicle, so that it should take into account those factors accordingly.
First of all, the main factor is the road, and, in particular, its width, length, curvature, lanes, alignment, crossings and so on. There is a need for all of mentioned factors in order to put trajectories of the ego-vehicle and surrounding agents so they will compose a complete picture of the road situation.
Then there is a the whole traffic with surrounding agents on the road and using it for further predictions.
And last but not least – the traffic rules. Any situation on the road is obeys the traffic regulations which are provided by signs, lanes, traffic lights, road traffic control in case of, for instance constructions, and so on. It is anything what dictates the rules which should be followed by the ego-vehicle and surrounding agents as well.
The difference between urban environment and environment outside the city is that the traffic inside the city is much more dense, contains more roads intersections, such as crossroads, the average speed difference in between urban environment and environment outside the city differs from country to country.
The blend of intersection, consolidating and wandering paths and comparing traffic rules make a mind boggling structure and a more grounded requirement for cooperation between traffic members.
1.2.8 Prediction of surrounding agents’ motion in urban environment
Urban mobility is a more complicated task than the previous one. Cities may be filled with many other participants on the road, which brings much more uncertainties, road conditions are more challenging which may possibly lead to collisions,
26
intersections and cut-ins. In addition to mentioned other surrounding agents, influence every other agent which makes the task of motion prediction much more complicated, and almost any task can have several solutions at the same time.Traditional approaches used for motion prediction are facing limitations and may not be relevant for conditions in the urban environment. Urban environment contains such logical obstacles as crossings, roundabouts, bystreets etc. In addition, the vehicle has to be ready for such maneuvers as merging, compliance with traffic rules and restrictions. Everything is getting more complicated with constantly evolving situation over the time and other participants’ behavior and mutual interaction. It generates set of possible trajectories which are interdependent and may overlap over some time in the future.
On the other hand, prediction of movement in the presence of traffic lights was extensively studied with the intention of increasing energy efficiency and reducing travel time. The method is typically hierarchical. At the top level, kinematic limits on speed or maximum velocity are set so that the vehicle can reach one or more traffic lights without stopping. (Ajanovic et al., 2018) The output is instead fed into MPC- based local motion preparation. (Ajanovic et al., 2018) Top-level planning methods vary from a simple kinematics to Dijkstra's algorithm and supervisory MPC. (Ajanovic et al., 2018) Usually, local motion planning is based on MPC, which can also include other vehicles but is considered only after vehicles and single-lane driving. (Ajanovic et al., 2018) To the best of the understanding of the writer, none of the relevant literature discusses multi-lane driving combined in the presence of traffic signals. (Ajanovic et al., 2018)
1.2.9 Long-term prediction
The task of long-term prediction is more complicated than just merely predict surrounding agents motion for a couple of meters or so. The situation on the road can change at any second so that in the future it will lead to adverse consequences, such as collisions. Therefore, it is very important to predict the movement of surrounding
27
agents for many seconds ahead for safer movement in order to avoid dangerous situations.
In addition, long-term projections contribute to more effective movement of cars, both in terms of overall travel time and in terms of economy, as transport services are used. (Gao et al., 2019)
For each vehicle onstage a drawn-out prediction strategy needs detailed movement history data. In particular, the use of the following technique is nice after a while to reduce the effects of commotion for noisy 3D point information from a sound system camera framework. (Hermes et al., 2010) Using a physical moving model for the expected part of a Kalman filter approach is popular, but this technology often needs speed when the product rapidly changes its conduct. (Hermes et al., 2010) Instead use the particle filter approach updated, where the motion model is represented by the recorded motion designs, and extend this technique with the simultaneous identification of a few objects, with the ultimate aim that each traffic participant is equally subject to certain motion theories. (Hermes et al., 2010)
The methods already mentioned, and described later in this work, allow, with the correct configuration, to implement a system that is capable of moving with the stated requirements and calculating predictions for many seconds ahead.
1.3 Research objectives and aim
1.3.1 Problem statement
Nowadays, more and more auto making companies are producing vehicles capable of driving support (ADAS) and autonomous driving.
Experts from “European Technology Platform on Smart Systems Integrations”
forecast three main milestones in the development of self-driving technology. (Dokic, Müller and Meyer, 2015) First developments in traffic support systems like traffic jam chauffer are already expected to be mature in 2020. (Dokic, Müller and Meyer, 2015)
28
While the self-driving technology for highways is expected to be ready by 2025, the robust and secure self-driving technology of the 4th automation level for the urban environment is expected to emerge by 2030, starting from limited environments.
(Dokic, Müller and Meyer, 2015)
In the future, it will be obligatory for the autonomous driving systems to generate understanding of the complex surrounding traffic situations, for example in the urban environments, and rod crossings. (Hermes et al., 2009) In order to be able to recognize dangerous scenarios as fast as possible, they will need to understand the movements and position of the surrounding agents for several seconds in the future. (Hermes et al., 2009)
Simple prediction methods, such as constant turn rate and velocity, may be adequate for short-term predictions and non-interactive situations. (Schulz et al., 2018) However they are fast approaching a limit in complex urban scenarios. The combination of crossing, merging and diverging lanes and associated traffic laws creates a complex system and a greater need for coordination between traffic participants. (Schulz et al., 2018)
There are a number of recent papers describing prediction of vehicle motion, such as “Search-based optimal motion planning for automated driving” (Ajanovic et al., 2018), “Predicting motion of vulnerable road users using high-definition maps and efficient convnets” (Chou et al., 2019) which present frameworks for facilitating autonomous driving, however, they are still not solving a problem of the long-term prediction in urban environment.
It was also discovered during the conducted interviews, which review will be presented in one of the next sections, that one of the biggest problems in current solutions of autonomous driving is the ability of vehicles to make long-term predictions for surrounding agents’ motion in urban environment. Quote: "The long-term prediction of movements/intents of surrounding agents in an urban environment is an open question in the self-driving domain, which is still remains unsolved. Anybody who claiming that is solved, might be too naive to understand the complexity and the
29
challenges of these problem" (Machine Learning Engineering Lead, personal interview, 2020)
So that, it is clear that in the future there will be a huge growth and demand on the self-driving vehicles where one of the main problems is the ability of the self- driving vehicles to make long-term predictions of surrounding agents’ motion in urban environments.
1.3.2 Aim
The aim of the thesis is to design a model for long-term predictions of surrounding agents’ motion in an urban environment for self-driving vehicles.
The output of the aim will be a proposed model, which includes components for capturing and recognizing the surrounding agents, tracking their motion, memorizing the history of their motion and making prediction about the future movements and maneuvers. The output of the proposed model is a set of trajectories for each of the surrounding vehicles, which are subsequently used by the control module to carry out appropriate maneuvers for the most efficient achievement of the driving goal.
1.3.3 Objectives
The main objectives of this work include a research on what are the best current approaches in the field of the long-term prediction of surrounding agents’ motion in an urban environment for self-driving vehicles, determine what are the biggest weaknesses and limitations and to design a model which solves appropriate problems.
More specifically, the main objectives of the research can be listed as following:
1. Make a research in the field of prediction.
2. Make a research in the field of long-term prediction.
3. Investigate current best practices and solutions in the field of long-term prediction and identify their advantages and disadvantages .
30
4. Conduct interviews with experts in order to get crucial insights on the field of autonomous driving and prediction abilities of self-driving vehicles required for safe and efficient driving experience.
5. Propose requirements for the model based on the conducted research.
6. Propose a model which meets all defined requirements.
7. Perform testing procedures in order to verify correctness of the developed system Further, these objectives will be break down into a set of requirements, which will define the specific design process and appropriate solutions needed in order to fulfill the main goal and objectives of the work.
1.3.4 Prerequisites and Limitations
The research conducted in this work is relevant for automotive companies, which are struggling to increase level autonomy and overall intelligence of their vehicles and at the same time leverage safety on the sufficient level so the customers will continue to trust them.
Likewise, the research is relevant for the companies, which do not have production capacities but involved in development of the algorithms and software, which solve the problem of vehicle autonomy.
Due to the currently growing demand on the more sophisticated algorithms to make vehicles more intelligent and safe.
However, at the same time there are only a few experts in the described field, which adds a number of limitations on getting information and real-world expertise regarding the problem and existing solutions. In addition, almost all the companies, which are already developing appropriate solutions, do not reveal their approaches explicitly what makes it hard to acquire an actual information about what is the state of art in the field.
31
1.4 Thesis Structure
The paper consists of ten chapters and can be conditionally divided into three parts.
The first part consists of five chapters and it is and gives an theoretical insight on the field of concept of autonomous driving.
The first chapter is an introduction, it describes the history of autonomous driving, reveals main milestones in the history of self-driving technology, describes the modern state of the field, allows you to find out the main concepts on which the area and this work rests. In addition, the first chapter describes the main aim, objectives and approach used to construct the work.
The second chapter allows to see the main literature sources used in the work.
The third chapter reveals main points which make the work relevant and actual these days.
The next chapter gives a chance to see what are the main problems nowadays, why the current approaches are facing difficulties to perform prediction efficiently and to make the driving experience safe and convenient.
In the fifth chapter represents an attempt to show the approach of long-term prediction of surrounding agents motion itself. It gives a sight on the advantages of the approach and some examples of attempts to solve similar problem.
The second part of the work is could be treated as practical. It begins with a chapter, which defines the main problem statement and development of system and functional requirements for the future model.
The next practical chapter describes the model design process and allows to see how the specified in the previous chapter requirements are implemented in specific components of the model.
In the last chapter of practical part, a testing of the proposed model is performed and appropriate results are described and shown.
32
The last part of the whole work consists only of one chapter, the conclusion. It concludes the whole work, and gives a perspective on the most important parts of the work and appropriate discoveries.
1.5 Method of Approach
This work utilizes a Design Science Research (hereafter DSR) approach which goal is to help building a new solution for an existing problem. (Peffers et al., 2007)
This approach is chosen because its primary aim is not to explain existing solutions of the considered problem but to design and develop a new solution which aligns with the main aim of this works which is to design a model for long-term predictions of surrounding agents’ motion in an urban environment for self-driving vehicles.
It also proposes to use gathered information and knowledge to solve the existing problem and to develop new knowledge and intelligence. (Peffers et al., 2007)
Figure 2 - Design Science Research process(Peffers et al, 2007)
33
The approach proposes a model which aimed to present and evaluate design science research in information systems and consists of six main stages. (Peffers et al., 2007) The main stages can be described as following:
1. Identification of the existing problem, problem of the research and discussing value of the future solution.
This step is mainly described in the problem statement section of this work.
2. Defining main aim and objectives for the solution.
The definition of the main aim and objectives is discussed in the section about research objectives and aim.
3. Designing and developing the model.
The design and development of the model are described starting from the development of requirements for the model in an appropriate section and in the section with design of the model itself where the crucial components of the model and technologies used are described.
4. Discussing developed model and how it may solve the problem.
This discussion is mainly placed to the testing and evaluation part of the work where it is evaluated and appropriate results discussed which helps to understand its advantages.
5. Evaluation of the developed solution.
This step is described in an appropriate section about model evaluation.
6. Communicating the model and its possible applications.
The discussion of the possible applications for the developed solution is located in the section which proposes possible ways of application for the developed model and how it can be used in real-world scenarios.
1.5.1 Conducted Interviews
While collecting data needed for the further research, interviews and discussions with experts from the field of autonomous driving were conducted. The experts were
34
chosen based on their field of work and research so the questions asked to them were actual and the experts could answer with full expertise to fulfill the gap in knowledge needed for the further research.
The main information that was required at the beginning of the research had to be connected to still open questions and problems in the field of autonomous vehicles.
Regarding still open questions and problems, an interviewed machine learning engineering lead said: “The main strategy that we working on regarding the department is artificial intelligence research in the domain self-driving cars.
Research directions that complies with industrial requirements, so the research work of the students can make immediate impact in the industry.
Since hot topics have big industrial value, I could not dig into details here, but I can give some hints:
1) automation of data labeling
2) long-term prediction of movements/intents of surrounding agents in an urban environment.
3) learning joint representations from multiple sensor data.
4) Learning from small data.
These are general open questions in the self-driving domain, which are still remain unsolved.” (Machine Learning Engineering Lead, personal interview, 2020)
The insight provided above clearly points out that all the researches which are being conducted right now are mostly in the theory of algorithms, machine learning and data science.
On the other hand, other experts pointed out that the current problems which are faced today exists not only in the mentioned fields, but also in the fields of control and objects recognition:” I can suggest some open problems that the industry has not yet sorted out.
For example, such a problem: in the picture from the cameras to determine pits, potholes and other irregularities on the road surface, and to calculate the speed of
35
travel at which vibrations and impacts on the suspension are minimized. Calculate the braking profile and commands in the control system.
In addition to the cameras, you can use IMU and tracking your own movement of an unmanned vehicle (egomotion - usually calculated by the IMU sensor and wheel turn signals).” (Principal Algorithms Developer, personal interview, 2020)
In order to know what is the current state of the field of autonomous driving it was very important to get information about actual state of the art. As it was mentioned in the section about the history of the field of autonomous driving, one of the most important event that influenced the field of self-driving vehicles was the famous DARPA Urban Challenge, at the end of which a lot of the teams and companies which were involved in the challenge published their papers with crucial insight about their solutions and approaches. An interviewed researcher gave a valuable information about that: ”Autonomous driving belongs to the research field robotics. Usually in this field more than 10-15 years old publications are outdated.
I would rather say that these methods rather more the classic and robust ones.
Since 2011 it has been the rise of neural networks and in computer vision they have outperformed classical methods.
The problem is with neural networks, that it is based probabilistic and it cannot be guaranteed that they work at any time.” (Autonomous Driving Researcher, personal interview, 2020)
Another researcher indicated that after the DARPA Urban Challenge, other changes were made in the field: “A lot of happened after DARPA Urban Challenge, particularly in prediction. You can find a good overview in the work of Stéphanie Lefèvre, Dizan Vasquez and Christian Laugier called “A survey on motion prediction and risk assessment for intelligent vehicles” (Lefèvre, Vasquez and Laugier, 2014)”
(Senior Autonomous Vehicles Researcher, personal interview, 2020)
The insights mentioned above brings us an understanding that the area of motion prediction is one of the hottest right now undergoes the greatest number of changes and improvements.
36
Another thing which was chosen as a crucial for the future research is about the trends in the field of autonomous driving. Some experts said: “At university people like to improve existing methods with Neural Networks. In practical, companies try to avoid them as much as they can, because the software must be certified due to safety”
(Autonomous Driving Researcher, personal interview, 2020)
The annotation provided above brings a thought that it is very important to narrow down the usage of neural networks and pay a lot of attention to their reliable usage and correct training. Generally, it means that its much better to stick to the most predictable approach and solution as it can be done in a particular situation.
In addition to the information received from the discussions with experts a set of materials, such as articles and electronic resources were received and studied for the purpose of further research.
1.5.2 Conducted interviews conclusion
Several conclusions can be distinguished based on the conducted interviews and information acquired from the.
Experts could not dig deep into the details because the field is very strict and close to everything what is related to the algorithms development.
It was discovered, that one of the main issues currently discussed is the long- term prediction of movements/intents of surrounding agents in an urban environment, which helped to clearly focus precisely on this particular topic.
The insights gathered during the interviews bring an understanding that the area of motion prediction is one of the hottest right now undergoes the greatest number of changes and improvements.
It was also discovered that the experts in the field of autonomous driving are very strict to everything what can give even an extremely small error which means that its much better to stick to the most predictable approaches and solutions.
37
Also experts pointed to some of the state of art techniques in the fields of autonomous driving, motion planning and prediction which were used in this work.
1.6 Outputs and Expected Benefits
Finally, the results of the research will be ready to be used in both automotive industry and in the companies, which are involved in development of algorithms for self-driving vehicles.
The research results and developed algorithms will allow vehicles to predict future trajectories of surrounding agents and avoid potentially dangerous situations on the road.
Finally, increase in level of safety and potential increase of trust in self-driving technology which can lead to more profit for automotive companies.
38
2 Literature review and current approaches
2.1 Description
In order to get sufficient information about current state of autonomous driving industry and to get an insight about the techniques that can be used to solve the problem of long-term prediction a number of literature sources were studied and used as a background for this research.
In general, for the technical details and required for the theoretical part of the study and then for the practical part, a number of data sources were studied to produce an image of the state-of-the-art in the field of autonomous driving vehicles and to obtain information on the techniques that can be used to achieve the purpose of the work.
Before the beginning of research, in order to start gathering information and developing the model, following research questions were formulated:
What are the current limitations in the field of long-term prediction of surrounding agents’ motion in urban environment?
Which requirements exist for the developing system and its components?
Which components are the most crucial for the developing system?
What are the most efficient ways of testing developing system?
In order to get started with development and evaluation pipeline, an investigation of the available datasets had been done. The data used in the current research is a result of secondary research and comes from an already prepared dataset by ApolloScape (Ma et al, 2019) which will be described more in the following section about the dataset used during training and evaluation phase of this work.
Research questions were used in order to filter out and separate all needed sources and get only most relevant information. The information investigated is
39
relevant according to the work goals and current situation in the field of autonomous driving.
The next step was to find the most suitable sources. On this step, an emphasis was placed only on the most relevant literature according to the work questions, objectives and outputs of the interviews conducted in the section 1.5.
After finding all necessary literature sources, their quality was assessed by appraising the clarity of design and research methods.
After the gathered literature sources were assessed for relevance and quality, the process of extracting necessary knowledge was started. Again, only information relevant to the questions and problematiques of the current work was used during the research.
As for citations, all the references and citations to the relevant sources are marked by indexes, according to the Harvard style of citation.
During the search for literature sources it was crucial to choose the exact set of keywords which can help to find required information the most effectively. As a result, the final set of keywords contains “Self-Driving Cars”, “Autonomous Driving”,
“Prediction”, ”Trajectory”, “Agents”, “Urban Environment”, “Localization”, “Motion Prediction”.
In process of searching for materials, a number of archives and databases were investigated and used as sources for literature for this work.
The most important databases include:
arXiv.org – a distribution network and open-access database of academic resources which provides materials in various fields, including computer science and ingineering.
ResearchGate – academic social network which, due to the availability of necessary practices, may give more insight into the understanding of self-driving vehicles, vehicles automation and algorithmization.
Google Scholar – a free search engine which provides an ability to search for a wide variety of articles and papers in any scholar field.
40
IEEE Xplore – a digital library providing access to the journals, transactions, letters, magazines and conference proceedings of the world's largest technical professional advanced technology organization.
For getting an official statistics, the website of World Health Organization was used for information about traffic fatalities and injuries.
In addition to the mentioned above information, in order to get the historical insights the following sources were used:
Wired – a technological magazine which focuses on the influence of technologies on society, politics and economy.
titlemax.com – a source which gives insights on current state in the auto industry.
digitaltrends.com – a websites which contains publications about electronics and technologies.
2.2 Analyze approaches in long-term agents motion prediction
2.2.1 Long-term Vehicle Motion Prediction (Hermes et al., 2009)
A long-term prediction approach based on a combined definition of the trajectories and a particle filter structure is suggested by this method. As a measure for similarities between trajectories, let the quaternion-based rotationally invariant longest common subsequence (QRLCS) metric be used. (Hermes et al., 2009) The trajectories are categorized by a radial base function (RBF) classifier with an architecture that is capable of handling arbitrary non-uniform length trajectories. (Hermes et al., 2009) The particle filter system monitors and tests a large number of motion hypotheses at the same time (nearly 102), where the class-specific probabilities determined by the RBF classifier are used for particle filter hypotheses as a-priority probabilities. (Hermes et al., 2009) The hypotheses are clustered using a mean-shift procedure, and assigned a probability value. Based on the cluster core, motion prediction is achieved with the greatest likelihood. (Hermes et al., 2009)
41
This paper was used the mostly for the algorithms insight and a current state of the art in the field of autonomous driving. Its approach for prediction and assessment of the road situation is used as an example of a state of art algorithm for comparison with the developing system in this work.
In addition, the evaluation methodology from this work plays a significant role for this work. It is used as one of the basements for evaluation methodology of this work, which will be described more in the section about evaluation.
2.2.2 A survey on motion prediction and risk assessment for intelligent vehicles (Lefèvre, Vasquez and Laugier, 2014)
This approach is a review of current approaches for intelligent vehicles for motion prediction and risk assessment. The proposed classification is based on the semantics used to describe movement and risk. (Lefèvre, Vasquez and Laugier, 2014)
The tradeoff between the completeness of the model and real-time constraints and the fact that the selected motion model determines the choice of a method for risk assessment is pointed out. (Lefèvre, Vasquez and Laugier, 2014)
In order to assess the risk associated with a specific situation, this paper surveys mathematical models that allow us to predict how the situation will develop in the future and their relationship to risk assessment. (Lefèvre, Vasquez and Laugier, 2014) According to the kind of assumptions they create about the modelled entities, we may choose to arrange motion modeling and pre-diction approaches. (Lefèvre, Vasquez and Laugier, 2014)
The study proposes a classification with a growing degree of abstraction at two levels:
Physics-based motion models are the simplest models, given that vehicle movement depends only on the physical laws. (Lefèvre, Vasquez and Laugier, 2014)
42
Maneuver-based motion models are more advanced because they assume that a vehicle's potential movement often relies on the maneuver the driver wants to produce. (Lefèvre, Vasquez and Laugier, 2014) Interaction-aware motion models take into account the interdependencies between the vehicles' maneuvers. . (Lefèvre, Vasquez and Laugier, 2014)
This paper very helps when it comes to the motion modeling and trajectory prediction. Its useful insight on risk assessment of vehicles motion helps to understand what is the current level of risk assessment and what should the developer of motion prediction model consider first when it comes to this criteria.
Some of the insights from this paper can be seen in the part which describes relevance of undertaking research.
2.2.3 How would surround vehicles move? A Unified Framework for Maneuver Classification and Motion Prediction (Deo, Rangesh and Trivedi, 2018)
An ablative analysis that is carried out to evaluate the relative value of each cue for trajectory prediction is defined in this approach. (Deo, Rangesh and Trivedi, 2018) In addition, an overview is provided of the execution time for framework components.
(Deo, Rangesh and Trivedi, 2018)
It presents numerous case studies that examine the outputs of our model for complex traffic scenarios. (Deo, Rangesh and Trivedi, 2018) Index words — Detection of maneuvers, interaction-aware prediction of motion, mounted vehicle cameras, variational Gaussian mixture (VGMM), Hidden Markov Models (HMM). (Deo, Rangesh and Trivedi, 2018)
This paper helps with its useful insight on the one of the best approaches in the field of autonomous driving and agent trajectory prediction.
It is used as a knowledge source in the evaluation part of this work where some of the techniques were used, which will be described more in an appropriate section about developing model evaluation.
