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

The paper addresses real-time level-4 autonomous-driving motion planning under safety, comfort, and scalability requirements. It presents the Apollo EM planner, which combines parallel multilane selection with iterative Frenet-frame path-speed optimization and dynamic programming plus quadratic programming. The system was tested in 3,380 hours and approximately 68,000 kilometers of closed-loop autonomous driving.

  • Problem

    Level-4 motion planning must support safety, ride experience, and scalable decisions across multilane and complicated traffic scenarios.

  • Method

    The Apollo EM planner compares parallel lane-level trajectories and iteratively optimizes path and speed using Frenet-frame projections, dynamic programming, and quadratic programming.

  • Results

    3,380 hours and approximately 68,000 kilometers (42,253 miles) of closed-loop testing were completed in Baidu Apollo autonomous driving vehicles.

  • Takeaways & Limitations

    The planner was evaluated across different countries, traffic laws, conditions, and crowded urban scenarios, with additional large-scale simulation testing.

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

The Apollo EM planner targets level-4 autonomous driving by combining safety, ride experience, and scalable multilane and lane-level planning. It compares parallel lane-level trajectories and uses Frenet-frame optimization to address lane changes, traffic rules, obstacles, and smoothness.

  • I. INTRODUCTION: Apollo’s motion planner generates safe and smooth trajectories for the vehicle control module from map, perception, localization, and prediction information.The planner receives synchronized environmental information and produces trajectories while considering traffic regulations and obstacle interactions.
  • I. INTRODUCTION: Safety considerations include traffic regulations, planning-range coverage, cycle-time efficiency, and emergency response.The system targets at least eight seconds or 200 meters of planning range and describes a 100 ms emergency reaction time.
  • I. INTRODUCTION: Ride experience is evaluated through scenario coverage, traffic regulation compliance, and trajectory smoothness across simple and complicated driving scenarios.The targeted scenarios include multilane driving and heavy traffic, while comfort is generally measured by trajectory smoothness.
  • I. INTRODUCTION: The Apollo EM planner uses an EM-type iterative algorithm with multilane, path-speed iterative, traffic-rule, and decision-combined design.The planner is presented as targeting both safety and ride experience.
  • I. INTRODUCTION: The multilane strategy handles passive and nonpassive lane changes by generating candidate lane trajectories in parallel and selecting one using cost and safety rules.Nonpassive changes are routing-triggered; passive changes respond to a blocked default lane.

B. Path-Speed Iterative Algorithm

The lane-level planner addresses constrained path-speed optimization through iterative Frenet-frame processing. It combines rough dynamic-programming solutions and spline-based quadratic programming while separating hard traffic constraints from negotiable obstacle decisions.

  • B. Path-Speed Iterative Algorithm: Lane-level planning formulates trajectory generation in a Frenet frame with time, reducing the problem from direct 3D optimization to path-speed decoupled optimization.The supplied passage identifies lane-level planning as a constrained optimization problem in station-lateral-time coordinates.
  • B. Path-Speed Iterative Algorithm: The planner iteratively uses the previous speed profile to estimate dynamic-obstacle interactions, generates a path, and then optimizes the corresponding speed profile.For high-speed dynamic obstacles, the planner prefers lane changes over nudging for safety reasons.
  • B. Path-Speed Iterative Algorithm: Traffic regulations are treated as non-negotiable hard constraints, while yield, overtake, and nudge decisions remain negotiable by scenario.Decisions are made before producing the smooth trajectory to clarify on-road intentions and reduce the search space.
  • B. Path-Speed Iterative Algorithm: The decision process uses a rough feasible trajectory to measure obstacle interactions and construct a convex feasible space for spline smoothing.Quadratic-programming-based smoothing generates path and speed profiles that follow the decision.
  • B. Path-Speed Iterative Algorithm: Within the EM framework, obstacles are projected onto Frenet and station-time representations, after which path and speed profiles are generated through alternating E- and M-steps.One planning cycle contains two E-steps and two M-steps, with trajectory information carried between cycles.
  • B. Path-Speed Iterative Algorithm: Dynamic programming first supplies rough path and speed solutions and obstacle decisions, while quadratic programming searches within the resulting convex hull for refined spline profiles.The combined procedure addresses the non-convexity of the optimal path and speed solution.

A. SL and ST Mapping (E-step)

The E-step projects static and dynamic obstacles into lane-based Frenet representations, enabling path optimization to reason about obstacle interactions and feasible maneuvers. The path optimizer then uses dynamic programming to select low-cost candidate paths and obstacle decisions from smoothness, obstacle, and lane costs.

  • SL and ST Mapping: Static and dynamic obstacles are projected into SL coordinates using a smooth reference line and the ego vehicle’s previous trajectory.Dynamic-obstacle interactions are marked when ego and obstacle bounding boxes overlap at corresponding times.
  • SL and ST Mapping: The ST projection maps obstacle trajectories onto the generated path to define the feasible region for speed optimization.A cut-in obstacle and an obstacle behind the ego car illustrate how the region constrains feasible speed profiles.
  • DP Path Optimizer: The path optimizer samples Frenet-frame lattice points and connects rows with quintic-polynomial edges whose spacing adapts to speed, road structure, and lane changes.The lattice covers at least 8 seconds or 200 meters for safety considerations.
  • DP Path Optimizer: Dynamic programming evaluates candidate path edges using a linear combination of smoothness, obstacle-avoidance, and lane-cost functionals.The selected candidate path also determines obstacle decisions such as nudging, yielding, or overtaking.
  • DP Path Optimizer: The smoothness cost reflects heading difference, curvature, and curvature derivative, while obstacle cost depends on bounding-box distance and safety thresholds.Obstacle costs distinguish collision, nudge, and sufficiently distant cases.

C. M-Step Spline QP Path

The spline QP path step refines a dynamically programmed path by generating a smooth path inside its feasible tunnel. Linearized boundary and dynamic-feasibility constraints make the spline problem suitable for fast quadratic-programming solution.

  • Spline QP Path: The spline QP path step refines the dynamic-programming path by generating a smooth path within its feasible tunnel.The dynamic-programming result supplies the feasible tunnel used by the refinement step.
  • Spline QP Path: The QP objective balances smoothness against following the dynamic-programming path as a guidance line for obstacle nudging.The guidance line estimates the desired nudging distance.
  • Spline QP Path: QP path constraints bound the spline and its derivatives at sampled station coordinates to enforce road boundaries and dynamic feasibility.The path must also match the ego vehicle’s initial lateral position and derivatives.
  • Spline QP Path: Boundary constraints are linearized for the vehicle’s corners using added half circles, preserving a convex and linear formulation.The linearization is applied to the remaining vehicle corners as well.
  • Spline QP Path: Because the constraints are linear in the spline parameters, a quadratic-programming solver can generate the path very fast.The spline and quadratic-programming details are covered later in the paper.

D. M-Step DP Speed Optimizer

The DP speed optimizer searches the ST graph for a rough speed solution using a cost functional, grids, and dynamic programming. Its output provides a piecewise-linear speed profile and feasible tunnel that guide the subsequent spline QP speed step.

  • DP Speed Optimizer: The DP speed optimizer searches ST-graph grids using a cost functional and dynamic programming.The resulting speed solution is piecewise linear and includes obstacle speed decisions.
  • DP Speed Optimizer: The DP speed result supplies a guidance line for spline QP speed optimization and a feasible tunnel for constructing a convex region.This bridges the rough search result and the later smooth speed-profile optimization.
  • DP Speed Optimizer: The DP speed step optimizes a cost functional within the constraints of the ST graph.The paper presents the cost as the basis for the dynamic-programming search.
  • DP Speed Optimizer: The optimizer’s first cost term encourages the vehicle to follow the designated reference speed when obstacles and traffic-light restrictions are absent.The reference speed is determined by speed limits, curvature, and other traffic regulations.

E. M-Step QP Speed Optimizer

The spline QP speed optimizer converts the rough DP speed profile into a smooth feasible profile. It combines guidance tracking and smoothness objectives with linearized traffic and vehicle-dynamic constraints.

  • QP Speed Optimizer: The spline QP speed step is needed because the piecewise-linear DP speed profile cannot satisfy dynamic requirements.Its pipeline contains a cost functional, linearized constraints, and a spline QP solver.
  • QP Speed Optimizer: The QP speed objective balances distance from the DP guidance profile against acceleration and jerk smoothness.The guidance profile is denoted Sref, while the generated speed profile is represented by S(t).
  • QP Speed Optimizer: The spline optimization enforces boundary, initial-velocity, initial-acceleration, monotonicity, traffic-regulation, and vehicle-dynamic constraints.These constraints define the feasible set for the speed profile.
  • QP Speed Optimizer: The spline solver generates a smooth feasible speed profile that combines with the path profile to produce a trajectory for vehicle control.The resulting trajectory is passed to the control module.

F. Notes on Solving Quadratic Programming Problems

The planner uses compact spline representations for path and speed optimization while handling many safety constraints.

  • Piecewise quintic polynomials represent both path and speed profiles.The spline generally contains 3 to 5 polynomials with approximately 30 parameters.
  • Approximately 100 locations or time points are evaluated, producing more than 600 constraints.

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

The EM planner combines DP’s coarse search with QP’s convex optimization to address non-convex planning, then iteratively refines trajectories across planning cycles. A dynamic-obstacle case study illustrates scenario-dependent iteration and a final trajectory that slows to nudge the obstacle before accelerating.

  • G. Notes on Non-convex Optimization With DP and QP: DP alone can choose a feasible but suboptimal obstacle-nudging path because its sampled candidates are limited by the processing-time grid.
  • G. Notes on Non-convex Optimization With DP and QP: QP requires a prior obstacle decision, such as nudging left or right, following, or overtaking, to formulate its constraints.Random or rule-based decisions can make QP susceptible to failure or local minima.
  • G. Notes on Non-convex Optimization With DP and QP: DP provides a rough grid-based solution, while QP searches for an optimal solution within the resulting convex region.The convex region is intended to most likely contain global optima.
  • IV. CASE STUDY: The EM planner iterates within and between planning cycles to generate an optimal trajectory when an oncoming dynamic obstacle enters the vehicle’s path.The case assumes both vehicles travel at 10 meters per second in opposite directions.
  • IV. CASE STUDY: The demonstrated trajectory slows to nudge the obstacle at S=30 m, then accelerates after passing it.The resulting behavior is described as similar to how human drivers may handle the scenario.
  • IV. CASE STUDY: The planner does not always require exactly four planning steps; more complicated environments may require more steps.

V. COMPUTATIONAL PERFORMANCE

The EM planner reduces computational complexity by decoupling station-lateral-speed optimization and is designed to remain efficient in complicated multi-obstacle scenarios. Closed-loop testing covered 3,380 hours and approximately 68,000 kilometers as of May 16th, 2018.

  • Computational complexity: O(n(M+N)) computational complexity results from splitting the three-dimensional station-lateral-speed problem into station-lateral and station-speed problems.The planner therefore reduces computational complexity relative to solving the full three-dimensional problem.
  • Multi-obstacle planning: Light-decision planning addresses complicated multi-obstacle scenarios without requiring predetermined decisions for every obstacle.Heavy-decision methods may fail when obstacle interactions are difficult to describe or when multiple obstacles block the road.
  • Safety and passability: The planner is designed to address the safety-passability trade-off and improve passability while resolving inconsistencies between potential decisions and planning.The manuscript illustrates lane changing as a case where stricter rules can increase safety but reduce passability.
  • Evaluation: 3,380 hours and approximately 68,000 kilometers (42,253 miles) of closed-loop testing were completed in Baidu Apollo vehicles by May 16th, 2018.Testing included different countries, traffic laws and conditions, including crowded urban scenarios in Beijing and Sunnyvale; simulation testing exceeded one-hundred-thousand hours and a million kilometers.
  • Availability: The planning algorithm is available in the Apollo planning repository.The cited repository link is provided in the manuscript.

APPENDIX 1

The appendix formulates spline smoothing as a quadratic program over piecewise polynomial bases. Its objective balances guideline adherence and smoothness under linearized constraints, including boundary, continuity and monotonicity requirements.

  • Spline representation: The smoothing spline f(x) is represented by piecewise polynomial functions defined over knots x0, x1, ..., xn.Each segment has polynomial coefficients, and the full spline parameter vector concatenates the segment coefficients.
  • Quadratic-programming formulation: The spline QP combines a quadratic objective functional, linearized constraints and a quadratic programming solver.The optimization is described as rapidly and stably solvable under a quadratic convex objective and linearized constraints.
  • Constraints: Linear constraints impose boundary bounds, derivative smoothness across spline knots and monotonicity conditions for the speed smoother.The monotonicity constraint guarantees that the path is monotonic at specified points.
  • Matrix form: The spline optimization uses derivative coefficient vectors and block-diagonal matrix representations to express the functionals in quadratic-programming form.The appendix introduces coefficient variables and matrix representations for the piecewise polynomial segments and their derivatives.

k x(0)g(x) + (g(x))2)dx

The appendix expresses the spline objective through integral functionals and relates the formulation to prior work on multipolicy decision-making for autonomous driving.

  • Functional formulation: The appendix represents a spline functional through integrals involving derivative-related matrix terms and the guideline function.The matrix representation contributes to the quadratic form of the objective with respect to the spline parameter vector.
  • Related work: The cited related work addresses multipolicy decision-making in dynamic, uncertain autonomous-driving environments.The references include a 2015 ICRA paper and a 2015 Robotics: Science and Systems paper.
Loading 1807.08048v1…