Visualization of a plane sweep algorithm for construction of the visibility graph for robot path planning
Vikas B. Patel · Digital Scholarship - UNLV (University of Nevada Reno) · 2019
Research and development work in robotics and industrial automation has prompted a need for efficient motion planning algorithms for collision avoidance. To build fully autonomous robots, these algorithms must also model the environment correctly and accurately to safely maneuver the robot around obstacles. The main focus of this thesis is on the following problem and its solution: Given a set of obstacles represented as polygons in two-dimensional space, determine the shortest, collision-free path from the source point of the robot to some destination point. A fast and efficient algorithm for solving this problem is based on a plane-sweeping technique and runs in O(N{dollar}\\sp2{dollar} log N) time; Since this solution has been studied very briefly in its theoretical form by (SS84), we present an in-depth analysis of the plane-sweep algorithm along with a full-scale implementation as well as an animation of the plane-sweeping technique.