1
|
Ul Islam N, Gul K, Faizullah F, Ullah SS, Syed I. Trajectory optimization and obstacle avoidance of autonomous robot using Robust and Efficient Rapidly Exploring Random Tree. PLoS One 2024; 19:e0311179. [PMID: 39392842 DOI: 10.1371/journal.pone.0311179] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/06/2024] [Accepted: 09/14/2024] [Indexed: 10/13/2024] Open
Abstract
One of the key challenges in robotics is the motion planning problem. This paper presents a local trajectory planning and obstacle avoidance strategy based on a novel sampling-based path-finding algorithm designed for autonomous vehicles navigating complex environments. Although sampling-based algorithms have been extensively employed for motion planning, they have notable limitations, such as sluggish convergence rate, significant search time volatility, a vast, dense sample space, and unsmooth search routes. To overcome the limitations, including slow convergence, high computational complexity, and unnecessary search while sampling the whole space, we have proposed the RE-RRT* (Robust and Efficient RRT*) algorithm. This algorithm adapts a new sampling-based path-finding algorithm based on sampling along the displacement from the initial point to the goal point. The sample space is constrained during each stage of the random tree's growth, reducing the number of redundant searches. The RE-RRT* algorithm can converge to a shorter path with fewer iterations. Furthermore, the Choose Parent and Rewire processes are used by RE-RRT* to improve the path in succeeding cycles continuously. Extensive experiments under diverse obstacle settings are performed to validate the effectiveness of the proposed approach. The results demonstrate that the proposed approach outperforms existing methods in terms of computational time, sampling space efficiency, speed, and stability.
Collapse
Affiliation(s)
- Naeem Ul Islam
- Department of Computer Science and Engineering and (IBPI), Yuan Ze University, Taoyuan City, R.O.C (Taiwan)
| | - Kaynat Gul
- National University of Science and Technology, Islamabad, Pakistan
| | - Faiz Faizullah
- National University of Science and Technology, Islamabad, Pakistan
| | - Syed Sajid Ullah
- Department of Information and Communication Technology, University of Agder (UiA), Kristiansand, Norway
| | - Ikram Syed
- Dept Information and Communication Engineering, Hankuk University of Foreign Studies, Yongin, South Korea
| |
Collapse
|
2
|
Wong CC, Chen CJ, Wong KY, Feng HM. Implementation of a Real-Time Object Pick-and-Place System Based on a Changing Strategy for Rapidly-Exploring Random Tree. SENSORS (BASEL, SWITZERLAND) 2023; 23:4814. [PMCID: PMC10224147 DOI: 10.3390/s23104814] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/01/2023] [Revised: 05/03/2023] [Accepted: 05/12/2023] [Indexed: 07/09/2023]
Abstract
An object pick-and-place system with a camera, a six-degree-of-freedom (DOF) robot manipulator, and a two-finger gripper is implemented based on the robot operating system (ROS) in this paper. A collision-free path planning method is one of the most fundamental problems that has to be solved before the robot manipulator can autonomously pick-and-place objects in complex environments. In the implementation of the real-time pick-and-place system, the success rate and computing time of path planning by a six-DOF robot manipulator are two essential key factors. Therefore, an improved rapidly-exploring random tree (RRT) algorithm, named changing strategy RRT (CS-RRT), is proposed. Based on the method of gradually changing the sampling area based on RRT (CSA-RRT), two mechanisms are used in the proposed CS-RRT to improve the success rate and computing time. The proposed CS-RRT algorithm adopts a sampling-radius limitation mechanism, which enables the random tree to approach the goal area more efficiently each time the environment is explored. It can avoid spending a lot of time looking for valid points when it is close to the goal point, thus reducing the computing time of the improved RRT algorithm. In addition, the CS-RRT algorithm adopts a node counting mechanism, which enables the algorithm to switch to an appropriate sampling method in complex environments. It can avoid the search path being trapped in some constrained areas due to excessive exploration in the direction of the goal point, thus improving the adaptability of the proposed algorithm to various environments and increasing the success rate. Finally, an environment with four object pick-and-place tasks is established, and four simulation results are given to illustrate that the proposed CS-RRT-based collision-free path planning method has the best performance compared with the other two RRT algorithms. A practical experiment is also provided to verify that the robot manipulator can indeed complete the specified four object pick-and-place tasks successfully and effectively.
Collapse
Affiliation(s)
- Ching-Chang Wong
- Department of Electrical and Computer Engineering, Tamkang University, New Taipei City 25137, Taiwan; (C.-C.W.)
| | - Chong-Jia Chen
- Department of Electrical and Computer Engineering, Tamkang University, New Taipei City 25137, Taiwan; (C.-C.W.)
| | - Kai-Yi Wong
- Department of Electrical Engineering, Chung Yuan Christian University, Taoyuan City 32023, Taiwan
| | - Hsuan-Ming Feng
- Department of Computer Science and Information Engineering, National Quemoy University, Kinmen County 892, Taiwan;
| |
Collapse
|
3
|
Xin P, Wang X, Liu X, Wang Y, Zhai Z, Ma X. Improved Bidirectional RRT* Algorithm for Robot Path Planning. SENSORS (BASEL, SWITZERLAND) 2023; 23:1041. [PMID: 36679837 PMCID: PMC9862987 DOI: 10.3390/s23021041] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 11/22/2022] [Revised: 12/31/2022] [Accepted: 01/05/2023] [Indexed: 06/17/2023]
Abstract
In order to address the shortcomings of the traditional bidirectional RRT* algorithm, such as its high degree of randomness, low search efficiency, and the many inflection points in the planned path, we institute improvements in the following directions. Firstly, to address the problem of the high degree of randomness in the process of random tree expansion, the expansion direction of the random tree growing at the starting point is constrained by the improved artificial potential field method; thus, the random tree grows towards the target point. Secondly, the random tree sampling point grown at the target point is biased to the random number sampling point grown at the starting point. Finally, the path planned by the improved bidirectional RRT* algorithm is optimized by extracting key points. Simulation experiments show that compared with the traditional A*, the traditional RRT, and the traditional bidirectional RRT*, the improved bidirectional RRT* algorithm has a shorter path length, higher path-planning efficiency, and fewer inflection points. The optimized path is segmented using the dynamic window method according to the key points. The path planned by the fusion algorithm in a complex environment is smoother and allows for excellent avoidance of temporary obstacles.
Collapse
|
4
|
Muhammad A, Ali MAH, Turaev S, Abdulghafor R, Shanono IH, Alzaid Z, Alruban A, Alabdan R, Dutta AK, Almotairi S. A Generalized Laser Simulator Algorithm for Mobile Robot Path Planning with Obstacle Avoidance. SENSORS (BASEL, SWITZERLAND) 2022; 22:8177. [PMID: 36365875 PMCID: PMC9657503 DOI: 10.3390/s22218177] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 06/28/2022] [Revised: 09/28/2022] [Accepted: 10/05/2022] [Indexed: 06/16/2023]
Abstract
This paper aims to develop a new mobile robot path planning algorithm, called generalized laser simulator (GLS), for navigating autonomously mobile robots in the presence of static and dynamic obstacles. This algorithm enables a mobile robot to identify a feasible path while finding the target and avoiding obstacles while moving in complex regions. An optimal path between the start and target point is found by forming a wave of points in all directions towards the target position considering target minimum and border maximum distance principles. The algorithm will select the minimum path from the candidate points to target while avoiding obstacles. The obstacle borders are regarded as the environment's borders for static obstacle avoidance. However, once dynamic obstacles appear in front of the GLS waves, the system detects them as new dynamic obstacle borders. Several experiments were carried out to validate the effectiveness and practicality of the GLS algorithm, including path-planning experiments in the presence of obstacles in a complex dynamic environment. The findings indicate that the robot could successfully find the correct path while avoiding obstacles. The proposed method is compared to other popular methods in terms of speed and path length in both real and simulated environments. According to the results, the GLS algorithm outperformed the original laser simulator (LS) method in path and success rate. With application of the all-direction border scan, it outperforms the A-star (A*) and PRM algorithms and provides safer and shorter paths. Furthermore, the path planning approach was validated for local planning in simulation and real-world tests, in which the proposed method produced the best path compared to the original LS algorithm.
Collapse
Affiliation(s)
- Aisha Muhammad
- Department of Mechatronics Engineering, Faculty of Technology, Bayero University, Kano 700241, Nigeria
| | - Mohammed A. H. Ali
- Department of Mechanical Engineering, Faculty of Engineering, University of Malaya, Kuala Lumpur 50603, Malaysia
| | - Sherzod Turaev
- Department of Computer Science and Software Engineering, College of Information Technology, United Arab Emirates University, Al-Ain P.O. Box 15556, United Arab Emirates
| | - Rawad Abdulghafor
- Department of Computer Science, Faculty of Information and Communication Technology, International Islamic University Malaysia, Kuala Lumpur 53100, Malaysia
| | - Ibrahim Haruna Shanono
- Department of Electrical Engineering, Faculty of Technology, Bayero University, Kano 700241, Nigeria
| | - Zaid Alzaid
- Department of Computer Science, Faculty of Computer and Information Systems, Islamic University of Medinah, Medinah 42351, Saudi Arabia
| | - Abdulrahman Alruban
- Department of Information Technology, College of Computer and Information Sciences, Majmaah University, Al Majmaah 11952, Saudi Arabia
| | - Rana Alabdan
- Department of Information Systems, Faculty of Computer and Information Sciences College, Majmaah University, Al Majmaah 11952, Saudi Arabia
| | - Ashit Kumar Dutta
- Department of Computer Science and Information Systems, College of Applied Sciences Al Maarefa University, Riyadh 13713, Saudi Arabia
| | - Sultan Almotairi
- Department of Computer Science, Faculty of Computer and Information Systems, Islamic University of Medinah, Medinah 42351, Saudi Arabia
- Department of Natural and Applied Sciences, Faculty of Community College, Majmaah University, Majmaah 11952, Saudi Arabia
| |
Collapse
|
5
|
Zhang X, Zhu T, Du L, Hu Y, Liu H. Local Path Planning of Autonomous Vehicle Based on an Improved Heuristic Bi-RRT Algorithm in Dynamic Obstacle Avoidance Environment. SENSORS (BASEL, SWITZERLAND) 2022; 22:s22207968. [PMID: 36298319 PMCID: PMC9609149 DOI: 10.3390/s22207968] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/20/2022] [Revised: 10/15/2022] [Accepted: 10/17/2022] [Indexed: 06/01/2023]
Abstract
The existing variants of the rapidly exploring random tree (RRT) cannot be effectively applied in local path planning of the autonomous vehicle and solve the coherence problem of paths between the front and back frames. Thus, an improved heuristic Bi-RRT algorithm is proposed, which is suitable for obstacle avoidance of the vehicle in an unknown dynamic environment. The vehicle constraint considering the driver's driving habit and the obstacle-free direct connection mode of two random trees are introduced. Multi-sampling biased towards the target state reduces invalid searches, and parent node selection with the comprehensive measurement index accelerates the algorithm's execution while making the initial path gentle. The adaptive greedy step size, introducing the target direction, expands the node more effectively. Moreover, path reorganization minimizes redundant path points and makes the path's curvature continuous, and path coherence makes paths between the frames connect smoothly. Simulation analysis clarifies the efficient performance of the proposed algorithm, which can generate the smoothest path within the shortest time compared with the other four algorithms. Furthermore, the experiments on dynamic environments further show that the proposed algorithm can generate a differentiable coherence path, ensuring the ride comfort and stability of the vehicle.
Collapse
Affiliation(s)
- Xiao Zhang
- School of Automobile, Chang’an University, Xi’an 710064, China
| | - Tong Zhu
- College of Transportation Engineering, Chang’an University, Xi’an 710064, China
| | - Lei Du
- School of Automobile, Chang’an University, Xi’an 710064, China
| | - Yueqi Hu
- School of Vehicle Engineering, Xi’an Aeronautical Institute, Xi’an 710077, China
| | - Haoxue Liu
- School of Automobile, Chang’an University, Xi’an 710064, China
| |
Collapse
|
6
|
ERCP: speedup path planning through clustering and presearching. APPL INTELL 2022. [DOI: 10.1007/s10489-022-04137-4] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/02/2022]
|
7
|
Lai T, Ramos F. Adaptively Exploits Local Structure With Generalised Multi-Trees Motion Planning. IEEE Robot Autom Lett 2022. [DOI: 10.1109/lra.2021.3132985] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/10/2022]
|
8
|
Hu Y, Li D, He Y, Han J. Incremental Learning Framework for Autonomous Robots Based on Q-Learning and the Adaptive Kernel Linear Model. IEEE Trans Cogn Dev Syst 2022. [DOI: 10.1109/tcds.2019.2962228] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/08/2022]
|
9
|
Zhang Z, Lu R, Zhao M, Luan S, Bu M. Robot path planning based on genetic algorithm with hybrid initialization method. JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2022. [DOI: 10.3233/jifs-211423] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/15/2022]
Abstract
The research of path planning method based on genetic algorithm (GA) for the mobile robot has received much attention in recent years. GA, as one evolutionary computation model, mimics the process of natural evolution and genetics. The quality of the initial population plays an essential role in improving the performance of GA. However, when GA based on a random initialization method is applied to path planning problems, it will lead to the emergence of infeasible solutions and reduce the performance of the algorithm. A novel GA with a hybrid initialization method, termed NGA, is proposed to solve this problem in this paper. In the initial population, NGA first randomly selects three free grids as intermediate nodes. Then, a part of the population uses a random initialization method to obtain the complete path. The other part of the population obtains the complete path using a greedy-related method. Finally, according to the actual situation, the redundant nodes or duplicate paths in the path are deleted to avoid the redundant paths. In addition, the deletion operation and the reverse operation are also introduced to the NGA iteration process to prevent the algorithm from falling into the local optimum. Simulation experiments are carried out with other algorithms to verify the effectiveness of the NGA. Simulation results show that NGA is superior to other algorithms in convergence accuracy, optimization ability, and success rate. Besides, NGA can generate the optimal feasible paths in complex environments.
Collapse
Affiliation(s)
- Zhaojun Zhang
- School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou, Jiangsu, China
| | - Rui Lu
- School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou, Jiangsu, China
| | - Minglong Zhao
- School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou, Jiangsu, China
| | - Shengyang Luan
- School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou, Jiangsu, China
| | - Ming Bu
- School of Electrical Engineering, Xi’an Jiaotong University, Xi’an, Shaanxi, China
| |
Collapse
|
10
|
Yi J, Yuan Q, Sun R, Bai H. Path planning of a manipulator based on an improved P_RRT* algorithm. COMPLEX INTELL SYST 2022; 8:2227-2245. [PMID: 35079563 PMCID: PMC8776557 DOI: 10.1007/s40747-021-00628-y] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/08/2021] [Accepted: 12/17/2021] [Indexed: 11/24/2022]
Abstract
Aiming to build upon the slow convergence speed and low search efficiency of the potential function-based rapidly exploring random tree star (RRT*) algorithm (P_RRT*), this paper proposes a path planning method for manipulators with an improved P_RRT* algorithm (defined as improved P_RRT*), which is used to solve the path planning problem for manipulators in three-dimensional space. This method first adopts a random sampling method based on a potential function. Second, based on a probability value, the nearest neighbour node is selected by the nearest Euclidean distance to the random sampling point and the minimum cost function, and in the expansion of new nodes, twice expansion methods are used to accelerate the search efficiency of the algorithm. The first expansion adopts the goal-biased expansion strategy, and the second expansion adopts the strategy of random sampling in a rectangular area. Then, the parent node of the new node is reselected, and the path is rerouted to obtain a clear path from the initial point to the target point. Redundant node deletion and the maximum curvature constraint are used to remove redundant nodes and minimize the curvature on the generated path to reduce the tortuosity of the path. The Bezier curve is used to fit the processed path and obtain the trajectory planning curve for the manipulator. Finally, the improved P_RRT* algorithm is verified experimentally in Python and the Robot Operating System (ROS) and compared with other algorithms. The experimental results verify the effectiveness and superiority of the improved algorithm.
Collapse
|
11
|
Wang S, Hu X, Xiao J, Chen T. Repulsion-Oriented Reciprocal Collision Avoidance for Multiple Mobile Robots. J INTELL ROBOT SYST 2021. [DOI: 10.1007/s10846-021-01528-6] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
|
12
|
ADD-RRV for motion planning in complex environments. ROBOTICA 2021. [DOI: 10.1017/s0263574721000436] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
Abstract
AbstractIn this paper, we present a novel sampling-based motion planning method in various complex environments, especially with narrow passages. We use online the results of the planner in the ADD-RRT framework to identify the types of the local configuration space based on the principal component analysis (PCA). The identification result is then used to accelerate the expansion similar to RRV around obstacles and through narrow passages. We also propose a modified bridge test to identify the entrance of a narrow passage and boost samples inside it. We have compared our method with known motion planners in several scenarios through simulations. Our method shows the best performance across all the tested planners in the tested scenarios.
Collapse
|
13
|
|