An Accelerated Block Searching Approach in A* for Autonomous Mobile Robots

Abstract

Path planning is crucial to ensure the safe navigation of autonomous mobile robots (AMRs). However, as the scale of maps and paths increases, achieving faster and more efficient computations becomes challenging due to constraints in memory and computational resources. In this paper, we present a hardware architecture for global path planning utilizing block searching A* (BSA*) for AMRs. The BSA* designates surrounding nodes as blocks and searching nodes for expansion with collision detection based on block-based jump point search (JPS(B)). This reduces the amount of stored data, enables faster map scanning, and provides advantages in parallelized architecture. The BSA* accelerator, consisting of a memory controller based on heap sorting and a parallelized collision detector, was implemented on a field-programmable gate array (FPGA). In the benchmarks for grid-based pathfinding, experimental results showed that BSA* stored 83.2% less data compared to A* and BSA* accelerator demonstrated real-time performance, ranging from 5.498 ms (181 Hz) to 6.126 ms (164 Hz), successfully verifying the feasibility of real-time path planning with a block searching approach.