路径规划的智能控制

（综述报告）

考

核

科

目 :机电系统智能控制

学生所在院（系）:机电学院 学生所在学科 :机学生姓名 学号 :

学生类别 :工考

核

结

果

械制学 造 阅卷人

智能控制在机器人领域的应用

遗传算法在移动机器人路径规划上的研究

摘要：近些年来机器人技术飞速发展，对机器人运动的控制要求越来越高，机器人的路径规划也越来越热门，智能优化算法在路径规划中的应用有其独特的优势，更能适应多变的环境，更像人一样进行决策。遗传算法对于所解的优化问题没有太多限制，可以灵活的处理问题，善于解决复杂问题和非线性问题，具有良好的隐含并行性和全局搜索能力。在移动机器人路径规划中得到了广泛的重视，本文主要介绍遗传算法的发展、原理及其在路径控制上的研究。

关键词：智能控制，移动机器人，遗传算法，路径规划

1 引言

随着科学技术的进步，机器人技术已经飞快发展，越来越多的机器人为人类工作服务，应用在人们的生产生活中，移动机器人路径规划是机器人应用中的一项重要技术，例如，在执行装配、焊接及抢险救灾等任务时，采用良好的移动机器人路径规划技术可以节省大量机器人作业时间、减少机器人磨损，同时也可以节约人力资源，减小资金投入，为机器人在多种行业中的应用奠定良好的基础。

念[3]，为分类器的构造提出了一个完整的框架。1989年，Goldberg 出版了专著《搜索、优化和机器学习中的遗传算法》[4]。该书系统地总结了遗传算法的主要研究成果，全面地论述了遗传算法的基本原理及应用，奠定了现代遗传算法的科学基础。1991年，Davis 编辑出版了《遗传算法手册》[5]，书中包括了遗传算法科学计算、工程技术和社会经济中的大量应用实例，它对推广和普及遗传算法起到了重要的作用。

3 移动机器人的路径规划

3.1 机器人的发展

自1947年机器人出现以来，机器人在不断的发展进步，能够实现的功能也越来越多，迄今为止，一共发展了三代机器人。

第一代机器人主要指只能以“示教一再现”方式工作的机器人，由于不配备传感器，无法通过感知环境的改变来改善自身的性能品质；

第二代机器人具有一定的感知能力，能获取作业环境和操作对象的信息；采用计算机控制，通过各种算法来实现复杂精确的操作；并且具有一定的自整定和自适应的能力，表现出低级的智能。

第三代机器人是智能型机器人，它具有多种感知功能，对外界环境有模式识别能力；可以进行一定的逻辑思维和决策，在作业环节中自行做出决策、规划动作，目前正处于研究和发展阶段[6]。 3.2 经典的的路径规划方法

2 遗传算法的发展

70年代初，J. Holland提出了遗传算法的基本定理：模式定理，奠定了遗传算法的理论基础。J. Holland教授于1974年在他的著作《自然系统和人工系统的适配》[1]中又提出了遗传算法，其主要特点是采取群体搜索策略和在群体中个体之间进行信息交换，利用简单的编码技术和繁殖机制来表现复杂的现象，不受搜索空间的限制性假设的约束，不要求诸如连续性、导数存在和单峰等假设。1975年，De. Jung在其论文《遗传自适应系统的行为分析》中结合模式定理进行了大量纯数值优化试验，将选择、交换和变异操作进一步完善和系统化，同时又提出了诸如代沟(generation gap)等新的遗传操作技术，建立了著名的De tong五函数测试平台[2]，定义了评价遗传算法性能的在线指标和离线指标。80年代Booker L B,Goldberg D E实现了第一个基于遗传算法的机器学习系统一分类器系统，开创了基于遗传算法的机器学习的新概

路径规划是指移动机器人按照某一性能指标(如距离、时间、能量等) 寻找一条从起始状态到目标状态无碰撞的最优或次最优路径，学家W. Pitts 首次提出神经元的数学模型即MP 模型。1957年Rosenblatt 制作了Perceptron 感知机，首次把人工神经网络理论付诸到工使之尽可能的平滑和安全。 (1)环境分割法（栅格法）

用预先确立的单元以及其间的联系组成一个连通图，构造出一个与环境同构的虚拟空间。在这个定义的虚拟空间中运用一些图搜索方法寻找最优路径。 (2)可视图法

把移动机器人看作一个质点，如图1所示把起始点、目标点和障碍物的各顶点连接起来，但不能穿越障碍物。每段连线看成是可达的路径段，最优路径的搜索过程就变成了起始点(或者机器人质点) 到目标点的最优线路问题。

图1 可视图法

(3)人工势场法

人工势场法是由Khatib[]提出的一种虚拟力法。其基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目标点产生引力，引力和斥力的合力作为机器人的加速力，来控制机器人的运动方向和计算机器人的位置。(4)模糊推理法

基于模糊推理的路径规划方法通过查表(提前建好的知识库) 的方法，指导移动机器人实现实时避开避障，到达目标。该方法最大的优点是实时性高，有效地克服了人工势场法易产生的局部极小值问题，但是最优的模糊隶属函数的设计、模糊控制规则的制定是非常困难的，对于这个缺点，可以引入其他方法与之融合，但复杂度高。 (5)神经网络

人工神经网络的研究可以追溯到本世纪40年代，1943年心理学家W.MeCu llch和数

程实践，60年代提出了自适应线性元件网络。80年代初两篇关于人工神经网络的研究论文奠定了其软件描述和硬件实现的基础。1986年Rumelhart 和Mcclelland 提出了多层网络的递学习算法即算法，该算法从后向前修正各层之间的连接权重，可以求解感知机无法解决的问题，人工祌经网络控制就是由此发展起来的。

随着神经网络的发展，人们始尝试将神经网络结合其它技术，开发出新的轨迹跟-控制万法。图 2所示为用于移动机器人局部路径规划的生物启发神经网结构图。

图2 生物启发神经网络规划

(6)遗传算法

上世纪60年代J. Holland提出了遗传算法，其整体搜索策略和优化计算具备全局搜索能力良好、鲁棒性好和可规模化、隐含并行性等优良性能。但是遗传算法的运行速度较慢，缺乏实时性，标准的遗传算法容易产生“早熟”而收敛到局部最小点。

本文主要介绍的就是遗传算法在路径规划上的研究。

4 遗传算法的路径规划

4.1 遗传算法的基本步骤

遗传算法的具体主要执行以下四步，简

单遗传算法的流程简图见图3。 ①:随机产生初始群体;

②:计算群体中每个个体x 的适应值f (x) ③:根据相对应的遗传概率，用下述操作产生下一代;

(a)选择:复制优良个体，删除劣质个体; (b)交叉:选出两个体进行交换，将子代加入到下一代中;

(c)变异:某一个体的某个字符突变后加入到下一代中;

④:循环执行②和③，直到达到终止条件，并选出最佳个体作为搜索结果。

图3 遗传算法流程图 4.2 初始种群

初始种群的产生是随机的，但是为了简化问题，初始群体的设定可以采用以下所述策略: (1)估计最优解的分布，在此处均匀选取个体。 (2)先随机生成一定数量的个体，择优添加到初始种群中，直到达到数量要求。 4.3适应度函数

适应度函数在遗传算法中评价个体的优劣，主要起搜索的作用。 常见的适应度函数有两种: ①对于求目标函数最小值的问题 ②对于求目标函数最大值的优化问题 4.4基本遗传算子

基本遗传算法只使用选择算子，交叉算子和变异算子这三种基本遗传算子。 (1)选择算子 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择，选择的目的是把优化的个体(或

解) 直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，个体适应度大的遗传到下一代的概率比较大，而个体适应度小的个体遗传到下一代的概率就大的遗传到下一代的概率比较大，而个体适应度小的个体遗传到下一代的概率就小。 (2)交叉算子 交叉是遗传操作中产生新个体的重要手段，仿照生物有性繁殖的基因重组过程，在以一定概率随机选出的交换点处进行交换，产生新个体。同时，将父体的优良基因遗传给新个体。这一独特的方式也是区别于其它进化算法的一个特征。 (3)变异算子 变异算子是仿照自然界生物在进化过程中，基因发生的变异现象而设计的，也称突变算子。变异运算是将染色体(位串) 中的某个或某些基因位上的基因值作变动，从而生成

一个新个体的方法，是在遗传操作中生成下

一代新个体的另一个方法。

4.5 终止条件

遗传算法是迭代过程，是渐渐逼近最优解的。

需要引入终止机制，输出最终结果，一般常用的有三种方法: (1)迭代次数超过一定限制就终止GA 搜索进程。 (2)最大适应值与目标值之差达到允许范围就终止GA 搜索进程。 (3)最优个体的适应值以及群体平均适应值连

续几代的变化范围很小就终止GA 搜索进程。

遗传算法在路径规划上的已经有了广泛

的应用，遗传算法自身具有并行的思想，提高了操作速度，优于一般的搜索算法，但是也带有一定的不足，标准的遗传算法容易“早熟”而收敛到局部最优点，因此很多学者对此做出了改进，朴松昊、洪炳熔提出了全局

规划层采用改进的遗传算法，给出初始全局

优化路径，而局部规划层采用基于行为的方

法，实时修正路径[7]。孙树栋、林茂提出了一种GA 的改进方法，以连接图顶点序列进行遗传编码，引入适应值调整矩阵，较好的解决了多机器人碰撞问题[8]。 5 路径规划的未来趋势

路径规划问题是搜索算法里十分热门的研究对象，移动机器人的路径规划问题的未来研究趋势是：

1) 全局路径规划与局部路径规划的有效结合

全局路径规划技术目前己经取得了丰硕的研究成果，得到了广泛的应用，理论研究也比较成熟，但由于它是建立在机器人工作环境已知的基础上，因此它所适应的范围相对有限，特别是在具有各种不规则障碍物的复杂环境中，很可能会失去它应有的效能。局部路径规划适用于环境未知的实时路径规划，但它反应速度较慢，耗时长，而且对于规划系统的效率要求较高。因此，把二者相互结合就可能取长补短，达到更好的规划效果[9~10]。

2) 基于慎思/反应混合式的路径规划

传统的基于模型自顶向下的感知一规划一执行是一种典型的慎思结构。它利用已知的全局环境模型为移动机器人提供最优动作序列，并到达目标点。该方法适于解决复杂静态环境中的路径规划。但慎思规划需要一定时间来执行对于环境中未预测到的变化反应较慢。而基于反应式行为的路径规划，由于缺乏全局环境信息，作出的路径规划可能不是全局最优。因此，将两种方法结合对于路径就更加有效。

3) 多传感器信息融合的引入

多传感器融合技术能有效的利用多个传感器信息，克服单一传感器信息的不完备性和不确定性，能够更加准确全面的作出路径规划。

4) 多智能移动机器人的路径规划

随着移动机器人应用范围的扩大，单体机器人有时很难胜任工作，迫切需要多个移动机器人的协同作业，即单体机器人的路径规划要与多移动机器人之间统一实现协调与避障。因此，多智能移动机器人系统已经成为人们关注热点。 移动机器人路径规划的研究趋势如上所示，但是机器人技术的发展，控制算法的改进各个因素都影响着路径规划的发展，相信在众多学者的努力攻克，移动机器人的路径规划问题肯定会得到更加深入的研究。

参考文献

[1] Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. 2nd edition, Cambridge, MA: MIT press, 1992.

[2] De Jong K A, An analysisn of behavior of a class of genetic adaptive systems. Ph. D.Dissertation. University of Michigan, 1975, NO. 76-9381.

[3] Booker L B. Goldberg D E. Classifier systems and genetic algorithm. Artificial Intellgence. 1989. 40: 235-282.

[4] Goldber D E. Genetic Algorithm in Serach, Optimization and Machine Learning.Reading.:, MA: Addison-Wesley Publish Company, 1989.

[5] Davis L. Handbook of Genetic Algoritluns. New York: van Nostrand Reinhold, 1991.

[6] 肖南峰智能机器人华南理工大学出版社2008. [7]朴松昊，洪炳熔. 一种动态环境下移动机器人的路径规划方法[fJl.机器人，2003(25): 18一21，43. [8]孙树栋，林茂. 基于遗传算法的多移动机器人协调路径规划[[J].自动化学报，2000(26): 672一676.

[9]蒋新松. 未来机器人技术发展方向的探讨. 机器人，1996, 18(5): 285-291.

[10]蔡鹤皋. 机器人将是21世纪技术发展的热点. 中国机械工程，2000, 11(1-2): 58-60.