LIDAR-Based Robot Navigation Using Voronoi Diagram Roadmap

Zhang, Xingzhong, Bo Cui, Chaomin Luo, Mohan Krishnan, Mark Paulik, and Sandra A. Yost

Point-to-point navigation requires an optimal path to be planned between the two, which the robot can follow a collision-free path. A navigation algorithm for a mobile robot by Voronoi Diagram roadmap is developed in this project.  A LIDAR is configured to collect environmental information and a motor encoder is employed to complete localization. 270° SICK LMS100 LIDAR unit is capable of collecting data over a 270°field-of-view in this project.  All hardware interactions and communication are developed with Player’s common interface by MATLAB, and simulated with Stage. A Voronoi Diagram based path planning technique to generate the global safe path with obstacle avoidance is also executed in the UDM intelligent vehicle. The waypoints are generated by the Voronoi Diagram roadmap algorithm. VFH as local navigator is employed to guide the robot between two waypoints.


The proposed enhanced Voronoi Diagram path planning technique has been successfully demonstrated in a Player/Stage simulation environment. In addition, tests on an actual course are very promising and reveal the potential for stable forward navigation.