机器及其具身 8

第6章决策与任务规划本章概述机器人任务规划是基于环境信息、任务需求和机器人自身能力，设计一系列能够完成特定目标的操作步骤和决策方案的过程。学习目标掌握任务规划问题的建模形式（经典规划、MDP模型）、求解方法（精确算法、启发式搜索、机器学习）和实际应用。核心概念预览任务规划的定义与特点、状态转移系统、决策过程、优化目标6.1机器人任务规划问题的建模这一部分介绍任务规划问题的不同建模方法，从经典假设逐步扩展到实际应用中需要考虑的不确定性因素。经典假设建模完全可观性、确定性、静态性等七大假设不确定性扩展马尔可夫决策过程（MDP）模型实际应用车辆路径问题（VRP）等典型案例6.1.1概述任务规划定义使用逻辑推理指导智能体选择一系列离散动作以完成目标的过程。与其他规划的关键区别与路径规划、运动规划相比，最重要特点是与领域无关基于抽象的、通用的动作模型，可适用于不同领域系统架构（图6-1）通用任务规划器分析预先定义的领域知识实时获取用户规划问题和系统状态自动分解为系列子任务（组件能执行的动作）规划通过控制器发送给系统组件控制器观察组件状态，反馈给规划模块6.1.2经典任务规划建模方法🔑经典规划的七大假设完全可观性：系统状态完全已知且可靠确定性：状态-动作对(s,a)最多对应转移到一个状态静态性：系统没有外部事件（事件集为空）受限目标：目标为特定状态或状态集合序列式规划结果：规划解是有限动作的线性序列不考虑时间：动作无时间延续，状态转移瞬间完成离线规划：不考虑系统实时变化经典任务规划模型：五元组Σ=(S,A,c,I,G)S：有限状态集合A：有限动作集合，每个a∈A表示为(name_a,pre_a,eff_a)c:A→ℝ₀⁺：动作耗费函数I⊆S：初始状态G⊆S：目标状态规划结果动作序列P=⟨a₁,a₂,…,aₙ⟩，使系统从I转移到G，总动作耗费最小化⚠️经典规划模型的局限性假设动作执行完全确定，但实际经常失败假设离线规划，但实际系统是动态的无法处理不确定性和外部随机事件难以应用于实际问题，需要扩展主要经典规划算法图规划（GraphPlan）：用可达性分析和析取求解命题可满足方法：基于逻辑推理启发式搜索方法：近年规划大赛冠军方法6.1.3马尔可夫决策任务规划模型MDP模型特点解决不确定性问题允许外部随机事件发生支持在线规划MDP基本假设系统下一刻的状态仅依赖当前状态和动作，与历史无关（马尔可夫性质）MDP五元组：Σ=(S,A,P,R,γ)S：有限状态集合A：有限动作集合P_a(s'|s)：状态转移概率分布，∑P_a(s'|s)=1R:S×A→ℝ：回报函数γ∈[0,1]：折扣因子，控制对未来奖励的重视程度求解算法动态规划（DP）、蒙特卡罗（MC）、时间差分（TD）主要限制维数爆炸——复杂度随状态变量呈指数增加。解决方法：状态近似、分层规划🔑MDP中的值函数（公式6-1）V^π(s)：从状态s执行策略π的回报值R(s,π(s))：当前状态-动作的即时回报γ：折扣因子P_{π(s)}(s'|s)：状态转移概率最优值函数（贝尔曼公式，公式6-2）最优策略（公式6-3）6.1.4经典任务规划问题实例车辆路径问题（VRP）组合优化问题，广泛应用于物流、邮政、芯片设计。简单例子：旅行商问题（TSP）——最短路线问题。目标：完成所有任务，最小化成本（路程、时间、油耗）。问题建模：图形Σ=(V,E,E₁,ω:E→ℤ⁺)n条离散任务路径e₁,e₂,…,eₙ∈E₁各路径端点Aᵢ与Bᵢ顶点集V={A₁,B₁,A₂,B₂,…,Aₙ,Bₙ}边集E={(vᵢ,vⱼ),vᵢ,vⱼ∈V}ω(vᵢ,vⱼ)：边的权值（成本）全路径总代价（公式6-7）优化目标（公式6-8）（T₁为常数，可忽略）VRP求解方法分类1精确求解优化算法、遍历搜索——找到理论最优解2启发式搜索构造型算法、元启发式搜索算法3深度学习方法端到端算法、结合启发式搜索/规则的算法方法对比精确求解：最优但计算时间长，难以处理大规模问题启发式搜索：次优解，计算时间较长神经网络：次优解，训练后推理时间短（线性复杂度）6.2机器人任务规划问题的求解本部分介绍任务规划模型的各种求解方法，从基础的精确搜索到高效的启发式和学习方法。精确求解算法深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra算法启发式搜索算法遗传算法（GA）、蚁群算法（ACO）、模拟退火算法（SA）机器学习方法监督学习（线性回归、逻辑回归、SVM、神经网络）、深度强化学习6.2.1精确求解算法1.深度优先搜索（DFS）基本思想：对每个可能分支路径深入到不能再深入为止，每个节点仅访问一次，是暴力搜索方法。工作流程将任务按优先级（时间、代价、顺序）排序用树形结构连接任务构成任务图从根节点沿深度方向遍历节点的所有边被探寻后，回溯到发现该节点的边的起始节点反复进行直到所有节点被访问🔑DFS的特点优点：算法简单直观，易于理解和实现；能遍历图中所有节点，不会遗漏任何可能序列局限性：可能陷入死循环（如图中存在环），需要状态检查和去重；找到的路径可能较长1广度优先搜索（BFS）基本思想：从根节点（起始节点）开始，逐层向下搜索，直到找到目标或遍历整个图。优点：能找到最少边数的路径（对无权图）局限性：空间复杂度高；时间复杂度高；不适用加权图（应使用Dijkstra或A*算法）2Dijkstra算法核心思想：通过逐步逼近方式，确定起点到各顶点的最短路径，基于贪心策略。示例流程（从节点A出发）步骤一：初始V₁={A}，交界边AB=4,AC=2，选AC=2，更新V₁={A,C}步骤二：检查AC+BC=3<AB=4（更优），更新V₁={A,C,B}步骤三：选CD=1，检查AC+CD=3<AC+BC+BD=7（更优），更新V₁={A,C,B,D}步骤四：选DE=3，检查AC+CD+DE=6<AC+CE=9（更优），更新V₁={A,C,B,D,E}结果：从A到E的最短路径为AC→CD→DE🔑Dijkstra特点贪心策略保证找到最优解适用于有权图（权值非负）时间复杂度：O(|V|²)或O((|V|+|E|)log|V|)（使用堆）6.2.2启发式搜索算法启发式搜索算法利用启发信息指导搜索方向，相比精确算法更高效。1.遗传算法（GA）基本原理：模拟生物进化过程，通过自然选择、遗传、交叉（配对）和变异等操作优化问题解。基本流程（8步）：编码→初始化种群→适应度函数（路径越短/避障越强/运动越平滑→适应度越高）→选择→交叉→变异→迭代→终止条件优点：能处理复杂的非线性问题；全局搜索能力强；易于与其他优化方法结合⚠️

易错：性能受种群大小、交叉概率、变异概率等参数影响；编码方式的选择也很重要2.蚁群算法（ACO）基本原理：模拟蚂蚁觅食行为，利用信息素的正反馈机制寻找最优解。基本流程（5步）：环境抽象建模→初始化参数（蚂蚁数量、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子）→路径选择→信息素更新（挥发+增强）→迭代寻找最优解优点：分布式优化方法；全局优化，不容易陷入局部最优；通用性强；搜索效率高局限：收敛速度较慢；易受初始解影响；参数调节困难3.模拟退火算法（SA）基本原理：模拟将固体加热至充分高温再徐徐冷却的退火过程，概率性地跳出局部最优解，求解全局优化问题。基本流程（6步）：初始化参数（初始温度T、起始解S、迭代次数L）→产生新解S'→计算能量差ΔE=f(S')-f(S)→接受新解（ΔE<0无条件接受；ΔE≥0按概率exp(-ΔE/T)接受）→温度更新（指数/线性降温）→终止判断优点：全局优化能力强；已广泛应用于机器学习、数据挖掘、图像处理、组合优化等局限：计算量大，耗时长；收敛速度较慢6.2.3机器学习方法1.监督学习监督学习利用已标注的数据集训练模型，学习特征与标签的映射关系。1）线性回归用于预测连续值，假设输入特征与输出存在线性关系。一元线性回归（公式6-9）：y=wx+b多元线性回归（公式6-10）：y=w_1x_1+w_2x_2+\dots+w_nx_n+b求解方法：寻找最佳回归系数，最小化残差平方和；对大规模数据集使用梯度下降法。2）逻辑回归分类学习算法，主要用于二分类问题，预测事件发生概率。使用Sigmoid函数作假设函数（公式6-12）：损失函数：交叉熵损失函数；参数优化：梯度下降法。3）支持向量机（SVM）通过找到超平面最大化分类间隔，将数据分为两类。支持向量：离超平面最近的样本点。线性不可分情况引入核函数（线性核、多项式核、高斯核）映射到高维特征空间。4）神经网络受生物神经系统启发，用神经元模型组成的复杂网络解决分类、回归等问题。神经元处理步骤：加权输入→激活函数（Sigmoid/ReLU/Tanh）→输出传递网络训练：前向传播→误差计算（MSE/交叉熵损失）→反向传播（链式法则，梯度下降/Adam优化器）常见网络类型：MLP（基础前馈网络）、CNN（图像处理）、RNN（序列数据）2.深度强化学习深度强化学习结合了深度学习的表征能力和强化学习的决策能力，使机器人能在复杂、动态、非结构化环境中进行有效的任务序列规划。四元组建模：{S,A,P,R}——状态集、动作集、状态转移概率、奖励函数奖励函数设计示例：成功完成任务→正奖励（激励）；前置任务未完成导致无法执行→负奖励（惩罚）1）任务分解与序列规划将复杂任务分解为简单子任务，为每个子任务规划最优执行序列。学习子任务间的依赖关系和转换条件。动作空间：任务集作为可选动作；观测空间：根据实际需求（如图像、坐标等）。2）策略学习与优化主流算法：深度Q网络（DQN）、策略梯度方法。优化目标：学习在不同状态下选择最优动作的策略，通过不断交互和试错，逐渐优化策略，最大化长期累积奖励，逼近全局最优任务序列。6.3多智能机器人任务规划应用实例——农业机器人自主作业本部分通过农业机器人自主作业的实例，展示VRP在实际应用中的解决方案。问题背景农业是国家重要产业，面临耕地减少、农业人口老龄化，亟需提高效率、降低成本核心挑战多台农机从机库出发，完成所有作业行的作业并返回机库，每条作业行需被作业且仅作业一次解决方案有序多变异遗传算法+基于深度强化学习的JPDSNN端到端任务规划方法6.3.1农机任务规划问题建模与评价指标计算典型农场环境（图6-11）绿色多边形：多块待作业地块五角星：机库（出发和返回点）粗实线：农场道路；细实线：地块内可通行道路；虚线：待作业行问题建模各作业行作为任务节点，构成任务图G。节点集：N={nᵢ|i=0,1,…,L}，其中n₀为机库，n₁~nL为任务节点（作业行）。任务节点特征（三维）：nᵢ=[sinθᵢ,cosθᵢ,lᵢ]（θᵢ：作业行与正东方向夹角；lᵢ：作业行长度）边特征（四维）：dᵢⱼ=[d*ᵢⱼ₀₀,d*ᵢⱼ₀₁,d*ᵢⱼ₁₀,d*ᵢⱼ₁₁]（任意两节点间4个距离维度）农机参数：第k台农机mₖ=[v^w_k,v^f_k,c^w_k,c^f_k]（作业速度、空行速度、作业油耗、空行油耗）评价指标第k台农机的空行路程（公式6-13）第k台农机的作业路程（公式6-14）第k台农机的总运行时间（公式6-15）第k台农机的总运行油耗（公式6-16）优化目标（共M台农机）运行路程：sₚ=∑sₖ（最小化）运行时间：tₚ=maxtₖ（最小化总耗时）运行油耗：cₚ=∑c^o_k（最小化）6.3.2基于有序多变异遗传算法的任务规划选用原因遗传算法通过模拟自然进化过程（交叉、变异、优胜劣汰）进行最优搜索，是常用的元启发式搜索算法。染色体编码（两部分）所有任务节点的排列T一组分段点，将T分为M段，分别代表M台农机的作业序列排列T中每个元素为元组：Tᵢ=[Pᵢ,eᵢ]（Pᵢ：作业行编号；eᵢ：该作业行的入口点）适应度函数对运行路程：fitness=1/sₚ对运行时间：fitness=1/tₚ对运行油耗：fitness=1/cₚ测试样例农场分别含1个和4个地块，4台农机参数如下：农机作业速度(m/s)空行速度(m/s)作业油耗(L/s)空行油耗(L/s)农机12.54.50.0080.006农机2350.0070.005农机335.50.0080.006农机4360.010.008🔑三个基本操作1选择算子在种群中按适应度强弱使用轮盘赌法，根据个体适应度强弱从种群中采样亲代。2交叉算子以某种方式交换两个优秀亲代编码中的部分，形成新的子代编码，扩大搜索空间。3变异算子（6种具体操作）局部倒置：将序列T的某段顺序倒置组间交换：交换两台农机任务序列中的某两个任务组间转移：将某台农机的任务转移到另一台入口点变换：随机选择1台农机，将其任务序列中所有节点入口点取反组内排序：对同一地块内的任务排序，将入口点设为始末交替贪婪路径：（具体内容见图示）优化结果分析（图6-13）01以路程为目标算法让一台农机完成几乎全部作业，地块边界和农场道路上路程较少02以时间为目标所有4台农机均参与工作，快速农机被分配更多任务，平均分配减少闲置03以油耗为目标油耗最低的农机2完成几乎全部作业6.3.3基于深度强化学习的任务规划算法研究目标探索高效的端到端任务规划方法。网络架构：使用联合概率分布采样神经网络（JPDSNN）。方法框架将农业机器人任务规划的决策过程建模成MDP用基于编码器-解码器结构的神经网络实现MDP网络成分输入编码器：处理任务图和机器特征，提取高维特征已生成序列编码器：处理由已生成动作产生的特征解码器：包括动作网络和评论家网络动作网络：根据当前状态选择动作a=P_{A,t}（指定下一节点及其入口）核心技术（图6-15展示）图注意力机制网络（GraphTransformer）GRU网络创新的基于联合概率分布采样的动作网络（基于指针网络），用于决定下一个任务节点及其入口点训练过程使用强化学习中的经典算法PPO