Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method

Path planning purpose is to find a collision-free path in a defined environment from a starting point to a target point. It is one of the vital aspects in enhancing an autonomy of a robot. Cun·ent studies have been focused on developing path planning algorithms to satisfy the criteria of path planni...

Full description

Saved in:

Bibliographic Details
Main Author:	Abdul Latip, Nor Badariyah
Format:	Thesis
Language:	English English English
Published:	2018
Subjects:	TA329-348 Engineering mathematics Engineering analysis
Online Access:	http://eprints.uthm.edu.my/253/1/24p%20NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP.pdf http://eprints.uthm.edu.my/253/2/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/253/3/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20WATERMARK.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-uthm-ep.253
record_format	uketd_dc
spelling	my-uthm-ep.2532021-07-14T04:17:32Z Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method 2018-08 Abdul Latip, Nor Badariyah TA329-348 Engineering mathematics. Engineering analysis Path planning purpose is to find a collision-free path in a defined environment from a starting point to a target point. It is one of the vital aspects in enhancing an autonomy of a robot. Cun·ent studies have been focused on developing path planning algorithms to satisfy the criteria of path planning namely minimum path length, low computation time and complete, i.e., it gives positive result if a path is available or negative if otherwise. There are several existing path planning methods such as Visibility Graph (VG), Voronoi Diagram (VD), Potential Fields (PF) and Rapidly-Exploring Random Tree (RRT). Among those, VG is superior in terms of producing a path with the least length and completeness. However, VG has a drawback due to the fact that its computation time will increase in obstacle-rich environments. Moreover, as a path planned by VG is piece-wise linear which has sharp turns at comers, it is infeasible due to the kinematic constraints of a robot. Kinematic constraints limit the degree of freedom of the robot. In order to address the high computation time, an improved VG called Iterative Equilateral Spaces Oriented Visibility Graph (IESOVG) has been developed by reducing the number of obstacles used for path planning. IESOVG manipulates the size of the equilateral space to determine the obstacles used in path planning and consequently produces a free-collision path in considerably shorter time. On the other hand, to overcome the kinematic constraint of a car-like robot, Proportional controller, Proportional-Derivative (PD) controller and Bezier curves have been implemented to ensure that the resulting paths are feasible. As a result of the proposed methods, computation time of conventional VG has been improved by 97 %. The implementation of PD controller may contribute to path planning software development for autonomous car industry. 2018-08 Thesis http://eprints.uthm.edu.my/253/ http://eprints.uthm.edu.my/253/1/24p%20NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP.pdf text en public http://eprints.uthm.edu.my/253/2/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20COPYRIGHT%20DECLARATION.pdf text en staffonly http://eprints.uthm.edu.my/253/3/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20WATERMARK.pdf text en validuser mphil masters Universiti Tun Hussein Onn Malaysia Faculty of Electrical and Electronic Engineering
institution	Universiti Tun Hussein Onn Malaysia
collection	UTHM Institutional Repository
language	English English English
topic	TA329-348 Engineering mathematics Engineering analysis
spellingShingle	TA329-348 Engineering mathematics Engineering analysis Abdul Latip, Nor Badariyah Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
description	Path planning purpose is to find a collision-free path in a defined environment from a starting point to a target point. It is one of the vital aspects in enhancing an autonomy of a robot. Cun·ent studies have been focused on developing path planning algorithms to satisfy the criteria of path planning namely minimum path length, low computation time and complete, i.e., it gives positive result if a path is available or negative if otherwise. There are several existing path planning methods such as Visibility Graph (VG), Voronoi Diagram (VD), Potential Fields (PF) and Rapidly-Exploring Random Tree (RRT). Among those, VG is superior in terms of producing a path with the least length and completeness. However, VG has a drawback due to the fact that its computation time will increase in obstacle-rich environments. Moreover, as a path planned by VG is piece-wise linear which has sharp turns at comers, it is infeasible due to the kinematic constraints of a robot. Kinematic constraints limit the degree of freedom of the robot. In order to address the high computation time, an improved VG called Iterative Equilateral Spaces Oriented Visibility Graph (IESOVG) has been developed by reducing the number of obstacles used for path planning. IESOVG manipulates the size of the equilateral space to determine the obstacles used in path planning and consequently produces a free-collision path in considerably shorter time. On the other hand, to overcome the kinematic constraint of a car-like robot, Proportional controller, Proportional-Derivative (PD) controller and Bezier curves have been implemented to ensure that the resulting paths are feasible. As a result of the proposed methods, computation time of conventional VG has been improved by 97 %. The implementation of PD controller may contribute to path planning software development for autonomous car industry.
format	Thesis
qualification_name	Master of Philosophy (M.Phil.)
qualification_level	Master's degree
author	Abdul Latip, Nor Badariyah
author_facet	Abdul Latip, Nor Badariyah
author_sort	Abdul Latip, Nor Badariyah
title	Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
title_short	Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
title_full	Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
title_fullStr	Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
title_full_unstemmed	Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
title_sort	computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method
granting_institution	Universiti Tun Hussein Onn Malaysia
granting_department	Faculty of Electrical and Electronic Engineering
publishDate	2018
url	http://eprints.uthm.edu.my/253/1/24p%20NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP.pdf http://eprints.uthm.edu.my/253/2/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/253/3/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20WATERMARK.pdf
_version_	1747830565381341184

Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method

Similar Items