Fast Tree-Based Exploration of State Space for Robots with Dynamics
Fast Tree-Based Exploration of State Space for Robots with Dynamics
复制标题
动力学机器人状态空间的快速树型探索
DOI：
10.1007/10991541_21
复制
发表时间：
2004
影响因子：
7.8
通讯作者：
L. Kavraki
中科院分区：
文献类型：
--
作者：
Andrew M. Ladd;L. Kavraki
摘要本文提出了一种新的运动规划算法，我们称之为路径导向细分树探索规划器PDST-EXPLORE。这是一种基于采样的方法，它构建了一棵树，并采取了与其他勘探计划者（如RRT [18]和EST [12]）截然不同的方法。PDST-EXPLORE是一个通用的规划，但旨在克服固有的困难，规划机器人与非平凡的动态。具体来说，我们的规划器将样本表示为路径段而不是单个状态，并使用状态空间的非均匀细分来估计覆盖范围。这种变化避免了以前基于抽样的规划者在里程碑放置、度量和覆盖估计方面遇到的许多问题。我们使用一个确定性的更新时间表与随机路径生成自适应贪婪的探索和有条不紊的搜索之间的平衡。我们已经得到了一个概率完备性的证明，该计划的规划师很少假设的特定机器人系统的规划师operationon. Finally，我们已经实现了平面kinodynamic点机器人，差分驱动机器人和飞艇机器人的规划。实验结果表明，该规划器的实施效率以及其在覆盖整个可达自由空间的鲁棒性。
AbstractThis paper presents a new motion planning algorithm which we call the Path-Directed Subdivision Tree exploration Planner PDST-EXPLORE. It is a sampling-based method which builds a tree and takes a substantially different approach from other exploration planners such as RRT [18] and EST [12]. PDST-EXPLORE is a general purpose planner but is designed to overcome difficulties inherent in planning for robots with non-trivial dynamics. Specifically, our planner represents samples as path segments rather than individual states and uses non-uniform subdivisions of the state space to estimate coverage. This change avoids many of the problems that previous sampling-based planners have had with milestone placement, metrics and coverage estimation. We use a deterministic update schedule together with randomized path generation to adaptively strike a balance between greedy exploration and methodical search. We have obtained a proof of probabilistic completeness for the planner which assumes very little about the specific robot system that the planner operates on. Finally, we have implemented the planner for planar kinodynamic point robots, differential drive robots and blimp-like robots. The experimental results demonstrate the efficiency of the planner’s implementation as well as its robustness in covering the entire reachable free space.