Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles
Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles
复制标题
机器人运动规划的广义惰性搜索：通过基于事件的切换进行交错搜索和边缘评估
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Aditya Mandalika;Sanjiban Choudhury;Oren Salzman;S. Srinivasa
懒惰的搜索算法可以有效地解决边缘评估是计算中瓶颈的问题，就像机器人运动计划一样。 Lazysp的最佳算法懒惰地将边缘评估限制在最短路径上。这样做是以搜索工作为代价的，即，每当发现边缘无效时，Lazysp都必须重新计算搜索树。当处理大图或高度混乱的环境时，这变得非常昂贵。我们的关键见解是需要平衡边缘评估和搜索工作，以最大程度地减少计划时间。我们的贡献是两个方面。首先，我们提出了一个框架，广义的懒惰搜索（GLS），该框架在搜索和评估之间无缝切换以防止浪费的努力。我们表明，对于选择切换，GLS比Lazysp更有效。其次，我们利用Edge概率的先前经验来得出最小化预期计划时间的GLS政策。我们表明，在R2，SE（2）和7-DOF操纵中，配备了此类先验的GLS明显优于竞争基线。
Lazy search algorithms can efficiently solve problems where edge evaluation is the bottleneck in computation, as is the case for robotic motion planning. The optimal algorithm in this class, LazySP, lazily restricts edge evaluation to only the shortest path. Doing so comes at the expense of search effort, i.e., LazySP must recompute the search tree every time an edge is found to be invalid. This becomes prohibitively expensive when dealing with large graphs or highly cluttered environments. Our key insight is the need to balance both edge evaluation and search effort to minimize the total planning time. Our contribution is two-fold. First, we propose a framework, Generalized Lazy Search (GLS), that seamlessly toggles between search and evaluation to prevent wasted efforts. We show that for a choice of toggle, GLS is provably more efficient than LazySP. Second, we leverage prior experience of edge probabilities to derive GLS policies that minimize expected planning time. We show that GLS equipped with such priors significantly outperforms competitive baselines for many simulated environments in R2,SE(2) and 7-DoF manipulation.
运动规划中惰性的可证明的优点
DOI：
--
发表时间：
2018
期刊：
ICAPS 2018
影响因子：
--
作者：
Haghtalab, N.;Mackenzie, S.;Procaccia, A. D.;Salzman, O.;Srinivasa, S.
通讯作者：
Srinivasa, S.