1.摘要
高维路径规划在无人机（UAV）应用中尤为重要，特别是在地下环境中，由于缺乏GPS信号，路径规划面临较大挑战。传统的快速探索随机树（RRT）算法使用伪随机序列，导致了欠采样、过采样以及计算成本高、路径冗余等问题。为了解决这些问题，本文提出了一种基于Halton序列的聚类（HBC-RRT）算法，该算法通过替代伪随机序列，根本性地解决了RRT算法中的采样问题。同时，HBC-RRT算法借鉴果蝇引导机制，采用新型采样器优化双树采样过程，通过选择最优采样策略或虚拟子目标点，算法有效减少了采样时间并加速了双树连接过程，从而降低了路径成本。
2.环境模型
在复杂地下空间中飞行的无人机（UAV）面临多种障碍物，为了减轻机载计算机的计算负担并提高路径规划效率，首先对这些复杂障碍物进行建模。选择与障碍物特征最匹配的包络形状：
Γ ( x , y , z ) = ( x − x o d ) 2 s + ( y − y o e ) 2 t + ( z − z o f ) 2 m = 1 \Gamma(x,y,z)=\left(\frac{x-x_o}{d}\right)^{2s}+\left(\frac{y-y_o}{e}\right)^{2t}+\left(\frac{z-z_o}{f}\right)^{2m}=1 Γ(x,y,z)=(dx−xo)2s+(ey−yo)2t+(fz−zo)2m=1
该方程表示三维空间中的广义二次曲面， ( x 0 , y 0 , z 0 ) (x_0,y_0,z_0) (x0,y0,z0)表示障碍物的中心坐标。
3.HBC-RRT算法
Halton序列
传统RRT算法采用伪随机序列进行采样，这可能导致某些区域采样空缺，另一些区域则出现冗余采样，从而使得算法在某些区域反复探索，而未能有效覆盖其他区域，进而减缓了收敛速度。为了解决这一问题，本研究引入了低差异性的Halton序列，其具有更优的覆盖性。Halton序列定义如下：
ϕ p ( n ) = b 0 p + b 1 p 2 + ⋯ + b m p m + 1 \phi_p(n)=\frac{b_0}{p}+\frac{b_1}{p^2}+\cdots+\frac{b_m}{p^{m+1}} ϕp(n)=pb0+p2b1+⋯+pm+1bm
设 p p p为素数，在 s s s维空间中，Halton序列定义为：
X n = ( ϕ p 1 ( n ) , ϕ p 2 ( n ) , . . . , ϕ p s ( n ) ) X_n=(\phi p_1(n),\phi p_2(n),...,\phi p_s(n)) Xn=(ϕp1(n),ϕp2(n),...,ϕps(n))
为了评估Halton序列与伪随机序列在三维空间中的采样性能，采用了星差异性和L2差异性度量。
D ∗ ( P ) = sup J ⊆ [ 0 , 1 ] d ∣ C o u n t ( x i ∈ J ) N − V o l ( J ) ∣ D^*(P)=\sup_{J\subseteq[0,1]^d}\left|\frac{Count(xi\in J)}{N}-Vol(J)\right| D∗(P)=J⊆[0,1]dsup
NCount(xi∈J)−Vol(J)
D L 2 = ( ∫ [ 0 , 1 ] d ∣ 1 N ∑ i = 1 N 1 [ 0 , t ] ( x i ) − t 1 t 2 ⋯ t d ∣ 2 d t 1 d t 2 ⋯ d t d ) 1 / 2 D_{L2}=\left(\int_{[0,1]^d}\left|\frac{1}{N}\sum_{i=1}^N1_{[0,t]}(xi)-t_1t_2\cdots t_d\right|^2dt_1dt_2\cdots dt_d\right)^{1/2} DL2=
∫[0,1]d
N1i=1∑N1[0,t](xi)−t1t2⋯td
2dt1dt2⋯dtd
1/2
果蝇启发的引导机制
果蝇转向机制有助于果蝇直接朝着记忆中的目标（如远距离觅食地点或避难所）进行导航，这一过程需要大脑设定目标方向（Wilson，2023）。目标方向由环境线索如太阳和风等固定（Westeinde等，2024）。如图所示，最暗的点和正弦曲线的峰值表示细胞头部当前的方向为0°，而正弦曲线从低到高的变化以及点的颜色从浅到深，反映了吸引子活动水平。
受到果蝇转向机制的启发，开发了一种仿生果蝇引导策略。在该策略下，当环境线索存在时，随机树的扩展沿着固定轨迹进行；而在没有环境线索的情况下，则沿着随机轨迹扩展。
xnew是由此次扩展生成的节点，xnearest是随机树中离xsample最近的点，xsample作为随机采样点，m为虚拟子目标点，s为扩展的步长。
{ ϕ < η x new = x nearest + m − x nearest ∥ m − x nearest ∥ ⋅ s ϕ ≥ η x new = x nearest + x sample − x nearest ∥ x sample − x nearest ∥ ⋅ s \begin{cases} \phi < \eta \quad x_{\text{new}} = x_{\text{nearest}} + \frac{m - x_{\text{nearest}}}{\| m - x_{\text{nearest}} \|} \cdot s \\ \phi \geq \eta \quad x_{\text{new}} = x_{\text{nearest}} + \frac{x_{\text{sample}} - x_{\text{nearest}}}{\| x_{\text{sample}} - x_{\text{nearest}} \|} \cdot s \end{cases} {ϕ<ηxnew=xnearest+∥m−xnearest∥m−xnearest⋅sϕ≥ηxnew=xnearest+∥xsample−xnearest∥xsample−xnearest⋅s
虚拟子目标点
在传统双向RRT算法中，树1和树2通过随机扩展连接，缺乏足够的方向性。在复杂环境中，这种方法可能导致树陷入局部死胡同，从而消耗大量时间和内存来完成树的连接。为了解决这个问题，算法在初始化时基于起始位置和目标位置预设了一个虚拟子目标，以加速树1和树2之间的连接。
(xa, ya, za)为起始位置，(xb, yb, zb)为目标位置。
m = [ 1 2 ( x a + x b ) , 1 2 ( y a + y b ) , 1 2 ( z a + z b ) ] m=\left[\frac{1}{2}\left(x_a+x_b\right),\frac{1}{2}\left(y_a+y_b\right),\frac{1}{2}\left(z_a+z_b\right)\right] m=[21(xa+xb),21(ya+yb),21(za+zb)]
如果点m被障碍物阻挡，则在点m₁或m₂周围构建一个半径为R的球体。
∥ ( x , y , z ) − ( x m , y m , z m ) ∥ = R 2 \|(x,y,z)-(x_m,y_m,z_m)\|=R^2 ∥(x,y,z)−(xm,ym,zm)∥=R2
此外，确定一个点C(xc, yc, zc) = (xm, ym, zm + d) 与线段A-B一起定义一个唯一的平面，该平面法向量为：
n = A B → × M C → = ( d ( y b − y a ) , − d ( x b − x a ) , 0 ) n=\overrightarrow{AB}\times\overrightarrow{MC}=(d(y_b-y_a),-d(x_b-x_a),0) n=AB×MC=(d(yb−ya),−d(xb−xa),0)
由平面方程推导出直线l，直线l垂直于平面，并经过已有的中点m2。
{ x = x m + t ⋅ n x y = y m + t ⋅ n y z = z m + t ⋅ n z \begin{cases} x=x_m+t\cdot n_x \\ y=y_m+t\cdot n_y \\ z=z_m+t\cdot n_z & \end{cases} ⎩
⎨
⎧x=xm+t⋅nxy=ym+t⋅nyz=zm+t⋅nz
最优抽样候选策略
在三维空间中算法采样成本较高，本文提出了一种最优采样候选策略，选择扩展过程中的最优节点，以提高采样点质量并降低采样成本。在采样阶段，建立了一个潜在候选池，将一定数量的采样点加入其中。当采样点数量达到预定阈值时，开始节点选择过程。根据三个权重约束评估采样点，并按相应的H值进行排序。最后，计算潜在候选池中每个采样点与目标点之间的距离：
d N = ( x s a m p l e ( N ) − x g o a l ) T w ( x s a m p l e ( N ) − x g o a l ) d_N=\sqrt{\left(x_{sample(N)}-x_{goal}\right)^Tw(x_{sample(N)}-x_{goal})} dN=(xsample(N)−xgoal)Tw(xsample(N)−xgoal)
确定潜在候选池中每个采样点的转弯角度：
θ N = arctan 2 ( ∥ ν 1 × ν 2 ∥ , ν 1 ⋅ ν 2 ) \theta_N=\arctan2(\|\nu_1\times\nu_2\|,\nu_1\cdot\nu_2) θN=arctan2(∥ν1×ν2∥,ν1⋅ν2)
4.结果展示
5.参考文献
[1] Zhong H, Du Y, Liu D, et al. A fruit fly-inspired path planning algorithm for unmanned aerial vehicle in underground environments based on low-discrepancy sequences[J]. Engineering Applications of Artificial Intelligence, 2025, 156: 111250.
6.代码获取
xx