PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles

Brian Paden, Michal Cap, Sze Zheng Yong, Dmitry Yershov, Emilio Frazzoli

arXiv:1604.07446v1cs.RO

TL;DR

Autonomous vehicles must plan motion through dynamic urban environments and execute it robustly through feedback control. This paper surveys proposed planning and control methods, comparing their performance, assumptions, mobility models, and computational requirements to inform system-level design.

  • Problem

    Autonomous driving requires safety-critical motion planning and feedback control for operation among other vehicles and pedestrians.

  • Method

    The paper surveys decision-making, motion-planning, and feedback-control techniques, emphasizing their performance, computational requirements, and compatibility for system-level design.

  • Results

    The survey identifies compatibility and computational tradeoffs among planning and control choices rather than reporting a single algorithmic performance result.

  • Takeaways & Limitations

    System design must integrate planning and control methods whose interactions are semantically valid and computationally efficient.

  • Takeaways & Limitations

    Kinematic models suit low-speed urban driving but permit instantaneous steering-angle changes that can produce problematic planned motions.

Abstract

from arXiv · show

Self-driving vehicles are a maturing technology with the potential to reshape mobility by enhancing the safety, accessibility, efficiency, and convenience of automotive transportation. Safety-critical tasks that must be executed by a self-driving vehicle include planning of motions through a dynamic environment shared with other vehicles and pedestrians, and their robust executions via feedback control. The objective of this paper is to survey the current state of the art on planning and control algorithms with particular regard to the urban setting. A selection of proposed techniques is reviewed along with a discussion of their effectiveness. The surveyed approaches differ in the vehicle mobility model used, in assumptions on the structure of the environment, and in computational requirements. The side-by-side comparison presented in this survey helps to gain insight into the strengths and limitations of the reviewed approaches and assists with system level design choices.

I. INTRODUCTION

The paper surveys hierarchical decision making for self-driving vehicles, focusing on planning and control for highly automated urban systems. It situates these problems within the development, potential benefits, and system-level structure of autonomous driving.

  • Motivation: Driverless vehicles could reduce collisions associated with driver error while improving the safety, accessibility, efficiency, and convenience of transportation.The introduction motivates autonomous driving using reported traffic fatalities, injuries, collisions, and the estimated contribution of driver error.
  • Scope: The survey focuses on decision making, motion planning, and control for automation levels 3 and above, while omitting perception.Perception is excluded from scope and redirected to other surveys.
  • Decision-making hierarchy: Contemporary autonomous-driving decision making is typically organized into route planning, behavioral decision making, local motion planning, and feedback control.The hierarchy partitions route selection, local driving-task decisions, feasible motion generation, and reactive execution correction.
  • Motion planning: Motion planning translates selected behaviors into dynamically feasible, comfortable, collision-free paths or trajectories that low-level controllers can track.The motion planner operates after behavioral selection and before feedback control.
  • Behavioral decision making: The behavioral layer selects context-appropriate actions such as stopping at intersections and yielding to other vehicles, bicycles, and pedestrians.Behavior is modeled using finite-state-machine approaches with transitions governed by perceived driving context.
  • Behavioral decision making: Urban driving requires predicting the intentions and future trajectories of other vehicles, bicycles, and pedestrians under uncertainty.The surveyed prediction techniques include machine-learning approaches such as Gaussian mixture models and Gaussian process regression.

A. The Kinematic Single-Track Model

The kinematic single-track model represents a car’s planar motion with no-slip wheel constraints and a steerable front wheel. It is useful for low-speed urban planning but can permit impractical instantaneous steering changes.

  • Model structure: The model represents a planar car as two wheels connected by a rigid link, with no wheel slip and a steerable front wheel.These assumptions capture the car’s inability to move laterally without simultaneously moving forward.
  • Model structure: The configuration uses vehicle position and heading, with rear and front wheel contact points constrained to move along their wheel orientations.The rear and front no-slip constraints are expressed through differential equations involving θ and the front steering angle δ.
  • Controls: Planning and control select the front steering angle δ and rear-wheel forward speed vr within mechanical and acceptable operating ranges.The model can instead use heading rate ω as a control-related simplification.
  • Model variants: The unicycle, Dubins-car, and Reeds-Shepp variants simplify the model further by using a single wheel or fixed forward and reverse speeds.Dubins and Reeds-Shepp models provide analytically characterized minimum-time or minimum-length paths in their respective settings.
  • Applicability and limitations: Kinematic models suit low-speed applications such as parking and urban driving because inertial effects are small relative to no-slip mobility limits.Their major drawback is permitting instantaneous steering-angle changes, which can make generated motions problematic.
  • Applicability and limitations: Steering continuity can be imposed by integrating a commanded steering rate, but the resulting higher-dimensional model can complicate planning and control.The augmented model also permits explicit steering-rate limits.

B. Inertial Effects

When acceleration makes the no-slip assumption invalid, vehicle models incorporate rigid-body momentum, tire slip, and nonlinear tire–ground forces. These models support planning and control but remain less detailed than models used for lower-level vehicle systems.

  • Inertial effects: Large acceleration invalidates the no-slip assumption, motivating a rigid-body model in which vehicle acceleration is proportional to tire-generated ground forces.The model governs both translational and rotational motion through the net tire forces and their moments.
  • Tire slip: Tire slip velocity combines wheel-center velocity with wheel angular velocity, so it can differ from the wheel-center velocity used in basic kinematics.For each tire, the slip velocity is expressed as s_r = ṗ_r + ω_r × R and s_f = ṗ_f + ω_f × R.
  • Tire forces: Traction force depends on tire slip, normal force, and a nonlinear friction model, with the same formulation applying to front and rear tires.The traction force is anti-parallel to slip and has magnitude proportional to normal force with nonlinear dependence on normalized slip.
  • Tire forces: The peak of the tire force map defines a friction circle representing the maximum force norm a tire can exert in any direction.The friction-circle interpretation follows from rotational symmetry of the force model together with the peak in the tire-friction curve.
  • Model scope: The surveyed vehicle models suit motion planning and control, whereas electronic stability control and active suspension typically require more sophisticated chassis, steering, and drivetrain models.The survey therefore distinguishes planning-oriented vehicle models from models used by lower-level control systems.

IV. MOTION PLANNING

Motion planning computes feasible vehicle motion from an initial configuration to a goal while accounting for obstacles, vehicle constraints, and objectives. The survey distinguishes path and trajectory formulations and reviews the computational trade-offs behind approximate planning methods.

  • Motion planning: Motion planning generates safe, comfortable, dynamically feasible, collision-free motion from a current configuration to a goal while satisfying vehicle constraints.The planner may optimize travel time, hazard, comfort, or related objectives.
  • Path and trajectory planning: A path is parameterized by progress along configuration space, whereas a trajectory is time-parameterized and prescribes how vehicle configuration evolves over a planning horizon.Trajectory planning directly represents vehicle dynamics and dynamic obstacles; path planning leaves timing to another layer or a chosen velocity profile.
  • Path planning: Optimal path planning searches for a constraint-satisfying path from the initial configuration to the goal that minimizes a specified cost functional.The formal problem includes free configurations, differential constraints, and a cost J(σ).
  • Complexity: Finding optimal paths under holonomic and differential constraints is PSPACE-hard, so research emphasizes approximate methods and tractable problem subsets.For car-like robots among polygonal obstacles, shortest curvature-bounded path planning is NP-hard, while obstacle-free bounded-curvature cases admit specialized solutions.
  • Planning approaches: Variational methods converge rapidly to locally optimal solutions but generally require a suitable initial guess to reach globally optimal solutions.Graph-search methods avoid local minima but optimize only over paths induced by a finite graph; incremental sampling methods build reachability graphs from sampled configurations.

C. Variational Methods

Variational trajectory planning converts an infinite-dimensional optimization problem into a finite-dimensional nonlinear program. Direct methods use finite-dimensional trajectory representations, while penalty and barrier formulations handle constraints through augmented costs.

  • Trajectory optimization: Trajectory optimization represents the trajectory using basis functions and coefficient variables so existing nonlinear programming methods can be applied.Numerical integrators with collocation and pseudospectral methods are identified as common approximation schemes.
  • Method comparison: Table I compares path-planning methods using properties such as completeness, optimality, computational complexity, and assumptions on collision checking or sampling.Its legend qualifies these properties by graph-induced path sets, algorithm variants, approximation tolerance, and differential-constraint assumptions.
  • Trajectory optimization: The converted nonlinear program enforces initial and terminal conditions together with equality and inequality constraints on the trajectory.These constraints encode holonomic and differential requirements over the planning horizon.
  • Constraint handling: Penalty methods replace constraints with an augmented cost and can be initialized with any trajectory, whereas barrier methods preserve feasible local minima but require feasible initialization.Barrier costs become infinite at or beyond the inequality boundary and diverge as the boundary is approached.
  • Direct methods: Direct variational methods restrict the approximate solution to a finite-dimensional subspace of the trajectory-function space.This finite-dimensional restriction enables numerical optimization over a parameterized trajectory rather than over arbitrary functions.

1) Numerical Integrators with Collocation:

Collocation-based trajectory optimization enforces approximate dynamics and state constraints at discrete points, using interpolation and numerical integration to form a nonlinear program. Related variational and graph-based approaches offer different trade-offs between local convergence, global search, and feasible vehicle motion.

  • Collocation formulation: Collocation enforces approximate dynamics and state constraints at a discrete set of time points.This produces nonlinear equality constraints for dynamics and nonlinear inequality constraints for trajectory states.
  • Numerical integration: Numerical integration approximates the trajectory between collocation points with an interpolating function.Piecewise linear interpolation yields Euler integration, while higher-order polynomials yield Runge–Kutta methods.
  • Numerical integration: Adams approximation is reported to improve numerical accuracy and convergence rates over Euler’s method for optimizing trajectories with a detailed vehicle model.
  • Pseudospectral methods: Pseudospectral schemes use Legendre or Chebyshev polynomial bases and typically converge faster than basic collocation methods.
  • Alternative planning strategies: Variational methods are limited by convergence to local minima, motivating graph-search methods that seek minimum-cost paths through discretized configuration spaces.
  • Lane graphs: Hand-crafted lane graphs encode desired lane and intersection paths but require more general planning when unexpected obstacles block encoded routes.

2) Geometric Methods:

Geometric methods construct roadmaps from explicit obstacle models and can provide complete or exact solutions in suitable settings, but they are limited by vehicle differential constraints and costly geometric modeling. Sampling-based methods instead use steering, collision checking, and sampled configurations to explore reachability without an explicit free-space geometry.

  • Geometric methods: Geometric path planners represent obstacles as polygons or polyhedra and can exploit exact algorithms when differential constraints are absent.For traditionally steered cars, omitting minimum-turn-radius constraints limits direct applicability.
  • Geometric methods: Roadmaps such as vertical cell decompositions, generalized Voronoi diagrams, and visibility graphs can yield complete planning algorithms for suitable geometric free spaces.For general semi-algebraic configuration spaces, cylindrical algebraic decomposition has single-exponential complexity in configuration-space dimension and remains largely theoretical.
  • Geometric methods: Geometric models are usually unavailable directly from autonomous-driving sensor data, while vehicle requirements often exceed a simple curvature constraint.These limitations help motivate sampling-based techniques.
  • Sampling-based methods: Sampling-based planners use steering and collision checking to connect sampled configurations with feasible path segments.Steering may be random, heuristic, or exact, depending on the vehicle and planning context.
  • Sampling-based methods: Recursive motion primitives can produce trees or lattice-like graphs, with lattice-generating primitives distributing vertices more uniformly across configuration space.The figure contrasts 90° primitives that form a lattice with 89° primitives that create looping branches and cover less area.
  • Sampling-based methods: Probabilistic Roadmaps use random sampling and can be run in an anytime fashion, with theoretical probabilistic completeness and asymptotic optimality under straight-line connections.

4) Graph Search Strategies:

Graph-search strategies find paths on discretized configuration spaces, while incremental methods refine or expand these discretizations over time. Their guarantees and efficiency depend on heuristic guidance, reuse of prior search, graph resolution, and the coverage of feasible motions.

  • Graph search: Dijkstra’s algorithm searches for shortest paths from a source, while admissible-heuristic A* is guaranteed to return an optimal solution.
  • Graph search: Weighted A* can obtain bounded-suboptimal paths with less computational effort by inflating the heuristic.
  • Real-time replanning: D*, Focussed D*, and D* Lite efficiently recompute paths after local graph changes caused by updated sensory information.
  • Anytime search: Anytime search methods return an initial suboptimal path quickly and improve it as additional computation becomes available.
  • Graph-search limitations: Graph discretization can produce paths significantly longer than the true configuration-space shortest path, and fixed primitives may exclude feasible or near-optimal paths.Any-angle methods and Field D* address related discretization effects through shortcuts or interpolation.
  • Incremental planning: Incremental planners progressively refine the configuration-space discretization, providing feasible solutions when possible and potentially unbounded computation time.Incremental optimal planners seek a sequence of improving solutions that converges to an optimal path.
  • Incremental tree-based methods: RRT explores reachable space by expanding randomly selected tree vertices, while RRT* rewires nearby vertices to achieve asymptotic optimality.The neighborhood radius scales with (log n/n)^(1/d), using an instance-dependent constant γ.

F. Practical Deployments

Vehicle control stabilizes planned paths or trajectories despite modeling error and uncertainty, with different controllers offering distinct trade-offs in computational cost, curvature tracking, and stability. Practical evaluation highlights both effective controller classes and limitations caused by discontinuities, finite-horizon behavior, and model complexity.

  • Control objectives: Feedback control stabilizes a reference path or trajectory against modeling error and uncertainty in motion execution.
  • Path stabilization: Path stabilization requires bounded tracking error, convergence of tracking error to zero, and convergence of progress along the path to a nominal rate.
  • Path-stabilization limitations: Nearest-point path feedback can create a discontinuous closed-loop vector field when the reference path self-intersects or is not differentiable.Such discontinuities may cause unpredictable behavior if the executed trajectory encounters them.
  • Trajectory stabilization: Trajectory stabilization is more straightforward than path stabilization, but its controllers are prone to performance limitations.
  • Predictive control: Predictive control strategies are effective for more complex vehicle models and can support both path and trajectory stabilization.

A. Path Stabilization for the Kinematic Model

Kinematic path stabilization includes pure pursuit and rear-wheel feedback controllers. Pure pursuit is simple but has curvature-dependent tracking limitations, while rear-wheel feedback provides local convergence under path and motion assumptions.

  • Pure pursuit: Pure pursuit fits a circle through the vehicle and a lookahead point on the reference path, with the circle tangent to the vehicle heading.The lookahead distance is L, and the resulting circle curvature determines the commanded heading rate.
  • Pure pursuit: Pure pursuit solves the tracking problem for zero-curvature paths at constant speed but has a small steady-state tracking error for fixed nonzero curvature.
  • Pure pursuit: Pure pursuit is undefined when the vehicle is farther from the path than L and may deviate when reference curvature changes, especially during parking maneuvers.Increasing speed also makes the heading-rate command more sensitive to the feedback angle; scaling L with speed is a common fix.
  • Rear wheel position based feedback: Rear-wheel feedback uses transverse path error and heading error, with the path tangent and tracking-error geometry defining the feedback variables.The signed transverse error distinguishes whether the vehicle lies to the left or right of the path.
  • Rear wheel position based feedback: Choosing g1(vr, θe, t) = kθ|vr| with ke > 0 yields local exponential convergence at a rate independent of vehicle speed when vr ≠ 0.The controller also remains stable regardless of the sign of vr, making it suitable for reverse driving, while requiring a twice continuously differentiable path.

3) Front wheel position based feedback:

Front-wheel position feedback regulates the front wheel relative to the path and can achieve local exponential stabilization. Compared with pure pursuit, it tracks high-curvature regions more effectively, subject to path regularity and forward-motion limitations.

  • Front wheel position based feedback: The steering law sets δ = arcsin(−ke/vf) − θe so that the transverse error obeys ˙e = −ke and converges exponentially when |ke/vf| ≤ 1.
  • Front wheel position based feedback: The front-wheel feedback angle combines a feed-forward nominal steering term with a heading-error term, rather than representing heading error alone.It remains nonzero even under perfect path tracking.
  • Front wheel position based feedback: The control law is undefined when |ke/vf| > 1, and local stabilization requires a continuously differentiable path.
  • Front wheel position based feedback: The front-wheel controller steers so the front wheel’s velocity component normal to the path is proportional to distance from the path.This local strategy yields local exponential convergence.
  • Front wheel position based feedback: In high-curvature regions, pure pursuit deviates from the reference path, whereas rear- and front-wheel controllers converge to and track the path.The comparison is based on the qualitative tracking results shown in Figure V.5.

1) Control Lyapunov based design:

Control-Lyapunov-based design expresses tracking error in a vehicle-fixed frame and shapes the closed-loop error dynamics through feedback. Its local exponential stability result depends on constant reference speed and angular rate.

  • Control Lyapunov based design: The method defines configuration error in a coordinate frame fixed to the car using the reference trajectory and its velocity.
  • Control Lyapunov based design: The feedback assignment transforms the configuration-error dynamics into closed-loop equations for position and heading error.
  • Control Lyapunov based design: For k1, k2, k3 > 0 with constant reference speed and angular rate, stability is verified using a Lyapunov function with a negative semi-definite derivative.
  • Control Lyapunov based design: The control law provides local exponential stability, but a time-invariant system requires ωref and vref to remain constant.A related backstepping controller addresses finite-domain uniform local exponential stability with time-varying references.

C. Predictive Control Approaches

Model predictive control repeatedly solves a short-horizon motion-planning problem and applies only part of the resulting control. Its generality supports constraints and nonlinear models, but real-time computation often motivates linearization.

  • Predictive control approaches: More accurate vehicle models are useful for slippery roads or emergency maneuvers, but their added detail complicates controller design.
  • Predictive control approaches: MPC solves motion planning over a short horizon, applies a short interval of open-loop control, and replans repeatedly during execution.
  • Predictive control approaches: The MPC formulation discretizes a continuous-time vehicle model and optimizes stage and terminal penalties subject to state and input constraints.Constraints can encode allowable states, obstacles, excessive tire slip, and actuator limits.
  • Predictive control approaches: Time discretization produces approximate solutions, with the mismatch between the discrete and continuous systems reported as O(∆t).
  • Predictive control approaches: Implementing MPC on a driverless car requires solving the optimization problem several times per second, creating a major computational obstacle.When the model and constraints yield a quadratic program, polynomial-time interior-point methods become available; complex models are often linearized to exploit this.
  • Predictive control approaches: Linearizing perturbation dynamics around a reference trajectory produces a linear time-varying system that supports quadratic-objective MPC formulations.Unconstrained cases can admit semi-closed-form dynamic-programming solutions based on an N-step matrix recursion.

1) Unconstrained MPC with Kinematic Models:

Unconstrained predictive control approaches trade computational simplicity against model fidelity and robustness across vehicle operating conditions. The survey emphasizes that controller and motion-planning choices must be assessed together for computational compatibility.

  • Unconstrained MPC with Kinematic Models:: Unconstrained MPC can provide semi-closed-form solutions with minimal computational requirements when using a CARIMA model.A related time-varying linear quadratic programming approach was also considered with a linearized kinematic model.
  • Unconstrained MPC with Kinematic Models:: A predictive controller using a center-of-mass linear dynamic model and approximate steering model was validated with detailed steering and 27-degree-of-freedom vehicle models.
  • Unconstrained MPC with Kinematic Models:: 20 Hz control stabilized a simulated emergency maneuver on icy conditions, but computation time was three times the sample time with a two-step horizon.The reported result concerns a full nonlinear predictive control strategy using a tire model.
  • Unconstrained MPC with Kinematic Models:: Linearized lateral dynamics are valid near small tracking errors, but a single operating-point model is difficult to rely on across normal driving conditions.The lateral-error example is linearized around θe = 0 and e = 0.
  • Unconstrained MPC with Kinematic Models:: Gain scheduling parameterizes kp by forward speed to keep closed-loop poles fixed, addressing oscillatory high-speed response and poor low-speed response.This remedy is categorized as control design for linear parameter-varying models.
  • Unconstrained MPC with Kinematic Models:: System-level design must balance planner detail, controller robustness, and computational cost because choices in one layer constrain compatible choices in another.The survey presents performance and computational requirements as references for assessing these compatibility and tradeoff decisions.
Loading 1604.07446v1…