Multi-Resolution POMDP Planning for Multi-Object Search in 3D

作者: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · IROS 2021

许可协议

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

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

一句话总结

将 3D 多物体搜索建模为 POMDP，并通过在多个八叉树分辨率上并行规划进行在线求解；它在大型模拟空间中优于无层级基线，并在 Kinova MOVO 上运行。

为何重要

它将 POMDP 物体搜索从 2D 地图推进到 3D 搜索区域，同时将在线规划保持在每步固定时间内。八叉树信念无需完整构建，遮挡则通过 UNKNOWN 体素标签处理，无需杂物的几何模型。

问题

家庭机器人必须在有限的截头锥体形相机视野和遮挡条件下，在架子上、桌子下和橱柜里找到多个物体。基于 POMDP 的物体搜索有理论依据，但早期工作将搜索空间或机器人移动性简化为 2D，因为在大型 3D 状态空间上计算精确信念不可行，而大观测空间会给规划器带来很高的分支因子。

提出的方法

作者定义了 3D-MOS：一种面向对象的 POMDP，具有 6D 相机位姿，MOVE、LOOK 和 FIND 动作，其观测由视锥内带标签的体素组成，并按物体分解。逐体素观测模型与八叉树信念可在 O(|V| log |G|) 内完成精确信念更新，并在 O(log |G|) 内以任意分辨率采样；较粗分辨率下的各个抽象 POMDP 分别由 POUCT 并行求解，并执行价值最高的动作（MR-POUCT）。

关键见解

• 按物体对状态和观测进行分解，使信念空间随物体数量线性增长，而非指数增长。
• 对每个体素的标签单独建模，并将被遮挡或视野外的体素视为无信息，可缩小用于规划的观测空间，并将信念更新限制在视野内的体素。
• 将信念存储在八叉树中、每个节点保存其子节点值之和，可在每个分辨率上得到精确信念，并实现对数时间采样。
• 在多个分辨率上并行规划并执行最佳动作，可应对单一分辨率无法适配的未知物体尺寸和距离。
• 粒子信念（POMCP）在大观测空间下会出现粒子匮乏，在该领域中退化为随机行为。

主要结果

• 在 12 种设置的模拟中（搜索空间边长 m ∈ {4, 8, 16, 32}，n ∈ {2, 4, 6} 个物体，每种 40 次试验），按折扣累积奖励计算，MR-POUCT 在 m = 16 和 m = 32 的所有测试用例中均优于 Exhaustive 搜索。
• Exhaustive 搜索在小空间（m = 4 和 8）中表现更好，此时一个视野最多覆盖网格的 17.2% 和 8.8%；在 m = 32 时，一个视野最多覆盖 2.6%。
• 每种方法每步最多有 3.0 s 规划时间，总计 120 s 至 480 s（取决于 m）；POMCP 因粒子匮乏而表现不佳。
• 在 (16, 2, 10) 实例上加入感知噪声时，MR-POUCT 在所有尝试的设置下始终最佳，且当 β < 1 时 β 几乎没有影响。正文称 α 有 5 种设置，但列出了六个值（10、100、500、10³、10⁴、10⁵）。
• 在 Kinova MOVO 上，机器人在约 15 分钟内，于两个约 10 m² × 2 m 的区域中找到了放置在不同高度的 6 个物体中的 3 个，并在需要看到目标时降低躯干。
• 抽象观测模型使用 k = 10 或 k = 40 个蒙特卡洛样本时，搜索性能相近；实际采用 k = 10。

局限

• 假设物体相互独立可节省计算，但可能丢弃物体之间有用的依赖关系；搜索相关联物体的问题仍未解决（作者自述）。
• 观测模型不对物体几何进行推理，并假设每个物体在规划分辨率下都能放入单个体素（作者自述）。
• 使用的是均匀随机 rollout 策略；作者建议在更贴近现实的问题中采用启发式 rollout，但会牺牲最优性。
• 在真实机器人上，拓扑地图的任何视点都未覆盖到的物体被遗漏；作者提出使用更密集的地图或采样的 MOVE 目的地。
• 假设物体和障碍物是静态的、机器人状态可观测；并且在小搜索空间中，简单的穷举搜索表现更好。

对领域的影响

它获得了 IROS 2021 最佳 RoboCup 论文奖，被引用 33 次。论文链接了一个项目页面，其中有体积观测和八叉树信念更新的视频；论文未说明是否发布代码。

摘要

在家庭中工作的机器人必须在架子上、桌子下和橱柜里找到物体。在这类环境中，以 3D 尺度高效搜索，同时应对有限的视野和搜索多个物体的复杂性，是至关重要的。有原则的物体搜索方法常以部分可观测马尔可夫决策过程（POMDP）作为计算搜索策略的底层框架，但将搜索空间限制在 2D。本文提出一种在 3D 区域中、以截头锥体形视野进行多物体搜索的 POMDP 建模。为高效求解该 POMDP，我们提出一种基于在线蒙特卡洛树搜索的多分辨率规划算法。在该方法中，我们设计了一种新颖的基于八叉树的信念表示，以在不同分辨率层级上刻画目标物体的不确定性，然后在较低分辨率下推导出状态空间和观测空间大幅缩小的抽象 POMDP。在模拟 3D 域中的评估表明，在相同计算需求下，与一组没有分辨率层级的基线相比，我们的方法在较大实例中能更高效、更成功地找到物体。我们在一台移动机器人上演示了该方法：它通过移动底座和驱动躯干，在两个 10m² × 2m 的区域中寻找放置在不同高度的物体。

链接

• arXiv 2005.02878: https://arxiv.org/abs/2005.02878
• DOI 10.1109/IROS51168.2021.9636737: https://doi.org/10.1109/IROS51168.2021.9636737
• PDF: https://arxiv.org/pdf/2005.02878v4
• 项目主页: https://zkytony.github.io/3D-MOS/