机器人路径动态规划

研究背景

近年来,机器人技术飞速发展,机器人的应用领域也在不断扩展。机器人的工作环境存在高度的多变性和复杂性,因此自主导航是实现真正智能化和完全自主移动的关键技术。机器人的导航问题可以归结为对“我在哪”、“我要去哪”以及“我如何到达那里”三个问题的回答。第三个问题就是路径规划,要求机器人在当前位置与目标位置之间寻找一条安全、合理、高效的路径,保证机器人能够安全地到达目标地点。机器人路径规划是机器人领域的一个研究热点。

一、 课题应用

机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。

智能移动机器人[1]，是一个集环境感知、动态决策与规划、行为控制与执行等多功能于一体的综合系统。它集中了传感器技术、信息处理、电子工程、计算机工程、自动化控制工程以及人工智能等多学科的研究成果，代表机电一体化的最高成就，是目前科学技术发展最活跃的领域之一。随着机器人性能不断地完善，移动机器人的应用范围大为扩展，不仅在工业、农业、医疗、服务等行业中得到广泛的应用，而且在城市安全、国防和空间探测领域等有害与危险场合得到很好的应用。因此，移动机器人技术已经得到世界各国的普遍关注。

移动机器人的研究始于60 年代末期。斯坦福研究院(SRI)的Nils Nilssen 和Charles Rosen 等人，在1966年至1972 年中研发出了取名Shakey的自主移动机器人[1]。目的是研究应用人工智能技术，在复杂环境下机器人系统的自主推理、规划和控制。

根据移动方式来分，可分为：轮式移动机器人、步行移动机器人(单腿式、双腿式和多腿式)、履带式移动机器人、爬行机器人、蠕动式机器人和游动式机器人等类型；按工作环境来分，可分为：室内移动机器人和室外移动机器人；按控制体系结构来分，可分为:功能式(水平式)结构机器人、行为式(垂直式)结构机器人和混合式机器人；按功能和用途来分，可分为:医疗机器人、军用机器人、助残机器人、清洁机器人等；

一种由传感器、遥控操作器和自动控制的移动载体组成的机器人系统。移动机器人具有移动功能，在代替人从事危险、恶劣（如辐射、有毒等）环境下作业和人所不及的（如宇宙空间、水下等）环境作业方面，比一般机器人有更大的机动性、灵活性。

移动机器人是一种在复杂环境下工作的，具有自行组织、自主运行、自主规划的智能机器人，融合了计算机技术、信息技术、通信技术、微电子技术和机器人技术等。 三、研究意义

路径规划技术是机器人研究领域中的一个重要分支,是机器人智能化的重要标志,是对

移动机器人进行更深层次研究和应用的基础。机器人的最优路径规划问题就是依据某个或某些优化准则(工作代价最小、行走时间最短、行走路线最短等),在机器人的工作空间中寻找一条从起始位置到目标位置的无碰撞路径。就如人一样,只有知道怎么在环境中行走,才不会与其他物体相碰撞并且正确地从起始地到达目的地,才能去做其他的事。但是即使是完成这样一个在我们看来十分简单的任务,其实也是经过了一个良好配合与正确分析的过程。首先眼睛要搜集环境信息,把看到的环境状态反馈给大脑,然后大脑根据眼睛反馈回来的环境信息和所要到达的目的地做出综合的分析,得到一个判断和结果,然后指挥人的身体移动,从而实现在环境中的行走。机器人也是类似,只不过在这里传感器充当了机器人的“眼睛”,而路径规划模块就相当于机器人的“大脑”,根据传感器信息和任务要求进行分析和决策,指挥机器人的运动。

四、课题工作方案

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

遗传算法包括三个基本操作：选择，交叉和变异。

2.2 路径规划的具体步骤

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

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

（1）机器人被看做是一个点；

（2）障碍物的尺寸都向外扩展半个机器人半径。 如图2.1所示

图2.1 路径规划环境模型图

Fig.2.1 Path planning environment model diagram

2.2.2编码

在机器人的工作环境图中可以看到，机器人的运动轨迹由若干直线段构成，每段直线段是机器人运动的基本单位。

机器人到达目标点的整个路径可表示成：

T?l1?l2?....?ln?1

其中Li是第i段直线段的矢量表示，它的两个端点分别可以表示为Pi和Pi+1,符号“+”表示矢量的运算。可以以O表示原点，于是

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

ii?1i

T?OP1,OP2???OPn设Pi的坐标点可以表示为（xi，yi），那么在算法实现时，路径就可以以坐标点形式储

l?OP??OP?存。这样就完成了对染色体的编码，所有的路径T是可能的一个满足条件路径。 2.2.3 群体初始化

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

2.2.4 适应度函数

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

N?1N?1)?a?? i ? F (T a 2 ? ? i (1) K 1

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

?i???j?0ij (2) M是障碍物的个数，βi是第i段直线与第j个障碍物的排斥度。定义为：

???ds? ?12?ij???do?(?2)?do?dsd ? s (3

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

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

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

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

? 交叉算子

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

图2.2 多点交叉操作

Fig.2.2 Multi-point crossover operation

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

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

（4）

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

（5） gi?fli?1?fli0?gi可能的取值为：1，0，-1。为f1l时第??i+1点前段直线与障碍物不相交后一段相交，-1i?1的时候相反，为0的时候说明前后段的情况相同。

??????这里选择分割点的原则是：

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

除此之外还要考虑交叉点数的选取，前面的交叉操作会使最后的染色体很短，所以后续的操作要设定染色体的长度，设定标准如下。

2?clen?5?1? （6） ?25?clen?20crossnm??? 变异算子 ?420?clen?35?6(35?clen?N变异过程中，个体中的分量以很小的概率或步长产生转移。 对于给定路径， 该操作对)?max路径上的各路点pi 以一定的概率改变其坐标。

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

?newnewli?OPi?1?OPi

?newli?1?OPinew?OPi?1 （7）

????newnewfli?1?fli?fli?1?fli

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

插入算子

该算子在其所作用路径上增加路点。考虑路径上某一直线段 与障碍物

相交，并且有端点坐标Pi处于障碍物外部空间。于是通过在Pi与Pi+1之间插入合适的端点 ，一定可以得到 不与障碍物相交。同理，对于Pi+1处于障碍物外部空间时，一定可以有不与障碍物相交 。对于Pi与Pi+1均位于障碍物内部的情况，该算子

P

newi?1Pnewi?1