【CMU博士论文】交错离散搜索与连续优化用于运动规划中的动力学运动规划

对于动态复杂的机器人任务，运动规划需要在速度、加速度、力/扭矩和运动学等约束条件内进行明确推理，例如避免障碍物。为了满足这些约束，规划算法必须同时进行高层次的离散决策和低层次的连续决策。例如，推动重物涉及对接触位置的离散决策和对细微交互的连续决策。现有的方法要么在通过采样构建的图上搜索，要么系统地对规划空间进行离散化，或优化受微分约束的参数化轨迹。然而，这些方法面临组合复杂性或在长时间范围内缺乏收敛的问题。我们假设这些高层次的离散决策通常位于完整规划空间的低维子空间中。因此，本论文主张，通过在该低维离散空间中交错搜索与在完整规划空间中的选择性推理，我们可以高效地发现全局、长时间范围内、动态丰富的任务能力。

本论文的目标是实现复杂动态系统长时间范围计划的自动发现。为此，我们提出了交错搜索与轨迹优化算法（INSAT）。INSAT结合了基于图的规划算法在非凸状态空间中寻找路径的优势和轨迹优化在高维空间中寻找动态可行轨迹的优势。我们在两个具有挑战性的领域展示了INSAT的有效性：1）在大环境中的激进四旋翼飞行（模拟）和2）在狭小空间中对重物的接触丰富操控。我们还表明，通过交错图搜索和轨迹优化，INSAT能够解决简单初始化的轨迹优化或独立图搜索无法解决的规划问题。

论文的下半部分探讨了加速INSAT规划器的三种不同方法：（1）CPU并行化：通过利用近期在并行化图搜索中的进展，我们实现了INSAT中基于优化的边缘计算的CPU加速；（2）更丰富的规划表示：我们使用稀疏且优化友好的规划空间表示——凸集图（GCS），以加速INSAT的规划。我们还展示了在凸集图（IxG）上使用INSAT作为规划器在某些理论属性和运行效率上超越了GCSOpt，前提是可以满足底层GCS中任何路径沿线的所有边约束；（3）预处理：通过离线计算运动库，我们可以保证对IxG的任何规划查询提供常数时间解决方案。这些方法共同提升了INSAT规划器的性能和效率，使其更能够应对复杂的规划任务。