Multiquery planning algorithms find paths between various different starts and goals in a single search space. They are designed to do so efficiently by reusing information across planning queries. This information may be computed before or during the search and often includes knowledge of valid paths. Using known valid paths to solve an individual planning query takes less computational effort than finding a completely new solution. This allows multiquery algorithms, such as PRM*, to outperform single-query algorithms, such as RRT*, on many problems but their relative performance depends on how much information is reused. Despite this, few multiquery planners explicitly seek to maximize path reuse and, as a result, many do not consistently outperform single-query alternatives. This paper presents Effort Informed Roadmaps (EIRM*), an almost-surely asymptotically optimal multiquery planning algorithm that explicitly prioritizes reusing computational effort. EIRM* uses an asymmetric bidirectional search to identify existing paths that may help solve an individual planning query and then uses this information to order its search and reduce computational effort. This allows it to find initial solutions up to an order-of-magnitude faster than state-of-the-art planning algorithms on the tested abstract and robotic multiquery planning problems.
翻译:多元规划算法在单个搜索空间中找到不同起始点和目标之间的路径。 设计这些算法的目的是通过在规划查询中重新使用信息, 从而高效地做到这一点。 这些信息可以在搜索之前或搜索期间计算, 并且往往包括有效路径的知识。 使用已知的有效路径解决个人规划查询, 与寻找全新的解决方案相比, 计算上的努力要少得多。 这使得多盘算法, 如 PRM* 等多盘算法, 能够比单盘算法( 如RRT* ) 更完善, 但其相对性能取决于再利用的信息量。 尽管如此, 很少有多盘算规划者明确寻求最大限度的路径再利用, 并且因此, 许多多盘算规划者并不一贯地超越单一查询方法。 本文展示了“ Efffort Intellicult Constructions( EIIRM* ), 几乎没有把握地以最优化的多盘计划算法算法, 明确优先重新使用计算努力。 EIRM* 使用不对称双向搜索来确定现有的路径, 以便帮助解决个人规划问题, 然后使用这些信息来命令搜索和减少计算努力。 。 。 。 使得它能够在初始算法上找到更快的进度。