Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi

Reza , Mashayekhi (2021) Bidirectional and semi-bidirectional rapidly-exploring random tree-based variants for robot motion planning / Reza Mashayekhi. PhD thesis, Universiti Malaya.

	PDF (The Candidate's Agreement) Restricted to Repository staff only Download (230Kb)
	PDF (Thesis PhD) Download (5Mb)

Abstract

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.

Actions (For repository staff only : Login required)