Back to search

Clemson University

Geometric Path-Planning Algorithm in Cluttered 2D Environments Using Convex Hulls

Abstract

dc:description.abstract

Routing or path planning is the problem of finding a collision-free path in an environment usually scattered with multiple objects. Finding the shortest route in a planar (2D) or spatial (3D) environment has a variety of applications such as robot motion planning, navigating autonomous vehicles, routing of cables, wires, and harnesses in vehicles, routing of pipes in chemical process plants, etc. The problem often times is decomposed into two main sub-problems: modeling and representation of the workspace geometrically and optimization of the path. Geometric modeling and representation of the workspace are paramount in any path planning problem since it builds the data structures and provides the means for solving the optimization problem. The optimization aspect of the path planning involves satisfying some constraints, the most important of which is to avoid intersections with the interior of any object and optimizing one or more criteria. The most common criterion in path planning problems is to minimize the length of the path between a source and a destination point of the workspace while other criteria such as minimizing the number of links or curves could also be taken into account. Planar path planning is mainly about modeling the workspace of the problem as a collision-free graph. The graph is, later on, searched for the optimal path using network optimization techniques such as branch-and-bound or search algorithms such as Dijkstra's. Previous methods developed to construct the collision-free graph explore the entire workspace of the problem which usually results in some unnecessary information that has no value but to increase the time complexity of the algorithm, hence, affecting the efficiency significantly. For example, the fastest known algorithm to construct the visibility graph, which is the most common method of modeling the collision-free space, in a workspace with a total of n vertices has a time complexity of order O(n2). In this research, first, the 2D workspace of the problem is modeled using the tessellated format of the objects in a CAD software which facilitates handling of any free-form object. Then, an algorithm is developed to construct the collision-free graph of the workspace using the convex hulls of the intersecting obstacles. The proposed algorithm focuses only on a portion of the workspace involved in the straight line connecting the source and destination points. Considering the worst case that all the objects of the workspace are intersecting, the algorithm yields a time complexity of O(nlog(n/f)), with n being the total number of vertices and f being the number of objects. The collision-free graph is later searched for the shortest path between the two given nodes using a search algorithm known as Dijkstra's.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mechanical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Masoudi, Nafiseh
Contributors dc:contributor
  • Dr. Georges Fadel, Committee Chair
  • Dr. Margaret Wiecek, Co-Chair
  • Dr. Joshua D. Summers
  • Dr. Gang Li

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/2784

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Masoudi, Nafiseh. Geometric Path-Planning Algorithm in Cluttered 2D Environments Using Convex Hulls. Thesis thesis, https://open.clemson.edu/all_theses/2784