Efficient and asymptotically optimal kinodynamic motion planning
Efficient and asymptotically optimal kinodynamic motion planning
复制标题
高效且渐近最优的运动动力学运动规划
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zakary Littlefield
中科院分区：
文献类型：
--
作者：
Zakary Littlefield
有效的和渐近最佳Kinodynamic运动规划ZAKARY LITTLEFIELD博士论文主任：Kostas E. Bekris本论文探讨了在机器人的状态空间中建立树数据结构的运动规划器的属性。基于采样的树规划器是特别有用的规划系统具有显着的动态，由于固有的前向搜索执行。这与路线图规划器形成对比，路线图规划器需要引导本地规划器以制作包含多个可能路径的图。本论文探讨了一个家庭的运动规划系统具有显着的动态，转向本地规划器可能是计算昂贵的或可能不存在。这些规划者专注于提供实用的路径质量保证，而无需高昂的计算成本。这些规划器可以被认为是彼此的后继者，因为每个后继算法都解决了其前任的一些缺点。第一个算法，稀疏RRT，解决了RRT方法的缺点，在树的构建过程中考虑路径质量。稀疏RRT被证明是在温和的条件下，第一次在这里，概率完全，虽然有一个穷人的收敛速度。第二个算法，SST，提供了概率的完整性和渐近近最优属性是可证明的，但在额外的算法开销的成本。SST显示，以提高收敛速度相比，稀疏RRT。第三种算法DIRT结合了这两种算法的经验教训，
OF THE DISSERTATION Efficient and Asymptotically Optimal Kinodynamic Motion Planning by ZAKARY LITTLEFIELD Dissertation Director: Kostas E. Bekris This dissertation explores properties of motion planners that build tree data structures in a robot’s state space. Sampling-based tree planners are especially useful for planning for systems with significant dynamics, due to the inherent forward search that is performed. This is in contrast to roadmap planners that require a steering local planner in order to make a graph containing multiple possible paths. This dissertation explores a family of motion planners for systems with significant dynamics, where a steering local planner may be computationally expensive or may not exist. These planners focus on providing practical path quality guarantees without prohibitive computational costs. These planners can be considered successors of each other, in that each subsequent algorithm addresses some drawback of its predecessor. The first algorithm, Sparse-RRT, addresses a drawback of the RRT method by considering path quality during the tree construction process. Sparse-RRT is proven to be probabilistically complete under mild conditions for the first time here, albeit with a poor convergence rate. The second algorithm presented, SST, provides probabilistic completeness and asymptotic near-optimality properties that are provable, but at the cost of additional algorithmic overhead. SST is shown to improve the convergence rate compared to Sparse-RRT. The third algorithm, DIRT, incorporates learned lessons from these two algorithms and