A vision-based path planning on a distance map and its cellular array VLSI architecture

This paper gives a hardware-efficient algorithm and VLSI architecture for finding a path for a robot on an environment image. The algorithm constructs a distance map to identify the collision-free region for a given robot and then finds a path on the region. The path obtained from a start to a goal is the shortest path in terms of the number of steps. The time-critical part of the algorithm is mapped on to a two-dimensional cellular architecture that consists of a locally interconnected array of identical processing elements. Due to this local interconnection and regular structure, the architecture can be operated at a high speed and is easily scalable. The design has been implemented on the XCV8000 device of Xilinx. The maximum frequency of operation obtained is 246 MHz. This leads to computing a collision-free path on images of size 100 times 100 in less than 41 mus. The hardware is capable of processing images at a video rate for real-time path planning in a dynamic environment.