Learning When to Quit: Meta-Reasoning for Motion Planning

作者: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

许可协议

• 开放获取
• 论文: CC BY 4.0

以下内容均依据论文全文，按其 CC BY 4.0 许可协议使用；其中的图已注明作者。

一句话总结

从以往的规划器运行中学习何时停止任意时间运动规划器（RRT、PRM、Lazy PRM*），使路径质量与规划时间之间的权衡达到最大化。

为何重要

任何使用 RRT 或 PRM 进行规划的机器人都必须选定规划时间预算，而固定时间或固定质量阈值要么浪费时间，要么牺牲路径质量。该方法封装一个未经修改的任意时间规划器，因此只要能获得来自目标环境分布的训练问题，就可以叠加在现有的 OMPL 式规划器之上。

问题

任意时间运动规划器运行得越久，路径就越短，但解的质量与计算时间之间并没有得到充分刻画的关系，因此不清楚何时应停止规划并开始移动。它们的性能曲线高度不平滑，因为当规划器找到新的同伦类时，更短的路径会突然跳跃式出现，这就排除了对未来质量进行简单在线外推的可能。

提出的方法

作者从来自同一分布的以往规划问题的性能曲线中学习停止策略，最大化一个由用户加权的效用 U(q, t) = wq − (1 − w)t。基于模型的变体在离散化的质量和时间上学习一个马尔可夫决策过程，并用值迭代求解；两种无模型变体（基于手工设计特征的前馈分类器，以及 RNN 序列到序列模型）模仿事后计算出的预言机（oracle）停止决策。一个 CNN 根据 2D 工作空间图像预测最优路径长度，使难度不同的问题的性能曲线能够归一化并相互比较。

关键见解

• 可以事后为每次训练运行计算出最优停止时间，从而把策略学习问题转化为监督式模仿学习，而不是强化学习。
• 对路径质量进行归一化需要未知的最优路径长度；用一个根据 2D 工作空间图像预测该长度的 CNN，可以使不同问题的性能曲线相互可比，而较差的归一化基准（从起点到目标的直线）会使效用大幅下降。
• 更丰富的历史特征（斜率、平坦度）使基于模型的转移模型准确得多，但其估计成本从数秒增长到超过一天，是维数灾难的直接例证。
• RNN 从原始效用序列中自行学习时间特征，在不同规划器和效用权重下给出了最稳定的良好结果。

主要结果

• CNN 最优路径长度预测器在 200 个留出工作空间上的精度：在三种环境分布中分别为 88.21%、96.23% 和 94.25%。
• 在这三种环境中，使用 CNN 归一化得到的效用为 0.58、0.65 和 0.66，而使用真实最优长度时为 0.63、0.70 和 0.67，使用直线归一化时为 0.39、0.40 和 0.60。
• 转移模型的留出损失从 1.84（无特征）降至使用 (t, q) 时的 0.22 和使用 (t, q, slope) 时的 0.10，而估计时间则从 0.41 s 增至 10.64 s 和 11,933.72 s。
• RRT* 在 w = 0.8 时：预言机效用 0.677，RNN 0.670，基于模型 0.663，分类器 0.658，而固定质量基线为 0.634，固定时间基线为 0.575。
• PRM* 在 w = 0.8 时：预言机 0.718，基于模型 0.702，RNN 0.698，分类器 0.697，固定质量 0.674，固定时间 0.662。
• 在 w = 0.2 时，固定质量基线变为负值（RRT 为 −0.283，PRM 为 −0.344，Lazy PRM* 为 −0.367），而学习方法仍保持正值。

局限

• CNN 最优解预测器以 2D 工作空间图像为输入，这使这些方法仅限于平面工作空间的问题；文中提出可通过体素网格或点云扩展到 3D，但并未实现。
• 假定新问题与训练问题来自同一分布，且训练需要在有代表性的问题上进行大量长时间的规划器运行。
• 在较大规模的实验中，为基于模型的方法加入历史特征在计算上不可行，因此它只使用了 (q, q_prev, t)。
• 所有评估均在仿真中进行，使用 2D 工作空间中的三自由度刚性机器人；未在实体机器人上测试。
• 只研究了线性效用 U(q, t) = wq − (1 − w)t。

对领域的影响

该论文入围 IROS 2021 认知机器人最佳论文奖决选，被引用 14 次。论文未说明是否发布代码或数据。

摘要

任意时间运动规划器在机器人领域被广泛使用。然而，其解的质量与计算时间之间的关系尚未得到充分理解，因此何时停止规划并开始执行并不明确。在本文中，我们针对任意时间运动规划，研究在有限计算能力下决定何时停止思考（即所谓的元推理）的问题。我们提出了数据驱动的学习方法，即基于模型和无模型的元推理，它们适用于不同的环境分布，且与所选用的任意时间运动规划器无关。作为该框架的一部分，我们设计了一种基于卷积神经网络的最优解预测器，可根据给定的 2D 工作空间图像预测最优路径长度。我们在仿真中对所提方法的性能进行了实证评估，并与基线方法进行了比较。

链接

• arXiv 2103.04374: https://arxiv.org/abs/2103.04374
• DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
• PDF: https://arxiv.org/pdf/2103.04374v1