Optimal sampling-based motion planning under differential constraints: The drift case with linear affine dynamics
Optimal sampling-based motion planning under differential constraints: The drift case with linear affine dynamics
复制标题
微分约束下基于采样的最优运动规划：线性仿射动力学的漂移情况
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Pavone
中科院分区：
文献类型：
--
作者：
E. Schmerling;Lucas Janson;M. Pavone
在本文中，我们提供了一个彻底的，严格的理论框架来评估漂移控制系统的基于采样的算法的最优性保证：系统，松散地说，由于动量不能立即停止。我们利用这个框架来设计和分析一个基于采样的算法（微分快速行进树算法），它是渐近最优的，也就是说，随着样本数量的增加，它保证收敛到最优解。此外，我们的方法允许我们提供这种收敛速度的具体界限。本文的重点是混合时间/控制能量成本函数和线性仿射动力系统，它包含了一系列应用感兴趣的模型（例如，双积分器），并且代表了通过连续线性化设计非线性漂移控制系统的基于采样和可证明正确的算法的必要步骤。我们的分析依赖于两点边值问题的原始摄动分析，这可能是独立的兴趣。
In this paper we provide a thorough, rigorous theoretical framework to assess optimality guarantees of sampling-based algorithms for drift control systems: systems that, loosely speaking, can not stop instantaneously due to momentum. We exploit this framework to design and analyze a sampling-based algorithm (the Differential Fast Marching Tree algorithm) that is asymptotically optimal, that is, it is guaranteed to converge, as the number of samples increases, to an optimal solution. In addition, our approach allows us to provide concrete bounds on the rate of this convergence. The focus of this paper is on mixed time/control energy cost functions and on linear affine dynamical systems, which encompass a range of models of interest to applications (e.g., double-integrators) and represent a necessary step to design, via successive linearization, sampling-based and provably-correct algorithms for non-linear drift control systems. Our analysis relies on an original perturbation analysis for two-point boundary value problems, which could be of independent interest.