Award Date

May 2023

Degree Type


Degree Name

Master of Science in Computer Science


Computer Science

First Committee Member

Laxmi Gewali

Second Committee Member

Kazem Taghva

Third Committee Member

Mingon Kang

Fourth Committee Member

Henry Selvaraj

Number of Pages



Path Planning is one of the widely investigated research areas in computational geometry and robotics. Given a set of polygonal obstacles inside a rectangular box, and start & goal points, the path planning problem is to construct a collision-free path connecting the start point to the goal point. We review existing well known algorithms for solving the path planning problem. We propose new approaches for constructing a collision-free path with high clearance from obstacles. The main idea of the proposed algorithm is the appropriate generation free-region nodes which can be processed to construct high clearance paths. Neighbors of free-region nodes are carefully joined to obtain a connected graph outside the obstacles. Standard graph searching algorithms are applied in the constructed connected graph to obtain high-clearance paths. We also present methods to remove a few free-region nodes to further increase clearance from obstacles. Finally, we present experimental results on the construction of high-clearance collision-free paths.


Collision-free Path; High Clearance; Path Planning; Visibility Graph


Computer Sciences

Degree Grantor

University of Nevada, Las Vegas




IN COPYRIGHT. For more information about this rights statement, please visit