检索结果-内蒙古大学图书馆

sampling-based algorithms for optimal motion planning

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2011年第7期30卷 846-894页

作者： Karaman, Sertac Frazzoli, Emilio MIT Lab Informat & Decis Syst Cambridge MA 02139 USA

During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e. g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e. g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.

关键词： Motion planning optimal path planning sampling-based algorithms random geometric graphs

来源：评论

学校读者我要写书评

暂无评论

sampling-based algorithms for optimal motion planning

Sampling-based algorithms for optimal motion planning

引用

5th Robotics - Science and Systems (RSS) Conference

作者： Karaman, Sertac Frazzoli, Emilio MIT Lab Informat & Decis Syst Cambridge MA 02139 USA

关键词： Motion planning optimal path planning sampling-based algorithms random geometric graphs

来源：评论

学校读者我要写书评

暂无评论

Speeding up single-query sampling-based algorithms using case-based reasoning

引用

EXPERT SYSTEMS WITH APPLICATIONS 2018年 114卷 524-531页

作者： Abdelwahed, Mustafa F. Saleh, Mohamed Mohamed, Amr E. Helwan Univ Fac Engn Dept Elect Commun & Comp 1 Sherif St Cairo 11792 Egypt

We present an extension to the single-query sampling-based algorithm for improving its response time using Case-based Reasoning (CBR) technique. Unlike traditional experience-based planners, CBR depends on a single thread execution which reduces the required computation power. Additionally, it is always biased towards exploration rather than exploitation to overcome experience-based algorithms drawbacks. Results indicate that CBR extension has significantly improved sampling-based response time for similar served queries. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： sampling-based algorithms Experience-based algorithms Case-based reasoning Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

MINIMUM DOSE PATH PLANNING IN COMPLEX RADIOACTIVE ENVIRONMENTS WITH sampling-based algorithms 25

引用

25th International Conference on Nuclear Engineering

作者： Chao, Nan Liu, Yong-kuo Xia, Hong Bai, Lu Harbin Engn Univ Fundamental Sci Nucl Safety & Simulat Technol Lab Harbin Heilongjiang Peoples R China

ISBN: (纸本)9780791857823

The objective of this paper is to provide a minimum dose path navigation method for occupational workers to avoid additional radiation exposure and quantitatively analyze the cost of paths in radioactive environments. A sampling-based algorithm named Bias-based T-RRT* (BT-RRT*) was proposed, which is an extension of nearly the latest sampling-based algorithm T-RRT*. It combines the exploration strength of T-RRT* that favors the exploration of low-cost regions and connects sampling points selectively with the strategy of biased sampling around the suboptimal paths to increase the convergence rate. To improve planning efficiency, a branch-and-bound strategy is also integrated to improve the efficiency of maintaining the node tree. A walking path-planning system was also developed using virtual reality. Simulation results presented in several radioactive environments show that the walking path planning method was effective in providing the minimum dose path navigation for occupational workers to avoid additional radiation exposure and to increase personnel safety.

关键词： Minimum dose path planning sampling-based algorithms Nuclear facilities Radiation safety

来源：评论

学校读者我要写书评

暂无评论

Information-Theoretic Stochastic Optimal Control via Incremental sampling-based algorithms

Information-Theoretic Stochastic Optimal Control via Increme...

引用

IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL)

作者： Arslan, Oktay Theodorou, Evangelos A. Tsiotras, Panagiotis Georgia Inst Technol Daniel Guggenheim Sch Aerosp Engn Atlanta GA 30332 USA Georgia Inst Technol Inst Robot & Intelligent Machines Atlanta GA 30332 USA

ISBN: (纸本)9781479945528

This paper considers optimal control of dynamical systems which are represented by nonlinear stochastic differential equations. It is well-known that the optimal control policy for this problem can be obtained as a function of a value function that satisfies a nonlinear partial differential equation, namely, the Hamilton-Jacobi-Bellman equation. This nonlinear PDE must be solved backwards in time, and this computation is intractable for large scale systems. Under certain assumptions, and after applying a logarithmic transformation, an alternative characterization of the optimal policy can be given in terms of a path integral. Path Integral (PI) based control methods have recently been shown to provide elegant solutions to a broad class of stochastic optimal control problems. One of the implementation challenges with this formalism is the computation of the expectation of a cost functional over the trajectories of the unforced dynamics. Computing such expectation over trajectories that are sampled uniformly may induce numerical instabilities due to the exponentiation of the cost. Therefore, sampling of low-cost trajectories is essential for the practical implementation of PI-based methods. In this paper, we use incremental sampling-based algorithms to sample useful trajectories from the unforced system dynamics, and make a novel connection between Rapidly-exploring Random Trees (RRTs) and information-theoretic stochastic optimal control. We show the results from the numerical implementation of the proposed approach to several examples.

关键词： path integral stochastic optimal control sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

FHQ-RRT*: An Improved Path Planning Algorithm for Mobile Robots to Acquire High-Quality Paths Faster

引用

SENSORS 2025年第7期25卷 2189-2189页

作者： Dong, Xingxiang Wang, Yujun Fang, Can Ran, Kemeng Liu, Guohui Southwest Univ Coll Comp & Informat Sci Chongqing 400715 Peoples R China

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.

关键词： path planning sampling-based algorithms rapidly explored random tree optimal path planning

来源：评论

学校读者我要写书评

暂无评论

An Overview and Comparison of Traditional Motion Planning based on Rapidly Exploring Random Trees

引用

SENSORS 2025年第7期25卷 2067-2067页

作者： Chu, Yang Chen, Quanlin Yan, Xuefeng Nanjing Univ Aeronaut & Astronaut Sch Comp Sci & Technol Nanjing 211106 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

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-based algorithms and provides an overview of their key methodological aspects.

关键词： kinodynamic planning motion planning sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Motion planning for robotics:A review for sampling-based planners

引用

Biomimetic Intelligence & Robotics 2025年第1期5卷 15-34页

作者： Liding Zhang Kuanqi Cai Zewei Sun Zhenshan Bing Chaoqun Wang Luis Figueredo Sami Haddadin Alois Knoll School of Computation Information and Technology(CIT)Technical University of MunichMunich 85748Germany Munich Institute of Robotics and Machine Intelligence(MIRMI) Technical University of MunichMunich 80992Germany School of Control Science and Engineering Shandong UniversityJinan 250061China School of Computer Science University of NottinghamNottingham 315199United Kingdom

Recent advancements in robotics have transformed industries such as manufacturing,logistics,surgery,and planetary exploration.A key challenge is developing efficient motion planning algorithms that allow robots to navigate complex environments while avoiding collisions and optimizing metrics like path length,sweep area,execution time,and energy *** the available algorithms,sampling-based methods have gained the most traction in both research and industry due to their ability to handle complex environments,explore free space,and offer probabilistic completeness along with other formal *** their widespread application,significant challenges still *** advance future planning algorithms,it is essential to review the current state-of-the-art solutions and their *** this context,this work aims to shed light on these challenges and assess the development and applicability of sampling-based ***,we aim to provide an in-depth analysis of the design and evaluation of ten of the most popular planners across various *** findings highlight the strides made in sampling-based methods while underscoring persistent *** work offers an overview of the important ongoing research in robotic motion planning.

关键词： Robotics Motion planning sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

CDRT-RRT*: Real-time rapidly exploring Random Tree Star based on convex dissection

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 268卷

作者： Liu, Jinyuan Fu, Minglei Zhang, Wenan Chen, Bo Sychou, Uladzislau Belotserkovsky, Alexei Zhejiang Univ Technol Coll Informat Engn Hangzhou 310023 Peoples R China Natl Acad Sci Belarus United Inst Informat Problems Minsk 220012 BELARUS

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.

关键词： sampling-based algorithms Real-time path planning Optimal distance Navigation

来源：评论

学校读者我要写书评

暂无评论

A novel RRT*-Connect algorithm for path planning on robotic arm collision avoidance

引用

SCIENTIFIC REPORTS 2025年第1期15卷 1-19页

作者： Cao, Miaolong Mao, Huawei Tang, Xiaohui Sun, Yuzhou Chen, Tiandong Zhejiang Univ Sci & Technol Sch Mech & Energy Engn Hangzhou 310023 Peoples R China Zhejiang Ansheng Sci & Technol Stock Co Ltd Jinhua 321300 Peoples R China

To address the limitations of the original algorithm, several optimization techniques are proposed. This article presents an original RRT*-Connect algorithm for the planning of obstacle avoidance paths on robotic arms. These strategies include implementing a target biasing algorithm, using elliptic space sampling to enhance the sampling process, the revision of the cost function to better guide path planning, and implementing an artificial potential field and gradient descent strategy to design adaptive step sizes. Furthermore, the use of segmented B & eacute;zier curves facilitates the generation of a more fluid trajectory when constructing the final path. The effectiveness of these augmentation strategies is corroborated by both simulations and experimental verification on a robotic arm. The simulations showed a 19.39% reduction in average run time and a 5% reduction in average path length compared to the existing RRT*-Connect algorithm. Therefore, The enhanced algorithm meets the requirement for optimal obstacle avoidance path planning by consistently finding the shortest path while avoiding obstacles.

关键词： Robotic arm Path planning RRT algorithm sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：