加速信息RRT*：结合RRT*-Connect和APF的快速渐近路径规划方法

# 加速信息RRT*：结合RRT*-Connect和APF的快速渐近路径规划方法 ## 1. 引言 路径规划问题是机器人、车辆和其他移动设备导航与运动控制中常见且基础的问题，其目标是为智能体在复杂的交互环境中找到一条可行且优质的路径。目前，已有许多方法被提出以解决路径规划问题。 ### 1.1 传统路径规划方法 - **势场法**：如人工势场法（APF），根据目标点和障碍物产生的引力和斥力来生成路径。然而，这些基于场的方法常陷入局部最优，且无法保证找到全局最优路径。 - **基于网格的方法**：将环境离散化为网格地图，并使用基于图的搜索算法（如A*和D*）来寻找最优路径（如果存在）。虽然基于网格的方法能保证最优性，但在高维空间中表现不佳，受维度诅咒影响，且难以处理不规则形状的复杂障碍物。 ### 1.2 基于采样的路径规划方法 近年来，基于采样的路径规划方法成为解决路径规划复杂性的流行且有效的方法。这些方法通过随机采样配置空间来构建环境的图表示，从而发现可行路径。其中，快速探索随机树（RRT）算法及其变体在生成无碰撞路径方面取得了显著成功。 - **RRT-connect**：是原始RRT的扩展，通过两棵分离的树同时从起点和目标点向外生长，快速连接两点以找到可行路径，节省内存，但得到的路径通常不是最短的。 - **RRT***：是一种渐近最优的基于采样的路径规划算法，通过重新选择新采样节点的父节点和重新连接树来减少冗余节点，但在有限的迭代次数内收敛到最优解的速度可能较慢。 - **信息RRT***：利用当前路径长度和起点与目标点之间的距离生成椭圆作为启发式采样区域，提高了RRT*算法的性能，但需要大量时间搜索可行的初始解，导致优化效率欠佳。 因此，在短时间内找到最优路径是当前路径规划方法面临的突出挑战。为解决这一问题，本文引入了一种基于APF的改进采样路径规划算法——信息RRT*-connect，它结合了RRT-connect算法和最优RRT*算法的优势，同时利用APF方法引导采样函数，有效减少无效采样尝试，加速信息RRT*迭代寻找最优解的过程，并弥补RRT-connect无法保证渐近最优性的不足。 ## 2. 预备知识 ### 2.1 路径规划问题定义 设 $\chi \in R^n$ 为状态空间，自由空间和障碍物空间分别表示为 $\chi_{free}$ 和 $\chi_{obs}$。设 $x_{start}$ 为起始状态，$x_{goal}$ 为目标状态。路径规划问题是在给定空间 $\chi$ 中找到一条从起始状态 $x_{start}$ 到目标状态 $x_{goal}$ 的路径 $\sigma[0, T]$，表示为： $\sigma[0, T] \to \chi_{free}$， $\sigma(0) = x_{start}$ 且 $\sigma(T) = x_{goal}$。 假设 $\alpha$ 是所有可行路径的集合，则具有最小路径长度的最优路径 $\sigma^*$ 可定义为： $\sigma^* = \arg \min_{\sigma \in \alpha} ||\sigma||$ s.t. $\sigma(0) = x_{start}$ $\sigma(T) = x_{goal}$ $\sigma(t) \in \chi_{free}(t)$ $\forall t \in [0, T]$ 其中，$||\cdot||$ 是使用欧几里得距离计算路径长度的函数，$T$ 是整个路径规划所需的时间。 ### 2.2 信息RRT* 信息RRT*算法主要通过基于当前可行解长度和起点与目标点之间的理论最短距离生成椭圆区域，作为RRT*采样的启发式方法，以提高算法的效率和有效性。信息椭圆采样集可以用标准方程表示为： $\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$ 其中，$a$ 表示椭圆的半长轴长度，$b$ 表示椭圆的半短轴长度。随着发现的路径长度不断减小，相应的椭圆采样区域变小，从而将采样区域进一步限制在有可能改善路径长度的区域。通过迭代，信息RRT*可以比RRT*更快地收敛到接近最优的路径。 然而，信息RRT*算法与RRT*存在相同的问题，即当未找到初始路径时，椭圆采样区域可视为无限大。这一缺点导致搜索初始路径进行优化需要大量时间，且由于RRT*的固有随机性，可能得到低质量的初始解，使得算法的大部分执行时间可能无法显著改善路径优化效果。 ## 3. 基于APF的信息RRT*-Connect算法 为改进信息RRT*算法，本文提出了一种结合RRT-connect和APF方法的加速信息RRT*算法。