目录1.摘要2.路径规划算法3.实验结果4.参考文献5.算法辅导·应用定制·读者交流1.摘要本文提出一种GPU加速的单/多机器人路径规划方法融合全局进化动态规划EDP与局部粒子群算法PSO。基于可视点图将路径规划建模为马尔可夫决策过程MDP利用EDP求解生成具备显著状态值的多条高质量初始路径随后通过并行化多种群PSO对初始路径进行同步近端优化。2.路径规划算法目标是在动态环境中从机器人当前位置和姿态到目标点生成最优路径。路径由若干航点组成需避开多边形障碍。障碍可为凸或凹多边形非多边形物体用较细多边形近似。机器人在移动过程中障碍也可能移动因此起点不是初始点而是实时当前位置。优化指标包括路径长度、平滑性和安全性。Methodology由视觉检测得到障碍并生成地图再构造可视图可视图节点包括起点、目标点和膨胀障碍顶点边为不穿越障碍的可行连接。障碍膨胀半径取R 0 0.235 m R_00.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 \gamma1γ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.Fvmax​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_{i1}^{n}d_i\sum_{i1}^{n}\sqrt{(x_i-x_{i-1})^2(y_i-y_{i-1})^2}.Li1∑n​di​i1∑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_{i0}^{n}|\phi_i| \phi_0\sum_{i1}^{n-1}\left|atan2(\Delta y_{i1}\Delta x_i-\Delta x_{i1}\Delta y_i,\Delta x_{i1}\Delta x_i\Delta y_{i1}\Delta y_i)\right|\phi_n.Φi0∑n​∣ϕi​∣ϕ0​i1∑n−1​∣atan2(Δyi1​Δxi​−Δxi1​Δyi​,Δxi1​Δxi​Δyi1​Δ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