Akers´s wavefront planner — One of the fastest stencil-based path planners on FPGAs

The efficient and fast processing of path planning algorithms based on stencil codes is a great challenge. On the one hand, these iterative approaches are advantageous because of their regular processing pattern and the characteristic to avoid problems of other path planning methods, like local minima in potential field algorithms. On the other hand, they are computational- and data-intensive because of their high number of required iterations. By comparing several algorithms based on stencil codes, we found one of the fastest and most efficient path planners for realization on FPGAs, Akers´s wavefront planner. A processing of 33 maps per second with a resolution of 1024×1024 is possible on a midsize Virtex-5 FPGA achieved through a column-based processing scheme combined with an efficient internal data storage.