论文标题
t*$ \ varepsilon $ - 最低时间平面曲率受限系统的有限次话
T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems
论文作者
论文摘要
我们考虑在存在障碍物的情况下为曲率受限系统找到无碰撞路径的问题，同时最大程度地减少执行时间。具体来说，我们专注于平面系统可以以无限加速的一定速度行驶的设置。该设置可以建模许多系统，例如固定翼无人机。不幸的是，针对此类系统的计划可能需要评估连接两个近距离配置的许多（本地）时间优势的转换，这在计算上很昂贵。现有的方法要么在预处理阶段预先计算所有此类过渡，要么使用启发式方法来加快搜索速度，从而预言了解决方案质量的任何保证。我们的关键见解是，计算所有时间优势的过渡既是〜（i）〜计算上的昂贵，〜（ii）〜在许多问题实例中不必要。我们表明，通过找到有界的临时解决方案（其成本为$ 1+\ varepsilon $乘以$ \ varepsilon $乘以最佳解决方案的成本，对于任何用户提供的$ \ varepsilon $），而不是时间优势的解决方案，可以大大减少使用时间优先转变的数量。我们使用经验评估证明，与最先进的情况相比，我们的计划框架可以将运行时减少多个数量级，同时仍提供解决方案质量的保证。
We consider the problem of finding collision-free paths for curvature-constrained systems in the presence of obstacles while minimizing execution time. Specifically, we focus on the setting where a planar system can travel at some range of speeds with unbounded acceleration. This setting can model many systems, such as fixed-wing drones. Unfortunately, planning for such systems might require evaluating many (local) time-optimal transitions connecting two close-by configurations, which is computationally expensive. Existing methods either pre-compute all such transitions in a preprocessing stage or use heuristics to speed up the search, thus foregoing any guarantees on solution quality. Our key insight is that computing all the time-optimal transitions is both~(i)~computationally expensive and~(ii)~unnecessary for many problem instances. We show that by finding bounded-suboptimal solutions (solutions whose cost is bounded by $1+\varepsilon$ times the cost of the optimal solution for any user-provided $\varepsilon$) and not time-optimal solutions, one can dramatically reduce the number of time-optimal transitions used. We demonstrate using empirical evaluation that our planning framework can reduce the runtime by several orders of magnitude compared to the state-of-the-art while still providing guarantees on the quality of the solution.
