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 |
| Summary: | 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.
|
|---|