Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps
Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps
复制标题
用于并行计算多个查询路线图的树的概率路线图
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
L. Kavraki
中科院分区：
文献类型：
--
作者：
M. Akinc;Kostas E. Bekris;B. Chen;Andrew M. Ladd;E. Plaku;L. Kavraki
在一个可高效并行化的运动规划框架中，我们提出了用单查询规划器来解决多查询运动规划问题的技术组合。在多查询运动规划中，为了快速响应在线查询，在预处理阶段建立了一个数据结构。或者，在单一查询规划中，没有预处理阶段，所有计算都在查询解析期间进行。本文展示了如何将一种主要用于多查询规划的强大的基于样本的方法(概率路线图方法-PRM)与主要用于单查询规划的基于样本的树方法(如扩展空间树、快速探索随机树等)有效地结合在一起。我们的规划器，我们称为树的概率路线图(PRT)，使用树算法作为PRM的子例程。PRM路线图的节点现在是树。我们利用最近树木规划师非常强大的抽样方案来填充我们的路线图。组合抽样方案遵循了早期PRM工作中采用的非均匀抽样和细化技术的精神。PRT不仅实现了多查询和单查询规划之间的平稳过渡，而且结合了两者的优点。我们给出的实验表明，PRT能够解决PRM或单查询规划器无法有效解决的问题。PRT的一个关键优势是，它比PRM和基于样本的树木规划器更具解耦性。利用这一性质，我们设计并实现了一个并行版本的PRT。我们的实验表明，PRT分布良好，可以很容易地解决耗尽单机可用资源的高维问题。
We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners in a motion planning framework that can be efficiently parallelized. In multiple query motion planning, a data structure is built during a preprocessing phase in order to quickly respond to on-line queries. Alternatively, in single query planning, there is no preprocessing phase and all computations occur during query resolution. This paper shows how to effectively combine a powerful sample-based method primarily designed for multiple query planning (the Probabilistic Roadmap Method - PRM) with sample-based tree methods that were primarily designed for single query planning (such as Expansive Space Trees, Rapidly Exploring Random Trees, and others). Our planner, which we call the Probabilistic Roadmap of Trees (PRT), uses a tree algorithm as a subroutine for PRM. The nodes of the PRM roadmap are now trees. We take advantage of the very powerful sampling schemes of recent tree planners to populate our roadmaps. The combined sampling scheme is in the spirit of the non-uniform sampling and refinement techniques employed in earlier work on PRM. PRT not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that PRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of PRT is that it is significantly more decoupled than PRM and sample-based tree planners. Using this property, we designed and implemented a parallel version of PRT. Our experiments show that PRT distributes well and can easily solve high dimensional problems that exhaust resources available to single machines.