1 基本概念
1.1 定义与作用
路径规划是指在已知或部分已知环境中，依据起点、终点以及各种约束条件，求解实体从出发位置到目标位置的可行移动方案。其结果通常表现为一条离散路径、连续轨迹，或一组可供执行的候选方案。
在自动化与智能系统中，路径规划承担“导航决策”的基础功能。它不仅决定移动方向，还影响到系统的效率、稳定性与安全水平。无论是移动机器人穿行于工厂通道，还是无人机穿越空域，路径规划都直接关系到任务能否顺利完成。
1.2 路径规划与运动规划的区别
路径规划更侧重于“空间上的通路选择”，强调从整体上找出一条可行路线；运动规划则进一步关注“如何执行这条路线”，需要处理速度、加速度、转角、动力学响应等问题。
在实际系统中，两者常常紧密衔接。路径规划给出几何层面的路线，运动规划则将其转换为可由执行机构跟踪的轨迹。前者偏向决策，后者偏向控制，但二者往往共同构成导航链路。
1.3 路径规划的核心目标
路径规划通常并不只追求“能到达”，而是综合多个指标进行权衡，以获得更适合任务需求的结果。
1.3.1 可达性
可达性指规划结果必须能够从起点通向终点，且满足环境中的基本约束。若路径无法穿越障碍区域、无法满足动作限制，便不具备实际意义。
1.3.2 最优性
最优性强调在多个可行方案中选取代价更低的一条。这里的“最优”不一定只指距离最短，也可能意味着时间更少、能耗更低或风险更小。
1.3.3 安全性
安全性要求路径尽量远离障碍物、危险区域或不稳定区域。在人机共存、交通复杂或设备密集的场景里，这一指标尤为重要。
1.3.4 实时性
实时性表示规划过程需要在可接受的时间内完成，尤其适用于环境变化频繁的系统。若规划耗时过长，可能导致结果失效，甚至影响系统响应。
1.4 路径规划的典型应用场景
路径规划广泛用于工业机器人、仓储物流、无人驾驶、无人机巡检、服务机器人、仿真游戏 AI 以及数字环境中的自动化控制等领域。不同场景对路径规划的侧重点不同，有的强调高精度，有的强调高速度，也有的更关注鲁棒性与资源消耗。
2 问题建模
2.1 环境表示
路径规划的首要步骤是将现实环境转化为计算机能够处理的模型。环境表示方式不同，会直接影响算法设计、搜索效率与结果精度。
2.1.1 栅格地图
栅格地图将环境划分为若干规则网格，每个格子记录可通行性、代价值或风险信息。这种方式结构清晰，便于图搜索算法处理，但在高精度场景下可能带来分辨率与计算量之间的矛盾。
2.1.2 拓扑地图
拓扑地图更关注区域之间的连接关系，而非精确几何形状。它通过节点和边描述环境中的关键位置，适合大范围路径导航，尤其便于表达道路网络、房间连接或站点关系。
2.1.3 连续空间模型
连续空间模型将环境视为一个连续区域，路径可以在其中自由变化。该模型更接近真实物理世界，适用于需要高精度轨迹的场合，但求解复杂度通常更高。
2.2 约束条件
路径规划问题通常不是纯粹的几何寻路，而是带有多种限制的综合优化问题。
2.2.1 静态障碍约束
静态障碍是指位置固定、在规划过程中基本不变化的障碍物，如墙体、设备、建筑边界等。规划时必须确保路径不与这些区域重叠。
2.2.2 动态障碍约束
动态障碍会随时间移动，例如行人、车辆或机械臂附近的其他部件。此类约束要求规划结果能够对环境变化及时响应。
2.2.3 运动学约束
运动学约束来自实体自身结构与运动方式，例如最小转弯半径、转向角限制、速度上限等。若忽略这些约束，路径即使在几何上可行，也可能无法执行。
2.2.4 能耗与时间约束
某些任务要求在限定时间内完成，或尽量减少电池消耗与运行负载。此时路径规划需要在效率与资源之间取得平衡。
2.3 目标函数设计
目标函数用于衡量不同路径方案的优劣，通常由多个代价项组合而成。
2.3.1 路径长度
路径长度是最常见的优化指标之一。较短路径通常意味着更快到达目标，也可能减少能耗，但并不总是最安全或最平稳的选择。
2.3.2 转向代价
转向代价用于惩罚频繁或剧烈的方向变化。它对车辆、机器人和飞行器尤为重要，因为过急的转弯会影响稳定性和舒适性。
2.3.3 风险代价
风险代价反映路径经过危险区域、障碍物边缘或不确定区域时的额外惩罚。该项常用于提高整体安全裕度。
2.3.4 平滑度代价
平滑度代价用于减少路径中的折线和突变，使输出更适合后续控制与执行。平滑路径通常更容易被跟踪，也能降低机械冲击。
3 经典算法
3.1 图搜索算法
图搜索算法将环境抽象为节点与边，在图结构上寻找从起点到终点的最优或近似最优路径。
3.1.1 Dijkstra 算法
Dijkstra 算法是一种经典最短路径搜索方法，适用于边权非负的图。它通过逐步扩展当前代价最小的节点，保证得到全局最短路径，但在大规模地图上计算成本较高。
3.1.2 A* 算法
A* 算法在 Dijkstra 的基础上引入启发式估计，通过结合已知代价与预估代价来加快搜索。若启发函数设计合理，它能在效率与最优性之间取得较好平衡。
3.1.3 D* 系列算法
D* 系列算法主要面向动态环境或局部地图更新场景，可在环境变化后对原有路径进行增量修正。它适合需要在线重规划的任务。
3.2 采样算法
采样算法通过在连续空间中随机或半随机地生成点，再连接这些点构建可行路径。其优势在于适合高维问题和复杂空间。
3.2.1 随机采样基础
随机采样的核心思想是在可行空间内不断生成候选点，并根据碰撞检测和连接规则形成搜索结构。这种方法不依赖完整离散化，灵活性较强。
3.2.2 PRM 算法
PRM 算法先在环境中采样若干节点，再通过局部连通测试构建概率路网，最后在图上搜索路径。它更适合静态环境中的多次查询任务。
3.2.3 RRT 算法
RRT 算法通过逐步扩展随机生成的树结构，快速覆盖搜索空间。它在高维场景中表现突出，尤其适合初步找到可行解。
3.2.4 RRT* 算法
RRT* 算法是在 RRT 基础上的优化版本，增加了重连机制，可逐渐提升路径质量。它通常能够在生成可行路径后继续逼近更优解。
3.3 代价优化方法
代价优化方法更强调在约束条件下直接求解最小代价方案，常用于需要精细权衡的场景。
3.3.1 动态规划
动态规划将复杂问题拆分为若干子问题，并通过递推方式求得整体最优解。其优势是理论清晰，但在状态空间较大时计算量容易上升。
3.3.2 启发式搜索
启发式搜索借助经验规则或估计函数引导搜索过程，以减少无效扩展。它常被用于提高路径发现速度，同时保持较好的结果质量。
3.3.3 轨迹优化
轨迹优化在初始可行路径的基础上，通过数值方法不断调整轨迹形状，使其更符合代价函数与动力学约束。该方法常用于高质量路径生成。
4 进阶规划策略
4.1 全局路径规划
全局路径规划通常基于整体地图信息，为任务提供宏观路线框架，强调路径的整体结构与可行性。
4.1.1 静态环境规划
在静态环境中，障碍物位置变化不大，规划器可利用较完整的先验信息生成稳定路径。这类规划结果通常较适合长期执行。
4.1.2 大规模地图规划
大规模地图规划关注长距离、多区域或复杂网络中的导航问题。此时常需要分层建模、区域划分或图简化，以降低计算开销。
4.2 局部路径规划
局部路径规划主要处理局部感知范围内的即时决策，目标是在全局方向指导下实现安全、平稳的短程移动。
4.2.1 实时避障
实时避障用于在移动过程中躲避突然出现的障碍物。它依赖快速感知与即时决策，往往需要较高的计算响应速度。
4.2.2 速度调节
速度调节不仅决定“走哪儿”，也决定“走多快”。在转弯、拥挤或风险较高的区域，降低速度有助于提升稳定性和安全性。
4.2.3 窄通道通过
窄通道通过是局部规划中的难点之一。由于可用空间有限，系统既要避免碰撞，又要兼顾姿态调整和连续运动。
4.3 动态路径规划
动态路径规划面向环境不断变化的场景，需要在执行过程中持续修正原有方案。
4.3.1 在线重规划
在线重规划指系统在运行时重新计算或局部调整路径，以适应新出现的障碍、目标变化或执行偏差。
4.3.2 目标重定位
目标重定位是指目标点发生改变后，规划系统重新建立终点并更新路径。该机制常用于任务重分配或目标移动的场景。
4.3.3 环境变化响应
环境变化响应强调系统对通道封闭、障碍移动、地图更新等情况的适应能力。响应越及时，系统整体可靠性越高。
4.4 多目标路径规划
多目标路径规划同时考虑多个互相制约的指标，通常需要在各类代价之间进行折中。
4.4.1 最短路径与最安全路径权衡
最短路径不一定最安全，最安全路径也未必最高效。实际规划中常需要根据任务优先级，对距离与安全程度进行平衡。
4.4.2 多约束联合优化
多约束联合优化将长度、时间、能耗、平滑度等指标同时纳入模型，以得到更符合真实需求的路径方案。
4.4.3 Pareto 最优解
Pareto 最优解指在多目标条件下，某一方案无法在不恶化其他指标的前提下继续改善某个指标。它常用于呈现一组可选折中方案。
5 机器人与自动化系统中的应用
5.1 移动机器人导航
移动机器人导航是路径规划最典型的应用之一，涉及室内外移动、障碍回避与任务执行。
5.1.1 室内导航
室内导航通常面对走廊、房间、家具等固定障碍，空间较封闭，但路径精度要求较高。
5.1.2 仓储物流机器人
仓储物流机器人需要在货架、通道和作业区之间高效穿行，路径规划常与调度系统协同，以提高搬运效率。
5.1.3 服务机器人
服务机器人多出现在酒店、医院、展馆等环境中，要求兼顾安全、礼让和路线清晰度，避免干扰人群活动。
5.2 工业自动化
工业场景中的路径规划不仅服务于移动平台，也服务于机械臂、输送线和检测设备。
5.2.1 机械臂末端规划
机械臂末端规划关注末端执行器到达目标位姿的运动路径，需要处理关节限制、避障与姿态要求。
5.2.2 产线搬运路径设计
产线搬运路径设计用于连接各工位和物料点，目标是减少等待时间、缩短往返距离并提升节拍稳定性。
5.2.3 自动化检测路线
自动化检测路线常用于巡检、喷涂或扫描任务，要求覆盖完整、运动平稳，并尽量减少遗漏区域。
5.3 无人系统
无人系统依赖路径规划完成自主飞行、行驶或航行任务。
5.3.1 无人机航线规划
无人机航线规划需考虑空域边界、航高、续航和避障要求。与地面平台相比，其环境更三维化，约束也更复杂。
5.3.2 无人车行驶规划
无人车行驶规划关注道路结构、交通规则、转弯半径与动态障碍，常需结合感知与预测模块共同完成。
5.3.3 水面与水下平台规划
水面与水下平台规划面临流体扰动、定位困难和通信受限等问题，因此常更注重鲁棒性与任务容错。
5.4 虚拟环境与游戏 AI
在虚拟环境中，路径规划用于构建更自然的角色行为与场景交互。
5.4.1 NPC 巡逻路径
NPC 巡逻路径决定非玩家角色在场景中的巡视路线，可用于增强环境的动态感和交互感。
5.4.2 地图寻路
地图寻路是游戏中最常见的自动移动机制，通常要求角色在复杂地形中快速找到可行路线。
5.4.3 群体行为路径控制
群体行为路径控制用于协调多个虚拟个体的移动，避免互相阻塞，并形成较自然的集体运动效果。
6 关键技术与实现
6.1 感知与定位支持
路径规划的质量高度依赖环境感知与位置信息的准确性。
6.1.1 传感器融合
传感器融合将摄像头、激光雷达、惯性测量单元等多源数据结合起来，以提高环境理解和状态估计的可靠性。
6.1.2 SLAM 支撑
SLAM 技术帮助系统在未知环境中同步完成定位与建图，为路径规划提供实时地图和位姿参考。
6.1.3 地图更新
地图更新使系统能够反映环境中的新障碍、临时封闭区域或结构变化，从而保证规划结果不过时。
6.2 规划与控制协同
路径规划并不是独立模块，最终仍需与控制系统配合，才能完成实际运动。
6.2.1 路径跟踪
路径跟踪指控制系统按照规划路线持续修正偏差，使实体尽量贴近目标轨迹运行。
6.2.2 轨迹平滑
轨迹平滑用于消除折线、尖角或不连续变化，使执行过程更稳定，也更符合动力学要求。
6.2.3 反馈控制
反馈控制通过实时测量执行状态并修正偏差，增强系统对扰动、误差和外部影响的适应能力。
6.3 性能优化
随着地图规模和任务复杂度提升，规划系统需要在速度、资源和质量之间进行优化。
6.3.1 计算效率
计算效率决定规划器能否在时限内输出结果。常见做法包括剪枝、分层搜索和启发式加速等。
6.3.2 内存与存储优化
在大地图或高频重规划场景中，内存管理非常重要。合理压缩状态、缓存中间结果可以减少系统负担。
6.3.3 并行与分布式计算
并行与分布式计算可将搜索、评估或仿真任务拆分到多个处理单元，以提升整体吞吐量和响应速度。
6.4 鲁棒性设计
鲁棒性设计旨在提高系统面对误差、噪声和异常情况时的稳定表现。
6.4.1 不确定性处理
不确定性处理关注感知误差、定位漂移和环境模型偏差等问题，通常通过概率建模或保守策略来降低风险。
6.4.2 容错机制
容错机制允许系统在局部失败时继续运行，例如路径失效后的重新计算、传感器异常后的降级模式等。
6.4.3 极端场景适应
极端场景适应是指系统在狭窄空间、强干扰环境或资源紧张条件下仍能保持基本可用性。
7 评价与测试
7.1 常用评价指标
路径规划的效果通常需要通过一组量化指标进行评估。
7.1.1 路径长度
路径长度反映实际移动距离，是衡量规划效率的基础指标之一。
7.1.2 规划耗时
规划耗时衡量算法从接收任务到输出结果所需的时间，是实时系统中的关键指标。
7.1.3 成功率
成功率表示规划器在多次测试中能否找到满足约束的有效路径，通常用于评估稳定性。
7.1.4 碰撞率
碰撞率用于衡量路径执行过程中与障碍物接触或发生冲突的频率，是安全性的重要参考。
7.2 仿真测试
仿真测试能在相对低成本条件下验证规划算法的功能、性能和边界表现。
7.2.1 标准场景测试
标准场景测试使用预设地图和典型任务，用于比较不同算法的基础能力与结果差异。
7.2.2 动态障碍测试
动态障碍测试用于考察规划器对移动物体和环境变化的响应能力。
7.2.3 压力测试
压力测试通过扩大地图规模、增加障碍数量或压缩时间预算，观察系统在极限条件下的表现。
7.3 实机验证
实机验证能够检验算法在真实环境中的可执行性与稳定性。
7.3.1 室内实测
室内实测常用于机器人、服务设备和仓储系统，重点验证定位精度、避障效果和路径跟踪能力。
7.3.2 户外实测
户外实测面对光照变化、路况复杂和干扰因素更多等情况，更能体现系统的环境适应能力。
7.3.3 复杂环境验证
复杂环境验证通常在高密度障碍、狭窄通道或多任务并发条件下进行，用以检验系统整体鲁棒性。
8 发展趋势
8.1 智能化规划
路径规划正从传统几何搜索逐渐走向智能化、数据驱动和自适应决策。
8.1.1 学习型路径规划
学习型路径规划利用机器学习方法从历史数据或交互经验中提取规律，以提升在复杂场景中的表现。
8.1.2 数据驱动优化
数据驱动优化依靠大量运行样本改进代价函数、启发策略或参数配置，使规划结果更贴近实际需求。
8.2 多智能体协同
多个移动单元同时工作时，路径规划需要考虑彼此之间的关系与整体任务效率。
8.2.1 编队路径规划
编队路径规划用于保持多个实体的相对位置和队形结构，常见于无人机群和协同移动平台。
8.2.2 冲突消解
冲突消解指处理多主体在同一空间中可能出现的路径冲突、等待冲突或资源竞争问题。
8.2.3 协同决策
协同决策强调多个智能体共享信息并统一行动策略，以减少局部最优造成的整体效率损失。
8.3 面向复杂环境的自适应规划
复杂环境中的路径规划越来越强调实时调整和环境感知能力。
8.3.1 不确定场景适配
不确定场景适配用于应对地图不完整、障碍信息模糊或状态估计不稳定的情况。
8.3.2 高动态场景响应
高动态场景响应要求系统在短时间内完成重规划，以适应密集移动对象和频繁变化的局面。
8.3.3 人机协作规划
人机协作规划将人的意图、习惯或实时指令纳入规划过程，使系统行为更符合实际使用需求。