Pareto-optimal search over configuration space beliefs for anytime motion planning
Pareto-optimal search over configuration space beliefs for anytime motion planning
复制标题
针对任意运动规划的配置空间信念的帕累托最优搜索
DOI：
10.1109/iros.2016.7759551
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Shushman Choudhury;Christopher M. Dellin;S. Srinivasa
我们提出了POMP（帕累托最优运动规划器），这是一种用于在路线图上进行几何路径规划的任意时间算法。对于具有多个自由度的机器人，碰撞检测在计算上是昂贵的，并且常常主导规划时间。我们的目标是最小化获取第一条可行路径以及依次更短的可行路径所需的碰撞检测次数。我们假设我们所搜索的路线图嵌入在一个连续的环境空间中，其中邻近的点往往具有相同的碰撞状态。这使我们能够构建一个概率模型，该模型计算未评估的配置无碰撞的概率。随着进行更多的检测，我们会随时间更新这个模型。这个模型让我们能够为路线图的边定义一个加权函数，该函数与边发生碰撞的概率相关。我们的方法是在这两个权重之间进行权衡，逐渐将边的长度优先于碰撞可能性。我们还表明，这种权衡大致等同于在有碰撞惩罚的情况下最小化预期路径长度。我们的实验表明，就碰撞检测和总规划时间而言，POMP在获取第一条可行路径方面与RRTConnect和LazyPRM性能相当，在任意时间性能方面与BIT*相当。
We present POMP (Pareto Optimal Motion Planner), an anytime algorithm for geometric path planning on roadmaps. For robots with several degrees of freedom, collision checks are computationally expensive and often dominate planning time. Our goal is to minimize the number of collision checks for obtaining the first feasible path and successively shorter feasible paths. We assume that the roadmaps we search over are embedded in a continuous ambient space, where nearby points tend to share the same collision state. This enables us to formulate a probabilistic model that computes the probability of unevaluated configurations being collision-free. We update the model over time as more checks are performed. This model lets us define a weighting function for roadmap edges that is related to the probability of the edge being in collision. Our approach is to trade off between these two weights, gradually prioritizing edge length over collision likelihood. We also show that this tradeoff is approximately equivalent to minimizing the expected path length, with a penalty of being in collision. Our experiments demonstrate that POMP performs comparably with RRTConnect and LazyPRM for the first feasible path, and BIT* for anytime performance, both in terms of collision checks and total planning time.
影响因子：
1.1
作者：
Salzman, Oren;Hemmer, Michael;Halperin, Dan
通讯作者：
Halperin, Dan