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...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://eprints.uthm.edu.my/253/ 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_ | 1848887139423485952 |
|---|---|
| author | Abdul Latip, Nor Badariyah |
| author_facet | Abdul Latip, Nor Badariyah |
| author_sort | Abdul Latip, Nor Badariyah |
| building | UTHM Institutional Repository |
| collection | Online Access |
| 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. |
| first_indexed | 2025-11-15T19:49:38Z |
| format | Thesis |
| id | uthm-253 |
| institution | Universiti Tun Hussein Onn Malaysia |
| institution_category | Local University |
| language | English English English |
| last_indexed | 2025-11-15T19:49:38Z |
| publishDate | 2018 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | uthm-2532021-07-14T04:17:32Z http://eprints.uthm.edu.my/253/ Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method 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 NonPeerReviewed text en http://eprints.uthm.edu.my/253/1/24p%20NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP.pdf text en http://eprints.uthm.edu.my/253/2/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20COPYRIGHT%20DECLARATION.pdf text en http://eprints.uthm.edu.my/253/3/NOR%20BADARIYAH%20BINTI%20ABDUL%20LATIP%20WATERMARK.pdf Abdul Latip, Nor Badariyah (2018) Computationally-efficient path planning algorithms in obstacle-rich environments based on visibility graph method. Masters thesis, Universiti Tun Hussein Onn Malaysia. |
| 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 |
| title | 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_short | 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 |
| topic | TA329-348 Engineering mathematics. Engineering analysis |
| url | http://eprints.uthm.edu.my/253/ 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 |