基于人工智能的机器人路径规划算法优化

路径规划算法及其应用综述

路径规划算法是人工智能领域中的重要分支，广泛应用于机器人导航、无人驾驶、图像处理、自然语言处理等领域。本文将综述路径规划算法的发展历程、种类、特点及其在不同领域的应用情况，并探讨未来的研究趋势和应用前景。关键词：路径规划算法，最优化算法，无模型算法，数据挖掘算法，应用领域，未来展望。

路径规划算法旨在为机器人或无人系统找到从起始点到目标点的最优路径。随着人工智能技术的不断发展，路径规划算法在各个领域的应用也越来越广泛。本文将介绍最优化算法、无模型算法和数据挖掘算法等路径规划算法的种类和特点，并探讨它们在不同领域的应用情况，同时展望未来的研究趋势和应用前景。

路径规划算法可以大致分为最优化算法、无模型算法和数据挖掘算法。最优化算法包括Dijkstra算法、A*算法、Bellman-Ford算法等，它们通过构建优化图和求解最优路径来寻找最短或最优路径。无模型算法则以行为启发式为基础，如蚁群算法、粒子群算法等，通过模拟自然界中的某些现象来寻找最优路径。数据挖掘算法则从大量数据中提取有用的信息来指导路径规划，如k-最近邻算法等。

最优化算法在路径规划中应用较为广泛，其中Dijkstra算法和A算法是最常用的两种。Dijkstra算法通过不断地扩展起始节点，直到找到目标节点为止，能够求解出最短路径。A算法则通过评估函数来对每个节点进行评估，从而找到最优路径。无模型算法则在求解复杂环境和未知环境下的路径规划问题中具有较大优势，例如蚁群算法可以通过模拟蚂蚁寻找食物的过程来求解最短路径问题。数据挖掘算法则可以通过对大量数据的挖掘来指导路径规划，例如k-最近邻算法可以根据已知的k个最近邻节点的信息来指导路径规划。

路径规划算法在各个领域都有广泛的应用。在机器人领域中，路径规划算法可用于机器人的自主导航和避障，例如在家庭服务机器人中，通过路径规划算法可以实现从客厅到餐厅的最短路径规划。在无人驾驶领域中，路径规划算法可用于实现自动驾驶车辆的导航和避障，从而保证车辆的安全行驶。在图像处理领域中，路径规划算法可用于图像分割、目标跟踪等任务，例如利用蚁群算法进行图像分割可以取得良好的分割效果。在自然语言处理领域中，路径规划算法可用于文本分类、情感分析等任务，例如利用朴素贝叶斯分类器可以对文本进行分类。

收稿日期：２０１９⁃１０⁃１５；修回日期：２０２０⁃０３⁃０２ 基金项目：国家重点研发计划资助项目（２０１８ＹＦＦ０２１４７０４）作者简介：赵明（１９９６⁃），女，山东青岛人，硕士研究生，主要研究方向为机器学习、深度学习、计算机视觉、多智能体、路径规划；郑泽宇（１９７６⁃），男，四川成都人，研究员，博士，主要研究方向为数据挖掘、复杂系统、时序列分析、风险预测；么庆丰（１９９５⁃），男，辽宁鞍山人，硕士研究生，主要研究方向为强化学习、多智能体、路径规划（ｙａｏｑｉｎｇｆｅｎｇ＠ｓｉａ．ｃｎ）；潘怡君（１９９２⁃），女，辽宁沈阳人，助理研究员，博士，主要研究方向为数据分析、机器学习、鲁棒主元分析；刘智（１９９４⁃），男，辽宁阜新人，博士研究生，主要研究方向为机器学习、深度学习、自然语言处理、自然语言理解、智能医疗、计算机视觉．基于改进人工势场法的移动机器人路径规划方法∗

赵　明１，２，３，郑泽宇１，２，３，么庆丰１，２，３，潘怡君１，２，刘　智１，２，３（１．中国科学院沈阳自动化研究所，沈阳１１００１６；２．中国科学院机器人与智能制造创新研究院，沈阳１１０１６９；３．中国科学院大学，北京１０００４９）摘　要：人工势场法是机器人局部路径规划常用算法，但是人工势场法中机器人会陷入局部稳定点的状况，基于此提出了域—人工势场法解决多目标点任务中局部稳定点问题。首先加入小范围强作用力的域势场，帮助机器人在陷入局部稳定点时通过域场逃离局部稳定点；其次为了域场范围难以确定的问题，进一步提出根据地图情况自动调整域场的大小的自适应域—人工势场法，解决不同地图情况局部稳定点的问题；最后加入域引导势场，对启发点进行域势场传递，解决复杂障碍下的局部稳定点问题。实验证明自适应域—人工势场法和域引导势场在解决多目标点和复杂障碍物局部稳定点问题的作用。关键词：路径规划；人工势场；人工智能；自适应０　引言随着机器人和人工智能理论的不断发展，自主式移动机器人技术日益成熟［１］，现已在工业、军事、医疗、服务等诸多领域得到广泛应用。与此同时，机器人所面临的任务也愈加复杂，所处环境由原来的单一机器人、静态环境转变为多机器人、动态环境。因此，近年来对复杂系统中机器人自主智能控制技术的研究得到了学术界和工业界的广泛关注，而路径规划及导航作为其中的关键性技术成为了目前机器人学的研究热点之一［２，３］。在复杂情况中的路径规划中需要多机器人协作，因为单个机器人无法完成某些需要协作的任务，必须依靠多个机器人才能完成。例如机器人搬运重物，对该类任务也许可以通过设计一个能力特强的机器人来完成，但从设计的复杂性和成本等方面考虑，这样的方案不如设计成多个功能简单的机器人来执行。并且对于可以分解的任务来说，多机器人可并行地完成不同的子任务，这比单个机器人完成所有的子任务所花时间少。这种情况下使用多机器人可提高工作效率，如多位置区域建图、固定区域探雷等均属于此类任务［４］。路径规划分类基于部分区域信息的局部路径规划和基于完整区域信息的全局路径规划，多机器人任务中需要较高灵活性和实时性，需要更多依靠局部路径规划，如人工势场法［５］、启发式Ａ∗算法［６］、模拟退火算法［７］、粒子群算法［８］等都是常见的局部路径规划算法。这些传统方法在单机器人中具有良好效果，但是在障碍物和机器人数量增多、多机器人需要协作合作的情况下难以保持算法的有效性，近年来引起国内外学者的广泛兴趣。Ｓｃｈｗａｇｅｒ等人［９］提出一种多机器人在具有大量未知信息的环境中的行为控制方法，使用贝叶斯过滤器帮助机器人进行在线控制。Ｚｈａｏ等人［４］提出使用模糊逻辑控制处理动态变化的环境，使用两种模糊控制器进行控制，一种用于避障，另一种用于目标定位。但是这些方法没有人工势场法结构简单、实用性强、路径平滑的优点。近年来有很多基于人工势场法改进的方法。胡小平等人［１０］加入了一个全局防止拥堵的防堵势场和防止碰撞的社群势场来平衡机器人移动与避障。张立阳等人［１１］提出结合模糊控制与人工势场法对斥力系数和引力系数根据环境调整来轨迹跟踪。仇国庆等人［１２］将多机器人与遗传算法结合，利用最优基因来调整机器人内在参数，并加入领航跟随法，保证队形的稳定性。本文对人工势场进行修改，加入了自适应的域势场，帮助机器人根据域势场快速到达目标点，避免陷入叠加势场带来的局部稳定点，改进后的算法能够提高机器人工作效率，避免停滞在环境中，最后使用域势场的域信息作为交流信号，加强多机器人的协作能力，提高路径规划的效率。１　人工势场法１􀆰１　人工势场法基本理论传统人工势场由两种势场叠加而成，将环境中的物体看做虚拟力场中的质点，目标点对机器人提供引力，形成引力势场；障碍物则提供斥力，形成斥力势场。障碍物处的势能较高，而目标点处的势能较低，在势场合力的驱动下，机器人沿着势函数从势能高的地方向势能低的方向运动，最终找到了一条可以到达目标点的无碰路径。目标点的作用吸引力覆盖整个地图，使机器人从地图的任意位置均可以感受到该目标点的作用力，而障碍物只对一定距离内的机器人产生排斥力，这是因为只有在距离障碍物很近时才需要进行障碍物的躲避。传统人工势场的引力势场函数为Ｕａｔｔ（ｑ）＝ｋａｔｔ×（ｑ－ｑｇ）２２（１）其中：Ｕａｔｔ（ｑ）为目标点在位置ｑ产生的引力场；ｋａｔｔ为目标点的引力系数，引力系数越大说明目标点具有更强的吸引力；ｑ为位置坐标；目标点所在坐标为ｑｇ，所以ｑｇ处势场为０，距离ｑｇ越远的地方具有更大的势场。引力由引力势场的负梯度计算可得Ｆａｔｔ（ｑ）＝－▽Ｕａｔｔ（ｑ）＝－ｋａｔｔ｜ｑ－ｑｇ｜（２）类似地，斥力势场函数为Ｕｒｅｐ（ｑ）＝１２ｋｒｅｐ１ｑ－ｑ０－１ｐ０æèçöø÷２ｑ－ｑ０≤ｐ００ｑ－ｑ０＞ｐ０ìîíïïïï（３）其中：Ｕｒｅｐ（ｑ）为障碍物在位置ｑ产生的斥力场；ｋｒｅｐ为障碍物的斥力系数，斥力系数越大说明障碍物周围具有更强的排斥力；ｑ－ｑ０为当前坐标与障碍物距离；障碍物的斥力场范围大小为ｐ０，超过该范围则机器人感受不到该障碍物的排斥力。使用斥力势场计算斥力：Ｆｒｅｐ（ｑ）＝－▽Ｕｒｅｐ（ｑ）＝１ｑ－ｑ０－１ｐ０æèçöø÷ｋｒｅｐ（ｑ－ｑ０）∂（ｑ－ｑ０）∂ｑ　ｑ－ｑ０≤ｐ００ｑ－ｑ０＞ｐ０ìîíïïïï（４）所以位置ｑ受到障碍物和目标点的势场的叠加，所受合力为Ｆｑ＝∑ｎｉ＝１Ｆａｔｔ（ｉ）＋∑ｍｊ＝１Ｆｒｅｐ（ｊ）（５）需要注意势场函数只受到障碍物和目标的叠加影响，而与机器人本身或者其他机器人无关，所以机器人仅仅通过当前位置的势场无法了解到其他机器人的情况。１􀆰２　环境地图的建立目前多机器人学习的路径规划技术尚处于理论研究阶段，大部分的研究成果都是基于栅格化地图的仿真实验。其主要原因有两点：ａ）目前多机器人路径规划算法鲁棒性和拓展性较差，不适用于实际系统；ｂ）栅格化地图实验能很好地反映算法效果，同时栅格法具有简单有效、易于实现等特点。机器人可以选择移动的方向如图１所示有上、下、左、右、左上、右上、右下、左下、原地不动等方向。栅格法将机器人工作环境用一系列相同大小的栅格进行表示，每个栅格具有两种状态，即占据状态和空闲状态。空闲状态为机器人可以移动和通过的区域，占据状态为机器人不能通过的区域。根据栅格法建立５０×５０的地图如图２所示。目标点和障碍物位置随机生成，目标点数量与机器人保持一致。图２中黑点（２１，２８）为目标点所在位置，２×２的灰色方块为障·６６·计算机应用研究２０２０年　碍物，障碍物与目标点不会重叠。基于人工势场下的地图热力如图３所示。图中越亮的地方代表势场越低，越暗的地方代表势场越高。所以障碍物和边界颜色很深，而目标点（２１，２８）旁边颜色最浅。

基于小生境遗传算法的移动机器人路径优化

基于小生境遗传算法的移动机器人路径优化

类别：传感与控制

0 引 言 移动机器人路径规划是机器人学的一个重要研究领域，也是人工智能与机器人学的一个结合点。不论是哪种类别的移动机器人，都要求根据某一准则(如行走路线总长度最短，能量消耗最少等)，在工作空间中沿一条最优(或次优)的路径行走。 路径规划的典型方法有图搜索法、栅格法、人工势场法等，这些算法都有一定局限性，易陷入局部最优解，而遗传算法在解决非线性问题上具有良好的适用性，已成为路径规划中使用较多的一种方法。但是标准的遗传算法本身也存在着早熟，易陷入局部最优解等缺陷，不能保证对路径规划上计算效率和可靠性的要求。为了提高路径规划的求解质量和求解效率，提出一种基于预选择机制小生境技术的改进遗传算法，并将其应用于移动机器人的路径规划，采用化复杂的二维坐标为一维坐标的编码方式，有效降低了遗传算法的搜索空间；根据移动机器人的行走特点，设计了自适应交叉算子、自适应变异算子、插入算子、删除算子、扰动算子和倒位算子。通过计算机仿真证明了改进后的遗传算法明显提高了搜索效率和收敛速度，并能保证收敛到全局最优解，克服了标准遗传算法的缺点，为机器人快速寻求一条无碰的最优路径。 1 基于遗传算法的机器人路径规划算法的改进与应用 本文的移动机器人路径规划，目标是在一幅已知障碍物分布的二维地图上寻找一条最优路径，使其到达目标点的距离最短，同时尽可能地使其与障碍物的距离最大化。为了简化讨论，将移动机器考虑为一个质点，而障碍物的边界向外扩张，这是移动机器人的最大安全距离。 1.1 基于预选择机制技术的小生境遗传算法机理 由于简单遗传算法是一种随机的方法，旨在对多个不同的个体进行隐并行寻优，其运行过程和实现方法在本质上仍是串行的，这样的进化运算过程相对缓慢；同时，基本遗传算法常在各个个体未达到最优解之前就收敛于一个局部最优点，从而导致染色体趋于一致，即产生“早熟”现象。为了克服这些不足，引入了小生境遗传机理，用基于预选择机制技术的小生境方法维持群体的多样性，避免群体内个别个体的大量增加，实现解空间内对局部最优解和全局最优解的寻优。 小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间，通过杂交、变异产生新一代个体群，同时采用预选择机制完成选择操作。基于这种小生境技术的遗传算法，可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度。 在预选择机制中，只有在子串的适应度超过其父串的情况下，子串才能替换其父串，进入下一代群体。这种方式趋向于替换与其本身相似的个体(父与子之间的性状遗传)，因而能够较好地维持群体的分布特性，即使在群体规模相对较小的情况下，仍可维持较高的群体分布特性。具体算法的实现步骤如下： (1)初始化(建立初始群体，确定遗传参数)； (2)计算个体的适应度； (3)遗传操作(选择、交叉、变异)； (4)比较子串和父串的适应度大小，如果子串的适应度高于父串的适应度，就替换父串；否则维持父串不变； (5)如果没有满足算法的终止条件，则返回第(2)步；否则，算法终止。 1.2

基于模糊逻辑的机器人路径规划优化

机器人技术已经成为现实，人们越来越关注机器人的交互，路径规划优化成为必须重要的一环。而基于模糊逻辑的机器人路径规划技术成为机器人路径规划的焦点。这种路径规划的方法更加灵活，对于一些复杂情况更加得心应手。

机器人路径规划，是指机器人根据在不同环境下的需求规划出一条最优的路径，达到目的地。路径规划的方法有多种，而基于模糊逻辑的路径规划方法就是其中最为重要的一种。它可以使机器人在充分考虑环境与约束力量情况下，生成最短路径。

模糊逻辑是一种广泛应用于人工智能方向的方法，它是一种近似理论，可以用来模拟自然中存在的模糊不确定性信息。在机器人路径规划的过程中，模糊逻辑能够为其提供决策依据，使机器人根据环境中包含的不确定性信息进行路径规划，并且考虑到这些信息中可能存在的“模糊”性质。

基于模糊逻辑的机器人路径规划方法有以下几个主要步骤：

一、建立模糊逻辑模型。首先，将机器人路径规划问题转化为基于模糊逻辑的问题，将机器人行动状态、可行性、可达性、手工干预程度等转化为模糊的语言描述。

二、构建模糊控制规则库。将经验控制规则转化为模糊控制规则，将模糊控制规则库存储到系统中。 三、输入模糊判断量，并运行模糊逻辑推理规则。输入机器人路径规划的关键信息，经过模糊逻辑推理，自动计算出机器人应该去的方向和路线。

四、生成机器人路径方案。根据输出模糊量即可得到精度更高的路径规划，使机器人能够自动避障，转移，周旋于不同的障碍物，达到更好的路径规划效果。

基于模糊逻辑的路径规划，能够对机器人的策略进行软件仿真，通过模拟在不同环境中的不同行为规律，提高机器人的路径规划，遵循某一条优化的路径，让机器人实现以最短路径为目标实现各种任务。同时，将基于模糊逻辑的路径规划与使用遗传算法甚至更高级的决策搜索算法相结合，能更好地解决路径规划中的问题。

模糊逻辑在路径规划方面的优势在于其一定的鲁棒性和健壮性，对于复杂的环境来说，其优越性更加显著。它与其他路径规划方式，如光线跟踪，随机没有最优路线的局限性。因此，机器人在极端难以预测的情况下，仍然可以获得有效的路径规划，同时也能够不需要连续的精细的路径更新，降低机器人运行的复杂度和能耗。