A High-Speed, Area-Efficient FPGA Accelerator for the $A^{*}$ Algorithm

Path planning is a computationally intensive task in real-time robotics and autonomous systems. Although the $A^∗$ algorithm is theoretically optimal, its hardware implementation is often bottlenecked by sequential memory access and the high area cost of parallel sorting queues. In this work, we propose a novel, high-performance, and area-efficient hardware accelerator for the $A^∗$ algorithm on FPGA. Our architecture introduces a hierarchical Open List, which combines a small, high-speed LUTRAM cache with a high-capacity, multi-port BRAM backend. This structure, equipped with a parallel 4-bank (even/odd row) memory for single-cycle neighbor data fetching, significantly reduces latency and logic utilization. The design was implemented in VHDL on a Xilinx Kintex-7 and Virtex-7 FPGA. The Post-implementation results show that the accelerator achieves a maximum frequency of 357 MHz and 311 Mhz respectively, demonstrating a 3.5−6.6× speedup over previous hardware implementations while reducing LUT and register utilization by 76 % and 70 %, respectively.