Collision-probability constrained PRM for a manipulator with base pose uncertainty
Collision-probability constrained PRM for a manipulator with base pose uncertainty
复制标题
具有基座姿态不确定性的机械臂的碰撞概率约束 PRM
DOI：
10.1109/iros.2009.5354168
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Gupta
中科院分区：
文献类型：
--
作者：
Yifeng Huang;K. Gupta
研究了具有基本姿态不确定性的机械臂系统的运动规划问题，例如当机械臂安装在移动基座上时。使用基于粒子的不确定性表示，我们扩展了PRM(概率路线图)方法来处理这种基本不确定性。由于不确定性，机械手的路径与无冲突的概率相关联，这从根本上改变了PRM的查询阶段的性质。我们规划了一条最短路径，使得机械手无碰撞的概率高于用户定义的阈值，如果机械手沿着这条路径走的话。路径查询问题转化为冲突概率约束最短路径问题(CP-CSPP)，并表现为NP-Hard W.r.t。粒子的数量[1]。在此基础上，提出了一种基于k-最短路径算法和标记算法的懒惰查询算法Lazy-CPC-PRM(Collision Probability Constraint LazyPRM)。Lazy-CPC-PRM利用了一个关键的洞察力，即如果算法考虑的路径的一部分无效(其无冲突的概率小于阈值)或由另一子路径主导，则包含该部分的所有较长路径不可能是解路径。这在实践中导致了显著的效率提升。尽管在最坏的情况下，粒子数量的复杂性是指数级的，但对于安装在移动基座上的模拟3-DOF机械手，我们用30个粒子的实验证明了我们的查询算法的有效性。
We address the motion planning problem for a manipulator system with base pose uncertainty, e.g., when the manipulator is mounted on a mobile base. Using a particle based representation for the uncertainty, we extend the PRM (probabilistic roadmap) approach to deal with this base uncertainty. Because of the uncertainty, a path for the manipulator is associated with a probability of being collision-free, which fundamentally changes the nature of the PRM's query phase. We plan for a shortest path such that the probability of the manipulator being collision-free is higher than a user defined threshold, were the manipulator to follow the path. The path query problem becomes a collision probability constrained shortest path problem (CP-CSPP), and is shown as NP-hard w.r.t. the number of the particles [1]. We then present a lazy query algorithm, called Lazy-CPC-PRM (collision probability constrained LazyPRM), based on a k-shortest path algorithm in conjunction with a labeling algorithm. Lazy-CPC-PRM exploits a key insight that if a portion of a path considered by the algorithm is invalid (the probability of it being collision-free is less than a threshold) or is dominated by another sub-path, then all the longer paths containing this portion can not be the solution path. This leads to significant efficiency gains in practice. Although, worst case complexity is exponential in the number of particles, we empirically show the effectiveness of our query algorithm with 30 particles for a simulated 3-dof manipulator mounted on a mobile base.