机器人感知与智能 课件 第七章 决策技术

机器人感知与智能第七章决策技术概述

OUTLINE决策技术使机器人在无需人类干预下，能基于算法和数据自主制定最优方案。它通过评估不同决策的潜在收益（如最大化效益、最小化成本），选择最佳路径。与人类不同，机器人的决策完全基于逻辑、一致性和可重复性，这是其智能化的重要标志。该技术应用广泛，从家用扫地机器人到工业制造和物流配送机器人。本章将重点介绍四种算法：有限状态机、决策树、马尔科夫决策过程和旅行商问题，并通过物流机器人案例和实验来展示其效果。目录

CATALOGUE01决策技术原理02应用举例03实验01决策技术原理有限状态机(FSM)

有限状态机系统有限状态机(FSM)基于系统输出，有限状态机主要可以被分为两种子类：摩尔型有限状态机（MooreMachine）和米利型有限状态机（MealyMachine）。若输出只和状态有关而与输入无关，则称为摩尔型状态机；若输出不仅和状态有关而且和输入有关系，则称为米利型状态机。如图所示，分别表示摩尔型有限状态机和米利型有限状态机的系统接收0和1的数据流，并在接收到输入序列011时输出1。应用于复杂场景时，存在以下问题，（1）需要人工设计大量状态和逻辑，容易遗漏；（2）输入集合可能无法涵盖所有现实情况，扩展性差；（3）可能因缺乏有效的死锁保护，导致机器人陷入死锁状态。摩尔型有限状态机系统米利型有限状态机系统决策树算法决策树算法是一种监督学习算法，通过根据输入特征的值将数据逐步分割为子集，生成树状决策模型。模型由根结点、内部节点（特征/属性）和叶节点（类别）组成，可解释性强。常见的决策树算法按照划分依据可以分为以下三种：ID3决策树，C4.5决策树和CART决策树。ID3决策树基于信息熵和信息增益划分属性。C4.5算法则是在ID3算法的基础上进行了改进和优化，它主要使用信息增益率来进行数据划分。CART算法主要使用基尼系数进行分类和回归。决策树结构决策树算法

决策树算法该算法的伪代码如表所示。算法缺陷：（1）过拟合:容易生成过于复杂的树结构，导致在未见过的数据上表现不佳；（2）不稳定性:小的数据变动可能导致生成完全不同的树结构；（3）局部最优:贪婪算法每次选择当前最佳分裂点，可能导致最终结果陷入局部最优而非全局最优；（4）特征关联弱:无法直接有效捕捉多个特征之间的复杂关系。解决方案：（1）过拟合:采用剪枝操作，限制树的深度或节点数；（2）不稳定性:引入随机性，例如随机选择分裂特征或样本子集；（3）局部最优:构建多棵决策树（如随机森林）；（4）特征问题:进行特征工程，如特征选择、提取和变换，或对原始数据进行预处理。决策树构建伪代码马尔科夫决策过程

马尔科夫决策过程

马尔科夫决策过程初始化第一次迭代

马尔科夫决策过程初始化第一次迭代

马尔科夫决策过程第一次迭代第二次迭代

马尔科夫决策过程继续执行迭代，直到结果收敛，如图7-7所示，为迭代133次后收敛的结果。第133次迭代马尔科夫决策过程

马尔科夫决策过程策略迭代计算示例：依旧考虑与值迭代示例相同的规则设置，首先随机初始化动作，如图所示。之后与值迭代步骤相同，计算每个格子的值函数，直至收敛，如图所示，为迭代111次后收敛的结果。之后根据公式进行策略更新，更新后的策略如图所示。循环策略评估和策略更新，直至最终收敛，如图所示。策略随机初始化策略评估策略更新最终策略旅行商问题旅行商问题是著名的组合优化NP难问题。问题是：旅行商从任意城市出发，拜访n个城市各一次并最终返回，目标是找到总路径长度最短的回路。其三个基本特点是：对称性、完全性和回路性。除了基本旅行商问题外，很多类似问题也可纳入旅行商问题的范畴，并可以根据其不同的特点和约束进行分类。以下是一些常见的分类：（1）非对称旅行商问题、（2）多旅行商问题、（3）车辆路径问题、（4）时间相关旅行商问题、（5）多目标旅行商问题。目前，求解旅行商问题的方法主要分为两类：传统方法和启发式方法。传统方法包括

线性规划（切割平面法）和分支边界算法。启发式方法:例如r-opt算法（如2-opt,3-opt）、蚁群算法、遗传算法、粒子群算法等。启发式算法可在较短时间内得到次优解。基本旅行商问题02应用举例：物流机器人配送方案应用举例：物流机器人配送方案配送路线优化仓库布局优化物流机器人的配送效率很大程度上取决于其选择的路线，因此需要使用合适的决策算法计算得到一条经过所有配送位置的配送路线，从而提高配送效率，降低物流成本。仓库布局对于物流企业的运营效率有很大的影响，因此需要进行布局优化。算法优化可以通过对仓库内部物品的存储位置进行优化，来达到最优的仓库布局。智能调度系统物流机器人装载优化物流企业需要进行运输调度，根据不同的订单和货物情况来确定物流机器人和人员的调度方案。算法优化可以用于智能调度系统中，通过对运输需求进行预测和规划，来实现最优的运