MATLAB 2024a

1、算法描述

摘  要
针对复杂障碍环境下路径规划过程中普遍存在的路径冗余、转折过多以及平滑性不足等问题，本文提出一种基于粒子群优化与图搜索拼接的复杂栅格地图路径规划方法。该方法以已知静态环境为研究对象，首先采用栅格地图对规划空间进行离散表达，在此基础上提取障碍物周边的候选关键点，并构建可通行节点图；随后利用粒子群优化算法对关键点的选取与访问顺序进行全局搜索，再借助图搜索机制完成相邻关键段之间的最短路径拼接，从而形成一条由全局引导与局部连接共同构成的原始可行路径；最后针对初始路径折线感强、转折频繁的问题，引入基于碰撞约束与连续可见性检测的平滑处理策略，对路径进行压缩与优化。本文在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、关键代码展示

略

当下时代学习怎么用AI是每个人已经之路，给大家推荐几本书：学习AI相关使用技巧！！！                       抓住时代红利！！！

4、MATLAB 源码获取

途径一：点击文章中蓝色字体阅读原文

途径二：复制以下网址到浏览器中打开麦完单品

https://www.maiwan8.com/#/dynamicDetail/0/3e08f3f131b6d10389da77bae3555b56/index?yqm=5FCPU

途径三：复制网址打开麦完店铺搜索该篇文章标题即可

https://www.maiwan8.com/#/packageA/userDynamicCenter/userDynamicCenter?user_id=1261511

途径四：如果以上方式均失效请通过QQ，邮箱或者微信公众号联系我

                                (点击上方↑↑↑↑↑蓝色字体跳转)