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

Anytime Informed Multi-Path Replanning Strategy for Complex Environments

IEEE ACCESS 2023年 11卷 4105-4116页

作者： Tonola, Cesare Faroni, Marco Beschi, Manuel Pedrocchi, Nicola Univ Brescia Dipartimento Ingn Meccan & Ind I-25123 Brescia Italy Natl Res Council Italy CNR STIIMA Inst Intelligent Ind Technol Syst Adv Mfg I-20133 Milan Italy Univ Michigan Dept Robot Ann Arbor MI 48109 USA

In many real-world applications (e.g., human-robot collaboration), the environment changes rapidly, and the intended path may become invalid due to moving obstacles. In these situations, the robot should quickly find a new path to reach the goal, possibly without stopping. Planning from scratch or repairing the current graph can be too expensive and time-consuming. This paper proposes MARS, a sampling-based Multi-pAth Replanning Strategy that enables a robot to move in dynamic environments with unpredictable obstacles. The novelty of the method is the exploitation of a set of precomputed paths to compute a new solution in a few hundred milliseconds when an obstacle obstructs the robot's path. The algorithm enhances the search speed by using informed sampling, builds a directed graph to reuse results from previous replanning iterations, and improves the current solution in an anytime fashion to make the robot responsive to environmental changes. In addition, the paper presents a multithread architecture, applicable to several replanning algorithms, to handle the execution of the robot's trajectory with continuous replanning and the collision checking of the traversed path. The paper compares state-of-the-art sampling-based path-replanning algorithms in complex and high-dimensional scenarios, showing that MARS is superior in terms of success rate and quality of solutions found. An open-source ROS-compatible implementation of the algorithm is also provided.

关键词： Robots Collision avoidance Trajectory Heuristic algorithms Computer architecture Motion planning Directed graphs Path planning Anytime search dynamic environments informed planning motion planning path replanning sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints

引用

AUTONOMOUS ROBOTS 2023年第3期47卷 281-297页

作者： Yu, Fujie Shang, Huaqing Zhu, Qilong Zhang, Hansheng Chen, Yuan Univ Shandong Univ Weihai Dept Mech Elect & Informat Engn Weihai 264209 Peoples R China

Quickly finding high-quality paths is of great significance for autonomous underwater vehicles (AUVs) in path planning problems. In this paper, we present a cylinder-based heuristic rapidly exploring random tree (Cyl-HRRT*) algorithm, which is the extension version of the path planner presented in our previous publication. Cyl-HRRT* increases the likelihood of sampling states that can improve the current solution by biasing the states into a cylindrical subset, thus providing better paths for AUVs. A direct greedy sampling method is proposed to explore the space more efficiently and accelerate convergence to the optimum. To reasonably balance the optimization accuracy and the number of iterations, a beacon-based adaptive optimization strategy is presented, which adaptively establishes a cylindrical subset for the next focused sampling according to the current path. Furthermore, the Cyl-HRRT* algorithm is shown to be probabilistically complete and asymptotically optimal. Finally, the Cyl-HRRT* algorithm is comprehensively tested in both simulations and real-world experiments. The results reveal that the path generated by the Cyl-HRRT* algorithm greatly improves the power savings and mobility of the AUV.

关键词： Optimal path planning Rapidly exploring random tree (RRT) Autonomous underwater vehicle Cylindrical subset sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Accelerating sampling-based optimal path planning via adaptive informed sampling

引用

AUTONOMOUS ROBOTS 2024年第2期48卷 6页

作者： Faroni, Marco Pedrocchi, Nicola Beschi, Manuel Politecn Milan Dipartimento Elettron Informaz & Bioingn Piazza Leonardo Vinci 32 I-20133 Milan Italy Natl Res Council Italy STIIMA CNR Inst Intelligent Ind Technol & Syst Via Alfonso Corti 12 I-20133 Milan Italy Univ Brescia Dipartimento Ingn Meccan & Ind Via Branze 38 I-25123 Brescia Italy

This paper improves the performance of RRT * \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {RRT}<^>*$$\end{document} -like sampling-based path planners by combining admissible informed sampling and local sampling (i.e., sampling the neighborhood of the current solution). An adaptive strategy regulates the trade-off between exploration (admissible informed sampling) and exploitation (local sampling) based on online reward from previous samples. The paper demonstrates that the resulting algorithm is asymptotically optimal and has a better convergence rate than state-of-the-art path planners (e.g., Informed-RRT * \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$<^>*$$\end{document} ) in several simulated and real-world scenarios. An open-source, ROS-compatible implementation of the algorithm is publicly available.

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

来源：评论

学校读者我要写书评

暂无评论

Solving the motion planning problem using learning experience through case-based reasoning and machine learning algorithms

引用

AIN SHAMS ENGINEERING JOURNAL 2020年第1期11卷 133-142页

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

This article presents two novel methodologies for solving the motion planning problem through retained experience. Both approaches employ AI's case-based reasoning (CBR) technique. Case-based reasoning is an expert system development methodology which reuses past solutions to solve new problems. The first approach uses CBR to retain K similar cases to solve the motion planning problem by merging those solutions into a set. Afterwards, it picks from this set based on a heuristic function to assemble a final solution. Regarding the second approach, it employs the retained K similar cases differently. It uses those solution to build a graph which can be queried using traditional graph search algorithms. Results prove the success of such approaches concerning solution quality and success rate compared to different experience-based algorithms. Such utilization for CBR systems develops new research directions for building systems that can solve NP problems based on retained experiences exclusively. (C) 2019 The Authors. Published by Elsevier B.V. on behalf of Faculty of Engineering, Ain Shams University. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

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

来源：评论

学校读者我要写书评

暂无评论

Cyl-IRRT*: Homotopy Optimal 3D Path Planning for AUVs by Biasing the sampling Into a Cylindrical Informed Subset

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2023年第4期70卷 3985-3994页

作者： Yu, Fujie Chen, Yuan Univ Shandong Univ Dept Mech Elect & Informat Engn Weihai 264209 Peoples R China

In a complex 3-D environment, efficiently and safely reaching the target position is of great significance for autonomous underwater vehicles. This article proposes a cylinder-based informed rapid exploration random tree (Cyl-iRRT*) algorithm, which seeks to find the homotopy optimal path by focusing the search space on the designed gradually shrinking cylinder. The proportional shrinkage method and obstacle-based sampling strategy are presented to yield a fast convergence response and robust stability. Furthermore, the probabilistic completeness and homotopic optimality of Cyl-iRRT* are proven to be effective. Finally, both simulation and real-world experimental results reveal the superiorities of the Cyl-iRRT* algorithm.

关键词： Autonomous underwater vehicle (AUV) optimal path planning rapidly exploring random tree (RRT) sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2015年 68卷 1-11页

作者： Qureshi, Ahmed Hussain Ayaz, Yasar NUST SMME Dept Robot & Artificial Intelligence Robot & Intelligent Syst Engn RISE Lab Islamabad 44000 Pakistan

The sampling-based motion planning algorithm known as Rapidly-exploring Random Trees (RRT) has gained the attention of many researchers due to their computational efficiency and effectiveness. Recently, a variant of RRT called RRT* has been proposed that ensures asymptotic optimality. Subsequently its bidirectional version has also been introduced in the literature known as Bidirectional-RRT* (B-RRT*). We introduce a new variant called Intelligent Bidirectional-ART* (IB-RRT*) which is an improved variant of the optimal RRT* and bidirectional version of RRT* (B-RRT*) algorithms and is specially designed for complex cluttered environments. IB-RRT* utilizes the bidirectional trees approach and introduces intelligent sample insertion heuristic for fast convergence to the optimal path solution using uniform sampling heuristics. The proposed algorithm is evaluated theoretically and experimental results are presented that compares IB-RRT* with RRT* and B-RRT*. Moreover, experimental results demonstrate the superior efficiency of IB-RRT* in comparison with RRT* and B-RRT in complex cluttered environments. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Motion planning sampling-based algorithms RRT RRT* Optimal path planning Bidirectional trees

来源：评论

学校读者我要写书评

暂无评论

ATS-RRT*: an improved RRT* algorithm based on alternative paths and triangular area sampling

引用

ADVANCED ROBOTICS 2023年第10期37卷 605-620页

作者： Zhang, Zhi-wei Jia, Yun-wei Su, Qi-qi Chen, Xiao-tong Fu, Bang-peng Tianjin Univ Technol Tianjin Key Lab Adv Mechatron Syst Design & Intell Tianjin Peoples R China Tianjin Univ Technol Natl Demonstrat Ctr Expt Mech & Elect Engn Educ Tianjin Peoples R China Tiandy Technol Co Ltd Tianjin Peoples R China

The Rapidly Exploring Random Tree Star (RRT*) is a probabilistically complete algorithm. It is recognized as a better path planning algorithm, but its path quality and path planning speed still have room for improvement. This paper proposes an improved RRT* algorithm based on alternative paths and triangular area sampling (ATS-RRT*). The alternative paths strategy generates multiple initial paths based on whether the sample points can communicate with the target points and set the path with the smallest cost as the final initial path, which can speed up the initial path planning and improve the initial path finding rate. The triangular area sampling strategy combines every three adjacent nodes to generate some triangle areas and corresponding half-triangle areas. The path quality can be improved quickly by limiting the sampling in these triangle areas. In addition, the direct connection strategy with triangle nodes and the tabu table using in the Rewire process also speeds up the algorithm. Experiments show that the speed of finding the initial path and the success rate of finding the suboptimal path are improved by 2.3 and 1.45 times respectively compared with RRT*, Quick-RRT*, and Informed + Quick-RRT*.

关键词： RRT* path planning sampling-based algorithms direct connection strategy

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Deterministic sampling-based motion planning: Optimality, complexity, and performance

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2018年第1期37卷 46-61页

作者： Janson, Lucas Ichter, Brian Pavone, Marco Stanford Univ Dept Stat Stanford CA 94305 USA Stanford Univ Dept Aeronaut & Astronaut William F Durand BldgRm 261 496 Lomita Mall Stanford CA 94305 USA

Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical performance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed (i.i.d.) random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certification for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random, sampling sequences. The objective of this paper is to provide a rigorous answer to this question. Specifically, we first show that PRM, for a certain selection of tuning parameters and deterministic low-dispersion sampling sequences, is deterministically asymptotically optimal, in other words, it returns a path whose cost converges deterministically to the optimal one as the number of points goes to infinity. Second, we characterize the convergence rate, and we find that the factor of sub-optimality can be very explicitly upperbounded in terms of the '2-dispersion of the sampling sequence and the connection radius of PRM. Third, we show that an asymptotically optimal version of PRM exists with computational and space complexity arbitrarily close to O(n) (the theoretical lower bound), where n is the number of points in the sequence. This is in contrast to the O(n log n) complexity results for existing asymptotically optimal probabilistic planners. Fourth, we discuss extending our theoretical results and insights to other batch-processing algorithms such as FMT*, to non-uniform

关键词： Motion planning optimal path planning sampling-based algorithms motion control l(2)-dispersion

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：