KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Ossairy, Ahmed; Nassar, Hassan ORCID iD icon 1; Henkel, Jörg 1; Afifi, Atef; Ghany, Mohamed A. Abd El
1 Institut für Technische Informatik (ITEC), Karlsruher Institut für Technologie (KIT)

Abstract:

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.


Originalveröffentlichung
DOI: 10.1109/ICMRE69538.2026.11533999
Zugehörige Institution(en) am KIT Institut für Technische Informatik (ITEC)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 02.03.2026
Sprache Englisch
Identifikator ISBN: 979-8-3315-6365-3
ISSN: 2996-1831
KITopen-ID: 1000193689
Erschienen in 2026 12th International Conference on Mechatronics and Robotics Engineering (ICMRE)
Veranstaltung 12th International Conference on Mechatronics and Robotics Engineering (2026), Oldenburg, Deutschland, 02.03.2026 – 04.03.2026
Verlag Institute of Electrical and Electronics Engineers (IEEE)
Seiten 100–105
Schlagwörter Robotics, FPGA, Hardware Acceleration
Nachgewiesen in OpenAlex
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page