【MATLAB源码-第418期】基于MATLAB的PSO算法栅格地图路径规划—减少转角和路径平滑

操作环境MATLAB 2024a1、算法描述摘 要针对复杂障碍环境下路径规划过程中普遍存在的路径冗余、转折过多以及平滑性不足等问题本文提出一种基于粒子群优化与图搜索拼接的复杂栅格地图路径规划方法。该方法以已知静态环境为研究对象首先采用栅格地图对规划空间进行离散表达在此基础上提取障碍物周边的候选关键点并构建可通行节点图随后利用粒子群优化算法对关键点的选取与访问顺序进行全局搜索再借助图搜索机制完成相邻关键段之间的最短路径拼接从而形成一条由全局引导与局部连接共同构成的原始可行路径最后针对初始路径折线感强、转折频繁的问题引入基于碰撞约束与连续可见性检测的平滑处理策略对路径进行压缩与优化。本文在30×30复杂栅格地图环境下完成仿真实验结果表明该方法能够在保证路径可达性与障碍规避有效性的前提下显著降低路径长度与转折次数。以本文构建的复杂地图场景为例平滑后路径长度由58.38降至48.71下降约16.56%转折次数由19次降至8次下降约57.89%。研究结果说明将群智能优化的全局搜索能力与图搜索的局部连通能力结合并在后处理阶段加入路径平滑机制能够有效提升复杂栅格环境下路径规划结果的整体质量。本文的研究可为无人机低空航迹设计、移动机器人静态环境导航以及复杂已知地图中的全局路径生成提供一定的理论参考与方法借鉴。关键词路径规划粒子群优化栅格地图图搜索拼接路径平滑复杂障碍环境1 引言路径规划是无人机自主飞行、移动机器人导航与智能运输系统中的核心技术之一其目标是在满足环境约束与避障要求的前提下从起点到终点生成一条可行、有效且具有较好执行性的路径。随着复杂任务环境的不断增多单纯依赖传统最短路搜索或单一启发式优化算法往往难以同时兼顾路径长度、转折数量、通行安全裕度与求解稳定性。因此围绕“经典搜索方法如何提升平滑性”和“智能优化算法如何增强可行性与全局性”的研究已成为近年来路径规划领域的重要方向。已有研究表明A*、人工势场、粒子群优化及其混合模型在无人机与移动机器人路径规划中均表现出较强的应用价值而“经典搜索 智能优化 平滑后处理”的融合思路正在逐步成为一条具有代表性的技术路线[4]-[10]。从方法演进的角度看经典图搜索算法具有结构清晰、结果可解释性强和可行路径生成稳定等优势但其在复杂栅格环境中容易产生转折密集、路径呈折线化等问题而粒子群优化算法作为典型的群智能优化方法具有参数形式简洁、全局搜索能力较强、易于与其他策略耦合等特点但若直接用于离散障碍环境路径规划则又容易受到编码方式、约束表达及局部可行性处理的影响。围绕这些问题已有研究提出了自适应惯性权重、排序编码、势场融合、RRT*引导以及多策略复合增强等改进思路以提高PSO在路径规划任务中的收敛性能和实用性[1]-[5][7]-[9]。与此同时关于移动机器人路径规划的综述研究也指出单一算法通常难以同时满足效率、平滑性与鲁棒性等多重需求融合式规划框架具有更好的应用前景[6]。基于上述认识本文面向复杂已知障碍环境构建了一种基于粒子群优化与图搜索拼接的路径规划方法。本文并不直接让粒子在整张地图上逐格搜索而是先在障碍物周边提取一组具有导航意义的候选关键点再利用粒子群优化确定关键点的选择与访问顺序随后借助节点图的最短路径连接能力将多个局部段拼接为完整路径。与仅依赖全局搜索或局部搜索的方法相比这种处理方式既保留了群智能方法对全局结构的引导作用又发挥了图搜索在局部通路求解上的稳定性。为了进一步改善路径执行质量本文还对原始拼接路径进行平滑处理并采用连续碰撞检测避免平滑后路径发生穿障、擦角等问题。本文的研究重点在于其一面向复杂栅格场景建立一种“关键点引导—图搜索拼接—碰撞约束平滑”的统一规划框架其二分析粒子群优化在关键点顺序规划中的作用机制其三通过30×30复杂障碍地图仿真对所提方法在路径长度与转折数优化方面的效果进行验证。全文后续内容依次包括环境建模、算法设计、平滑策略、仿真分析与结论。2 问题描述与环境建模本文研究对象为已知静态障碍环境下的二维全局路径规划问题。为兼顾环境表达的清晰性和算法实现的稳定性采用栅格地图对规划区域进行离散化建模。地图中每一个单元格具有明确的通行属性其中障碍栅格表示不可穿越区域自由栅格表示可通行空间。本文构建的实验场景为30×30复杂栅格地图障碍物由块状障碍、条带型障碍以及局部留孔通道共同组成既包含较宽区域的封闭结构也包含狭窄通路与局部拐角空间能够较好反映复杂路径规划环境中常见的多样障碍分布特征。在此环境中起点设于地图左下角附近终点设于地图右上角附近。由于规划任务发生在已知静态地图上因此问题的核心不在于在线重规划而在于如何在复杂障碍布局下获得一条兼顾可达性、路径长度与转折平滑性的全局路径。若仅依赖常规栅格搜索虽然能够获得可行路径但路径通常沿障碍边界频繁转折不利于后续轨迹跟踪与运动执行。若完全使用连续优化方法直接在复杂障碍场中进行整条路径搜索则容易面临编码维数高、可行约束处理困难等问题。基于此本文采取分层思路对规划问题进行处理。首先将所有自由栅格映射为图节点并依据邻接关系建立节点图从而保证局部连接的可求解性。其次在障碍物周边提取一批候选关键点这些关键点不直接构成最终路径而是作为粒子群优化的全局引导对象。再次由PSO确定若干关键点的优先访问次序再通过图搜索完成起点、关键点、终点之间各局部路段的连接。最后在得到原始可行路径后执行平滑化处理以减少不必要的折线拐角提高路径整体执行品质。这样的建模方式具有两个优点。其一它将高维整路径优化问题转化为较低维的关键点顺序优化问题降低了PSO搜索空间的复杂度。其二它利用图搜索保障局部路径一定程度上的可达性与连通性避免粒子群优化直接面对复杂离散约束时出现大量不可行解。总体而言这一建模思路适合用于复杂栅格地图中的离线路径规划研究也与当前将经典搜索与智能优化相融合的研究趋势相一致[5]-[10]。3 基于粒子群优化与图搜索拼接的路径规划方法3.1 候选关键点提取候选关键点的设置是本文方法的重要基础。与直接在整张地图上对所有自由栅格进行全局优化不同本文认为障碍物周边区域往往决定了路径形态的主要变化位置因此应优先从障碍外缘附近提取具有引导意义的关键点。具体而言先对障碍连通区域进行识别再根据障碍边缘与自由区域的空间分布从障碍外围具有代表性的通行位置中筛选出候选关键点。为避免关键点过多造成搜索冗余本文进一步对候选点进行去重、稀疏采样及边界过滤处理使关键点既能够覆盖主要通路结构又不会因过度密集而降低优化效率。这种候选关键点机制的作用不在于机械地规定路径必须逐点经过全部障碍边缘而在于为PSO提供一组具有环境结构信息的候选导航点。换言之关键点相当于复杂栅格环境中的结构性特征它们帮助算法把注意力集中到可能影响路径转向与通行走廊选择的核心区域。通过这种方式PSO的搜索从“在整张地图上盲目找路”转变为“在关键结构点之间优化全局引导关系”。3.2 粒子群优化的关键点顺序搜索在候选关键点确定之后本文利用粒子群优化算法对关键点的访问顺序进行求解。与连续空间中直接优化轨迹坐标的做法不同本文采用基于排序的思想将粒子位置向量理解为关键点优先级的编码。粒子中各维分量经过排序后可得到关键点的访问次序再从排序结果中选取若干优先级较高的关键点构成原始路径中的中间引导节点序列。这一处理方式能够较好适配PSO的连续更新特性同时避免离散组合优化中常见的编码不稳定问题。粒子在迭代过程中不断更新个体最优和群体最优位置从而实现对关键点访问顺序的全局搜索。若某个候选序列在后续局部拼接时出现不可达情况则通过适应度惩罚机制予以抑制若序列能够形成连通且较优的路径结构则对应粒子将获得更高的适应度评价。这样一来PSO的搜索方向逐步被引导到更有利于整体路径生成的关键点次序上。已有研究表明PSO在路径规划场景中的有效性很大程度上取决于其编码方式、惯性权重调节和与其他方法的协同形式将PSO用于路径节点或关键点层面的次序优化通常比直接作用于全部栅格点更容易获得稳定结果[1][3]-[5][7]-[9]。3.3 图搜索拼接机制当PSO确定关键点访问顺序后本文进一步采用图搜索方法连接起点、各中间关键点以及终点从而形成一条完整的原始可行路径。这里的图搜索并非作为全文的独立对比算法而是作为所提方法内部的局部求解模块存在。其基本思想是对路径序列中的每一对相邻节点在已建立的可通行节点图上寻找局部最短连接段再将各局部段按顺序拼接为整条路径。这种“全局引导 局部拼接”的结构有助于同时兼顾路径宏观方向与局部可通行性。若仅依赖PSO进行整体求解则复杂障碍环境中的离散约束会显著增加搜索难度而若仅依赖图搜索则虽能保证连通却难以主动借助关键点信息优化整体形态。两者结合后PSO负责给出路径走廊的大致方向与关键过渡位置图搜索负责在局部图结构上生成真实可通行的细节路段从而提高求解成功率与路径合理性。3.4 路径平滑策略经过图搜索拼接后得到的原始路径通常具有较强的栅格离散特征表现为路径拐点较多、局部折线明显、执行过程中的姿态切换频繁。为此本文在原始路径基础上引入平滑处理策略。平滑的基本思想并非简单地删除节点而是在满足避障要求的前提下尽可能压缩冗余折线段减少不必要的中间拐点使路径整体更接近实际运动平台所需的连续转向形式。考虑到复杂障碍环境中容易出现“线段未穿障但擦过障碍拐角”的情况本文在平滑阶段加入连续碰撞检测机制并设置一定安全余量对候选平滑段进行可见性验证。只有当一段更直接的连接不会与障碍物发生碰撞也不会因过分贴近障碍拐角而导致潜在风险时该段才会替代原有折线路径。这样处理后既能避免过度保守导致的平滑无效又能减少简单离散采样判定可能带来的误判。在方法层面上平滑并不是独立于规划结果之外的附加美化操作而是关系到路径可执行性的重要后处理环节。对于无人机或移动机器人而言转折过于密集意味着姿态切换频繁、控制负担加重而适度的平滑则有助于提高后续路径跟踪的稳定性。因此本文将平滑后的路径质量作为最终评估结果的重要组成部分。4 评价指标与仿真方案为了客观评价所提方法在复杂环境下的规划效果本文采用路径长度和转折次数两个指标进行分析。路径长度反映从起点到终点的整体通行代价长度越短通常意味着任务执行效率越高转折次数则反映路径的几何复杂程度转折越少说明路径越平顺越有利于实际平台完成连续运动。需要指出的是本文将转折次数作为平滑效果的重要表征而不再将额外风险指标作为图像输出重点从而使评价体系更集中于路径几何性能的改进效果。仿真实验在30×30复杂栅格地图中进行。场景内包含多个大块障碍、狭窄走廊以及局部通道留孔能够较好考验路径规划算法在复杂障碍布局下的全局引导与局部连接能力。实验流程包括候选关键点提取、PSO搜索、原始路径拼接、平滑后处理以及结果可视化。通过地图示意图、原始路径与平滑路径对比图、PSO收敛过程图、关键点访问顺序图以及指标归一化对比图对所提方法进行综合分析。5 仿真结果与讨论从实验结果可以看出所提方法能够在复杂30×30栅格地图中生成从左下区域到右上区域的完整可行路径。原始路径在总体方向上已经较好反映了PSO对关键通行走廊的引导作用路径能够绕开主要障碍区并通过预留通道抵达目标位置。与此同时由于原始路径由局部最短段拼接构成因此在若干局部区域仍表现出明显的折线化特征这也是复杂离散环境路径规划中常见的问题。在平滑处理之后路径整体形态更加紧凑局部冗余折段被有效压缩。实验数据显示原始路径长度为58.38平滑后下降至48.71长度降低约16.56%原始路径转折次数为19次平滑后降至8次下降约57.89%。这一结果说明本文设计的平滑策略不仅减少了路径在几何上的曲折程度也改善了路径在整体行进方向上的连贯性。对于实际无人机或移动机器人系统而言这种改进意味着更少的姿态切换、更平稳的运动轨迹以及更高的执行效率。从PSO收敛过程来看群体最优值在前期迭代中下降较快说明候选关键点与顺序编码机制能够为群智能搜索提供明确的优化方向进入中后期后群体平均适应度仍保持缓慢改善表明算法在一定程度上仍具备继续搜索和细化解空间的能力。相比于完全随机生成中间节点的方式本文通过候选关键点提取将搜索重点集中于障碍结构主导区域使得PSO能够更有效地利用环境信息减少无效搜索。从关键点访问顺序图可以进一步看出最终被选中的关键点主要分布在地图中通道转折和障碍间隙附近这与路径规划问题的实际规律是一致的。换言之真正影响全局路径形态的并不是所有自由区域而是少数决定“向哪里拐、从哪里过”的关键结构位置。PSO通过对这些关键位置进行全局排序有效地改变了后续图搜索拼接的宏观走向使局部最短段不再是彼此孤立的连接而是在统一的全局引导下形成更合理的通路。需要说明的是本文方法面向的是已知静态环境因此其优势主要体现在复杂地图中的全局路径生成与后处理优化而不涉及动态障碍条件下的实时重规划。若将来进一步扩展到动态场景则还需要将环境更新、局部避碰与滚动优化机制纳入统一框架。此外当前方法采用二维栅格环境进行验证虽然适用于全局路径设计思路的分析但对于面向真实低空无人机任务的三维航迹规划而言仍需要在高度维度、飞行动力学约束以及多目标任务代价方面进行进一步拓展。尽管如此本文提出的“关键点引导—图搜索拼接—碰撞约束平滑”的基本框架仍然具有较好的可迁移性可为后续更高维度、更复杂约束的路径规划问题提供方法基础。6 结论本文围绕复杂障碍环境下的全局路径规划问题提出了一种基于粒子群优化与图搜索拼接的路径规划方法并在30×30复杂栅格地图中完成了仿真验证。该方法首先通过障碍周边候选关键点提取压缩搜索空间再利用粒子群优化完成关键点顺序的全局求解随后借助节点图上的局部最短路径拼接生成完整可行路径最后通过连续碰撞检测约束下的平滑处理降低路径折线感与转折密度。实验结果表明该方法能够在复杂地图中稳定获得可行路径并在长度与转折两项指标上取得明显优化效果。从研究结果来看本文方法的意义主要体现在三个方面。其一通过关键点机制将复杂环境中的结构信息显式引入PSO搜索过程提高了群智能算法在离散障碍地图中的适配性。其二通过图搜索拼接提高了局部路段生成的可靠性使PSO不必直接承担全部离散可行性约束。其三通过平滑处理显著改善了路径的几何品质使规划结果更接近实际运动平台的执行需求。总体而言本文所构建的方法兼顾了全局性、可行性与可执行性适用于复杂已知环境下的无人机或移动机器人路径规划研究。后续可进一步围绕三维场景扩展、动态障碍处理、多目标代价设计以及与轨迹跟踪控制的一体化融合展开深入研究。参考文献[1] Wang D, Tan D, Liu L. Particle swarm optimization algorithm: an overview[J]. Soft Computing, 2018, 22: 387-408.[2] Ajeil F H, Ibraheem I K, Sahib M A, et al. Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm[J]. Applied Soft Computing, 2020, 89: 106076.[3] Tao Q, Sang H, Guo H, et al. Improved particle swarm optimization algorithm for AGV path planning[J]. IEEE Access, 2021, 9: 33522-33531.[4] Phung M D, Ha Q P. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J]. Applied Soft Computing, 2021, 107: 107376.[5] Zheng L, Yu W, Li G, et al. Particle Swarm Algorithm Path-Planning Method for Mobile Robots Based on Artificial Potential Fields[J]. Sensors, 2023, 23(13): 6082.[6] Liu L, Wang X, Yang X, et al. Path planning techniques for mobile robots: Review and prospect[J]. Expert Systems with Applications, 2023, 227: 120254.[7] Cheng Q, Zhang Z, Du Y, et al. Research on Particle Swarm Optimization-Based UAV Path Planning Technology in Urban Airspace[J]. Drones, 2024, 8(12): 701.[8] Wang Q, Yi W. Composite Improved Algorithm Based on Jellyfish, Particle Swarm and Genetics for UAV Path Planning in Complex Urban Terrain[J]. Sensors, 2024, 24(23): 7679.[9] Meng Q, Chen K, Qu Q. PPSwarm: Multi-UAV Path Planning Based on Hybrid PSO in Complex Scenarios[J]. Drones, 2024, 8(5): 192.[10] Choi J, Choi Y. Path Planning for Unmanned Aerial Vehicle: A-Star-Guided Potential Field Method[J]. Drones, 2025, 9(8): 545.2、仿真结果演示3、关键代码展示略4、MATLAB 源码获取V点击下方名片关注公众号获取