- 11/18
- 2024
-
QQ扫一扫
-
Vision小助手
（CMVU）
当环境中有很多障碍物时，传统的轨迹优化方法（如基于采用规划器的方法）往往表现不佳。本文提出了一种新的基于凸优化的运动规划方法，该方法结合了贝塞尔曲线与凸集图（GCS）的最短路径优化框架。通过这种方法，研究人员将轨迹规划问题转化为一个混合整数优化问题，能够在快速解决高维空间中的问题。
背景简介
为了应对这一难题，研究人员常常转而使用基于采样的运动规划算法，这类算法在复杂的配置空间中具有一定的优势，因为它们能够通过采样来找到可行的路径，并且具有概率完备性，意味着只要可行路径存在，它们理论上总能找到。然而，这些算法在处理高维空间的连续微分约束时表现不佳，生成的轨迹往往不是全局最优的，并且需要大量的采样和计算时间。在更复杂的动态系统中，轨迹优化与高层次的图搜索方法结合使用，虽然可以部分改善这一问题，但这些多层架构并未提供一个统一的优化框架。
基于这些背景，混合整数凸优化方法（MICP）为运动规划问题提供了新的思路。MICP方法能够结合基于采样的算法的完备性以及轨迹优化方法处理运动学和动力学约束的能力，并且可以提供全局最优解。然而，MICP方法在计算复杂性上存在很大的局限性，其求解时间通常非常长，即便是在小规模问题上也需要数分钟才能生成轨迹。
在这个背景下，研究者们致力于寻找一种新的方法，既能够应对复杂环境下的高维运动规划问题，又能快速地生成高质量的避障轨迹。文章基于此背景提出了一种新的运动规划算法，能够有效地解决这些问题，并在很短的时间内生成全局最优的避碰轨迹。
问题陈述
在此基础上，研究者的目标是找到一条花费总时间 的安全轨迹 。在求解优化问题的过程中，设定求解目标是轨迹持续时间 ，轨迹长度 和能量 的加权求和，即 。
优化框架
3.1 凸集图中的最短路径问题（SPP）
最短路径问题（SPP）在凸集图（GCS）中，是经典最短路径问题的推广。给定一个带有有向图 的问题，其中 是顶点集， 是边集。每个顶点 关联一个有界凸集 。
不同于经典的最短路径问题，该问题中每条边的长度是由顶点之间的连续变量 和 决定的，通过一个凸函数 来表示，并且该函数要求取非负值。
凸集图中的最短路径问题可以形式化为以下优化问题：
3.2 凸松弛的随机舍入
作者提出了一种通过凸松弛方法来解决最短路径问题，然后使用随机舍入策略来近似求解的框架。首先，通过求解凸松弛问题得到边的概率分布，然后通过深度优先搜索（DFS）和回溯算法来从这些概率中生成一条有效路径。
对于任意边 ，二元变量被松弛为连续区间。在每条边 上，其值可以被自然地解释为该边成为最短路径一部分的概率。在随机舍入过程中，给定当前的顶点 ，算法以概率选择下一条边 ，并继续构建路径，直到到达目标顶点。
最终，该框架提供了一个自动生成最优解近似的能力，即通过比较凸松弛解和舍入解的成本，估算最优性能误差：且可被估算为：这种方法在很多实际问题中非常有效，并且在大多数情况下，简单的舍入操作就足以生成全局最优的无碰撞运动轨迹。此外，整个过程的计算成本仅相当于一次凸优化，极大地降低了传统混合整数规划的计算开销。
使用凸集图的无碰撞运动规划
这一部分的核心是将无碰撞运动规划问题转化为凸集图（GCS）中的最短路径问题，并通过凸优化方法来求解轨迹和时间缩放函数。具体而言，目标是让机器人在一系列凸区域中移动，并通过连接这些凸区域的路径来生成无碰撞的连续轨迹。
4.1 图的构建
首先，作者通过将机器人所在的配置空间分解成若干个“安全”凸区域 ，然后通过图来表示这些区域的连接关系。每个顶点 对应一个安全的凸区域 ，并且两个凸区域之间的交集决定了是否在图上添加一条边。额外地，起点顶点和终点顶点被作为辅助顶点加入图中，用于保证初始和最终状态的边界条件。
边集的定义如下：
4.2 凸集的定义
接下来，为每个顶点 定义一个凸集 ，其中包含对应贝塞尔曲线的控制点 和时间缩放函数 的控制点 。这些控制点定义了在该区域内的轨迹片段和时间缩放曲线。凸集的定义如下：
这些条件确保了贝塞尔曲线的所有控制点 位于对应的凸区域内，同时保证时间缩放函数 单调递增，并对机器人速度施加硬性约束。
在每条边 上，作者使用了线性约束来确保不同区域之间的轨迹是连续可微的。对于每条边 ，定义以下约束：这些约束确保了轨迹和时间缩放函数在通过边界时的连续性，使得全局轨迹具有阶的连续性。
4.4 边的长度
为了将路径规划问题形式化为最短路径问题，边的长度定义为轨迹的代价，包括时间、路径长度和能量消耗。
4.5 重建无碰撞轨迹
一旦最短路径问题（SPP）求解完成，最优路径决定了机器人必须经过的安全区域序列。通过对这些区域中的贝塞尔曲线和时间缩放函数进行拼接，可以重建全局无碰撞轨迹 和时间缩放函数 ，即：
通过使用本文提出的GCS框架，可以将各种运动规划问题转化为凸优化问题。当安全区域 为多面体，且目标是最小时间规划（即a=1且b=c=0）时，该问题可以转化为一个混合整数线性规划（MILP）。而当安全区域是二次型或者包含其他成本项时，问题则转化为混合整数二阶锥规划（MISOCP），通过求解一个二阶锥规划（SOCP）加上舍入步骤即可获得解。
实验验证
首先，作者研究了二维空间中的一个简单示例，以说明问题中不同参数对轨迹形状的影响。在此实验中，目标是在包含多个障碍的二维平面中从起点移动到终点。通过调整不同的参数（如最小化轨迹长度或最小化时间），生成了多种不同的轨迹。这些轨迹的生成基于凸优化放松方案，通过求解凸放松的最短路径问题后，再进行取整操作以生成最终轨迹。实验结果表明，生成的轨迹的成本相对最优解的差距非常小，并且在最小化路径长度的情况下，成本差距在1.7%以内。
接着，作者将实验环境扩展到一个更加复杂的迷宫中，测试了GCS算法在复杂环境中的性能。此实验主要考察了算法在面对大量障碍物时的鲁棒性和效率。在此场景中，算法依旧表现出良好的性能，能够在较短时间内生成高质量的路径。
本节作者进行了统计分析，以测试算法在规划四旋翼飞行器穿越随机生成的建筑物任务中的性能。实验环境模拟了包含随机障碍物的三维空间，飞行器需要从起始点到达终点并避开所有障碍。实验结果表明，GCS算法在大多数场景中能够生成与全局最优解相差不到1%的轨迹，而在最差情况下，算法生成的轨迹仅比最优解高出2.9%的成本。该分析还包括对算法生成解的可行性和优化度的量化评估，结果显示GCS在68%的问题中能提供最优性差距小于4%的解。
作者进一步将GCS与经典的采样方法PRM进行比较，以测试其在七自由度机械臂运动规划任务中的表现。实验结果表明，相较于PRM算法，GCS在相同的初始和最终条件下能够生成更高质量的轨迹，并且用时更短。此实验中使用的机械臂为KUKA LBR iiwa，配置空间为七维，这种较高维度的空间中GCS的优势得到了充分体现。
5.5 双臂机器人协调规划
最后，作者在一个14维配置空间中测试了GCS的扩展性，通过规划双臂机器人在有限空间中的协调运动任务验证了算法的性能。实验中双臂需在狭窄的空间中避开彼此以及环境中的障碍物完成指定任务。GCS成功生成了符合边界条件的光滑轨迹，并展示了其在复杂、高维度环境中良好的可扩展性和实时性。
总结与展望
然而，作者也指出了GCS方法的局限性，尤其是在额外的成本和约束方面：GCS方法虽然可以有效避障，但对于较复杂的目标（如要求轨迹有最小的速度或最小的时间成本），可能导致不安全的轨迹。
同时，作者将本文算法和其他算法进行了对比：
与现有的混合整数规划（MICP）算法的对比的优势
其一是凸松弛优化的紧密性；其二是程序中二元决策变量的数量减少；其三是该方法能够转化为相对简单的优化问题。尽管如此，GCS方法仍然受到凸性要求的限制，影响了所能处理的规划问题的复杂性和轨迹的多样性。
与直接轨迹优化的对比：直接轨迹优化方法虽然可以处理多种成本函数和约束条件（包括动态和任务空间约束），但由于这些程序的非凸性问题，求解时往往较慢且不稳定。相比之下，GCS方法更强调求解的低运行时间和完整性。
对于未来的工作，作者认为可以在自定义求解器，扩展代价函数和约束条件，处理机器人接触问题以及在真实世界中进行应用等几个方面进行改进。
（文字来源于Science机器人子刊，如有侵权请联系删除）