Although Trajectory Optimization (TO) is one of the most powerful motion planning tools, it suffers from expensive computational complexity as a time horizon increases in cluttered environments. It can also fail to converge to a globally optimal solution. In this paper, we present Lazy Trajectory Optimization (LTO) that unifies local short-horizon TO and global Graph-Search Planning (GSP) to generate a long-horizon global optimal trajectory. LTO solves TO with the same constraints as the original long-horizon TO with improved time complexity. We also propose a TO-aware cost function that can balance both solution cost and planning time. Since LTO solves many nearly identical TO in a roadmap, it can provide an informed warm-start for TO to accelerate the planning process. We also present proofs of the computational complexity and optimality of LTO. Finally, we demonstrate LTO's performance on motion planning problems for a 2 DOF free-flying robot and a 21 DOF legged robot, showing that LTO outperforms existing algorithms in terms of its runtime and reliability.
翻译:虽然轨迹优化是最强大的运动规划工具之一,但随着时间范围在环绕环境中的增加,它也因时间范围增加而面临昂贵的计算复杂性。它也可能无法汇集到一个全球最佳解决方案。在本文中,我们介绍Lazy轨迹优化优化优化(LTO),将本地短视与全球图形搜索规划(GSP)统一起来,以产生一个长视距全球最佳轨道。LTO解决了与最初的长视距与时间复杂性提高的相同限制。我们还提议了一个能够平衡解决方案成本和规划时间的通向成本功能。由于LTO在路径图中解决了许多几乎相同的问题,它可以为加速规划进程提供知情的热力启动。我们还介绍了LTO的计算复杂性和最佳性证据。最后,我们展示了LTO在2个DF自由飞行机器人和21个DF型机器人的动作规划问题上的表现,显示LTO在运行时间和可靠性方面比现有的算法要差。