A Hardware Accelerator for Path Planning on a Distance Transform

This paper presents a novel hardware-directed algorithm for finding a path for a mobile robot using the Euclidean distance transform of the binary image of an environment. The robot can translate as well as rotate. The path obtained from start to goal is the shortest in terms of the number of steps. The mapping of the algorithm to hardware is described. Results of implementation on a Xilinx FPGA device show that the device can be operated at a clock rate of about 35 MHz. Such a high frequency of operation is necessary for real time path planning in a dynamic environment.