Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi
Motion planning is involved in various applications such as Unmanned Aerial Vehicles (UAVs), Autonomous Underwater Vehicles (AUVs), driver-less cars, virtual prototyping, biology, and computer graphics. Planners need to find collision-free paths for movable agents from one point to another in sta...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://studentsrepo.um.edu.my/14406/ http://studentsrepo.um.edu.my/14406/1/Reza.pdf http://studentsrepo.um.edu.my/14406/2/Reza_Mashayekhi.pdf |
| _version_ | 1848774958325432320 |
|---|---|
| author | Reza , Mashayekhi |
| author_facet | Reza , Mashayekhi |
| author_sort | Reza , Mashayekhi |
| building | UM Research Repository |
| collection | Online Access |
| description | Motion planning is involved in various applications such as Unmanned Aerial Vehicles
(UAVs), Autonomous Underwater Vehicles (AUVs), driver-less cars, virtual prototyping,
biology, and computer graphics. Planners need to find collision-free paths for movable
agents from one point to another in state spaces. Path planning is mostly about finding
paths in continuous spaces, which is considered as an Np-hard problem. In order to
avoid this complexity, planners discretize continuous spaces into discrete spaces to limit
the number of states that planners need to check to release paths. There are two types
of motion planners: graph-based planners and sampling-based planners. Graph-based
methods, such as A*, are efficient. Nonetheless, they need to use a priori approximation
of the state space. If these approximations are not chosen accurately, they are not able to
provide appropriate solutions. If the selected resolution is low, the output would be low
quality. If the selected resolution is high, it is computationally expensive to solve. On
the other hand, sampling-based methods do not need to have any resolution for solving
planning problems. They use random sampling to avoid prior discretization of state spaces.
Rapidly-exploring Random Tree (RRT) is one of the most popular sampling-based methods
for single-query planning problems due to its ability to find solutions efficiently. Informed
RRT* is an optimized version of RRT, which not only implements the rewiring process
to optimize the tree but also limits the search area to a subset of the state space to return
near-optimal solutions faster. However, before finding an initial solution, the planner is not
able to shrink the problem domain. Therefore, it searches all over the problem domain
to be able to find an initial solution. Moreover, unidirectional RRTs, such as Informed RRT*, take more time to find initial solutions in comparison to the bidirectional RRTs.
This thesis proposes two new motion planners, one is a bidirectional motion planner
(Informed RRT*-Connect), and another one is a semi-bidirectional motion planner (Hybrid
RRT). Informed RRT*-Connect is the informed version of RRT*-Connect that uses direct
sampling after an initial solution is found. Unlike RRT*-Connect, the proposed method
checks only the states that can potentially provide better solutions than the current solution.
On the other hand, Hybrid RRT divides the planning process into three parts: finding
initial solutions by a dual-tree search, combining two trees into one, and optimizing the
solution. Hybrid RRT implements a dual-tree search to obtain its initial solution, which
helps it find solutions faster than unidirectional searches. Then, it combines the start tree
and the goal tree of the dual-tree search into one to implement informed sampling on a
single tree to optimize the current solution. The simulation has been carried out in the
Open Motion Planning Library (OMPL). Planners have been compared in terms of finding
initial solutions, success rate, and path length. The simulations show that the proposed
methods surpass state-of-the-art motions planners in terms of the success rate and the path
length.
|
| first_indexed | 2025-11-14T14:06:34Z |
| format | Thesis |
| id | um-14406 |
| institution | University Malaya |
| institution_category | Local University |
| last_indexed | 2025-11-14T14:06:34Z |
| publishDate | 2021 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | um-144062023-05-10T22:41:43Z Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi Reza , Mashayekhi QA75 Electronic computers. Computer science T Technology (General) Motion planning is involved in various applications such as Unmanned Aerial Vehicles (UAVs), Autonomous Underwater Vehicles (AUVs), driver-less cars, virtual prototyping, biology, and computer graphics. Planners need to find collision-free paths for movable agents from one point to another in state spaces. Path planning is mostly about finding paths in continuous spaces, which is considered as an Np-hard problem. In order to avoid this complexity, planners discretize continuous spaces into discrete spaces to limit the number of states that planners need to check to release paths. There are two types of motion planners: graph-based planners and sampling-based planners. Graph-based methods, such as A*, are efficient. Nonetheless, they need to use a priori approximation of the state space. If these approximations are not chosen accurately, they are not able to provide appropriate solutions. If the selected resolution is low, the output would be low quality. If the selected resolution is high, it is computationally expensive to solve. On the other hand, sampling-based methods do not need to have any resolution for solving planning problems. They use random sampling to avoid prior discretization of state spaces. Rapidly-exploring Random Tree (RRT) is one of the most popular sampling-based methods for single-query planning problems due to its ability to find solutions efficiently. Informed RRT* is an optimized version of RRT, which not only implements the rewiring process to optimize the tree but also limits the search area to a subset of the state space to return near-optimal solutions faster. However, before finding an initial solution, the planner is not able to shrink the problem domain. Therefore, it searches all over the problem domain to be able to find an initial solution. Moreover, unidirectional RRTs, such as Informed RRT*, take more time to find initial solutions in comparison to the bidirectional RRTs. This thesis proposes two new motion planners, one is a bidirectional motion planner (Informed RRT*-Connect), and another one is a semi-bidirectional motion planner (Hybrid RRT). Informed RRT*-Connect is the informed version of RRT*-Connect that uses direct sampling after an initial solution is found. Unlike RRT*-Connect, the proposed method checks only the states that can potentially provide better solutions than the current solution. On the other hand, Hybrid RRT divides the planning process into three parts: finding initial solutions by a dual-tree search, combining two trees into one, and optimizing the solution. Hybrid RRT implements a dual-tree search to obtain its initial solution, which helps it find solutions faster than unidirectional searches. Then, it combines the start tree and the goal tree of the dual-tree search into one to implement informed sampling on a single tree to optimize the current solution. The simulation has been carried out in the Open Motion Planning Library (OMPL). Planners have been compared in terms of finding initial solutions, success rate, and path length. The simulations show that the proposed methods surpass state-of-the-art motions planners in terms of the success rate and the path length. 2021-04 Thesis NonPeerReviewed application/pdf http://studentsrepo.um.edu.my/14406/1/Reza.pdf application/pdf http://studentsrepo.um.edu.my/14406/2/Reza_Mashayekhi.pdf Reza , Mashayekhi (2021) Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi. PhD thesis, Universiti Malaya. http://studentsrepo.um.edu.my/14406/ |
| spellingShingle | QA75 Electronic computers. Computer science T Technology (General) Reza , Mashayekhi Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title | Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title_full | Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title_fullStr | Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title_full_unstemmed | Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title_short | Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi |
| title_sort | bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / reza mashayekhi |
| topic | QA75 Electronic computers. Computer science T Technology (General) |
| url | http://studentsrepo.um.edu.my/14406/ http://studentsrepo.um.edu.my/14406/1/Reza.pdf http://studentsrepo.um.edu.my/14406/2/Reza_Mashayekhi.pdf |