R3T: Rapidly-exploring Random Reachable Set Tree for Optimal Kinodynamic Planning of Nonlinear Hybrid Systems
R3T: Rapidly-exploring Random Reachable Set Tree for Optimal Kinodynamic Planning of Nonlinear Hybrid Systems
复制标题
R3T：快速探索随机可达集树，用于非线性混合系统的最优运动动力学规划
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Russ Tedrake
中科院分区：
文献类型：
--
作者：
A. Wu;Sadra Sadraddini;Russ Tedrake
我们介绍R3T，一个基于可达性的快速探索随机树（RRT）算法的变种，适用于非线性和混合动力系统中的（最优）kinodynamic规划。我们开发了工具，使用多面体近似可达集，并使用它们执行基于采样的规划。该方法在混合系统中有一个独特的优点：可达集中的不同动态模式可以用多个多面体显式表示。我们证明了在温和的假设下，R3T是概率完备的Kinodynamic系统，并通过重新布线渐近最优。此外，R3T为非线性系统的可达性分析提供了一种形式化的验证方法。R3T的优势证明了非线性，混合动力，接触丰富的机器人系统的案例研究。
We introduce R3T, a reachability-based variant of the rapidly-exploring random tree (RRT) algorithm that is suitable for (optimal) kinodynamic planning in nonlinear and hybrid systems. We developed tools to approximate reachable sets using polytopes and perform sampling-based planning with them. This method has a unique advantage in hybrid systems: different dynamic modes in the reachable set can be explicitly represented using multiple polytopes. We prove that under mild assumptions, R3T is probabilistically complete in kinodynamic systems, and asymptotically optimal through rewiring. Moreover, R3T provides a formal verification method for reachability analysis of nonlinear systems. The advantages of R3T are demonstrated with case studies on nonlinear, hybrid, and contact-rich robotic systems.