A Vision-Based Path Planning on a Distance Map and its Cellular Array VLSI Architecture

This paper gives a hardware-efficient algorithm and a 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 he 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 x 100 in less than 41 mu s. The hardware is capable of processing images at a video rate for real-time path planning in a dynamic environment.