1.Introduction

The first autonomous vehicle was designed and developed in the 1980s by Ernst Dickmanns and his team at the Bundeswehr University Munich in Munich, Germany. It achieved a speed of 59.6 miles per hour (95.9 km/h) on streets without traffic [1]. With government support and increasing demand from the public, autonomous vehicles gradually required more reliable motion planning algorithm to ensure safety of passenger and driver. However, in the mid-1980s, even the most advanced motion planning algorithm was hardly able to generate collision-free path with multiple moving obstacles around ego vehicle [14]. The major breakthrough of this problem is due to invention of idea of deep learning (DL) in 1986 by Rina Dechter Dechter [15]. Application of this idea into autonomous vehicles allow algorithm to calculate non-linear function importing GNN (Graphic Neural Network), and furthermore, allow vehicles to predict motion of surrounding obstacles [16]. Uncertainty-aware motion planning algorithm was then invented but was optimized in 2022[2]. Many other motion planning systems are developed to give vehicles the ability to operate under specific environments but using essentially same algorithm and neural network.

An on-road motion planner designed in 2012 uses The Dynamic Programming algorithm to find multiple desired trajectories first and apply a focused trajectory search to find the best path [2]. Another motion planner proposed in 1991 uses vehicle kinematics, dynamics, and terrain topography to find a global optimal way and minimize motion time [3]. These planners are highly adaptive to the dynamic environment and can be applied to other path-dependent cost functions. However, they give slight consideration to the sudden or dangerous maneuvers of surrounding vehicles.

The main focus of motion planning in autonomous vehicles is to avoid approaching obstacles while selecting the shortest path(energy-saving) or maximum speed (time-saving) to reach the desired destination [4]. A practical motion planner should also be adaptive to the changing environment. That is, the motion planner needs the capability of predicting the motion of surrounding objects and alter the vehicle’s path accordingly.

The recent popularization of autonomous vehicles and the development of motion planning algorithms shift the planner's focus from efficiency to safety. Autonomous car requires not only fast and efficient motion but also the ability for danger prediction and prevention. In this paper, we will discuss a recently developed motion planner for autonomous cars: driving environment uncertainty-aware motion planner.

The experimental validation of the uncertainty-aware motion planner has demonstrated a notable enhancement in safety for submerged and aerial vehicles [5]. The planner can be designed in various ways to cater to distinct objectives. Currently, there exist multiple approaches for addressing uncertainty-aware motion planning challenges. The efficiency of a highway-based mobility planner utilizing a Graphic Neural Network (GNN) prediction model is demonstrated in a study [5]. Additionally, the Augmented Markov Decision Processing (A-MDP) and model predictive control algorithm (MPC algorithm) approach offers a robust strategy for addressing this issue.

The utilization of uncertainty-aware planners has the potential to assist autonomous vehicle manufacturers in enhancing vehicle safety and mitigating the occurrence of car accidents. Section II will go into the essential concepts and mechanisms associated with the uncertainty-aware motion planner. This information aims to enhance readers' understanding and familiarity with recently emerging technologies. Section III will examine the diverse applications of an uncertainty-aware motion planner in complex scenarios. This will demonstrate its capacity to adapt to a dynamic environment. Section IV discusses the problems that must be overcome to seek a more efficient planner.

2.Core Principles

This section introduces the core mechanism of uncertainty-aware motion planners. Even though each system or algorithm is presented separately, we should focus on the cooperation between each system, which, in general, forms the fundamental framework of the planner. Slightly different from traditional motion planners, in which the trajectories are generated based on the current environment around the vehicle, the uncertainty motion planning system includes both perception and prediction systems. The ladder is used to predict the future behavior of surrounding objects and design the vehicle’s path by taking that into account. The vehicle equipped with this system has been proven to have a lower possibility of having a car accident than a vehicle with traditional motion planning system.

2.1.Model Predictive Control Algorithm (MPC Algorithm)

MPC Algorithm is used to optimize the prediction made in a highly complex dynamic system [13]. This is different from other predictor, such as a linear-quadratic regulator, which its optimization strategy only minimizes the cost. MPC Algorithm can take into account future event while optimizing the current prediction. That is, the algorithm covers more diverse factors that make the final decision more reliable.

In the same highway case, ego vehicles not only need to predict the motion of merging vehicle but also need to consider the sudden maneuvers of other vehicles. The main advantage of applying the MPC Algorithm in this case is that it is more sensitive to environmental change. With a high success rate, it is able to predict sudden speed changes and lane changes. This significant result makes this algorithm highly essential in most motion planning system.

2.2.Graph Neural Network

GNN is becoming a new research hotspot in the vehicle trajectory prediction due to its ability to extract interaction information between vehicles. [5]. The most astonishing function of this network is that it cannot only predict the behavior of surrounding vehicles but also give uncertainty of this prediction due to the existence of situations which the network didn’t encounter during the learning process.

Figure 1. A 2D model is established to demonstrate the function of an uncertainty-aware motion planning algorithm. It provides a typical problem that uncertainty-aware motion planning algorithm need to solve when apply to the vehicle. An ego vehicle needs to make maneuver so the vehicle on lane #1 can merge into lane #2 without colliding with another surrounding vehicle.

As a generalization of Convolution Neural Network, GNN employs convolutional graph filters [16]. The output of the first layer can be represented by a nonlinearity σ and is given as [17]:

\( { y_{1}}= σ [{z_{1}}]=σ [\sum _{k=0}^{K}{h_{1k}}{S^{k}}x] (1) \)

Where z can be given as:

\( z =\sum _{k=0}^{K}{h_{k}}{S^{k}}x =H(S)x (2) \)

These outputs allow system to make trajectory prediction, which makes this algorithm extremely powerful and applicable.

The traditional trajectory prediction approach uses t-pattern trees. This method is only functional in the short-distance prediction but incorrect for the long distance [19]. This is because when each objects’ data is captured, it keeps on diminishing as algorithm begins to process next set of data. In 2021, Divya Singh and Rajeev Srivastava proposed a method to reduce this diminishing effect by highlighting the pattern before giving it to the input [18]. This gives the neural network stronger ability to handle long-term information and produces more reliable prediction.

2.3.Augmented Markov Decision Processing (A-MDP)

Uncertainty-Aware Motion Planning is an advanced approach that takes into account environmental elements and aims to effectively address uncertainties throughout the process of motion path planning. The utilization of this methodology is prevalent in autonomous mobile systems, including self-driving vehicles, robotic devices, and unmanned aerial vehicles, with the aim of guaranteeing their ability to move securely and optimally within intricate and unpredictable surroundings. The navigation scenario in question is considered to be one of the most complex due to the combination of the subject's great agility and the critical importance of accurate and timely condition estimates in order to prevent crashes [7].

In a publication from 2019 authored by Lorenzo Nardi and Cyrill Stachniss [8], a novel methodology utilizing the Augmented Markov Decision Process (A-MDP) was introduced. Similar to the approach taken by Bopardikar et al. [9], the researchers employed a condensed depiction of the robot's belief system in order to address more expansive surroundings and make progress in practical scenarios. The methodology employed in this study is structured as follows:

2.3.1.Augmented State: Augmented state is introduced here to propose integrating robot localization uncertainty on road networks including road intersections and variance-based representation of uncertainty. The state S is defined as:

\( S=\lbrace s=( v,{σ^{2}})|v∈V, {σ^{2}}∈W\rbrace (1) \)

Where\( V \)is the intersections, and\( W \)is a variance set. Each augmented state\( s \)corresponds to the normal distribution\( ϰ(v, Σ) \), with\( \sum =|\begin{matrix}{σ^{2}} & 0 \\ 0 & {σ^{2}} \\ \end{matrix}| \).

2.3.2.Transition Function Considering Position Uncertainty: This function holds significant importance in the process of selecting subsequent actions. Fig .2 shows the three key steps that involved in the process.

Figure 2. The three key steps when doing the transition function.

Posterior Probability: To estimate the propagation of position uncertainty, a prediction step incorporating a Gaussian distribution and a local localizability map was employed.

\( p(x|s,a)= η\sum _{i=1}^{|v|}p(x={v_{i}}|s)p(x|{v_{i}},a) (2) \)

Where\( a \)represents the action,\( η \)is a normalization factor.

2.3.3.Reward Function: The objective of the A-MDP reward function is to decrease the average journey time by maximizing the negative time, taking into account the presence of uncertainty. The incentives for traversing between crossings are determined by considering the road length and the velocity of the robot. A penalty is applied in the event that one intersection is not accessible from another. Intersections that contribute to the achievement of the goal are rewarded with positive incentives.

2.3.4.Navigation Following A-MDP. Solving A-MDP efficiently with policy iteration. π∗ guides navigation using estimated robot position bel(x) at intersections, selecting optimal actions based on belief states.

\( {S_{bel}}={argmin_{s∈S}}{D_{B}}(bel(x),s) \)(3)

Then execute the corresponding action\( {a^{*}}={π^{*}}({S_{bel}}) \).

Based on the provided algorithms, we can analyze the advantages and disadvantages of each algorithm. Table 1 on page 4 provides a concise comparison of these three algorithms, including not only the pros and cons but also other capabilities such as handling uncertainty and applicability to different scenarios.

Table 1. Comparison of the three algorithms

3.Applications

As a hot topic in recent years, motion planning has been widely used and spread in our daily lives. From navigation devices to self-driving cars, it all reflects its close relationship with human life. In this section, several related applications are introduced.

3.1.Navigator of Mobile Robots Using AMDP

As previously stated in Section II, the researchers utilized a concise representation of the robot's belief system to effectively navigate larger environments and achieve advancements in real-world situations [9].

In their study, a localization prior is utilized in order to assess the propagation of uncertainty along the road network. The resultant policy aims to minimize the anticipated duration of trip while concurrently mitigating the occurrence of errors made by the robot during navigation, particularly when faced with substantial positional uncertainty. Taking into account the inherent uncertainty of the robot, the planning methodology exhibits two key characteristics. Firstly, it possesses the capability to choose from a range of actions based on the level of uncertainty present. Secondly, in intricate scenarios, it generates plans that, on average, are shorter in duration compared to a shortest path policy that operates under uncertainty but disregards it.

3.2.Autonomous Electric Vehicles

The demand for fossil fuel has significantly increased due to increasing industrialization and recent advancements in the vehicle industry. The emission of greenhouse gases (GHGs) has significantly increased as a result of the widespread usage of gasoline-powered vehicles in everyday transportation activities, leading to their accumulation and negative impact on the natural environment. Therefore, it is imperative to preserve the natural environmental conditions in order to safeguard the well-being of the human population. Hence, the conversion of conventional gasoline-powered automobiles to electric vehicles and autonomous vehicles is imperative This is also an important application of motion planning [10].

3.2.1.Fully Autonomous Shuttle. In the year 2017, an autonomous Shuttle was meticulously constructed and developed by an individual named Harry in the country of England. Subsequently, the Shuttle underwent rigorous testing in the city of London. In the United Kingdom, areas characterized by limited or nonexistent public transportation options, such as the absence of buses or trains in close proximity to diverse sites, have undertaken strategic measures to improve the efficiency and effectiveness of public transportation services. Therefore, these shuttles are employed in such regions with the aim of enhancing transportation efficiency. The activity involves a group of approximately 5 to 6 individuals and encompasses a total distance of 12 kilometers. The system is operated by the utilization of advanced sensors, sophisticated cameras, LiDAR technology, and other intelligent monitoring and control systems [10].

3.2.2.Autonomous Microbus. The Autonomous Robot Bus, a self-driving vehicle, has been introduced by Finland. This term is commonly referred to as GACHA. The present vehicle under consideration is an autonomous shuttle that is capable of operating in a wide range of weather conditions. This refers to the collaboration between Japanese and Finnish land workers. The bus has the ability to operate without a driver, utilizing advanced obstacle detection, navigation, and positioning systems. The dimensions of the object in question are approximately 2.5 meters in width, 5 meters in length, and approximately 3 meters in height. The vehicle in question is a quadrupedal mode of transportation that functions at a velocity of 45 kilometers per hour and possesses a maximum travel distance of 110 kilometers. Additionally, it offers the convenience of both wireless and cable charging options. The vehicle has a maximum capacity of 18 individuals, with 11 occupants seated and 7 occupants standing. During the winter season, the inhabitants of Finland's distant regions gather in order to foster cleanliness, safety, and amicability within their communities. This device is designed to be compatible with a wide range of weather conditions, allowing for efficient navigation even in challenging circumstances such as cloud cover, heavy rainfall, storms, and fog.

4.Challenges

Uncertainty-aware motion planning system requires support from many other systems in the vehicle. It should also be able to solve motion planning problem in a large environment with abundant variables. Current challenges that can obstruct further development of this planning system include: (1) Insufficient accuracy of sensors; (2) Excessive complexity of calculation in large environment; (3) The Challenge of Software Structure and Integration in Autonomous Vehicles.

4.1.Insufficient Accuracy of Sensors

Perception system inside a vehicle include multiple sensors (sensor groups) that collect information from surrounding environment and transmit it to other system for analysis. It needs to collect as much information as possible so that the algorithm can make fast and correct decision. Current sensors including radar, ultrasonic, proprioceptive sensors etc. have limited ability of detecting surrounding environment [11]. This problem can be solved by introducing Sensor Fusion. It is fundamental a technology that provides connection between multiple sensors by sharing information with each other. This section also introduces how Sensor Fusion technology can maximizes potential of each sensor.

First and most important sensor in the perception is camera, like human eyes. It provides majority of visual information to the perception system. It is also a very sensitive component where it can be severely affected by surrounding environment such as intensive lighting and harsh weather. By introducing Sensor Fusion, even a low-cost entry-level digital camera can efficiently model a 3D indoor environment [9]. The application of Sensor Fusion technique in this case consists of using a LiDAR sensor, which is used to minimize the tract losses when conducing multi-target tracking by importing data from the camera [11]. These data focus on the blind spot where LiDAR cannot detect so the final prediction can be more precise than decision made by LiDAR sensor only. Also, applying same technique to the odometry and a camera can increase frequency and accuracy of the vision data [11]. The final result is tested and the error is contained within an acceptable range. This optimization also increases the stability of camera when moving simultaneously with vehicle by making it focus on highlighted target, which provide clearer visual information [20].

4.2.Low Computational Efficiency in Large Environment

A-MDP is an efficient approach for solving uncertainty-aware motion planning problems. However, in certain situations, the algorithm still requires a high-complexity computing strategy, especially in the city, where there are many intersections. As a matter of fact, in practice, to avoid missing correct intersections, planning that takes uncertainty into account at the local scale is more relevant. Therefore, A-MDP can be more effective in these situations by combining it with a hierarchically higher-level planner [9]

4.3.Integration with Other Software Components of Autonomous Vehicle

Autonomous cars can be characterized as intricate and multifaceted systems. Hence, it is more practical for researchers to adopt a compartmentalized approach to the structure of autonomous vehicle (AV) software, prioritizing the development of particular subsystems inside the larger framework. By enhancing these distinct subsystems, researchers can effectively achieve novel functionalities and capabilities for AVs. One often neglected yet crucial obstacle in the field of autonomous system research is to the meticulous incorporation of all constituent elements, hence guaranteeing the meaningful and correct interaction among diverse software components. The guarantee of achieving the desired final output of a system can be challenging due to the complexity of the entire system and the difficulty in ensuring that the sum of local process intentions aligns with this goal. The allocation of computational resources among different separate activities inside the system is a significant difficulty [10].

5.Conclusion and future work

This review paper offers a thorough examination of the current methodologies pertaining to Uncertainty aware motion planning. The works that have been evaluated emphasize the substantial advancements that have been achieved in comprehending the fundamental principles behind algorithms. Over the course of time, an increasing number of vehicles equipped with uncertainty-aware technology have been introduced to the market. Consequently, a growing number of individuals have embraced this advanced product. In order to facilitate further progress, it is imperative to address various issues that have been previously mentioned. In future iterations, it is imperative for these vehicles to undergo necessary configuration enhancements, such as refining sensor accuracy and optimizing collaboration efficiency. In summary, this review highlights the imperative for ongoing investigation and cooperation within the domain of uncertainty-aware motion planning. Through the identification and subsequent resolution of existing deficiencies, as well as the utilization of emerging technologies and multidisciplinary methodologies, researchers have the potential to achieve substantial advancements in the development of more intelligent algorithms and flawless mechanisms. In the progression of our research, it is imperative for academics to maintain a state of vigilance, engaging in critical analysis of established frameworks, and actively pursuing novel approaches to further our understanding of uncertainty-aware motion planning.

Acknowledgement

Haoran Xu and Haodong Lu contributed equally to this work and should be considered co-first authors.