Search-Based Motion Planning for Performance Autonomous Driving

arXiv:1907.07825 · cs.RO, cs.SY, eess.SY, math.OC · Submitted 2019-07-18 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "Search-Based Motion Planning for Performance Autonomous Driving".

Dev: A search-based motion planning approach is presented to generate suitable reference trajectories for dynamic vehicle states to achieve minimum lap time on slippery roads.

Rosa: First, who's behind it and why it matters.

Title and authors: Rosa: We’ve just touched on the core idea of "Search-Based Motion Planning for Performance Autonomous Driving," which is about using search to find optimal paths on slippery roads by respecting nonlinear dynamics, and I want to start by talking about who put this research together.

Dev: Before we get into the mechanics, let's acknowledge the authors: Zlatan Ajanovic, Enrico Regolin, Georg Stettinger, Martin Horn, and Antonella Ferrara from the Virtual Vehicle Research Center and Graz University of Technology. They are clearly experts in vehicle dynamics and autonomous systems.

Taro: I noticed they’re from a mix of institutions—a university center in Austria and the University of Pavia—which suggests a strong foundation in both theoretical modeling and practical application, which is interesting for this kind of planning work.

Rosa: Right, so they bring together different strengths to tackle this complex problem; it shows how interdisciplinary collaboration can be key when dealing with vehicle dynamics and path planning under these kinds of constraints.

Dev: Their background in control engineering and robotics should give them a good handle on the loop rate considerations we discussed earlier, which is crucial for any system that needs to operate in real-time.

Taro: I think their combined expertise is what allows them to tackle the dual challenge of modeling complex nonlinear dynamics and applying a robust search strategy for performance driving simultaneously.

Rosa: So they’ve built a strong foundation, which sets the stage for how this AI system tackles generating those reference trajectories that aim for minimum lap time on challenging surfaces.

Dev: And given their expertise, I expect the vehicle model they use to be quite detailed, incorporating all those aspects we talked about earlier.

The paper's summary: Rosa: Now let's look at what the paper actually summarizes about "Search-Based Motion Planning for Performance Autonomous Driving." Essentially, it lays out how they use this search method to generate safe and optimal reference trajectories for a vehicle on slippery roads.

Dev: The summary explains that the main goal is to achieve the minimum lap time on empty tracks under low-friction conditions, specifically mentioning gravel road scenarios as an example.

Taro: So it’s not just about getting from point A to B; it’s about optimizing *how* you get there—the driving style itself, which is what makes this performance-oriented.

Rosa: Right, and the summary highlights that the search-based approach allows them to explicitly incorporate a nonlinear vehicle dynamics model as well as constraints on states and inputs for safety and optimality.

Dev: That’s key because it moves beyond simpler models where you might just be dealing with linear approximations that break down when side-slip is high.

Taro: So the paper is essentially showing that a search framework, when coupled with detailed physics, can handle those nonlinear dynamics safely where traditional methods fail.

Rosa: Precisely; they decompose the problem into motion primitives and then use A* search to explore combinations of these primitives guided by a heuristic for minimum lap time.

Dev: And they detail how they create these motion primitives using both a bicycle model and an approximation of the full nonlinear model based on equilibrium states.

The paper's improvements: Rosa: Moving on to the specific improvements proposed in "Search-Based Motion Planning for Performance Autonomous Driving," it suggests several ways this approach can be enhanced beyond what they’ve presented in their initial work.

Dev: One major improvement is the use of a hybrid motion primitive generation strategy, which allows them to switch between models dynamically based on whether they are driving straight or cornering.

Taro: That hybrid approach sounds very practical; it means the system can choose the right tool for the job, which I think is essential when conditions aren't constant.

Rosa: Exactly; they use a bicycle model for mild scenarios and switch to a full nonlinear vehicle model approximation specifically during steady-state cornering maneuvers.

Dev: And they also add constraints on state evolution, limiting the rate of change of velocity and side-slip angle to ensure the resulting trajectories are smooth, not jerky.

Taro: Those rate limits are important for robustness; it means you’re not just planning a theoretically perfect path that might be physically impossible to execute smoothly in practice.

Rosa: Furthermore, they introduce penalization for trajectories near the road sides and penalize nodes that have very few siblings, which helps prune the search space effectively.

Dev: That pruning mechanism is smart; it stops the search from wasting time on parts of the path that are clearly not feasible or don't lead anywhere useful.

Conclusion: Rosa: So to wrap up this discussion on "Search-Based Motion Planning for Performance Autonomous Driving," we’ve seen how this method uses a search framework guided by detailed dynamics to generate trajectories that aim for minimum lap time on slippery roads.

Dev: The main implication is that this approach offers a way to move toward more robust planning methods that explicitly handle nonlinearity in vehicle dynamics, which is important for real-world autonomy.

Taro: I think the biggest impact is showing how detailed model-based planning can lead to better performance metrics than relying solely on simpler, less dynamic approximations.

Rosa: Agreed; it gives us a concrete framework for generating high-performance driving plans that respect the physical limits of the vehicle in challenging environments.

Dev: It's a step toward systems that can manage those complex dynamics with much greater fidelity, even if it still has to work within certain computational constraints.

Taro: For me, it confirms that when you push the modeling complexity up to match the physical reality, you get better results in terms of performance metrics on tricky tasks.

Rosa: So that’s what we have today with this paper; a search-based motion planning for performance autonomous driving is a system built to navigate the limits of vehicle dynamics safely and optimally.

Virtual Vehicle Research Center · Dipartimento di Ingegneria Industriale e dell’Informazione, University of Pavia · Graz University of Technology

cs.RO, cs.SY, eess.SY, math.OC

Submitted: 2019-07-18

Updated: 2019-07-18

Comments: Accepted to IAVSD 2019

DOI: 10.1007/978-3-030-38077-9_134

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 65/100

The gist: A search-based motion planning approach is presented to generate suitable reference trajectories for dynamic vehicle states to achieve minimum lap time on slippery roads.

Key concepts

Motion Primitives: These are small, pre-defined segments of vehicle motion used to build larger trajectories. They are based on a simplified bicycle model for straight driving or approximations of the full nonlinear model for cornering maneuvers, helping manage computational complexity.
Equilibrium States Manifold (ESM): This is a specific set of desired vehicle states calculated offline using the full nonlinear vehicle model and tire friction models. Only reference states within this manifold are considered during search, ensuring that the planned trajectories are physically achievable on gravel roads.
A* Search Framework: The continuous driving problem is treated as a combinatorial optimization task solved by A* search. It systematically explores combinations of motion primitives in a discretized state space, guided by an optimistic heuristic to find the path with the lowest cost (minimum lap time).
Heuristic Function Augmentation: The heuristic function is enhanced beyond simple distance estimation. It includes costs for smooth state evolution, penalizes trajectories near road edges, and avoids areas with very few feasible paths to bias the search toward robust and drivable maneuvers.

Terminology

Motion Primitives — 19× in this paper · explained in 2 episodes
Motion Planning — 16× in this paper
Combinatorial Optimization — 3× in this paper · explained in 2 episodes
Robustness — 3× in this paper · explained in 5 episodes
Steering — 3× in this paper · explained in 2 episodes
Closed-Loop Control — 2× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Magic Formula — 2× in this paper
Reinforcement Learning — 2× in this paper · explained in 4 episodes
Accuracy — 1× in this paper · explained in 1 episode
Curse of Dimensionality — 1× in this paper · explained in 6 episodes
Fidelity — 1× in this paper · explained in 2 episodes
Hybrid Approach — 1× in this paper · explained in 4 episodes
Pruning — 1× in this paper · explained in 4 episodes

Summary

A search-based motion planning approach is presented to generate suitable reference trajectories for dynamic vehicle states to achieve minimum lap time on slippery roads. This method explicitly considers nonlinear vehicle dynamics and constraints, enabling safe and optimal performance in challenging driving scenarios that are difficult for traditional exhaustive search methods.

Problem Formulation and Vehicle Models

The core problem addressed is minimum lap time driving on an empty track under low-friction conditions, such as gravel road. The vehicle is assumed to have a map, localization system, and full state feedback information, including dynamic states and estimates of wheel forces and wheel slips. The road is modeled as flat with static road-tire characteristics but arbitrary shape with constant width.

The vehicle trajectories are generated by concatenating smaller segments called motion primitives, which are based on a model for planar motion defined by six states: [x, y, ψ, v, β, ψ˙]. The evolution of the kinematic states (x and y) is given by equations (1), while the evolution of velocity (v), side-slip angle (β), and yaw rate (ψ˙) is governed by a selected vehicle model. For regular driving situations with small side-slip angles, linearized vehicle models are used. However, for slippery surfaces, this approach is unsuitable due to the effect of β in equation (1) and the complexity of the full nonlinear model, which leads to the curse of dimensionality.

Motion Primitive Generation

To mitigate computational burden when using a full nonlinear vehicle model, motion primitives are generated using two distinct models:

The bicycle model is used for straight-driving/mild-turning scenarios.
A convenient approximation of the full nonlinear model, based on theoretical vehicle equilibrium states during cornering, is employed for steady-state cornering maneuvers.

For cornering, motion primitives are generated based on previously computed vehicle equilibrium states (ESM). To ensure that reference values can be actually reached in a sufficiently short time, two devices are exploited:

Slow varying reference set-points are used to allow the low-level actuator to bring the actual state in proximity of the desired one.
Only reference states belonging to a specific Equilibrium States Manifold (ESM) are considered, which is obtained through offline computation using the full vehicle nonlinear model and tire-road contact forces derived from the Magic Formula (MF) tire friction model for gravel.

Search-Based Trajectory Generation

The continuous driving problem is treated as a combinatorial optimization problem, leading to the use of heuristic search methods like A∗ for automated optimal trajectory generation. The proposed method is a novel A∗ search-based approach to generating trackable references, which is a modified version of previous work. The space of possible trajectories is explored by expanding different combinations of motion primitives in a systematic way, guided by a heuristic function.

The search framework involves:

Constructing a grid via discretization of state variables x.
Expanding the current node using motion primitives to determine child nodes, which are added to the OPEN list if they have a lower cost than existing paths.
Selecting the node with the lowest cost from OPEN and repeating until the horizon is reached or computation time limits are met.

To manage computational time, a hybrid A∗ approach is used, keeping continuous values for expansion without rounding to grid points to prevent accumulation of rounding errors. The planning process can be compensated by introducing Tplan, an upper bound on planning time, allowing execution of the old trajectory while the new one is processed.

Heuristic Function and Trajectory Evaluation

The heuristic function h(n) estimates the cost needed to travel from node n to the goal state (cost-to-go). For minimum lap time, this heuristic is optimistic: it assumes that the vehicle accelerates (with maximum acceleration) in the direction of the road central line until it reaches the maximum velocity, and then maintains it for the rest of time horizon.

To bias expansions towards preferred motion and robustness, the heuristic function is augmented with:

A dynamic states evolution cost to limit the rate of change of references (v, β, ψ˙) for smooth trajectories.
Penalization for trajectories approaching the road side.
Penalization of nodes with fewer siblings to avoid regions where only few trajectories are feasible.

The drivability of a generated trajectory is validated based on vehicle coordinates x, y and yaw angle ψ only, using a Frenet frame where one dimension represents distance along the road (s) and the other deviation from the road centerline (d). The evaluation criteria for minimizing lap time is achieved by maximizing the distance traveled along the road in a defined time horizon, simply by considering the first coordinate in Frenet frame.

Simulations and Results

The concept is evaluated in a Matlab/SIMULINK environment assuming perfect actuation. The trajectory exploration is visualized using Fig.

Improvements for AI systems

Here are the specific improvements that can be made to existing AI systems, based on the methodology described in this research paper:

The core improvement lies in replacing current motion planning methods (which often fail in low-friction/high-slip conditions) with a novel, search-based approach guided by a detailed vehicle dynamics model.

Here are the specific improvements and capabilities of the resulting AI system:

Improved Motion Planning for Low-Friction Scenarios:

The system can now generate optimal trajectories on slippery surfaces (like gravel roads) that explicitly account for nonlinear vehicle dynamics, unlike current methods constrained by linear models or short prediction horizons.

Transition from Sustained to Continuous Driving:

The AI system moves beyond modeling only sustained drift or transient drift parking. It can now plan for continuous driving, enabling the vehicle to fluidly enter and exit drifting maneuvers and seamlessly switch between left and right turns on a complex track with varying curvature radii.

Hybrid Motion Primitive Generation:

The system utilizes two distinct motion primitives simultaneously:

A bicycle model for low-slip operations (entry, exit, close-to-straight driving).
A full nonlinear vehicle model for steady-state cornering maneuvers.

This allows the AI to select the most appropriate dynamic model for any given segment of the planned path, ensuring accuracy where needed and computational efficiency where possible.

Equilibrium State Manifold (ESM) Guidance:

The search space is constrained not just by kinematics but by a pre-computed Equilibrium States Manifold derived from full nonlinear vehicle and tire-road contact force models (using the Magic Formula). This ensures that all generated reference states are physically reachable within a short time frame, preventing the planner from suggesting impossible or unstable maneuvers.

Heuristic Optimization for Performance:

The A∗ search is guided by a sophisticated heuristic function designed specifically for minimum lap time. This heuristic estimates the maximum possible travel distance under optimistic acceleration/speed assumptions, biasing the search towards high-performance paths rather than merely finding any feasible path.

Hybrid A∗ Search Framework:

The planning algorithm employs a hybrid A∗ approach. It uses a grid-like search for global pathfinding but maintains continuous state values during node expansion to avoid discretization errors. Furthermore, it incorporates time compensation using a guaranteed upper bound on planning time (Tplan), ensuring that the trajectory is ready before the required execution step, enabling real-time replanning in an MPC-like scheme.

Robust Trajectory Regularization:

The search includes explicit constraints to maintain road drivability (checking deviation from the centerline) and to prevent excessive state changes (limiting velocity deviation between successive nodes, ∆v/Ts < amax). This results in smoother, more robust trajectories that are less likely to cause the vehicle to dangerously approach obstacles or violate physical limits.

This improved AI system can perform:

Optimal Racing/Performance Driving: Achieve the minimum lap time on tracks with mixed surfaces (e.g., gravel).
Complex Maneuver Execution: Execute sequences involving aggressive drifting, trail-braking, and rapid switching between sharp left and right turns.
Continuous Path Generation: Plan entire continuous driving routes rather than just discrete waypoints or simple sustained maneuvers.
Safe and Feasible Control: Generate trajectories that adhere strictly to the physical limits of the vehicle (based on tire friction models) while maximizing speed, leading to safer and more aggressive autonomous driving behavior in challenging environments.