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

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

来源：评论

学校读者我要写书评

暂无评论

Neural Network Approximation based Near-Optimal Motion Planning With Kinodynamic Constraints Using RRT

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2018年第11期65卷 8718-8729页

作者： Li, Yang Cui, Rongxin Li, Zhijun Xu, Demin Northwestern Polytech Univ Sch Marine Sci & Technol Xian 710072 Shaanxi Peoples R China South China Univ Technol Coll Automat Sci & Engn Guangzhou 510641 Guangdong Peoples R China

In this paper, the problem of near-optimal motion planning for vehicles with nonlinear dynamics in a clustered environment is considered. based on rapidly exploring random trees (RRT), we propose an incremental sampling-based motion planning algorithm, i.e., nearoptimal RRT (NoD-RRT). This algorithm aims to solve motion planning problems with nonlinear kinodynamic constraints. To achieve the cost/metric between two given states considering the nonlinear constraints, a neural network is utilized to predict the cost function. On this basis, a new reconstruction method for the random search tree is designed to achieve a near-optimal solution in the configuration space. Rigorous proofs are presented to show the asymptotical near-optimality of NoD-RRT. Simulations are conducted to validate the effectiveness of NoD-RRT through comparisons with typical RRT and kinodynamic RRT*. In addition, NoD-RRT is demonstrated in an experiment using a Pioneer3-DX robot.

关键词： Kinodynamic constraints motion planning neural networks (NNs) sampling-based algorithms

来源：评论

学校读者我要写书评

暂无评论

New perspective on sampling-based motion planning via random geometric graphs

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2018年第10期37卷 1117-1133页

作者： Solovey, Kiril Salzman, Oren Halperin, Dan Tel Aviv Univ Blavatnik Sch Comp Sci Borochov 3 IL-59558 Bat Yam Israel Carnegie Mellon Univ Robot Inst Pittsburgh PA 15213 USA

Roadmaps constructed by many sampling-based motion planners coincide, in the absence of obstacles, with standard models of random geometric graphs (RGGs). Those models have been studied for several decades and by now a rich body of literature exists analyzing various properties and types of RGGs. In their seminal work on optimal motion planning, Karaman and Frazzoli conjectured that a sampling-based planner has a certain property if the underlying RGG has this property as well. In this paper, we settle this conjecture and leverage it for the development of a general framework for the analysis of sampling-based planners. Our framework, which we call localization-tessellation, allows for easy transfer of arguments on RGGs from the free unit hypercube to spaces punctured by obstacles, which are geometrically and topologically much more complex. We demonstrate its power by providing alternative and (arguably) simple proofs for probabilistic completeness and asymptotic (near-)optimality of probabilistic roadmaps (PRMs) in Euclidean spaces. Furthermore, we introduce three variants of PRMs, analyze them using our framework, and discuss the implications of the analysis.

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

来源：评论

学校读者我要写书评

暂无评论

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

引用

Procedia CIRP 2019年 81卷 488-493页

作者： Ziting Hou Shumei Ma Qingfei Zeng Aiping Li Institute of Advanced Manufacture Technology Tongji University Shanghai 201800 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.

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Robotics-inspired methods to enhance protein design

Robotics-inspired methods to enhance protein design

引用

作者： Laurent Denarie INP DE TOULOUSE

学位级别：博士

The ability to design proteins with specific properties would yield great progress in pharmacology and bio-technologies. Methods to design proteins have been developed since a few decades and some relevant achievements have been made including de novo protein design. Yet, current approaches suffer some serious limitations. By not taking protein's backbone motions into account, they fail at capturing some of the properties of the candidate design and cannot guarantee that the solution will in fact be stable for the goal conformation. Besides, although multi-states design methods have been proposed, they do not guarantee that a feasible trajectory between those states exists, which means that design problem involving state transitions are out of reach of the current methods. This thesis investigates how robotics-inspired algorithms can be used to efficiently explore the conformational landscape of a protein aiming to enhance protein design methods by introducing additional backbone flexibility. This work also provides first milestones towards protein motion design.

关键词： path planning protein design structural biology robotics sampling-based algorithms computational biology

来源：评论

学校读者我要写书评

暂无评论

Asymptotically optimal sampling-based kinodynamic planning

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2016年第5期35卷 528-564页

作者： Li, Yanbo Littlefield, Zakary Bekris, Kostas E. Rutgers State Univ 110 Frelinghuysen Rd CS Rutgers Piscataway NJ 08854 USA

sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, STABLE_SPARSE_RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.

关键词： Motion planning asymptotic optimality sampling-based algorithms kinodynamic planning steering functions

来源：评论

学校读者我要写书评

暂无评论

Anytime Dynamic Exploring Rapid Random Tree Approach in Higher Dimension Search Space for Non-Holonomic Robotics

Anytime Dynamic Exploring Rapid Random Tree Approach in High...

引用

International Conference on Advanced Robotics and Intelligent Systems (ARIS)

作者： Luo, Ren C. Huang, Charly Natl Taiwan Univ Dept Elect Engn Taipei Taiwan

ISBN: (纸本)9781509051021

With the breakthrough of exploring Rapid Random Tree and several other improvement efforts, the sampling-based motion planning method has been gaining ground in 2D planning and gradually being accepted by many systems as their global planning algorithm. There are many recent approaches on integrating the incremental nature and algorithmic simplicity of sampling-based approach with the agile replanning strategy studied on Incremental Heuristic based motion planning algorithms. Therefore, we develop an anytime dynamic RRT* for non-holonomic systems. We also implement Lyapunov function, which better represents the true-cost-to-go, in order to generate ideal and smoother trajectories. Our method proved to be more robust than some state-of-the-art planning algorithms, with lower cost and smoother path. We evaluate our algorithm with 3 major benchmarks in simulated as well as real-environment. We compared our algorithm with other major planning approaches and proved the cost yields between 8.5%similar to 16.7% less cost and as may reach as low as 58.17% and 95% less than RRT and RRT* respectively.

关键词： Motion Planning optimal path planning sampling-based algorithms Rapidly Exploring Random Tree Anytime Dynamic Approach

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：