Numerical Approach to Reachability-Guided Sampling-Based Motion Planning Under Differential Constraints
Numerical Approach to Reachability-Guided Sampling-Based Motion Planning Under Differential Constraints
复制标题
微分约束下可达性引导采样运动规划的数值方法
DOI：
--
复制
发表时间：
2017
影响因子：
5.2
通讯作者：
M. Ang
中科院分区：
文献类型：
--
作者：
S. Pendleton;Wei Liu;Hans Andersen;Y. Eng;Emilio Frazzoli;D. Rus;M. Ang
本文提出了一种新的微分约束下的运动规划方法，通过将一个数值求解的离散表示的可达状态空间，更快的状态采样和最近邻搜索。离线求解可达状态空间，并将其存储为可达图，可有效地应用于在线规划。状态采样仅在可达映射所包含的状态上执行，以减少不成功的运动有效性检查查询的数量。最近邻距离函数进行了修改，使得只考虑可达状态，与不可达的状态或仅可达超过指定的时间范围被忽略。该方法可推广应用于任何控制系统，因此可用于无法找到解析解的车辆模型，对于运动检查成本相对较高的更多约束系统，预计会有更大的改进。仿真结果进行了讨论的完整模型和Dubins汽车模型的案例研究，最大速度限制和时间包括作为一个维度在配置空间中，规划速度（测量树的生长速率）可以提高通过可达性指导在每个系统中的至少一个因素3和9，分别。
This paper presents a new method for motion planning under differential constraints by incorporating a numerically solved discretized representation of reachable state space for faster state sampling and nearest neighbor searching. The reachable state space is solved for offline and stored into a “reachable map” which can be efficiently applied in online planning. State sampling is performed only over states encompassed by the reachable map to reduce the number of unsuccessful motion validity checking queries. The nearest neighbor distance function is revised such that only reachable states are considered, with states which are unreachable or only reachable beyond a designated time horizon disregarded. This method is generalized for application to any control system, and thus can be used for vehicle models where analytical solutions cannot be found. Greater improvement is expected for more constrained systems where motion checking cost is relatively high. Simulation results are discussed for case studies on a holonomic model and a Dubins car model, both with maximum speed limitation and time included as a dimension in the configuration space, where planning speed (measured by tree growth rate) can be improved through reachability guidance in each system by at least a factor of 3 and 9, respectively.