A hardware implementation of the level set method for robotic path finding with multiple obstacle avoidance

This dissertation describes the application and implementation of the level set method (LSM) for path finding through multiple obstacles. A number of new algorithms are introduced and used (i) to numerically generate the signed distance function (SDF) from the obstacle boundaries, (ii) to extract a global path from the resulting SDF, (iii) to select the shortest local path connecting any two points through the multiple obstacles in a plane from the global path, and (iv) to reduce the total length of the latter path using a curve smoothing process based upon minimizing the curve bending energy function. A complete hardware architecture design that is written in the Very High Speed Integrated Circuit (VHSIC) Hardware Description Language (VHDL) is created to numerically solve the relevant PDEs arising in the LSM in 32-bit floating point format on the Altera FPGA device. In addition, the dissertation also introduces the FPGA-to-HardCopy conversion technique to generate the low-cost structured application-specific integrated circuit (ASIC) chip in a much shorter time-to-market. The functional and timing verifications for the hardware implementations are performed by using the FPGA Altera-ModelSim design software. MATLAB software is used to analyze the difference errors and to verify the hardware simulation results.