An Efficient Spatial-Temporal Trajectory Planner for Autonomous Vehicles in Unstructured Environments

As a fundamental component of autonomous driving systems, motion planning has garnered significant attention from both academia and industry. This paper focuses on efficient and spatial-temporal optimal trajectory optimization in unstructured environments using compact convex approximations of vehicle shapes. Conventional approaches typically model the task as an optimal control problem by discretizing the motion process in state configuration space. However, this often results in a tradeoff between optimality and efficiency since generating high-quality motion trajectories often requires high-precision discretization of the dynamic process, which imposes a substantial computational burden. To address this issue, we leverage the differential flatness property of car-like robots to simplify the trajectory representation and analytically formulate the spatial-temporal joint optimization problem with flat outputs in a compact manner, while ensuring the feasibility of nonholonomic dynamics. Moreover, we achieve efficient obstacle avoidance with a collision-free driving corridor for unmodelled obstacles and signed distance approximations for dynamic moving objects. We present comprehensive benchmarks with State-of-the-Art methods, demonstrating the significance of the proposed method in terms of efficiency and trajectory quality. Real-world experiments verify the practicality of our algorithm. We will release our codes for the research community.

I. Introduction

Autonomous driving has become one of the hottest research topics in recent years because of its vast potential social benefits. It reveals a huge demand for robust and collision-free motion planning in complex and high-dynamic environments. Lightweight and efficiency are strongly demanded in real-world applications to ensure rapid response to dynamic and unstructured environments with limited onboard computing power. Motion planning for autonomous driving aims to generate a comfortable, low-energy, and physically feasible trajectory that makes the ego vehicle reach end states with collision-free guarantees and designed velocities in constrained environments. Classical trajectory planning methods can be broadly categorized into two main groups: sampling-based and optimization-based. Sampling-based methods typically generate samples in a discretized state space and evaluate the cost function of these samples to obtain the path. Conversely, optimization-based methods formulate trajectory planning as an optimization problem and utilize gradient-based numerical solvers to find the optimal solution. While sampling-based methods are theoretically resolution-complete and can explore the entire state space to obtain the optimal solution, this often requires computationally expensive resources. Therefore, in this paper, we focus on optimization-based methods, which can achieve accurate and effective convergence to local optimal solutions by allowing trajectories to have strong deformation abilities in continuous space. However, generating feasible and high-quality trajectories online in arbitrarily complex scenarios is still challenging. In fact, ideal motion planning for autonomous driving typically faces three challenging problems: 1)

Nonholonomic Dynamics: Unlike holonomic robots such as omnidirectional mobile robots and quadrotors, autonomous vehicles must consider nonholonomic constraints during trajectory planning. Moreover, the strong non-convexity and nonlinearity of nonholonomic dynamics make it difficult to ensure the physical feasibility of states and control inputs in highly constrained environments.

2)

Precise Obstacle Avoidance: Collision-free constraints have to balance the accuracy of object shape modeling while maintaining an affordable computation time for online vehicle (re)planning. In real-world applications, rough approximation of the ego vehicle shape, such as one or multiple circular covering of the ego vehicle, always reduces the solution space, which introduces conservativeness or even fails to find a collision-free solution in extremely cluttered areas. On the other hand, taking into account the true physical shape of obstacles in Euclidean space, which we refer to as “full-dimensional obstacle avoidance,” often increases the complexity of the planning problem, resulting in a significant computational burden.

3)

Trajectory Quality: There is always a tradeoff between computation efficiency and trajectory quality. Common methods that optimize time and space separately reduce a large partition of solution space, especially in tightly coupled spatial-temporal scenarios such as highly dynamic environments. By contrast, spatial-temporal joint optimization can fully utilize the solution space to achieve better trajectory optimality but tends to complicate the optimization problem and reduce the real-time performance.