4. 任务规划算法基础与选型

无人系统任务规划的核心问题可以统一描述为：在状态空间 X 中，给定起点 x_start、目标集合 X_goal、约束集合 C（禁飞区、最小转弯半径、续航、通信中断区等）以及代价函数 J，求一条可行且代价较低的路径或任务序列。不同算法族对“状态空间如何表示”“约束如何进入求解”“代价如何评估”的处理方式差异很大，这直接决定了它们的适用条件。本节按启发式搜索、采样规划、优化求解、强化学习四类展开，并给出选型判据。

一、启发式搜索：离散图上的最优性保证

启发式搜索把连续空间离散为图或栅格，节点为位姿或航路点，边为可执行动作，代价为距离、时间或能耗。A* 的评估函数为 f(n)=g(n)+h(n)，其中 g(n) 是从起点到节点 n 的实际代价，h(n) 是到目标的启发式估计。当 h(n) 满足可采纳性（不高估真实代价）时，A* 能保证最优解；当 h(n) 满足一致性时，节点无需重复展开。工程中常用八邻域栅格配合对角距离启发式，或三维栅格配合欧氏距离启发式。

启发式搜索的优点是确定性强、可复现、能给出最优性边界，适合静态、结构化、维度较低的场景，例如已知建筑群的巡检航线、固定航路网的物流配送。其瓶颈在于状态空间随维度指数增长：三维栅格分辨率 1 m、范围 1 km×1 km×200 m 时节点数约 2×10^8，直接搜索不可行，必须依赖分层规划、跳点搜索（JPS）或稀疏图抽象。此外，A* 对动态障碍和在线重规划支持较弱，通常需要配合滚动时域重规划。

二、采样规划：高维连续空间中的可行性优先

采样规划不显式构造图，而是在连续空间中随机采样并连接，代表算法为 RRT、RRT*、PRM 及其变体。RRT 通过向随机采样点扩展树来快速探索空间，概率完备但不保证最优；RRT* 引入重选父节点和重连操作，在采样数趋于无穷时渐近最优。PRM 适合多次查询同一环境，先构建路线图再查询。

采样规划的优势在于对高维状态空间和复杂约束的适应性，例如带机械臂的无人机抓取、多关节无人车、狭窄通道穿越。它不需要对空间做精细离散，但代价是解的质量随机、路径通常不平滑，需要后处理（B 样条、贝塞尔或最小加速度优化）。工程参数上，扩展步长 step_size 常取 0.5～2.0 m，目标偏置概率 goal_bias 取 0.05～0.2，最大迭代次数按场景复杂度取 10^4～10^6。判断收敛的实用指标是连续若干次迭代未找到更优解，或代价下降率低于阈值。

三、优化求解：把任务规划写成数学规划

优化求解将任务规划建模为混合整数线性规划（MILP）、二次规划（QP）、模型预测控制（MPC）或非线性规划（NLP）。决策变量包括航路点位置、到达时间、任务分配变量；约束包括动力学、避障、时序、电量；目标函数为总时间、总能耗或加权组合。MILP 适合任务分配与路径联合优化，能给出全局最优性间隙，但求解时间随整数变量增长很快；QP/MPC 适合局部轨迹平滑与动态避障，求解频率可达 10～100 Hz；NLP 适合带非线性动力学的高精度轨迹优化，但依赖初值且可能陷入局部最优。

优化求解的适用条件是：约束可显式表达、规模可控、对最优性或约束满足有硬性要求。例如多无人机协同侦察中，用 MILP 分配目标并保证每架次续航约束，用 QP 对分段轨迹做平滑。实际使用时通常采用分层结构：上层用 MILP 或启发式做任务分配，下层用 QP/MPC 做轨迹生成与跟踪，避免单一模型规模爆炸。

四、强化学习：从交互中学习策略

强化学习把任务规划建模为马尔可夫决策过程 (S,A,P,R,γ)，通过与环境交互学习策略 π(a|s)。深度强化学习（DQN、PPO、SAC）可处理高维观测，适合环境动态、规则难以显式建模、需要在线适应的场景，例如未知环境搜索、对抗规避、多机协同策略。其优势是推理阶段计算量小、响应快，策略可端到端输出动作。

但强化学习在任务规划中面临几个现实问题：训练样本效率低，仿真环境与真实环境的差异会导致策略迁移失败；奖励设计困难，稀疏奖励下难以收敛；安全约束难以硬保证，通常需要安全层或屏蔽机制。因此工程上更常见的做法是“RL 做上层决策或局部避障，传统规划做安全兜底”，而不是完全替代搜索或优化。

五、选型对比与决策依据

四类算法的选型不应只看算法热度，而应看四个维度：状态空间维度与连续性、约束是否可显式表达、是否要求最优性或可证明安全性、以及在线计算预算。下表给出典型判据。

一个实用的选型流程是：先判断约束能否显式写出。能显式写出且规模可控，优先优化求解；不能显式写出或环境高度动态，考虑强化学习。再看空间维度：低维离散用启发式搜索，高维连续用采样规划。最后看是否要求可证明安全性：若要求，则必须保留搜索或优化作为安全层，RL 只做辅助决策。

需要强调的是，实际系统很少只用一种算法。更常见的架构是分层组合：上层用启发式搜索或 MILP 完成任务分配与粗路径，中层用采样规划处理复杂几何约束，下层用 QP/MPC 做轨迹平滑与动态避障，强化学习则用于局部策略或对抗决策。选型的最终依据不是算法本身先进与否，而是它能否在给定计算预算内稳定满足任务的安全性与时效性要求。