A parallel algorithm and architecture for robot path planning

Path planning is an essential step in any mobile robot system. In this paper, we propose a parallel algorithm and architecture for this computationally intensive problem. The parallel implementation is based on the trulla algorithm proposed by the authors in Proc. 5th Intl. Conf. on Intelligent Robots and Systems, Raleigh, NC, USA (July 1992). The algorithm uses a wavefront-like propagation technique and computes the near-optimal paths from every point in the grid space to the specified destination. The algorithm is implemented on a linear systolic array architecture which is simple and regular in structure and can be implemented as a VLSI system. Currently, a prototype VLSI chip with 5 processor cells is being implemented