论文标题
db-a*：与运动动力学移动机器人运动计划的不连续性搜索
db-A*: Discontinuity-bounded Search for Kinodynamic Mobile Robot Motion Planning
论文作者
论文摘要
我们考虑针对翻译不变的动态系统的时间 - 最佳运动计划，该属性适用于许多移动机器人，例如差速器，汽车，飞机和多旋转器。我们的关键见解是，当与优化共生时，我们可以将图形搜索算法扩展到连续情况。在图形搜索中，我们引入了不连续性的A*（db-a*），这是A*算法的概括，该算法使用了基于采样计划者的概念和数据结构。 db-a*重用短轨迹，所谓的运动原语，作为边缘，并在顶点允许最大的用户指定的不连续性。这些轨迹通过轨迹优化对局部修复，这也提供了新的改进的运动原语。我们的新型动力学运动计划者KMP-DB-A*几乎肯定具有渐近的最佳行为，并且可以迅速计算近乎最佳的解决方案。对于我们的经验验证，我们提供了第一个基准，该基准测试在不同设置中的多个动态系统上比较搜索，采样和基于优化的时间优化运动计划。与基准相比，KMP-DB-A*始终求解更多的问题实例，找到较低成本的初始解决方案并更快地收敛。
We consider time-optimal motion planning for dynamical systems that are translation-invariant, a property that holds for many mobile robots, such as differential-drives, cars, airplanes, and multirotors. Our key insight is that we can extend graph-search algorithms to the continuous case when used symbiotically with optimization. For the graph search, we introduce discontinuity-bounded A* (db-A*), a generalization of the A* algorithm that uses concepts and data structures from sampling-based planners. Db-A* reuses short trajectories, so-called motion primitives, as edges and allows a maximum user-specified discontinuity at the vertices. These trajectories are locally repaired with trajectory optimization, which also provides new improved motion primitives. Our novel kinodynamic motion planner, kMP-db-A*, has almost surely asymptotic optimal behavior and computes near-optimal solutions quickly. For our empirical validation, we provide the first benchmark that compares search-, sampling-, and optimization-based time-optimal motion planning on multiple dynamical systems in different settings. Compared to the baselines, kMP-db-A* consistently solves more problem instances, finds lower-cost initial solutions, and converges more quickly.
