基于FPGA的六自由度智能移动机器人设计毕业论文 - 图文

毕业论文

基于FPGA的六自由度智能移动机器人设计

摘要：智能移动机器人是指无需人工干预，可以自主完成行驶任务的车辆。路径规划是移动机器人的一个重要组成部分，它的任务就是在具有障碍物的环境内，按照一定的评价标准，寻找一条从起始状态到达目标状态的无碰路径。遗传算法就是对自然界中生物的遗传特性进行模拟而得出的一种模拟进化算法，它是继模糊方法、神经网络、蚁群之后新加入路径规划研究领域的一种算法。提出了一种基于遗传算法解决移动机器人路径规划问题的方法。通过本文的研究及实验结果证明，将遗传算法应用于移动机器人的路径规划问题研究，能够探索与改进一种新的路径优化方法。

关键词：移动机器人；路径规划；遗传算法

Abstract：Intelligent mobile robot can complete the task independently without human intervention. Path planning is an important part of the mobile robot. Its task is to follow a certain evaluation criteria and find a route to goal state from the initial state without collision path in environments with obstacles. Genetic algorithm is a simulation of the genetic characteristics of the biological nature of the simulation and the results of evolutionary algorithms which is a path planning algorithm following the fuzzy methods, neural networks ant colony algorithm. This paper proposes a method to solve the problem of mobile robot path planning based on genetic algorithms. The research and experimental results show that the genetic algorithm can be applied to the mobile robot path planning, which improves a new path optimization methods.

Key words: Mobile robot; Path planning; Genetic algorithm

1、智能移动机器人

1.1智能移动机器人概述

机器人的应用越来越广泛 ,几乎渗透到所有领域。智能移动机器人[1][2]是机器人 学中的一个重要分支。早在 60年代 ,就已经开始了关于智能移动机器人

的研究。关于智能移动机器人的研究涉及许多方面 ,智能移动机器人是一个集环境感知、动态决策与规划、行为控制与执行等多种功能于一体的综合系统。对智能移动机器人的研究 ,提出了许多新的或挑战性的理论与工程技术课题 ,引起越来越多的专家学者和工程技术人员的兴趣 ,更由于它在军事侦察、扫雷排险、防核化污染等危险与恶劣环境以及民用中的物料搬运上具有广阔的应用前景 ,使得对它的研究在世界各国受到普遍关注。

自1961年美国Unimation公司研制出世界上第一台往复式工业机器人以来,机器人的发展经历了三个阶段:第一代示教/再现(Teaching/Playback)机器人,第二代传感控制(Sensorycontrolled)机器人,第三代智能(Inteligent)机器人。机器人以其具有灵活性、提高生产率、改进产品质量、改善劳动条件等优点而得到广泛应用。但是,目前绝大多数机器人的灵活性,只是就其能够\反复编程\而言,工作环境相对来说是固定的,所以一般人们称之为操作手(Manipulator)。正如人类活动范围和探索的空间是人类进步的标志一样,机器人的智能同样体现在运动空间的大小上。为了获得更大的独立性,人们也对机器人的灵活性及智能提出更高的要求,要求机器人能够在一定范围内安全运动,完成特定的任务,增强机器人对环境的适应能力。因此,近年来,智能移动机器人特别是自主式智能移动机器人成为机器人研究领域的中心之一。

1.2智能移动机器人的研究现状

1.体系结构自主式智能移动机器人的复杂性以及当前计算技术的局限性等

决定了体系结构是影响机器人性能的主要因素。自主式智能移动机器人的智能体现为具有感知(Sensing)、决策(Decision-making)和行为(Acting)等基本功能。根据实现这些基本功能的过程的不同,常见的体系结构有三类:分层递阶结构、行为系统和黑板系统。

2.信息感知信息感知来源于传感器。对传感器来说,最主要的两个品质是可靠性和带宽(实时性)。目前自主式智能移动机器人普遍使用的传感器有:声纳、红外、激光扫描、摄像机和陀螺等。每种传感器各有利弊,于是人们自然想到了\取长补短\也即多传感器集成和融合,其优点在于提供了信息冗余、互补和适时(Timeliness),从而提高了信息的可靠性。

3.智能移动机器人控制

(1)建模根据所受约束的不同,可以将控制系统分为完整(Holonomic)系统和非完整(Nonholonomic)系统。约束条件能够以位形变量显式代数方程描述的系统,即为完整系统;约速条件为不完全可积的微分方程则为非完整系统。智能移动机器人是典型的非完整系统。目前,智能移动机器人普遍使用的运动学模型为基于

机器人几何中心或轮轴线中心的时间微分方程,该模型物理意义明确。为避免繁琐的时间微分,E.T.Baumgartner选择了独立变量,建立独立于时间变量的运动学模型,并由此实现了对速度的独立调节。最近,链式(Chained form)方程和幂式(Power form)方程用于描述一类非完整系统。该模型虽然描述的是非线性系统,但具有良好的线性结构,基于此可开环类解耦控制、闭环反馈稳定控制,特别适用于带有拖车的智能移动机器人。

(2)定位(Localization) 定位是智能移动机器人控制中的关键问题,其准确性和精度直接影响规划的实现,从而影响整个系统的性能。定位有静态定位和动态定位之分。静态定位每次将传感器得到的环境信息和环境的先验模型相匹配来定位,计算量大,很难满足实时性要求。为了克服以上缺点,人们采用动态定位,即将外部传感器获得的信息与推算航行法的信息进行融合,以获取高精度定位。融合方法多用Kalman滤波进行最小方差估计和基于模糊逻辑进行模糊推理。

(3)控制及其稳定性智能移动机器人的控制困难在于机器人平面运动具有三个自由度,即平面位置和方位,而控制只有二个自由度,即两个驱动轮的速度或机器人的平移速度和转动速度。Samson指出,智能移动机器人开环可控。但不存在光滑的时不变稳定状态反馈。由于开环控制容易受不确定因素的影响,为了获得较强的鲁棒性和对规划出的路径具有良好的跟踪性能,反馈控制方案才是研究者所寻求的。由于智能移动机器人不存在光滑的时不变稳定状态反馈控制,所以一般采用不连续控制或分段光滑控制实现稳定反馈,控制目的是减少运动自由度或增加控制自由度。各种反馈控制方案虽然解决了作为系统工作必要条件的稳定性问题,但系统要获取良好的性能,还取决于控制律中参数的确定,而所有控制律的参数均很难确定。利用神经网络的学习和容错能力对智能移动机器人控制和基于规则的模糊控制,避免了控制参数的确定,并增强了系统对参数扰动的鲁棒性。

4.路径规划自主式智能移动机器人

它能够按照预先给定的任务指令,根据已知的地图信息作出全局的路径规划,并在行进过程中不断感知周围的局部环境信息,自主地作出各种决策,引导自身安全行驶,并执行要求的动作和操作。由此可以看出,全局路径规划和局部避障是智能移动机器人自主性的核心体现。路径规划为在给定起始点和目标点之间寻求满足一定条件的无碰撞路径。路径规划根据规划时所利用的信息不同可分为基于模型(Model-based)的规划和基于情形(Case-based)的规划。前者根据已知的环境模型或感知的地图知识作出规划,是目前普遍使用的规划方法;而后者则根据已有的规划知识利用匹配法解决新的规划问题。基于情形的规划适用于较为复杂但相对固定的环境,因为,情形的增加对存储容量提出了更高的要求,并且匹配时计算量大,需要不断地更新情形库,使系统复杂化。基于模型的规划从规划所利用

地图知识范围的角度又有全局规划和局部规划之分。全局规划需要完整的环境模型,而局部规划只需要机器人周围的局部信息,主要完成避障任务。基于模型的规划方法主要有物理模拟、拓扑、统计决策、启发式、模糊和神经网络以及遗传算法等。上述的规划方法大多认为机器人具有完备的环境知识,并且假设能对机器人进行精确控制,但实际上这些条件是不能够满足的,因此有必要在规划中考虑不确定因素的影响。Miura对定位误差、控制误差和传感器误差建立分布,运用统计决策理论规划。SUF通过规划路径减小环境、传感器对定位的影响。

2、机械手的发展现状与趋势

机器手首先是从美国开始研制的。1958年美国联合控制公司研制出第一台机器。它的结构是：机体上安装一个回转长臂，顶部装有电磁块的工件抓放机构，控制系统是示教形的。1962年，美国联合控制公司在上述方案的基础上又试制成一台数控示教再现型机器手。商名为Unimate（即万能自动）。运动系统仿照坦克炮塔，臂可以回转、俯仰、伸缩、用液压驱动；控制系统用磁鼓作为存储装置。不少球坐标通用机器手就是在这个基础上发展起来的。同年该公司和普鲁曼公司合并成立万能自动公司,专门生产工业机器手。

1962年美国机械制造公司也实验成功一种叫Vewrsatran机器手。该机器手的中央立柱可以回转、升降采用液压驱动控制系统也是示教再现型。虽然这两种机器手出现在六十年代初，但都是国外工业机器手发展的基础。1978年美国Unimate公司和斯坦福大学，麻省理工学院联合研制一种Unimate-Vicarm型工业机器手，装有小型电子计算机进行控制，用于装配作业，定位误差小于±1毫米。联邦德国机械制造业是从1970年开始应用机器手，主要用于起重运输、焊接和设备的上下料等作业。日本是工业机器手发展最快、应用最多的国家。自1969年从美国引进两种机器手后大力从事机器手的研究。

目前，随着单片机等控制器的发展，工业机器手在自动控制和定位精度上有了很大提高。机器手是近几十年发展起来的一种高科技自动化的生产设备。机器手是机器人的一个重要分支。它的特点是可通过编程来完成各种预期的作业任务，在构造和性能上兼有人和机器的优点。尤其体现了人的智能和适应性。机器手作业的准确性和各种环境中完成作业的能力，在全国经济各领域有着广阔的发展前景，随着工业自动化的发展，出现了数控加工中心，它在减轻工人的劳动强度的同时，大大提高了劳动生产率，但是数控加工中心加工中常见的上下料工序，通常乃采用人工操作或传统继电器控制的半自动化装置。前者费时费工，效力低；后者因设计复杂，需要较多继电器，接线复杂。容易车体震动干扰，而存在可靠性差，故障多，维修困难等问题。可编程控制器单片机控制的上下料机器手控制

系统动作简便，线路设计合理，具有较强的抗干扰能力。保证了系统运行的可靠性，降低了维修率。提高了工作效率。机器手技术涉及到力学，单片机，自动控制技术，传感器技术计算机技术等科学领域，是一门跨学科综合技术。机器手是一种能自动化定位控制并可重新编程序以变动的多功能机器，他又多个自由度，可用来搬运物体以完成在各个不同环境中工作。在工资水平较低的中国，分拣行业尽管仍属于劳动密集型，机器手的使用已经越来越普及，那些电子和汽车业的奥美跨国公司很早就在它们设在中国的工厂中引进了自动化生产。但现在的变化时那些分布在工业密集的华南，华东沿海地区也开始对机器手表现出越来越浓厚的兴趣，因为他们要面对工人流失率高，以及交带来的挑战。随我国工业生产的飞跃发展，自动化程度的迅速提高，实现工件的装卸，转向，输送或分拣流程越来越节约劳动力，可见机器手的大力发展有着很重要的意义。

3、系统结构图

3.1控制系统

基于上述分析,本课题的六自由度工业机器人采用基于DSP和FPGA的架构模式。DSP是一种独特的可编程处理器、,可是实时、快速地实现各种复杂的数自信号处理。除了具备通用微处理器的高速运算和控制功能外,针对高速数据传输、密集数据运算、实时数据处理等需求,在处理器结构、指记系统的指令流程等都有专门的设计,为六自由度工业机器人复杂的运动控制算法捉供了可行的硬件保障。本课题所使用的DSP芯片是IT公司的TMS320F2812芯片,这款芯片一直是运动控制的首选芯片,既具备数字信号处理器强大的数据处理能力,又像单片机一样带有丰富的外设资源和扩展接口,其外部扩展接口XINTF可以与FPGA很好地是实现并行通信。

图1 运动控制器硬件总体框架

3.2感知系统

机器人感知系统从逻辑上来看，可以分为物理层、应用服务层、应用开发层以及应用层这四个层次，其结构如图２．１所示。物理层也叫做传感器层，负责原始信号的采集，获取物理世界的信息：应用服务层把采集到的信息进行局部功能的封装，成为具有特定服务功能的模块，为更高层的开发提供服务：应用开发层借助第三方开发工具、算法等对下层的功能模块进一步集成；应用层面向最终的用户，针对具体应用定制自己的系统。仿照人体神经系统的结构，仿生的机器人感知系统（如图２４）也采用类似的分层网络组织结构，最上层是人直接操纵的决荒层．完成类似人体大脑的决策功能；中间层负责底层节点信息收集融合与集成、上层决策信息执行与下传、节点附近信息收集以及本层节点信息向上层节点的高速实时传输，类似脊柱、器官与传导神经系统的功能，中间层节点根据需要可以是只有单一智能的模块，也可以是功能强大的模块；底层节点相当于周围神经系统，直接与物理世界接触，采用嵌入式处理器架构实现对现场模拟信号的采集，类似人体体表皮肤以及其他感觉器官的功能．作为机器人的感官部分。中间层节点之间与底层节点之间是树型合作，同层次节点之间水平型合作。

统一的传感器数据描述屏蔽了最底层传感器的信息，为传感器的即插即用提供了基础：另外统一的用户接口给用户带来了极大的方便，促进新产品及时上市。这两个规范为机器人感知系统层次间的合作提供了便利。该模型形成了一个优秀的软、硬件整合的设计模型。

图2 机器人感知系统的框架结构

图3 机器人感知系统模型

3.3 驱动系统

目前机械手常用的驱动方式有液压驱动、气压驱动、电机驱动等多种方式，各种驱动方式有其自身的特点，在工业机器人中液压和气压驱动应用很广泛，有些机器人则同时采用多种驱动方式，这都视不同机器人的特点和要求所定。比较这些驱动方式的特点，从中选出适合上料机械手的驱动方式。

机械手的传动系统，根据动力源的不同，分为液压、气压、电器、机械气液联合和电液联合等方式。目前采用的主要是前三种。据资料统计，液压占55%，气压占40%，电器占1%。

3.3.1液压驱动

液压驱动的特点有:

1)驱动力和驱动力矩较大，臂力可达100公斤;

2)速度反应性较好。因为被驱动件的速度快慢取决于油液的容积变化，所以当不考虑油液的温度变化时，被驱动系统的滞后也几乎没有，而且液压机构的适量轻、惯性小，因此它的速度反应性较好;

3)调速范围较大，而且可以无级调速，易于适应不同的工作要求: 4)传动平稳，能吸收冲击力，可以实现较频繁而平稳的换向;

5)在产生相同驱动力的条件下，液压驱动比其他驱动方式体积小、重量轻、惯性小;

6)定位精度比气动高，但比电机低;

7)液压系统的泄漏对机构的工作稳定性有一定的影响;

8)油液中如果混入气体，将降低传动机构的刚性，影响定位精度(产生爬行); 9)油液的温度和粘度变化影响传动性能。液压驱动机械手多用于要求臂力较大而运动速度较低的工作场合。

3.3.2气压驱动

气动驱动的特点有:

1)通过调节气流，就可实现无级变速;

2)由于压缩空气粘性小，流速大，因此气压驱动的机械手动作速度快; 3)压缩空气可从大气中吸取，故动力源获得方便、价格低廉，而且废气处理方便;

4)由于压缩空气粘度小，因此在管路中的压力损失也很小，一般其阻力损失不到油液在油路中损失的千分之一;故压缩空气可以集中供应，远距离输送;

5)压缩空气的压缩性较大，因此使机械手的运动平稳性较差，定位精度较低，而且压缩空气排到大气中时噪声较大，另外还须考虑润滑和防锈等;

6)耐压缩空气的工作压力较低，致使机械手结构较大。因此，气压驱动的机械手，常用于臂力小于30公斤、运动速度较快以及高温、低温、高粉尘等工作条件较恶劣的场合。

3.3.3电机驱动

电机驱动系统按电机的功能可分为直流电机驱动系统、交流异步电机驱动系统、无刷直流电机驱动系统、开关磁阻电机驱动系统和多态电机驱动系统等。各种电机系统的工作原理有很大的区别，性能上也存在着较大的差异。电机驱动机械手可避免电能变为压力能的中间环节，电机系统将电动机、测速机、编码器、减速器及制动器组装在一次加工的壳体中，使得整个电机系统体积小，可靠性和通用性高;另外，电动机根据运行距离及电机的脉冲当量算出脉冲数，将数据输入计算机，可达到非常高的位姿准确度，这些都是电机驱动的优点。

气动机械手与其他驱动方式的机械手相比，价格低廉，结构简单，功率体积比较高，动作速度快，远距离输送，适合抓取质量较小的工件而且有抗干扰无污染等优点。综上，本设计选取气压驱动系统。表1-1给出了各种驱动方式的各方面比较。

表1各种驱动方式的比较

现代气动机械手的基本结构由感知部分、控制部分、主机部分和执行部分四个部分组成。采集感知信号及控制信号均由智能阀岛来处理，气动伺服定位系统代替了伺服电机步进马达或液压伺服系统;气缸、摆动马达完成原来由液压缸或

机械所作的执行动作;主机部分采用了标准型材并辅以模块化的装配形式，使得气动机械手能拓展成系列化、标准化的产品。代表气动技术今后的发展方向，也将始终贯穿着气动机械手的发展与实用性。

3.4 执行系统

机器人主臂机构设计主要包括机械本体、伺服电机、减速器等机构的设计，为了实现机械传动机构简单、体积小、结构紧凑，减速比大（100:1）等要求，整个机器人的结构大致分成腰部关节、肩部关节、肘部关节、大臂与小臂。各关节之间均采用转动关节，采用伺服电机驱动，以实现精密控制。为实现大传动比，采用谐波减速器传动，不仅实现大的传动比，而且是结构更紧凑。 查找fanuc robot M-6iB机器人相关资料，获得以下设计资料和参数：

图4 工业机器人结构图

3.4.1 谐波减速器简介

谐波齿轮减速器是利用行星齿轮传动原理发展起来的一种新型减速器。谐波齿轮传动（简称谐波传动），它是依靠柔性零件产生弹性机械波来传递动力和运动的一种行星齿轮传动。主要包括刚轮、柔轮、和波发生器组成。 由于波发生器的连续转动，迫使柔轮上的一点不断的改变位置，这时在柔轮的节圆的任一点，随着波发生器角位移的过程，形成一个上下左右相对称的和谐波，故称之为：“谐波”。

图5 谐波减速器实体图

3.4.2谐波减速器基本结构

谐波减速器主要由三个基本构件组成：

（1）带有内齿圈的刚性齿轮（刚轮），带有齿轮的刚性齿环，通常与柔轮相差2齿，它相当于行星系中的中心轮；

（2）带有外齿圈的柔性齿轮（柔轮），他是一个孔径略小于波发生器长轴的薄壁柔性齿轮，在波发生器的作用下，可以产生弹性变形，它相当于行星齿轮；

（3）波发生器H，具有长短轴通常它的转动迫使柔轮按一定的变形规律产生弹性变形，它相当于行星架。

作为减速器使用，通常采用波发生器主动、刚轮固定、柔轮输出形式。 谐波减速器内部结构示意图见图6.

图6 谐波减速器内部结构图

3.4.3谐波减速器工作原理

当波发生器为主动时，凸轮在柔轮内转动，就使柔轮及薄壁轴承发生变形（可控的弹性变形），这时柔轮的齿就在变形的过程中进入（啮合）或退出（啮离）刚轮的齿间，在波发生器的长轴处处于完全啮合，而短轴方向的齿就处在完全的脱开。波发生器通常成椭圆形的凸轮，将凸轮装入薄壁轴承内，再将它们装入柔轮内。此时柔轮由原来的圆形而变成椭圆形，椭圆长轴两端的柔轮与之配合的刚轮齿则处于完全啮合状态，即柔轮的外齿与刚轮的内齿沿齿高啮合。这是啮合区，一般有30%左右的齿处在啮合状态；椭圆短轴两端的柔轮齿与刚轮齿处于完全脱开状态，简称脱开；在波发生器长轴和短轴之间的柔轮齿，沿柔轮周长的不同区段内，有的逐渐退出刚轮齿间，处在半脱开状态，称之为啮出。波发生器在柔轮内转动时，迫使柔轮产生连续的弹性变形，此时波发生器的连续转动，就使柔轮齿的啮入—啮合—啮出—脱开这四种状态循环往复不断地改变各自原来的啮合状态。这种现象称之错齿运动，正是这一错齿运动，作为减速器就可将输入的高速转动变为输出的低速转动。

对于双波发生器的谐波齿轮传动，当波发生器顺时针转动1/8周时，柔轮齿与刚轮齿就由原来的啮入状态而成啮合状态，而原来脱开状态就成为啮入状态。同样道理，啮出变为脱开，啮合变为啮出，这样柔轮相对刚轮转动（角位移）了1/4齿；同理，波发生器再转动1/8周时，重复上述过程，这时柔轮位移一个齿距。依此类推，波发生器相对刚轮转动一周时，柔轮相对刚轮的位移为两个齿距。 柔轮齿和刚轮齿在节圆处啮合过程就如同两个纯滚动（无滑动）的圆环一样，两者在任何瞬间，在节圆上转过的弧长必须相等。由于柔轮比刚轮在节圆周长上少了两个齿距，所以柔轮在啮合过程中，就必须相对刚轮转过两个齿距的角位移，这个角位移正是减速器输出轴的转动，从而实现了减速的目的。

3.5 通信系统

运动控制器在对工业机器人进行运动控制时，PC机、DSP以及FPGA之间需要交换大量的数据，才能使各个关节协调运动，保证六自由度工业机器人按照指令正常运行。

3.5.1 PC与DSP机之间的通信

成熟的运动控制卡需要在上位机上实现人机交互界面[3]，而运动控制卡本身需要执行实时的运动轨迹规划算法，因此上位机与运动控制卡之间需要大量的数据，因此PC与DSP之间的通信接口对传输的速率和实时性有很高的要求。

本课题所涉及的初级阶段的运动控制卡DSP中已经写入了两种固定的运动轨迹插值点-直线插值点和圆弧插值点，PC机只需要给DSP发送命令选择六自由度工业机器人的末端执行器以何种轨迹运动，这样就不需要上位机进行运动轨迹规划，大大降低了上位机的程序复杂性，也使得DSP与PC机之间的通信变得简单。

通过上述的分析，DSP与PC机之间的通信使用串口就可以满足本课题要求，也减小了硬件设计和软件设计的难度，一面MAX232就可以实现。

3.5.2 DSP与FPGA之间的通信

本课题的方案中，FPGA通过增量式编码器的反馈可以得到各个关节轴相对于初始时刻的位置，将反馈得到的实际位置发送给DSP。DSP计算出各个关节轴实际位置和理论位置的误差。用PID调节控制FPGA模拟量的输出大小，也就是控制各个关节轴电机的转速，而FPGA继续每隔50ms将各个关节轴的实际位置发送给DSP，与下一个插值点的理论位置相比较，周而复始形成运动控制的反馈控制，也实现了末端执行器连续的轨迹控制。综上上述，DSP与FPGA之间需要交换的数据如下：

(1)每隔50ms的时间，FPGA向DSP发送从增量式编码器反馈处理后的六组位置量，每组位置为32数据。

(2)DSP计算出各个关节轴实际位置和理想位置的误差，并作PID调节处理，向FPGA发送六组16为控制命令，该命令也就是接下来50ms内六组电机的转速。

(3)从上述可以看出，DSP与FPGA之间的数据交换量比较大，使用普通的串口通信，会造成数据堵塞、数据丢失等问题，无法满足要求。本设计采用双端口RAM，来实现DSP与FPGA之间的并行通讯，其中双端口RAM是基于FPGA内部来实现，没有用实际的双端口RAM芯片。利用FPGA来构建双端口RAM解决了数据交换的速度问题，而且FPGA的灵活可配置性也使得该双端口RAM易于修改和升级。

4、算法设计

4.1 传统路径规划方法

（1）自由空间法 （free space approach） 基于简化问题的思想 , 采用“结构空间” 来描述机器人及其周围的环境。 这种方法将机器人缩小成点 ,将其周围的障碍物及边界按比例相应地扩大 ,使机器人点能够在障碍物空间中移动到任意一点 ,而不与障碍物及边界发生碰撞。

（2）图搜索法 采用预先定义的几何形状构造自由空间，并将其表示为连通图，然后通过搜索连通图进行路径规划。这种方法比较灵活，改变初始位置和目标位置不会重构连通图，但是障碍物比较多时，算法会比较复杂，且不一定能找到最短路径。

（3）人工势场法（artificial potential field） 既是把机器人工作环境模拟成一种力场。目标点对机器人产生引力，障碍物对机器人产生斥力，通过求合力来求控制机器人的运动。

4.1.1 智能路径规划方法

（1）基于模糊逻辑算法（fuzzy logic algorithm）的机器人路径规划 此方法基于传感器的实时信息，参考人的的经验，通过查表获得规划信息，实现局部路径规划。通过把约束和目标模糊化，利用隶属度函数寻找使各种条件达到满意的程度，在模糊意义下求解最优解。

（2）基于神经网络（NN）的机器人路径规划 主要是基于神经网络结构构造出来能量函数，根据路径点与障碍物位置的关系，选取动态运动方程 ，规划出最短路径。

（3）基于遗传算法（GA）的机器人路径规划 遗传算法运算进化代数众多，占据较大的存储空间和运算时间，本身所存在的一些缺陷(如解的早熟现象、局部寻优能力差等)，保证不了对路径规划的计算效率和可靠性的要求。为提高路径规划问题的求解质量和求解效率，研究者在其基础上进行改进。

机器人路径规划算法[4][5][6]的方法很多，除了上面介绍的常见的路径规划方法外，还有基于蚁群算法的路径规划，基于微粒群算法的路径规划，结合模拟退火算法的遗传算法等。

前面对路径规划的方法做了整体的介绍，下面则要讲解的具体的算法：遗传算法在路径规划中的应用。

4.2 基于遗传算法的机器人路径规划

4.2.1 遗传算法相关知识

遗传算法(GA)由美国Miehigan大学的JohnHolland等在20世纪60年代末期到70年代初期研究形成的一个较完整的理论方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。 遗传算法包括三个基本操作：选择，交叉和变异。

4.2.2 路径规划的具体步骤

利用遗传算法[7]进行路径规划时，一般包含：环境建模，编码，群体初始化，确定适应度函数（fitness function），遗传操作。

（1）所谓建模是指建立合理的数学模型来描述机器人的工作环境.本次涉及的机器人工作环境都是障碍物已知的二维空间。本文中遗传算法应用的环境都是基于下面条件考虑的：

机器人被看做是一个点； 障碍物的尺寸都向外扩展半个机器人半径。 如图所示

图7.路径规划环境模型图

（2）编码在机器人的工作环境图中可以看到，机器人的运动轨迹由若干直线段构成，每段直线段是机器人运动的基本单位。 机器人到达目标点的整个路径可表示成：

T?l1?l2?....?ln?1 其中Li是第i段直线段的矢量表示，它的两个端点分别可以表示为Pi和Pi+1,

li?OPi?1?OPi

符号“+”表示矢量的运算。于是

于是整个机器人的运动路径可以表示为如下的路点矢量集合：

T?OP1,OP2???OPn? ? 设Pi的坐标点可以表示为（xi，yi），那么在算法实现时，路径就可以以坐标点形式储存。这样就完成了对染色体的编码，所有的路径T是可能的一个满足条件路径。

（3） 群体初始化

群体初始化往往是随即产生的，这里所讲的两种遗传算法都是随即生产从出发点到目标点的任意一条可行路径集合作为初始群体。例如在第一个遗传算法应用中采用均匀分布的方法进行群体初始化。 （4） 适应度函数

规划出路径的优劣程度要有一个评价的标准。适应度函数就是为了评价这个优劣程度。在这个适应度函数中以路径长度和障碍物作为评价指标，并使所求解向指标渐小的方向进化。该函数的构造如下：

i ?1 i ?1 (1)

F(TK)?a1??i?a2??iN?1N?1 在函数中a1，a2是权重系数，分别强化了不同指标的重要性。第一项表示路径的总长度，第二项是障碍物的排斥函数。 M?i???ij M

j? 0 (2)

是障碍物的个数，βi是第i段直线与第j个障碍物的排斥度。定义为：

???ds??1?ij???do2?(?2)?do?ds

?ds? ?0 （3）

共3 项分别对应: ①直线段与障碍物相交时; ②直线段距离障碍物do≤ ds；

③直线段远离障碍物 do > ds 。其中γ为使直线段不与障碍物相交所要移动的最

短距离，do 为直线段到障碍物的距离，称ds为安全距离,当 do ≥ ds后,算法将不再试图使路径进一步远离障碍物,称该线段和障碍物无排斥。

给出适应度函数后，在后面的运行过程中，算法试图使适应度函数最小化并认为使得该函数取得较小值的解为较优解。 （5） 遗传操作 交叉算子

交叉操作对两个对象操作，对对象进行随即分割，然后重组得到两个新的个体。交叉根据分割点的数量分为单点交叉和多点交叉，单点交叉是多点交叉的一种特殊形式。基本的操作如下图2.2所示：

图8多点交叉操作

在图中，父染色体被随机四个分割点分为五部分，标有箭头的部分互换。这样完成交叉操作后产生两条子染色体

基本的交叉操作产生的子代染色体的长度可能不等，结果是，对应的适应度函数也发生变化。对交叉算子的改进是使为了获得更低函数值的适应度函数。前面已经给出路径的表达式。这里给出一个线段的相交函数：

?0??fl?? 1 （4）

i? 0表示第i段直线与所有的障碍物不相交，1表示第i段直线与障碍物相交。并定义如下路段与障碍物相交状态变化函数：

g i ? f l i? 1 ? f l i （5） gi可能的取值为：1，0，-1。为1时第i+1点前段直线与障碍物不相交后一段相交，-1的时候相反，为0的时候说明前后段的情况相同。 这里选择分割点的原则是：

选择 gi为 1 时对应的变化点作为1号父个体的第一分割点，选择紧随该点之后使得 gi为 -1 的点作为第 2分割点。对于2号父个体， 选择过程恰好相反， 选择 gi为 -1时对应的变化点作为2号父个体的第一分割点， 选择紧随该点之后使得gi为1的变化点作为第 2 分割点。更多的分割点同理可得。

除此之外还要考虑交叉点数的选取，前面的交叉操作会使最后的染色体很

????

短，所以后续的操作要设定染色体的长度，设定标准如下。

2?clen?5?1 （6） ?25?clen?20?crossnm?? ?420?clen?35??6(35?clen?Nmax)

? 变异算子

变异过程中，个体中的分量以很小的概率或步长产生转移。 对于给定路径， 该操作对路径上的各路点pi 以一定的概率改变其坐标。

标准变异对地图中的信息并没有加以利用，变异是随机的搜索，常常导致路径劣化。而改进型变异算子优先选取和障碍物相交的线段的端点进行变异，同时限制变异所得的路点坐标在障碍物之外， 并且使变异所得的路点新坐标满足： ?newnewli?OPi?1?OPi

?newnewli?1?OPi?OPi?1 （7）

?new?new??fli?1?fli?fli?1?fli

????????通过这样的约束条件保证了每次变异对路径优化的非负效果。

5、仿真结果与总结

5.1仿真结果

图9 算法输出结果1

其代价函数值为 109.9561，路径全长 109.9561.

图10 算法输出结果2

其代价函数值为 80.0835，路径全长80.0835.

图11 算法输出结果3

其代价函数值为 76.1412，路径全长76.1412.

在上面三个仿真图中[8][9]，适应度函数的值和路径值是一样的。上面的仿真的群体规模都是100，进化50次，染色体变异概率0.3，权重系数a1，a2分别是1，1000。算法比较： 算法1 算法2 算法3 地图1 57 72 100 地图2 41 59 99 地图3 0 0 92 表2 成功率对比

算法1 算法2 算法3 地图1 113.2342 111.3242 109.6178 地图2 82.5809 81.1283 82.6478 地图3 NA NA 78.2485 表3平均代价对比

本文来源：https://www.bwwdw.com/article/v91x.html