An Optimized FPGA Implementation for a Parallel Path Planning Algorithm Based on Marching Pixels

Path Planning is one of the most computationally intensive tasks in robot systems and a challenge in dynamically changing environments. By means of FPGAs it is possible to process time-critical and data-intensive tasks in robot systems efficiently. We have developed a parallel path planning algorithm which is based on Marching Pixels, an organic computing principle. The algorithm is optimized for FPGA-based processing. A parallel implementation approach together with an efficient buffering of the map data allowed us to obtain a processing rate suitable for real time applications, even for higher resolutions. We achieved a processing rate of 80 maps per second for VGA resolution (640 × 480) on a midsize Virtex-5 FPGA.