PaperlayerView exact revision on arXiv

Source-linked AI summary

Baidu Apollo EM Motion Planner

Haoyang Fan, Fan Zhu, Changchun Liu, Liangliang Zhang, Li Zhuang, Dong Li, Weicheng Zhu, Jiangtao Hu, Hongye Li, Qi Kong

arXiv:1807.08048v1cs.ROcs.AIcs.LGeess.SY

TL;DR

Level-4 planning needs scalable, feasible decisions across scenarios involving dozens of obstacles. The Apollo EM planner combines multilane planning with iterative path-speed planning and traffic-rule and decision handling. By May 16, 2018, the system underwent 3,380 hours and approximately 68,000 kilometers of closed-loop testing; simulation testing exceeded 100,000 hours and covered a million kilometers.

  • Problem

    Level-4 planning needs scalable, feasible decisions across scenarios involving dozens of obstacles.

    Source: C. Decisions and Traffic Regulations · p. 3

  • Method

    The Apollo EM planner combines multilane planning with iterative path-speed planning and traffic-rule and decision handling.

    Source: §I · p. 2

  • Results

    By May 16, 2018, the system underwent 3,380 hours and approximately 68,000 kilometers of closed-loop testing; simulation testing exceeded 100,000 hours and covered a million kilometers.

    Source: §VI · p. 13

  • Takeaways & Limitations

    The authors report that the light-decision planner can perform in complicated scenarios with multiple obstacles.

    Source: §VI · p. 13

    Further safety design is outside the manuscript’s scope.

    Source: §I · p. 2

Abstract

from arXiv · show

In this manuscript, we introduce a real-time motion planning system based on the Baidu Apollo (open source) autonomous driving platform. The developed system aims to address the industrial level-4 motion planning problem while considering safety, comfort and scalability. The system covers multilane and single-lane autonomous driving in a hierarchical manner: (1) The top layer of the system is a multilane strategy that handles lane-change scenarios by comparing lane-level trajectories computed in parallel. (2) Inside the lane-level trajectory generator, it iteratively solves path and speed optimization based on a Frenet frame. (3) For path and speed optimization, a combination of dynamic programming and spline-based quadratic programming is proposed to construct a scalable and easy-to-tune framework to handle traffic rules, obstacle decisions and smoothness simultaneously. The planner is scalable to both highway and lower-speed city driving scenarios. We also demonstrate the algorithm through scenario illustrations and on-road test results. The system described in this manuscript has been deployed to dozens of Baidu Apollo autonomous driving vehicles since Apollo v1.5 was announced in September 2017. As of May 16th, 2018, the system has been tested under 3,380 hours and approximately 68,000 kilometers (42,253 miles) of closed-loop autonomous driving under various urban scenarios. The algorithm described in this manuscript is available at https://github.com/ApolloAuto/apollo/tree/master/modules/planning.

I. INTRODUCTION · A. Multilane Strategy

The Apollo EM planner combines iterative path-speed planning with a multilane strategy that evaluates candidate lane trajectories in parallel. It targets safe, smooth driving by integrating traffic rules and lane-change decisions into the planning process.

I. INTRODUCTION

  • The Apollo open-source platform uses a flexible modular architecture to support autonomous-driving deployment amid challenges in environment sensing, understanding vehicle intentions, and driving safely across scenarios.A motion-planner safety module is described as a last protective layer that should trigger immediate emergency behavior and warnings if upstream modules fail; further safety design is beyond the manuscript’s scope.Source: §I · pp. 1–2
  • The planner uses information from the HD map, perception, localization, and prediction modules to generate a safe, smooth trajectory for vehicle control.The HD map is accessible to every online module; perception and localization provide dynamic environment information used to predict future environment status.Source: §I · p. 1
  • The motion planner makes safety its top priority, aiming for a trajectory of at least eight seconds or 200 meters to support safe driving within regular vehicle dynamics, and could react within 100 ms in emergencies.Other stated safety considerations include traffic regulations, range coverage, and cycle-time efficiency.Source: §I · p. 1
  • The planner is intended to cover simple and complex scenarios, including multilane driving and heavy traffic, while providing comfort through smooth trajectories and following traffic regulations.Examples of simple scenarios include stopping, nudging, yielding, and overtaking.Source: §I · p. 2
  • The Apollo EM planner targets safety and ride experience through multilane planning and an iterative path-speed design that combines traffic rules and decisions.The manuscript identifies the planner as an EM-type iterative algorithm.Source: §I · p. 2

A. Multilane Strategy

  • Searching across all possible lanes can be computationally expensive and complicates applying lane-specific traffic rules in a common frame, while trajectory stability must prevent abrupt cycle-to-cycle changes.Consistent driving behavior also helps communicate the vehicle’s intentions to other drivers.Source: A. Multilane Strategy · p. 2
  • The multilane strategy handles routing-triggered and obstacle-forced lane changes by optimizing a trajectory for each candidate lane, then selecting across lanes using cost and safety rules.Candidate-lane obstacles and environment information are projected into lane-based Frenet frames, where lane-specific traffic regulations are applied.Source: A. Multilane Strategy · pp. 2–3

B. Path-Speed Iterative Algorithm … III. EM PLANNER AT LANE LEVEL

Apollo EM planner combines iterative path-speed optimization with decisions made before trajectory smoothing. Its lane-level process projects obstacles into Frenet and station-time frames, then uses dynamic programming and quadratic programming to generate feasible, smooth profiles.

B. Path-Speed Iterative Algorithm

  • Path-speed decoupling offers flexible optimization, but dynamic obstacles can make it suboptimal; direct SLT search also faces complexity that forces coarser searches and suboptimal trajectories.Direct methods search jointly in space and time, while decoupled approaches optimize path and then derive speed.Source: B. Path-Speed Iterative Algorithm · p. 3
  • The planner iterates path and speed optimization, using the previous cycle’s speed to estimate dynamic-obstacle interactions before evaluating a new speed profile.For high-speed dynamic obstacles, it favors lane changes over nudging for safety.Source: B. Path-Speed Iterative Algorithm · p. 3

C. Decisions and Traffic Regulations

  • Traffic regulations are hard constraints, while yield, overtake, and nudge decisions are negotiable; Apollo makes decisions before smoothing to clarify intent and reduce trajectory-search space.The passage contrasts this with planners that jointly optimize decisions and plans or use hand-tuned or model-based driving statuses.Source: C. Decisions and Traffic Regulations · p. 3
  • For level-4 driving, decisions need scenario scalability and maneuver feasibility, but hand-tuned and model-based approaches do not verify a collision-free trajectory.Apollo instead describes intent with a rough feasible trajectory and generates a convex feasible space for spline smoothing.Source: C. Decisions and Traffic Regulations · pp. 3–4

II. EM PLANNER FRAMEWORK WITH MULTILANE STRATEGY

  • The framework gathers and synchronizes data, generates candidate lane reference lines from map and routing information, and evaluates surroundings and regulations in a Frenet frame.The lane-level optimizer generates path and speed profiles for each lane, and a trajectory decider selects among them using vehicle status, regulations, and trajectory cost.Source: §II · p. 4

III. EM PLANNER AT LANE LEVEL

  • The lane-level iteration has two E-steps and two M-steps per planning cycle, with trajectory information carried between cycles.In the first E-step, static and dynamic obstacles are projected onto the lane Frenet frame; only low-speed and oncoming traffic are considered for path nudging, while lane changes cover high-speed traffic.Source: §III · pp. 4–5
  • The second E-step projects high-speed, low-speed, and oncoming obstacles onto the station-time frame using the generated path, marking regions where obstacle trajectories overlap it.The first E-step uses the Frenet frame, with dynamic-obstacle positions estimated from the previous cycle’s trajectory.Source: §III · p. 5
  • Dynamic programming first finds rough path and speed solutions and obstacle decisions, then quadratic programming optimizes spline profiles within a convex hull set by those decisions.This combination addresses the non-convexity of the optimal path and speed solution.Source: §III · p. 5

A. SL and ST Mapping (E-step) · B. M-Step DP Path

The planner maps vehicle and obstacle interactions into SL and ST Frenet-frame representations, then uses dynamic programming to choose a feasible path through sampled candidates scored for smoothness, obstacle avoidance, and lane guidance.

A. SL and ST Mapping (E-step)

  • Dynamic obstacles are projected into SL using the ego vehicle’s previous-cycle trajectory to estimate station by time, marking bounding-box overlaps as interaction regions.Static obstacles map directly; the method illustrates the dynamic projection with oncoming traffic.Source: A. SL and ST Mapping (E-step) · p. 5, Figure 4 · p. 6
  • After path generation, obstacle trajectories are projected into ST; their bounding-box overlaps constrain the feasible speed region for smooth speed optimization.The illustration shows a cut-in obstacle 2 seconds ahead at 40 meters and an obstacle behind the ego car.Source: A. SL and ST Mapping (E-step) · pp. 5–6, Figure 5 · p. 6

B. M-Step DP Path

  • The M-step path optimizer finds l = f(s) in nonconvex SL space through dynamic-programming path decisions followed by spline-based planning.The DP step provides a rough path with feasible tunnels and obstacle-nudge decisions.Source: B. M-Step DP Path · p. 6
  • The Frenet-frame lattice samples multiple rows ahead and connects them with quintic polynomial edges, adapting row spacing to speed, road structure, and maneuver.Sampling can be customized by scenario, such as using longer intervals for lane changes; total station distance covers at least 8 seconds or 200 meters.Source: B. M-Step DP Path · p. 6
  • Each graph edge combines smoothness, obstacle-avoidance, and lane costs, drawing on SL projections, traffic regulations, and vehicle dynamics.Source: B. M-Step DP Path · p. 6
  • Smoothness cost accounts for heading difference, path curvature, and curvature derivative, and polynomial forms allow analytical evaluation.Source: B. M-Step DP Path · pp. 6–7
  • Obstacle cost uses bounding-box distance: it is zero beyond the nudge range, applies a decreasing nudge cost within range, and assigns a large collision cost inside the safety buffer.The nudge range can vary by scenario.Source: B. M-Step DP Path · p. 7
  • Lane cost combines guidance-line and on-road costs; dynamic programming selects the lowest-cost candidate path, which also determines obstacle decisions.The guidance line is an ideal path, generally the path centerline, while points outside road boundaries receive a high penalty.Source: B. M-Step DP Path · p. 7

C. M-Step Spline QP Path

The spline QP path step refines the dynamic-programming path by smoothing it within a feasible tunnel. It balances smoothness against obstacle-nudging guidance while enforcing linearized boundary and dynamic-feasibility constraints.

C. M-Step Spline QP Path

  • The spline QP step smooths the selected dynamic-programming path within its feasible tunnel.Fig. 8 illustrates the refinement.Source: C. M-Step Spline QP Path · p. 7, Figure 8 · p. 8
  • The objective balances smoothness costs with a guidance-line cost from the DP path, which estimates obstacle-nudging distance.The objective terms use path derivatives related to heading, curvature, and curvature derivative.Source: C. M-Step Spline QP Path · p. 7
  • Linearized boundary constraints account for all four vehicle corners because, under the bicycle model, lateral-position bounds alone omit heading effects.The method adds half circles at the vehicle’s front and rear ends to keep constraints convex and linear.Source: C. M-Step Spline QP Path · pp. 7–8, Figure 10 · p. 8
  • The QP enforces curvature-related dynamic-feasibility ranges and matches the ego vehicle’s initial lateral position and derivatives; linear constraints enable fast solving.Constraints apply to the spline and its derivatives at station coordinates.Source: C. M-Step Spline QP Path · p. 8

D. M-Step DP Speed Optimizer

The M-step speed optimizer uses dynamic programming and spline quadratic programming to generate a smooth speed profile in the ST graph, with DP output guiding the spline-QP step.

D. M-Step DP Speed Optimizer

  • The speed profile is a non-convex ST-graph optimization, addressed with dynamic programming combined with spline quadratic programming.The DP profile guides the spline-QP speed step.Source: D. M-Step DP Speed Optimizer · p. 8
  • DP produces a piecewise linear speed profile, a feasible tunnel, and obstacle speed decisions for the spline-QP step.The feasible tunnel is used to generate a convex region.Source: D. M-Step DP Speed Optimizer · p. 9
  • The DP speed optimizer minimizes a cost functional in the ST graph subject to constraints.Its velocity-keeping term follows the designated reference speed when obstacles and traffic-light restrictions are absent; the reference speed reflects road speed limits, curvature, and other traffic regulations.Source: D. M-Step DP Speed Optimizer · p. 9

E. M-Step QP Speed Optimizer

The M-step spline QP speed optimizer addresses dynamic requirements that a piecewise-linear speed profile cannot satisfy. It balances following the dynamic-programming speed guidance with smoothness, while enforcing boundary, traffic-rule, and vehicle-dynamics constraints to produce a feasible speed profile.

E. M-Step QP Speed Optimizer

  • The spline QP speed step has three parts: a cost functional, linearized constraints, and a spline QP solver.The resulting speed profile combines with the path profile to form a smooth trajectory for the control module.Source: E. M-Step QP Speed Optimizer · pp. 9–10, Figure 13 · p. 10
  • The objective balances distance from the DP speed guidance profile Sref with speed-profile smoothness measured by acceleration and jerk.The first cost term measures distance between Sref and the generated path S.Source: E. M-Step QP Speed Optimizer · p. 10
  • Constraints enforce monotonicity at designated points, traffic regulations, vehicle dynamics, and matching the initial velocity and acceleration.The spline solver generates a smooth feasible speed profile, illustrated in Fig. 14.Source: E. M-Step QP Speed Optimizer · p. 10, Figure 14 · p. 10

F. Notes on Solving Quadratic Programming Problems

The path and speed optimizers use compact piecewise-quintic splines with many safety constraints, making an active-set QP solver with a previous-cycle hot start suitable. The QP solves in 3 ms on average.

F. Notes on Solving Quadratic Programming Problems

  • 3 ms on average is the QP solve time, meeting the planner’s time-consumption requirement.The previous cycle’s result is used as a hot start to accelerate quadratic programming.Source: F. Notes on Solving Quadratic… · p. 10
  • Approximately 100 locations or time points are evaluated, producing more than 600 constraints for path and speed optimization.Source: F. Notes on Solving Quadratic… · p. 10
  • Piecewise quintic polynomials provide a compact spline representation, typically using 3 to 5 polynomials and approximately 30 parameters.Because the objective is relatively small while the constraint count is large, the authors select an active-set QP solver.Source: F. Notes on Solving Quadratic… · p. 10

G. Notes on Non-convex Optimization With DP and QP · IV. CASE STUDY

The planner combines grid-based DP with QP to address their limitations in non-convex optimization, and the case study shows iterative path-and-speed updates for an oncoming obstacle. The case studies illustrate the light-decision planner on situations encountered in Baidu’s heavy-decision planning modules.

G. Notes on Non-convex Optimization With DP and QP

  • DP’s finite sampling grid yields a rough solution that is generally not optimal, such as a path that nudges an obstacle at a non-best distance.The number of candidate solutions is limited by processing time.Source: G. Notes on Non-convex Optimization… · p. 11
  • QP optimizes within a convex domain and needs DP’s help to choose an obstacle decision; random or rule-based choices can cause failure or a local minimum.Possible decisions include nudging left or right, following, or overtaking.Source: G. Notes on Non-convex Optimization… · p. 11
  • The EM planner uses grid-based DP for a rough solution, then uses its results to define a convex domain and guide QP toward an optimum likely to contain the global optimum.This combination is intended to minimize the limitations of DP and QP alone.Source: G. Notes on Non-convex Optimization… · pp. 10–11

IV. CASE STUDY

  • Heavy-decision planning is understandable but can be trapped in corner cases and may not be optimal; the case studies use situations exposed in Baidu’s heavy-decision modules.Those situations were resolved by the latest light-decision planning module.Source: §IV · p. 11
  • With both vehicles initially at 10 m/s, cruising predicts a meeting at S=40 m and a right nudge; slowing to 5 m/s shifts the encounter to S=30 m.The updated path places the nudge at S=30 m, so slowing at S=40 m is no longer needed.Source: §IV · pp. 11–12
  • In the oncoming-obstacle case, the final trajectory slows to nudge at S=30 m, then accelerates after passing the obstacle.Figure 15 illustrates the iterative path and speed updates that produce this trajectory.Source: Figure 15 · p. 12, §IV · p. 12
  • The four-step sequence is not fixed: fewer or more steps may be needed, and more complicated environments may require more steps.The case study traces historical planning, two path-profile iterations, and two speed-profile iterations.Source: §IV · pp. 11–12

V. COMPUTATIONAL PERFORMANCE · VI. CONCLUSION

EM planner reduces computational complexity by splitting the station-lateral-speed problem into two two-dimensional problems. The conclusion emphasizes its light-decision approach, passability, and extensive vehicle and simulation testing.

V. COMPUTATIONAL PERFORMANCE

  • Splitting the three-dimensional problem into station-lateral and station-speed problems yields O(n(M+N)) complexity for n obstacles, M candidate paths, and N candidate speeds.Source: §V · pp. 12–13

VI. CONCLUSION

  • The planner uses light decisions to handle complicated scenarios with multiple obstacles, avoiding the trajectory failures that can arise from predetermining actions for each obstacle.Heavy-decision methods can struggle to predict obstacle interactions and may fail to find a trajectory satisfying all predetermined decisions.Source: §VI · p. 13
  • The planner addresses the safety-passability tradeoff by resolving inconsistencies between potential decisions and planning while improving vehicle passability.The conclusion illustrates the tradeoff with lane changing: pausing for a vehicle behind can improve safety but reduce passability.Source: §VI · p. 13

V. COMPUTATIONAL PERFORMANCE

  • The reduced complexity lowers processing time and increases system interaction ability; on the specified PIC, average runtime is less than 100 ms.Source: §VI · p. 13, §V · p. 13

VI. CONCLUSION

  • As of May 16th, 2018, the system’s effectivity was proven through 3,380 hours and approximately 68,000 kilometers (42,253 miles) of intense closed-loop testing in Baidu Apollo autonomous driving vehicles.The algorithm was also evaluated under different countries, traffic laws and conditions, including extremely crowded urban scenarios such as Beijing, China, and Sunnyvale, CA, USA.Source: §VI · p. 13
  • More than one-hundred-thousand hours and a million kilometers (0.621 million miles) of simulation testing also evaluated the algorithm.Source: §VI · p. 13

APPENDIX 1 · APPENDIX 2: CONSTRAINED SMOOTHING SPLINE · AND QUADRATIC PROGRAMMING

The appendices describe Apollo as an open, high-performance autonomous-driving platform and formalize its spline QP optimizer as a piecewise-polynomial smoothing problem with a quadratic objective and linearized constraints.

APPENDIX 1

  • Apollo is described as an open, high-performance autonomous-driving platform with fully autonomous driving capabilities.Source: APPENDIX 1 · p. 14

AND QUADRATIC PROGRAMMING

  • The path and speed optimizer uses a shared constrained smoothing-spline framework, whose quadratic convex objective and linearized constraints enable rapid, stable solution.Source: AND QUADRATIC PROGRAMMING · p. 14
  • The function is expressed piecewise as f0(x −x0) on [x0, x1), continuing through fn−1(x −xn−1) on the final interval [xn−1, xn].Source: AND QUADRATIC PROGRAMMING · p. 14
  • The spline solver parameterizes polynomial coefficients and seeks a function optimizing a linear combination of functionals on a reproducing-kernel Hilbert-space domain.Source: AND QUADRATIC PROGRAMMING · p. 14
  • The objective combines four functionals: one measures distance to a prescribed guidance line, while the other three encode smoothness.Source: AND QUADRATIC PROGRAMMING · p. 14
  • Constraints include bounds on function values or derivatives and matching polynomial derivatives across spline knots to enforce continuity.Source: AND QUADRATIC PROGRAMMING · p. 14
  • The speed smoother enforces monotonicity at specified points; Theorem 1 states that P is quadratic and L is linear in parameter p.Source: AND QUADRATIC PROGRAMMING · p. 15

k x(0)xT

The objective P(f) is quadratic and convex with respect to the spline parameter vector p.

k x(0)xT

  • P(f) has a quadratic convex form with respect to spline parameter vector p.The passage also identifies X(0) as a diagonal block matrix, but its definition is truncated.Source: k x(0)xT · p. 15

Related papers

Loading 1807.08048v1…