《工业大数据与人工智能》 课件 第六章-6.3 路径规划问题

工业大数据与人工智能HFUT12第六章

工业中的智能优化方法

路径规划问题的分类6.3路径规划问题路径规划的一般步骤常用的路径规划算法路径规划不同应用场景遗传算法在机器人路径规划中的应用3路径规划问题路径规划技术广泛应用于工业领域，构成了生产线自动化与智能化建设的基石。诸如机器人独立无碰撞行走、无人机避开障碍物执行高难度飞行任务、巡航导弹在复杂环境中巧妙规避雷达探测、实施突破式打击等，均依赖于精密的路径规划。。4路径规划问题的分类根据对环境认知的详尽程度，路径规划可分为两个类别：（1）基于完整预知信息的全局路径规划（2）依赖实时传感信息的局部路径规划。从障碍物信息获取方式来看，全局路径规划通常属于静态规划范畴，相反，局部路径规划则归属动态规划领域，通常被称为在线规划。5路径规划问题的分类根据环境信息的特性，路径规划可划分为（1）离散空间路径规划问题离散空间路径规划问题主要涉及在已知、简化的一维环境中进行静态优化，相当于是对环境信息高度抽象后的路径优化问题。（2）连续空间路径规划问题。连续空间路径规划问题则涉及到在多维连续变化环境中的动态规划，它要求在连续变化的空间中实时规划并调整路径，以应对复杂且实时变化的环境条件。6路径规划的一般步骤在连续环境空间内的路径规划问题，如机器人和飞行器等的动态路径规划，其典型处理流程通常由三个关键步骤构成：环境模型构建、路径探索和路径优化平滑。7路径规划的一般步骤（1）环境建模：这是路径规划过程的基石，旨在建立一个能够被计算机算法有效解析和操作的环境模型，即将复杂的实际物理空间转化成算法可处理的抽象空间结构，实现两者之间的合理映射。（2）路径搜索：在此阶段，基于已经建立的环境模型，采用适宜的算法探寻一条连接起始点和目标点的路径，以期在满足预设性能指标的前提下，找到全局或局部最优路径。8路径规划的一般步骤（3）路径平滑：初步搜索得出的路径可能并非运动实体能够实际通行的平滑路径，因此需要进一步运用相关算法对其进行细化处理和优化平滑，确保最终生成的路径切实可行且满足运动体的实际行驶需求。9常用的路径规划算法路径规划算法多样，依据不同算法的特点和局限性，其适用场景有所差异。根据算法的历史发展脉络及其核心工作原理，将它们概括地划分为四个主要类别：传统算法、图形学方法、智能算法以及其他算高效算法。10路径规划不同应用场景离散域路径规划：离散域路径规划主要聚焦于那些能够被简化的环境，其中空间被划分成有限数量的不连续状态或节点。在此框架下，路径被视为一系列离散节点间的转移过程，每一步转移代表一种可能的状态变换。仓储物流，网格化游戏地形导航，网络通信路由场景都会用到离散域路径规划。11路径规划不同应用场景连续域路径规划：与之相对，连续域路径规划则关注于环境状态可连续变化的情况，处理对象是无界、无缝隙的物理空间。此类路径规划不仅要求精确的数学模型支撑，还需运用高级优化算法，在无限可能性中筛选出最优解。自动驾驶，无人机航迹规划，机器人臂运动规划场景都会用到连续域路径规划。12遗传算法在机器人路径规划中的应用在机器人路径规划领域，核心挑战聚焦于两个关键方面：（1）选取合适的环境模型，（2）确定高效的路径规划算法。环境模型的选项繁多，其中包括但不限于栅格地图、几何地图和拓扑图等。其中，栅格地图因其实现的直观性、构造的便捷性而被广为采纳。13遗传算法在机器人路径规划中的应用环境建模：栅格地图通过栅格的占有率来表示环境中的障碍物，通过“0”和“1”的数字矩阵区分无障碍空间与障碍区域，其中“0”代表可通过区域，“1”则代表障碍物所在。下图展示了这一概念，图中中的栅格地图矩阵可表达为[[0,0,0],[0,1,1],[0,1,0]]。14遗传算法在机器人路径规划中的应用障碍物处理：鉴于障碍物形态的不规则特性，为了模型的简易性和实用性，将涉及障碍的所有相邻栅格均标记为不可通行区域，使得栅格地图模型贴近真实场景。下左图为障碍物的膨胀化处理，右图为栅格的填充处理。15遗传算法在机器人路径规划中的应用栅格地图信息编码：直角坐标法在平面中，以以栅格地图的左下角落为坐标系的原点，定义水平方向为X轴，垂直向上为Y轴，从而建立起一个直角坐标系统。以图下图为例，展示的是一个10行10列的栅格地图，采用直角坐标表示法，其中某一点A的具体坐标为（4.5，1.5）16遗传算法在机器人路径规划中的应用遗传算法路径规划方法设计：个体编码方式选择了路径点的栅格序号编码方式。在这种编码方式下，机器人从起始栅格出发，穿越一系列连贯的可行路径点，直至抵达目标栅格，整个路径构成了遗传学概念中的染色体，其中每个路径点如同染色体上的基因单元。以下图为例：用序号法可表示为1-2-3-4-5-15-25-35-45-55-66-77-88-89-90-100。17遗传算法在机器人路径规划中的应用种群初始化：使用中点法产生初始路径的具体步骤如下：Step1：首先，在起点S和终点E之间绘制一条直线段。Step2：接着，找到直线段SE的中点栅格M。若M点位于障碍物栅格上，则随机选择M点附近的非障碍物栅格点M'，并将M'取代M。若M点是自由栅格点，则无需做任何处理。18遗传算法在机器人路径规划中的应用种群初始化：使用中点法产生初始路径的具体步骤如下：Step3：然后，将线段SM（或SM’）视为起点到终点的路径段。接着，将M（或M’）点作为新的起点S，E点保持不变；或者将M（或M’）点作为新的终点E，S点保持不变。Step4：重复执行Step1至Step3，直到所有生成的路径段都是连续的路径段。Step5：最后，将从起点S到终点E的每一条路径经过的栅格编号连接起来，形成一条初始路径。通过这样的方式，生成与种群数量N相等的路径群体。19遗传算法在机器人路径规划中的应用使用中点法生成初始路径如下：20遗传算法在机器人路径规划中的应用适应度函数确立：在机器人路径规划中，核心优化目标通常是确定最短的可行路径。现在生成的所有初始路径均满足可行性条件，故无需额外添加惩罚项来规避不可行解。适应度函数如下：21遗传算法在机器人路径规划中的应用1.选择算子：采用了传统遗传算法常用的比例法，也称为轮盘赌法。2：交叉算子：具体操作步骤如下：(1）在种群中随机选择两个个体。（2）如果这两个个体中存在一个或多个相同的栅格点，则随机选择其中一个相同的栅格点作为交叉点。（3）如果两个个体没有相同的栅格点，则放弃本次交叉，重新选择两个个体进行交叉。22遗传算法在机器人路径规划中的应用遗传算子：3.变异算子：具体步骤概括为：（1）从现有路径中随机抽取一条作为变异对象；（2）在这条路径中随机挑选两个节点，移除这两节点间的全部路径片段；（3）直接连接这两个节点，形成新的直线段；（4）检验新形成的线段是否穿越障碍区域，若发生碰撞，则进入（5）；否则依次进入(1)-(4)；(5)：应用中点法填补这两个节点间的空白路径段，完成变异步骤。23遗传算法在机器人路径规划中的应用遗传算子：4.修复算子：尽管交叉和变异操作可以增加种群的多样性，但可能会导致生成的路径包含冗余路径段。为了确保获得最优