Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges
Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges
复制标题
惰性后退地平线 A* 用于在具有昂贵的评估边的图中进行有效路径规划
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Aditya Mandalika;Oren Salzman;S. Srinivasa
运动规划问题，例如在混乱的环境中操纵，通常需要一条无碰撞的最短路径才能在路线图图中迅速计算。通常，评估路线图的边缘是否无碰撞的计算成本主导了搜索算法的运行时间。已经提出了诸如懒惰加权A*（LWA*）和Lazysp之类的算法，以减少边缘评估的数量，分别采用懒惰的LookAhead（分别为OneSpep LookAhead和Infinite step lookahead）。但是，这是以其他图形操作为代价的：lookahead越大，通常需要的图形操作就越多。我们建议通过平衡边缘评估和图形操作来最大程度地降低懒惰的Horizon A*（LRA*）。 LRA*具有懒惰的LookAhead，代表了一个懒惰的最短图形搜索算法，将LWA*和Lazysp推广。我们分析了LRA*的理论特性，并证明在许多情况下，为了最大程度地减少计划时间，该算法需要中间的懒惰lookahead。也就是说，使用中间懒惰的lookahead，我们的算法均优于lwa*和lazysp。这些实验涵盖了R^2和R^4中的随机世界，并使用7-DOF操纵器进行操纵问题。
Motion-planning problems, such as manipulation in cluttered environments, often require a collision-free shortest path to be computed quickly given a roadmap graph. Typically, the computational cost of evaluating whether an edge of the roadmap graph is collision-free dominates the running time of search algorithms. Algorithms such as Lazy Weighted A* (LWA*) and LazySP have been proposed to reduce the number of edge evaluations by employing a lazy lookahead (one-step lookahead and infinite-step lookahead, respectively). However, this comes at the expense of additional graph operations: the larger the lookahead, the more the graph operations that are typically required. We propose Lazy Receding-Horizon A* (LRA*) to minimize the total planning time by balancing edge evaluations and graph operations. Endowed with a lazy lookahead, LRA* represents a family of lazy shortest-path graph-search algorithms that generalizes LWA* and LazySP. We analyze the theoretic properties of LRA* and demonstrate empirically that, in many cases, to minimize the total planning time, the algorithm requires an intermediate lazy lookahead. Namely, using an intermediate lazy lookahead, our algorithm outperforms both LWA* and LazySP. These experiments span simulated random worlds in R^2 and R^4, and manipulation problems using a 7-DOF manipulator.
运动规划中惰性的可证明的优点
DOI：
--
发表时间：
2018
期刊：
ICAPS 2018
影响因子：
--
作者：
Haghtalab, N.;Mackenzie, S.;Procaccia, A. D.;Salzman, O.;Srinivasa, S.
通讯作者：
Srinivasa, S.