We present a metric space approach for high-dimensional sample-based trajectory planning. Sample-based methods such as RRT and its variants have been widely used in robotic applications and beyond, but the convergence of such methods is known only for the specific cases of holonomic systems and sub-Riemannian non-holonomic systems. Here, we present a more general theory using a metric-based approach and prove the algorithm's convergence for Euclidean and non-Euclidean spaces. The extended convergence theory is valid for joint planning of multiple heterogeneous holonomic or non-holonomic agents in a crowded environment in the presence of obstacles. We demonstrate the method both using abstract metric spaces ($ell^p$ geometries and fractal Sierpinski gasket) and using a multi-vehicle Reeds-Shepp vehicle system. For multi-vehicle systems, the degree of simultaneous motion can be adjusted by varying t.he metric on the joint state space, and we demonstrate the effects of this choice on the resulting choreographies.
翻译:我们为基于高维样本的轨迹规划提供了一种衡量空间方法,例如RRT及其变体等基于样本的方法在机器人应用中和之后被广泛使用,但此类方法的趋同仅针对Holonomic系统和亚Riemannian非holoomic系统的具体情况而已知,这里我们提出了一个使用基于计量方法的比较一般性的理论,并证明Euclidean空间和非Euclidean空间的算法趋同程度。扩展的趋同理论对于在存在障碍的情况下在拥挤环境中联合规划多种多元的holonomic或非holomic剂是有效的。我们用抽象的光度空间(ell ⁇ $和fractal Sierpinski垫片)和多机动车辆-Shepp车系统来演示这种方法。对于多机动车辆系统,可以通过对联合空间的不同测量来调整同时运动的程度。我们展示了这一选择对由此产生的舞蹈绘制的影响。