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

PQ-RRT*: An improved path planning algorithm for mobile robots

EXPERT SYSTEMS WITH APPLICATIONS 2020年 152卷 113425-113425页

作者： Li, Yanjie Wei, Wu Gao, Yong Wang, Dongliang Fan, Zhun South China Univ Technol Sch Automat Sci & Engn Guangzhou 510641 Guangdong Peoples R China Shantou Univ Dept Elect & Informat Engn Shantou 515063 Peoples R China Shantou Univ Key Lab Digital Signal & Image Proc Guangdong Pro Shantou 515063 Peoples R China Shantou Univ Key Lab Intelligent Mfg Technol Minist Educ Shantou 515063 Guangdong Peoples R China Huazhong Univ Sci & Technol State Key Lab Digital Mfg Equipment & Technol Wuhan 43003 Peoples R China

During the last decade, sampling-based algorithms for path planning have gained considerable attention. The RRT*, a variant of RRT (rapidly-exploring random trees), is of particular concern to researchers due to its asymptotic optimality. However, the limits of the slow convergence rate of RRT* makes it inefficient for applications. For the purposes of overcoming these limitations, this paper proposes a novel algorithm, PQ-RRT*, which combines the strengths of P-RRT* (potential functions based RRT*) and Quick-RRT*. PQ-RRT* guarantees a fast convergence to an optimal solution and generates a better initial solution. The asymptotic optimality and fast convergence of the proposed algorithm are proved in this paper. Comparisons of PQ-RRT* with P-RRT* and Quick-RRT* in four benchmarks verify the effectiveness of the proposed algorithm. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Path planning sampling-based algorithms Rapidly-exploring random tree (RRT) Optimal path planning

来源：评论

学校读者我要写书评

暂无评论

The critical radius in sampling-based motion planning

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2020年第2-3期39卷 266-285页

作者： Solovey, Kiril Kleinbort, Michal Stanford Univ Dept Aeronaut & Astronaut 496 Lomita MallWilliam F Durand Bldg Stanford CA 94305 USA Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

We develop a new analysis of sampling-based motion planning in Euclidean space with uniform random sampling, which significantly improves upon the celebrated result of Karaman and Frazzoli and subsequent work. In particular, we prove the existence of a critical connection radius proportional to Theta ( n - 1 / d ) for n samples and d dimensions: below this value the planner is guaranteed to fail (similarly shown by Karaman and Frazzoli). More importantly, for larger radius values the planner is asymptotically (near-)optimal. Furthermore, our analysis yields an explicit lower bound of 1 - O ( n - 1 ) on the probability of success. A practical implication of our work is that asymptotic (near-)optimality is achieved when each sample is connected to only Theta ( 1 ) neighbors. This is in stark contrast to previous work that requires Theta ( log n ) connections, which are induced by a radius of order ( log n n ) 1 / d . Our analysis applies to the probabilistic roadmap method (PRM), as well as a variety of "PRM-based" planners, including RRG, FMT*, and BTT. Continuum percolation plays an important role in our proofs. Lastly, we develop similar theory for all the aforementioned planners when constructed with deterministic samples, which are then sparsified in a randomized fashion. We believe that this new model, and its analysis, is interesting in its own right.

关键词： Motion planning sampling-based algorithms probabilistic roadmaps random geometric graphs continuum percolation probabilistic completeness asymptotic optimality

来源：评论

学校读者我要写书评

暂无评论

Informed scenario-based RRT* for aircraft trajectory planning under ensemble forecasting of thunderstorms

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2021年 129卷 103232-103232页

作者： Andre, Eduardo Gonzalez-Arribas, Daniel Soler, Manuel Kamgarpour, Maryam Sanjurjo-Rivo, Manuel Univ Carlos III Dept Bioengn & Aerosp Engn Madrid Spain Univ British Columbia Elect & Comp Engn Vancouver BC Canada

Thunderstorms represent a major hazard for flights, as they compromise the safety of both the airframe and the passengers. To address trajectory planning under thunderstorms, three variants of the scenario-based rapidly exploring random trees (SB-RRTs) are proposed. During an iterative process, the so-called SB-RRT, the SB-RRT* and the Informed SB-RRT* find safe trajectories by meeting a user-defined safety threshold. Additionally, the last two techniques converge to solutions of minimum flight length. Through parallelization on graphical processing units the required computational times are reduced substantially to become compatible with near real-time operation. The proposed methods are tested considering a kinematic model of an aircraft flying between two waypoints at constant flight level and airspeed;the test scenario is based on a realistic weather forecast and assumed to be described by an ensemble of equally likely members. Lastly, the influence of the number of scenarios, safety margin and iterations on the results is analyzed. Results show that the SB-RRTs are able to find safe and, in two of the algorithms, close to-optimum solutions.

关键词： Aircraft path planning sampling-based algorithms Uncertain thunderstorm avoidance Parallel programming

来源：评论

学校读者我要写书评

暂无评论

F-RRT*: An improved path planning algorithm with improved initial solution and convergence rate

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 184卷 115457-115457页

作者： Liao, Bin Wan, Fangyi Hua, Yi Ma, Ruirui Zhu, Shenrui Qing, Xinlin Northwestern Polytech Univ Sch Aeronaut Xian 710072 Peoples R China

During the last decades, sampling-based algorithms have been used to solve the problem of motion planning. RRT*, as an optimal variant of RRT, provides asymptotic optimality. However, the slow convergence rate and costly initial solution make it inefficient. To overcome these limitations, this paper proposes a modified RRT* algorithm, F-RRT*, which generates a better initial solution and converges faster than RRT*. F-RRT* optimizes the cost of paths by creating a parent node for the random point, instead of selecting it among the existing vertices. The creation process can be divided into two steps, the FindReachest, and CreatNode procedures, which require few calculations, and the triangle inequality is used repeatedly throughout the process, thus, resulting in paths with higher performance than those of RRT*. Since the algorithm proposed in this paper is a tree extending algorithm, its performance can be further enhanced when combined with other sampling strategies. The advantages of the proposed algorithm in the initial solution and fast convergence rate are demonstrated by comparing with RRT*, RRT*-Smart, and Q-RRT* through numerical simulations in this paper.

关键词： Path planning sampling-based algorithms Rapidly-exploring random tree (RRT) Optimal path planning

来源：评论

学校读者我要写书评

暂无评论

T*-Lite: A Fast Time-Risk Optimal Motion Planning Algorithm for Multi-Speed Autonomous Vehicles

T*-Lite: A Fast Time-Risk Optimal Motion Planning Algorithm ...

引用

Global OCEANS Singapore - U.S. Gulf Coast Conference

作者： Wilson, James P. Shen, Zongyuan Gupta, Shalabh Wettergren, Thomas A. Univ Connecticut Dept Elect & Comp Engn Storrs CT 06269 USA Naval Undersea Warfare Ctr Newport RI 02841 USA

ISBN: (纸本)9781728154466

In this paper, we develop a new algorithm, called T*-Lite, that enables fast time-risk optimal motion planning for variable-speed autonomous vehicles. The T*-Lite algorithm is a significantly faster version of the previously developed T* algorithm. T*-Lite uses the novel time-risk cost function of T*;however, instead of a grid-based approach, it uses an asymptotically optimal sampling-based motion planner. Furthermore, it utilizes the recently developed Generalized Multi-speed Dubins Motion-model (GMDM) for sample-to-sample kinodynamic motion planning. The sample-based approach and GMDM significantly reduce the computational burden of T* while providing reasonable solution quality. The sample points are drawn from a four-dimensional configuration space consisting of two position coordinates plus vehicle heading and speed. Specifically, T*Lite enables the motion planner to select the vehicle speed and direction based on its proximity to the obstacle to generate faster and safer paths. In this paper, T*-Lite is developed using the RRT* motion planner, but adaptation to other motion planners is straightforward and depends on the needs of the planner.

关键词： Autonomous vehicles curvature-constraints time-risk optimal motion planning sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

A fruit fly-inspired path planning algorithm for unmanned aerial vehicle in underground environments based on low-discrepancy sequences

引用

Engineering Applications of Artificial Intelligence 2025年 156卷

作者： Huageng Zhong Yu Du Dong Liu Minghao Wang Ming Cong Xiaojing Tian School of Mechanical Engineering Dalian University of Technology Dalian 116024 China School of Mechanical Engineering Dalian Jiaotong University Dalian 116028 China Ningbo Institute of Dalian University of Technology Ningbo 315032 China

sampling planning algorithms are crucial in high-dimensional path planning for unmanned aerial vehicle (UAV), particularly in underground environments where Global Positioning System (GPS) signals are absent. The Rapidly-exploring Random Tree (RRT) algorithm, however, faces challenges due to the use of pseudo-random sequences, resulting in issues such as under-sampling, over-sampling, and they also suffer from high computational costs and redundant paths. To address these limitations, the (Halton-based Clustering) HBC-RRT algorithm is proposed. This algorithm utilizes the Halton sequence, replacing the pseudo-random sequence, which fundamentally resolves the problems of under-sampling and over-sampling in the RRT method. Additionally, a novel sampler is introduced, inspired by the fruit fly guidance mechanism, which optimizes the dual-tree sampling process by selecting either the optimal sampling candidate strategy or virtual sub-goal points. The optimal sampling candidate strategy conducts global sampling in three-dimensional space, effectively reducing sampling time. The virtual sub-goal points accelerate the dual-tree connection process, enhancing the directional guidance. The fruit fly mechanism reconstructs the path, leading to a reduction in UAV path costs. The performance of the HBC-RRT algorithm is evaluated through simulation experiments, demonstrating superior results in comparison to four baseline algorithms, including reductions in path length, convergence time, and memory usage. The practical applicability of the algorithm is further validated through real-world experiments involving a UAV and radar in an underground environment.

关键词： Halton sequence Path planning Rapidly-exploring random tree sampling-based algorithms Underground space Unmanned aerial vehicle

来源：评论

学校读者我要写书评

暂无评论

Improving Solution Quality for Experience-based Framework Through Clustering algorithms

引用

IEEE ACCESS 2019年 7卷 106720-106725页

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

This paper presents an extension for the current developed experience-based frameworks. The current experience-based scheme depends on executing two parallel threads;one tries to solve the problem using traditional approaches, while the other thread uses experience from past solutions for solving it. Once one of these threads solves the problem, its solution is promoted to be the problem's solution, yet disregarding the solution quality. However, our extension to experience-based frameworks uses clustering to decides which thread will solve the problem while maintaining solution quality. We have used experience-based motion planners for benchmarking our approach, where the presented results demonstrate that this approach works with different experience representations while maintaining better path quality, experience utilization, and reduced computational cost.

关键词： Artificial intelligence case-based reasoning experience-based algorithms motion planning sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate

引用

EXPERT SYSTEMS WITH APPLICATIONS 2019年 123卷 82-90页

作者： Jeong, In-Bae Lee, Seung-Jae Kim, Jong-Hwan Georgia Inst Technol Sch Civil & Environm Engn North Ave Atlanta GA 30332 USA Korea Adv Inst Sci & Technol Sch Elect Engn 291 Daehak Ro Daejeon 34141 South Korea

The Rapidly-exploring Random Tree (RRT) algorithm is a popular algorithm in motion planning problems. The optimal RRT (RRT*) is an extended algorithm of RRT, which provides asymptotic optimality. This paper proposes Quick-RRT* (Q-RRT*), a modified RRT* algorithm that generates a better initial solution and converges to the optimal faster than RRT*. Q-RRT* enlarges the set of possible parent vertices by considering not only a set of vertices contained in a hypersphere, as in RRT*, but also their ancestry up to a user-defined parameter, thus, resulting in paths with less cost than those of RRT*. It also applies a similar technique to the rewiring procedure resulting in acceleration of the tendency that near vertices share common parents. Since the algorithm proposed in this paper is a tree extending algorithm, it can be combined with other sampling strategies and graph-pruning algorithms. The effectiveness of Q-RRT* is demonstrated by comparing the algorithm with existing algorithms through numerical simulations. It is also verified that the performance can be further enhanced when combined with other sampling strategies. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： RRT sampling-based algorithms Navigation Motion planning Optimal path planning

来源：评论

学校读者我要写书评

暂无评论

Simultaneous system design and path planning: A sampling-based algorithm

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2019年第2-3期38卷 375-387页

作者： Molloy, Kevin Denarie, Laurent Vaisset, Marc Simeon, Thierry Cortes, Juan Univ Toulouse CNRS LAAS CNRS Toulouse France

This paper addresses the simultaneous design and path-planning problem, in which features associated to the bodies of a mobile system must be selected to find the best design that optimizes its motion between two given configurations. Solving individual path-planning problems for all possible designs and selecting the best result would be straightforward only for very simple cases. We propose a more efficient approach that combines discrete (design) and continuous (path) optimization in a single stage. It builds on an extension of a sampling-based algorithm, which simultaneously explores the configuration-space costmap of all possible designs, aiming to find the best path-design pair. The algorithm filters out unsuitable designs during the path search, which breaks down the combinatorial explosion. Illustrative results are presented for relatively simple (academic) robotic examples, showing that even in these simple cases, the computational cost can be reduced by two orders of magnitude with respect to the naive approach. A preliminary application to challenging problems in computational biology related to protein design is also discussed.

关键词： Robot motion planning sampling-based algorithms computational biology protein design

来源：评论

学校读者我要写书评

暂无评论

Kinematics analysis and self - collision detection of Truss type multi-robot cooperative welding platform 52

Kinematics analysis and self - collision detection of Truss ...

引用

52nd CIRP Conference on Manufacturing Systems (CMS)

作者： Hou, Ziting Ma, Shumei Zeng, Qingfei Li, Aiping Tongji Univ Inst Adv Manufacture Technol Shanghai 201800 Peoples R China

A collaborative welding platform consists of a XYZ-mobile truss, a 3R (revolute joint) clamping robot and a dual-arm welding robot. based on Denavit-Hartenberg (D-H) method, the analytical inverse kinematics solution of the platform is obtained. Dual-arm coordination is a technical difficulty in robot control field. Focusing on self-collision problem during dual-arm robot motion planning, this paper proposes a new obstacle avoidance algorithm based on Rapidly Exploring Random Tree (RRT) algorithm. Setting searching area founded on artificial potential field (APF) algorithm and adopting note-pruning strategy achieves high searching efficiency. Simulation results verify the correctness of kinematics analysis and self-collision detection algorithm. (C) 2019 The Authors. Published by Elsevier Ltd.

关键词： muti-robot platform self-collision kinematics sampling-based algorithms motion planning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：