The RRT algorithm is widely used in path planning due to its high efficiency in searching high-dimensional space. However, RRT will sample the entire workspace when sampling, resulting in many invalid sampling points,...
详细信息
The RRT algorithm is widely used in path planning due to its high efficiency in searching high-dimensional space. However, RRT will sample the entire workspace when sampling, resulting in many invalid sampling points, thus greatly increasing the planning time. To overcome these problems, we proposed OGRRT-Connect, an improved RRT algorithm based on opposite guided sampling, which has higher sampling efficiency and planning speed. Referred to the RRT-Connect algorithm, the algorithm expands two trees simultaneously. When the tree grows, the idea of triangular shrinkage guided sampling is introduced to limit the sampling area, improve sampling efficiency, and reduce planning time. Finally, we conducted robotic simulation experiments to prove the superiority of the algorithm in time planning and path nodes. Furthermore, we applied the algorithm to a real robot to demonstrate our proposed method.
sampling-based algorithms are widely used to solve path planning problems, and PRM is one of the most popular ones. Random sampling PRM is the classic version of the PRM series, which has the advantages of simplicity ...
详细信息
ISBN:
(纸本)9798350387780;9798350387797
sampling-based algorithms are widely used to solve path planning problems, and PRM is one of the most popular ones. Random sampling PRM is the classic version of the PRM series, which has the advantages of simplicity and robustness, but also suffers from low success rate, long collision detection time and low path quality in narrow environments. To address these issues, an improved PRM algorithm based on obstacle distance sampling is proposed. A sampling strategy based on obstacle distance is used in this algorithm, so that more sampling points appear in narrow areas, thereby improving the success rate of the algorithm in finding paths in narrow areas. In addition, a collision detection method based on obstacle distance is proposed in this paper, which reduces the time required for collision detection and improves the efficiency of the algorithm. Further, in order to improve the quality of the path, the proposed algorithm uses triangle inequality and dichotomy to optimize the path. Finally, the proposed algorithm is compared with Random sampling PRM, MSAPRM and Gaussian PRM through simulation experiments, and it is verified that the algorithm has certain advantages in the success rate, time and path length of finding paths in narrow environments.
Motion planning is one of the important research topics of robotics. As an improvement of Rapidly exploring Random Tree (RRT), the RRT* motion planning algorithm is widely used because of its asymptotic optimality. Ho...
详细信息
Motion planning is one of the important research topics of robotics. As an improvement of Rapidly exploring Random Tree (RRT), the RRT* motion planning algorithm is widely used because of its asymptotic optimality. However, the running time of RRT* increases rapidly with the number of potential path vertices, resulting in slow convergence or even an inability to converge, which seriously reduces the performance and practical value of RRT*. To solve this issue, this paper proposes a two-phase motion planning algorithm named Metropolis RRT* (M-RRT*) based on the Metropolis acceptance criterion. First, to efficiently obtain the initial path and start the optimal path search phase earlier, an asymptotic vertex acceptance criterion is defined in the initial path estimation phase of M-RRT*. Second, to improve the convergence rate of the algorithm, a nonlinear dynamic vertex acceptance criterion is defined in the optimal path search phase, which preferentially accepts vertices that may improve the current path. The effectiveness of M-RRT* is verified by comparing it with existing algorithms through the simulation results in three test environments.
Autonomous navigation in narrow indoor environments such as indoor factory, warehouse and laboratory environments, and so on requires higher flexibility and navigation accuracy of the vehicle. This article presents an...
详细信息
Autonomous navigation in narrow indoor environments such as indoor factory, warehouse and laboratory environments, and so on requires higher flexibility and navigation accuracy of the vehicle. This article presents an autonomous navigation method for four-wheel steering vehicle which combines extended Kalman filtering (EKF) and rapidly-exploring random tree (RRT) to improve the precision and flexibility of autonomous navigation of the vehicle in narrow indoor environments. The four-wheel steering model was established by the key parameters such as shape size and minimum angle of rotation of the experimental vehicle. Considering the problem that the uncertainty of pose estimation increases with time during autonomous navigation, an error model is schemed by adding noise to the output terminal of the analog odometer sensor. In order to suppress the accumulation of the uncertainty and keep it stable for a long time, the prediction and update steps of Kalman filter are introduced to filter the error. Then, the simultaneous positioning and mapping are established. based on accurate positioning, a set of driving paths to reach the target is generated by RRT sampling algorithm. The simulation results show that positioning uncertainty remains stable over time, which verifies the effectiveness of the method. The overall positioning percentage error is 0.21%. Compared with traditional dead reckoning algorithm, the positioning accuracy is improved by 73.1% and the vehicle flexibility is increased by 68.6%. The four-wheel steering vehicle can find an ideal trajectory in narrow indoor environments, which assures the efficiency of the autonomous navigation and the traveling quality of the navigation route. Finally, the experimental results are consistent with the simulation results, which further verifies the effectiveness of the proposed algorithm.
Rapidly Exploring Random Trees (RRT) is one of the most widely used algorithms for motion planning in the field of robotics. To reduce the exploration time, RRT-Connect was introduced where two trees are simultaneousl...
详细信息
ISBN:
(纸本)9781713872344
Rapidly Exploring Random Trees (RRT) is one of the most widely used algorithms for motion planning in the field of robotics. To reduce the exploration time, RRT-Connect was introduced where two trees are simultaneously formed and eventually connected. Probabilistic RRT used the concept of position probability map to introduce goal biasing for faster convergence. In this paper, we propose a modified method to combine the pRRT and RRT-Connect techniques and obtain a feasible trajectory around the obstacles quickly. Instead of forming a single tree from the start point to the destination point, intermediate goal points are selected around the obstacles. Multiple trees are formed to connect the start, destination, and intermediate goal points. These partial trees are eventually connected to form an overall safe path around the obstacles. The obtained path is tracked using an MPC Stanley controller which results in a trajectory with control commands at each time step. The trajectories generated by the proposed methods are more optimal and in accordance with human intuition. The algorithm is compared with the standard RRT and pRRT for studying its relative performance. Copyright (c) 2023 The Authors. This is an open access article under the CC BY -NC -ND license (hdps://***/licenscs/b-nolld/4.0/)
We propose an online single-query sampling-based feedback motion re-planning algorithm using finite-time invariant sets, "funnels". We combine concepts from nonlinear systems analysis, sampling-based motion ...
详细信息
We propose an online single-query sampling-based feedback motion re-planning algorithm using finite-time invariant sets, "funnels". We combine concepts from nonlinear systems analysis, sampling-based motion planning, and graph-search methods to create a single framework that enables feedback motion planning/replanning for general nonlinear dynamical systems in a dynamic workspace. We introduce a novel graph data structure to represent a network of volumetric funnels, enabling the use of quick graph-replanning techniques. The use of incremental search techniques and a pre-computed library of motion-primitives ensure that our method can be used for quick on-the-fly rewiring of controllable motion plans in response to changes in the environment. We validate our approach on a simulated 6DOF quadrotor platform operating in a maze, and random forest environment.
Motion planning is a fundamental problem in robotics that involves determining feasible or optimal paths within finite time. While complete motion planning algorithms are guaranteed to converge to a path solution in f...
详细信息
Motion planning is a fundamental problem in robotics that involves determining feasible or optimal paths within finite time. While complete motion planning algorithms are guaranteed to converge to a path solution in finite time, they are proven to be computationally inefficient, making them unsuitable for most practical problems. Resolution-complete algorithms, on the other hand, ensure completeness only if the resolution parameter is sufficiently fine, but they suffer severely from the curse of dimensionality. In contrast, sampling-based algorithms, such as Rapidly Exploring Random Trees (RRT) and its variants, have gained the increasing attention of researchers due to their computational efficiency and effectiveness, particularly in high-dimensional problems. This review paper introduces RRT-basedalgorithms and provides an overview of their key methodological aspects.
The Rapidly-exploring Random Tree Star (RRT*) algorithm, widely utilized for path planning, faces challenges, such as slow acquisition of feasible paths and high path costs. To address this issue, this paper presents ...
详细信息
The Rapidly-exploring Random Tree Star (RRT*) algorithm, widely utilized for path planning, faces challenges, such as slow acquisition of feasible paths and high path costs. To address this issue, this paper presents an improved algorithm based on RRT* that can obtain high-quality paths faster, termed Faster High-Quality RRT*(FHQ-RRT*). The proposed algorithm enhances the exploration efficiency and path quality of mobile robots through three key innovations: First, a dynamic sparse sampling strategy that adaptively adjusts the sampling density according to the growth rate of the random tree, thereby increasing the algorithm's growth speed while maintaining adaptability to complex environments. Second, a new node creation method that combines the bisection method, triangle inequality, and the concept of KeyPoints to reduce the cost of creating new nodes. Third, a focused rewiring strategy that restricts the rewiring operation to valuable regions, thereby improving rewiring efficiency. The performance of FHQ-RRT* was validated in four simulation maps and compared with other algorithms. In all validated maps, FHQ-RRT* consistently achieved the lowest path cost. Regarding time cost, FHQ-RRT* reduced the planning time by over 40% in the circular-obstacle map, 77% in the simple maze map, 56% in the complex maze map, and 50% in the narrow map. The simulation results show that FHQ-RRT* can rapidly generate high-quality paths faster than other algorithms.
This study presents CDRT-RRT*, an algorithm for rapid real-time path planning in N-dimensional Euclidean spaces, based on convex dissection. CDRT-RRT* introduces a convex dissection dynamic neighborhood graph that dif...
详细信息
This study presents CDRT-RRT*, an algorithm for rapid real-time path planning in N-dimensional Euclidean spaces, based on convex dissection. CDRT-RRT* introduces a convex dissection dynamic neighborhood graph that differs from traditional methods by effectively guiding the sampling and connection processes. This approach significantly reduces the computational cost of collision detection, making it more efficient in dynamic environments. A delayed rewiring strategy, underpinned by a heuristic cost-based priority queue, enhances computational efficiency by minimizing redundant rewiring operations. Furthermore, a dual-key cost representation enables CDRT-RRT* to provide feasible temporary paths even when the goal is unreachable due to dynamic obstacles. At the theoretical level, the analysis substantiates the completeness of the path space corresponding to the proposed dynamic neighborhood graph for distance-optimal path planning problems. Extensive simulations and physical experiments demonstrate CDRT-RRT*'s superior performance and efficiency in real-time path planning tasks across various complex and dynamic environments.
In-depth studies of algorithms for solving motion planning problems have been conducted due to the rapid popularization and development of unmanned aerial vehicles in previous decades. Among them, the classic rapidly ...
详细信息
In-depth studies of algorithms for solving motion planning problems have been conducted due to the rapid popularization and development of unmanned aerial vehicles in previous decades. Among them, the classic rapidly exploring random tree (RRT) algorithm has derivative algorithms (e.g., RRT*, Q-RRT*, and F-RRT*) that focus on the optimal path cost of the initial solution. Other improved algorithms, such as RRT-connect and BG-RRT, focus on the optimal time of the initial solution. This article proposes an improved density gradient-RRT (DG-RRT) algorithm based on RRT that improves the efficiency of the guide point and reduces the time lost in the process of obtaining the initial solution through the dynamic gradient sampling strategy. Simultaneously, it reduces the path cost by reconstructing the output path. The proposed algorithm is an expansion algorithm of a random tree, and the performance of the algorithm can be further improved by combining it with other RRT optimization algorithms. DG-RRT and other algorithms are compared in different environments through simulation experiments to verify the advantages of DG-RRT. In addition, it used a set of simulation flight tests to verify the feasibility of the DG-RRT algorithm for UAV path planning.
暂无评论