Visualization of a plane sweep algorithm for construction of the visibility graph for robot path planning

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.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

1989

Author dc:creator

• Patel, Vikas B

Contributors dc:contributor

• Yonina Cooper

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/82

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-1081