2026年ESWA，基于全局进化动态规划与局部粒子群优化GPU 支持去中心化多机器人路径规划

1.摘要

本文提出一种GPU加速的单/多机器人路径规划方法，融合全局进化动态规划（EDP）与局部粒子群算法（PSO）。基于可视点图将路径规划建模为马尔可夫决策过程（MDP），利用EDP求解生成具备显著状态值的多条高质量初始路径，随后通过并行化多种群PSO对初始路径进行同步近端优化。

2.路径规划算法

目标是在动态环境中，从机器人当前位置和姿态到目标点生成最优路径。路径由若干航点组成，需避开多边形障碍。障碍可为凸或凹多边形，非多边形物体用较细多边形近似。机器人在移动过程中障碍也可能移动，因此起点不是初始点，而是实时当前位置。优化指标包括路径长度、平滑性和安全性。

Methodology

由视觉检测得到障碍并生成地图，再构造可视图；可视图节点包括起点、目标点和膨胀障碍顶点，边为不穿越障碍的可行连接。障碍膨胀半径取R 0 = 0.235 m R_0=0.235\,mR0​=0.235m，包含机器人尺寸和定位误差，使机器人可视为点。用可视图建立 MDP，用 GPU 并行 EDP 生成多条可行全局路径。EDP 路径按航点数补充局部航点，使每条 PSO 初始路径至少含两个待优化航点。PSO 只优化机器人附近前两个航点的x , y x,yx,y坐标，远处路径因动态环境变化大，不做重优化。最后按适应度从多条 PSO 优化路径中选择最优路径。（去中心化多机器人规划）

Obstacle detection

障碍由三台俯视鱼眼相机采集图像并拼接得到。图像拼接使用 ORB 特征，结合 FAST 关键点、BRIEF 描述子、汉明距离匹配和 RANSAC 单应矩阵估计。拼接图灰度化后阈值分割黑色障碍区域，OpenCV 提取轮廓，Douglas–Peucker 算法将边界近似为多边形顶点。

路径规划被表示为 MDP⟨ S , A , R , γ ⟩ \langle S,A,R,\gamma\rangle⟨S,A,R,γ⟩。状态s = [ x , y , θ ] s=[x,y,\theta]s=[x,y,θ]表示机器人位置和朝向，动作是从当前状态到可见后继状态的移动，奖励衡量动作质量。目标是从起始状态最大化状态价值：

v ( s s ) = max ⁡ s g ( r s → g + γ v ( s g ) ) . v(s_s)=\max_{s_g}\left(r_{s\to g}+\gamma v(s_g)\right).v(ss​)=sg​max​(rs→g​+γv(sg​)).

其中，s s s_sss​为起点状态，s g s_gsg​为指向目标点的状态，r s → g r_{s\to g}rs→g​为从起点到目标过程的奖励。

EDP 将 MDP 分解为大量子问题，并在 GPU 上并行更新状态价值，不需要预设子问题求解顺序。每个子问题计算状态s i s_isi​的价值：

v ( s i ) = max ⁡ s j ( r i → j + γ v ( s j ) ) . v(s_i)=\max_{s_j}\left(r_{i\to j}+\gamma v(s_j)\right).v(si​)=sj​max​(ri→j​+γv(sj​)).

取γ = 1 \gamma=1γ=1，因为节点有限且迭代在价值收敛时停止。奖励综合路径长度和平滑性：

r i → j = β 1 l i → j v m a x + β 2 θ i → j w m a x . r_{i\to j}=\beta_1\frac{l_{i\to j}}{v_{max}}+\beta_2\frac{\theta_{i\to j}}{w_{max}}.ri→j​=β1​vmax​li→j​​+β2​wmax​θi→j​​.

PSO 目标函数综合路径长度、平滑性和安全惩罚：

F = L v m a x + Φ w m a x + P . F=\frac{L}{v_{max}}+\frac{\Phi}{w_{max}}+P.F=vmax​L​+wmax​Φ​+P.

路径长度为：

L = ∑ i = 1 n d i = ∑ i = 1 n ( x i − x i − 1 ) 2 + ( y i − y i − 1 ) 2 . L=\sum_{i=1}^{n}d_i=\sum_{i=1}^{n}\sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2}.L=i=1∑n​di​=i=1∑n​(xi​−xi−1​)2+(yi​−yi−1​)2​.

路径平滑性为起点、终点和航点处转角之和：

Φ = ∑ i = 0 n ∣ ϕ i ∣ = ϕ 0 + ∑ i = 1 n − 1 ∣ a t a n 2 ( Δ y i + 1 Δ x i − Δ x i + 1 Δ y i , Δ x i + 1 Δ x i + Δ y i + 1 Δ y i ) ∣ + ϕ n . \Phi=\sum_{i=0}^{n}|\phi_i| =\phi_0+\sum_{i=1}^{n-1}\left|atan2(\Delta y_{i+1}\Delta x_i-\Delta x_{i+1}\Delta y_i,\Delta x_{i+1}\Delta x_i+\Delta y_{i+1}\Delta y_i)\right|+\phi_n.Φ=i=0∑n​∣ϕi​∣=ϕ0​+i=1∑n−1​∣atan2(Δyi+1​Δxi​−Δxi+1​Δyi​,Δxi+1​Δxi​+Δyi+1​Δyi​)∣+ϕn​.

3.实验结果

实验系统包括移动机器人平台、室内定位系统和障碍检测系统。

4.参考文献

Ou J, Song G, Guo J, et al. GPU-enabled Decentralized, multi-robot path planning based on global evolutionary dynamic programming and local particle swarm optimization[J]. Expert Systems with Applications, 2026, 321: 132321.

5.算法辅导·应用定制·读者交流

xx