Analysis of Baidu Apollo 7.0 Planning Algorithm Framework (Dry Goods)

Introduction

This article aims to share the latest planning algorithm of Apollo 7.0 with the readers. Since the planning code of Apollo is quite large, it is better to first understand its framework and then tackle each algorithm block step by step.

This article hopes to help readers understand the overall framework of planning, sort out the data flow, analyze the preparation work before the task (the main algorithm of Apollo planning) logic and how the input is constructed using the main scenario as an example. Then it will be easier to understand the details inside the task.

It is important to note that the flowcharts in this article are all sorted out by the author spending a lot of time, so that readers can easily understand the overall framework of planning, and focus on the main points without being led off track by details.

Input and Output of Planning

To understand a module, it is necessary to first understand its upstream and downstream, that is, what the input and output are. Little friends who are familiar with the Apollo CyberRT framework know that under this framework, the input and output are composed of Readers and Writers, and are defined in the component files of each module. In addition, the CyberRT framework defines two modes, message triggering and time triggering, and planning uses message triggering. Therefore, it is necessary to enter the internal main logic only after receiving specific upstream messages, and the upstream messages triggered by message triggering are defined as the input parameters of the Process () function in the component.

Therefore, to summarize the upstream and downstream relationships of planning, refer to the following figure:

To reiterate, the reason why planning’s input is divided into Reader and Process () input parameters is that planning relies on the three upstream inputs of Process () and will only trigger the main logic of planning if all three inputs are received simultaneously, which is a necessary condition for planning to start normally. Reader is not. Some of the upstream also depend on whether the configuration parameter is turned on or not, which can be found in the source code of Apollo.## The Framework of Planning

The output of planning is quite simple, mainly consisting of the control ADCTrajectory data, which contains a set of trajectory points with time and speed. The specific format definition can be viewed in the corresponding proto file.

The above two flowcharts are the framework of Apollo planning algorithm, which has no significant changes compared to before. The main framework is divided into two threads, with the sub-thread ReferenceLineProvider running at a frequency of 20HZ, used to calculate the most important data structure referenceline in planning; and for most scenarios, the planning algorithm based on ReferenceLine is still adopted, while for parking-related scenarios, open space algorithm is used. Currently, Apollo’s scenario division is 16 kinds, which can be viewed in the proto file. In Apollo 7.0, the deadendturnaround scenario is added, which is used for trajectory planning of U-turns by utilizing the openspace method when the unmanned vehicle encounters a dead end. I will look into the details of the algorithm implementation later.

Scene Management in Planning

The important idea of planning in Apollo is to call different tasks for processing based on scene division, and how to perform scene allocation is the core of realizing this idea. From the above configuration parameters, it can be seen that Apollo has set 16 scenes, and the specific switch logic within the scene is also quite complicated, the specific flow logic of the scenario_manager is shown in the following figure:

# Translation

In the scene judgment within the red box shown in the figure above, I have only drawn the scene judgment for the first step. The 5 types of scenes inside the red box are the main categories, and the remaining scenes are further divided and judged within these 5 main categories. In addition, it should be noted that the 5 types of scenes inside the red box have a priority order, that is, if it is determined as a certain type of scene, the subsequent scenes will not be judged again. Below, starting from these 5 types of scenes, I will introduce the scene judgment conditions in Apollo and the specific subcategories of scenes contained in each main category.

1. ParkAndGo

The condition of this scene judgment is that the vehicle is stationary, more than 10m away from the destination, and the current vehicle is either offlane or not on a city road. The openspace algorithm is used in this scenario. Personally, I feel that this scene will be triggered when the vehicle stops due to normal planning failure while driving away from the target lane, and the open_space method is used to make it return to the normal road. Therefore, it is the first scene that needs to be checked in the scene judgment.

2. Intersection

In this scene, there are four sub-scenes. First, determine the category by identifying the first overlap encountered in the previously calculated map, is it an intersection with traffic signs or other intersections. Second, if it is an intersection with traffic signs, it is further divided into stopsign, trafficlight or yield_sign, as shown in the specific diagram below.

3. PullOver

The PullOver scene refers to parking by the side of the road. The following conditions must be met before switching to this scene:

• When not changing lanes, i.e., there is only one reference_line
• The current position is within a certain range from the destination and meets the minimum distance that can be executed for pullover
• The position of the pullover can be found in the map
• The location of the destination is not near an intersection
• The lane_type of the rightmost lane can be found, and this lane allows pullover
• Switching to PullOver can only be done from the lane_follow scene

The overall logic is as described above, and the specific parameter settings can be viewed in the code.4. ValetParking

The ValetParking scenario refers to the valet parking service provided. The logic for judgment is as follows:

• Obtain the target parkingspotid from the routing

• Search the map for a path to reach the parking_spot

• Check the distance from the current location to the parking_spot. If it meets the condition, switch to this scenario

1. DeadEnd

The DeadEnd scenario is a new feature added in Apollo 7.0, which includes a “three-point turn” function and the ability to enter and exit, expanding the operational boundary of the city road network. The “three-point turn” function is based on the open space planner framework and consists of the following parts: DeadEnd scenario conversion, open space ROI construction, and turn trajectory planning. The following images show the entire process from entering DeadEnd to leaving DeadEnd, and I will also learn about the implementation logic of this algorithm in detail later.

The above is the scene switching and management logic in Apollo. In each scenario, there is one or more stages, and under each stage, multiple tasks are divided to complete the corresponding planning tasks. Taking the lanefollow scenario as an example, which is the most commonly used, it includes a stage-lanefollowdefaultstage, and under this stage, there are multiple tasks, as shown in the figure below:

By carefully examining the task under the lane_follow scenario, we can see that Apollo’s planning strategy also decouples longitudinal and lateral planning, prioritizing path planning before speed planning. Specifically, for path planning, the decision of whether to change lanes or borrow lanes is made first, and based on the decision state, a convex space is generated. Finally, based on the reference line and convex space, a quadratic optimization problem is solved to obtain the optimized path. For speed planning, DP+QP optimization method is used based on ST graph, where DP is used to find a feasible solution with the minimum cost value, and then QP is used to smooth the feasible solution to obtain the final smoothed ST graph point set. Ultimately, based on the s value, the path and speed are fused to obtain a smooth trajectory.

Summary

Thus, the core framework and algorithms of Apollo 7.0 planning have been explained, and overall, Apollo’s planning strategy is very clear. However, the details require a lot of time to understand. I personally have been looking through this code for more than two years and have always felt that many details have not been deeply understood. Simply looking through the code is not enough. Without the opportunity to run this algorithm on a real vehicle or a simulation, and without solving the problems encountered in the corresponding scenarios, one cannot truly claim the knowledge as their own. I hope to inspire and encourage everyone to exchange ideas in the comment section if you have any questions.

This article is a translation by ChatGPT of a Chinese report from 42HOW. If you have any questions about it, please email bd@42how.com.