Abstract
Real-time path planning is a critical component of autonomous driving systems, requiring the solution of complex Quadratic Programming (QP) problems under strict latency constraints. Traditional hardware platforms often struggle to balance throughput, latency, and power efficiency for these tasks. This paper presents a specialized FPGA-based accelerator that leverages the structural sparsity inherent in path-planning matrices. By integrating hardware/software co-design with multi-level dataflow pipelining, the proposed framework achieves an average planning latency of 17ms. Experimental results on an AMD ZCU102 FPGA demonstrate significant performance gains, outperforming high-end CPUs, GPUs, and existing FPGA solvers while providing nearly 400× better energy efficiency than GPU-based implementations.
Introduction
Path planning serves as the "brain" of autonomous vehicles, responsible for generating safe and smooth trajectories in dynamic environments. This process typically involves solving Quadratic Programming (QP) optimization problems. However, the computational intensity of QP solvers presents a significant challenge for real-time deployment. CPUs often fail to meet the sub-100ms latency requirements necessary for safety in complex scenarios. While GPUs offer high throughput, they are hindered by high power consumption and kernel launch overheads. Existing FPGA-based solvers, though more efficient, often treat matrices as general sparse entities, failing to exploit the specific mathematical structure of trajectory optimization.
This work addresses these limitations through a hardware-software co-design that optimizes the path-planning pipeline across algorithmic, hardware, and system levels.
Methodology
The proposed framework employs a multi-tiered optimization strategy to streamline the path-planning process.
Algorithmic Level: ADMM and PCG
The framework utilizes the Alternating Direction Method of Multipliers (ADMM) to decompose the QP problem into smaller, manageable sub-problems. To solve the resulting linear systems, the authors implement a Preconditioned Conjugate Gradient (PCG) method. PCG is chosen for its high degree of parallelizability, making it ideal for hardware acceleration.
Hardware Level: Structural Sparsity Awareness
A key observation of this research is that path-planning matrices exhibit a predictable, repeating block structure rather than random sparsity. Unlike general sparse solvers that use Compressed Sparse Column (CSC) or Row (CSR) formats—which require complex and costly indexing—the proposed design utilizes this "structural sparsity." Custom Sparse Matrix-Vector Multiplication (SpMV) and Sparse Matrix-Matrix Multiplication (SpMM) units are designed to store and compute only non-zero elements using hard-coded memory access patterns, significantly reducing resource utilization and eliminating indexing overhead.
Dataflow Level: Operator Fusion and Pipelining
To minimize memory bottlenecks, the architecture employs "Operator Fusion." This technique allows data to stream directly between operators (e.g., from matrix multiplication to vector addition) without the need for intermediate write-backs to global memory. Furthermore, to address the latency-carrying dependencies inherent in floating-point addition on FPGAs, the design implements eight independent accumulation paths. These paths are merged at the final stage, enabling a fully pipelined design with an Initiation Interval (II) of 1.
System Level: HW/SW Co-Design
The end-to-end pipeline is distributed between the CPU and the FPGA. The CPU handles reference path generation, while the FPGA is dedicated to the heavy-duty QP optimization. This concurrent execution model effectively doubles the overall system throughput compared to sequential processing.
Experimental Evaluation
The design was implemented on an AMD ZCU102 FPGA and evaluated using a 140m × 140m gridmap. The testing suite included 40 path-planning tasks categorized by difficulty (Easy, Medium 1, Medium 2, and Hard), where difficulty was defined by the curvature and complexity of the required maneuvers, such as U-turns in confined spaces.
Results and Discussion
The accelerator achieved an average planning time of 17ms, a substantial improvement over the 62ms to 1.08s range reported in prior sampling-based or neural-network-based approaches.
Key performance comparisons include:
- Latency: The design is 1.48× faster than the state-of-the-art FPGA-based solver, 2.89× faster than a high-end Intel i7 CPU, and 1.56× faster than an NVIDIA RTX 3090 GPU.
- Energy Efficiency: The system delivered 19.2 Samples/J, representing a nearly 400× improvement in energy efficiency over the RTX 3090 GPU.
- Throughput: System-level pipelining resulted in a 2× improvement in end-to-end throughput.
A critical factor in this performance was the optimization of the ADMM penalty parameter (ρ). Through simulation-based analysis, the authors identified a "sweet spot" for ρ that balances the convergence rates of the outer optimization loop and the inner PCG loop, minimizing the total number of iterations required.
Conclusion
This paper demonstrates that by tailoring hardware architecture to the specific mathematical structure of path-planning problems, it is possible to achieve significant gains in both latency and energy efficiency. The combination of structural sparsity awareness, operator fusion, and HW/SW co-design provides a robust framework for real-time autonomous vehicle navigation. Future work will focus on extending the accelerator to handle high-speed dynamic obstacles and exploring the scalability of the architecture for larger-scale trajectory optimization problems.
Summary updated