Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

作者: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · RSS 2023

许可协议

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

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

一句话总结

把具有环绕特性的关节空间（移动底盘、连续关节）视为平坦流形，使 GCS 最短路径规划器仍能给出全局最优、无碰撞的路径。

为何重要

移动机械臂以及底座关节不受限位约束的机械臂，现在可以使用一种规划器，它能证明轨迹上的每一点都无碰撞，并且在精确求解时，在已认证的自由空间内是最优的。论文还证明了正曲率（例如 SO(3) 球关节或自由漂浮的物体）会破坏凸性，这标出了该方法无法触及的范围。

问题

Marcucci 等人的 GCS 规划器通过把自由构型空间分解为凸集来寻找无碰撞、全局最优的路径，但仅适用于欧几里得构型空间。可以完整转动 360° 的移动底盘或连续旋转关节具有环绕特性，因此其构型空间不是欧几里得的。人为添加关节限位，或将角度视为无界实数，要么使最优解不可行，要么需要事先知道答案并复制大量集合。

提出的方法

作者将构型空间建模为黎曼流形，并定义了测地凸集图（Graph of Geodesically-Convex Sets，GGCS），证明它保留了普通 GCS 的各项保证。对于平坦（零曲率）流形，这涵盖由 1-DoF 关节加 SE(2) 底盘构成的任何机器人，每个集合都通过一个局部等距坐标卡映射到欧几里得空间，问题便归约为具有仿射转移约束的标准混合整数凸 GCS 问题。区域用 IRIS 生长，并按关节以凸性半径加以约束；带连续性约束的分段 Bézier 轨迹也可沿用。

关键见解

• SE(2)、所有 1 维流形以及平坦流形的乘积都是平坦的，因此由单自由度关节和移动底盘组成的机器人适用该方法；3-DoF 球关节则不适用
• 按关节用凸性半径约束每个 IRIS 区域，可保证该区域映射回流形时仍保持测地凸
• 在具有全局对齐坐标的平坦空间上，转移映射是仿射的，因此端点匹配约束和导数连续约束仍保持凸
• 哪怕只有一个正曲率点，也会使黎曼距离函数在该点的每个邻域内都非凸（定理 5）

主要结果

• 环面上的点机器人：0.79 s 得到最优的环绕路径；带连续关节的 5 关节平面机械臂：规划耗时 5.36 s 和 4.63 s，其中一条路径使中间关节转动超过 360°
• 平面机械臂：松弛取整得到的路径长度为 7.749 和 8.448，而分支定界的最优值为 7.274 和 8.008
• 带连续底座关节的 KUKA iiwa（仿真）：使用 18 个凸区域完成 14 个杯子分拣动作，每个动作平均 25.75 s（范围 4.63–50.30 s）
• PR2（仿真，15 维构型空间），7 个货架取物任务：GGCS 路径在所有情况下均无碰撞，例如 1M→4M 长度为 3.875，而 PRM 为 14.554；Drake-Trajopt 和 PRM+Trajopt 有时给出更短的路径，但这些路径有轻微碰撞
• PR2 在线规划方面，GGCS-Planner 耗时 25.51–66.15 s，而 PRM 为 0.49–0.54 s，Drake-Trajopt 为 2.26–15.23 s，PRM+Trajopt 为 11.61–40.10 s
• PR2 离线准备：一个 IRIS 区域平均耗时 30.20 s（8.56–75.42 s），所有区域并行共 156.63 s；构建 100,000 个样本的 PRM 耗时 124.39 s

局限

• 作者表示该方法无法处理非凸代价和约束，例如非线性动力学和闭合运动链，也无法处理球关节
• SO(3) 等正曲率空间被排除在外，因为可以证明距离函数在其上是非凸的
• 最优性仅在区域所覆盖的“已认证”自由空间内成立；性能在很大程度上取决于区域的选择，并且对于 PR2，一些中间区域是手动添加的
• PR2 的在线规划时间（25.51–66.15 s）高于所比较的所有基线
• 所有机器人结果均在仿真中获得；作者将带隐式运动学约束的双臂规划以及经由接触的规划列为未来工作

对领域的影响

入围 RSS 2023 最佳论文奖决选，被引用 44 次。作者在一个结果网站上发布了每条轨迹的交互式记录。

摘要

为高维系统计算最优、无碰撞的轨迹是一个具有挑战性的问题。基于采样的规划器难以应对高维度，而轨迹优化器则可能由于优化地形中固有的非凸性而陷入局部极小值。使用混合整数规划来封装这些非凸性并求得全局最优轨迹，近来展现出巨大潜力，这部分得益于紧致的凸松弛以及大幅缩短运行时间的高效近似策略。这些方法以往仅限于欧几里得构型空间，因而无法用于移动底盘或连续旋转关节。在本文中，我们将构型空间建模为黎曼流形来处理此类情形，并针对零曲率情况描述了一种将问题归约为混合整数凸优化问题的过程。我们在多种机器人平台上展示了结果，包括为 PR2 双臂移动机械臂生成高效的无碰撞轨迹。

链接

• arXiv 2305.06341: https://arxiv.org/abs/2305.06341
• DOI 10.1177/02783649241302419: https://doi.org/10.1177/02783649241302419
• PDF: https://arxiv.org/pdf/2305.06341v1
• 项目主页: https://ggcs-anonymous-submission.github.io/