机器人轨迹规划算法的分析
摘要: 本文根据机器人最优轨迹规划的约束与要求，采用了一种新的基于最小耗能的轨迹规划方法。该方法在传统的差分进化算法的基础上，采用样条插值法来获得机器人连续型的最优轨迹。通过MA TLAB软件建立机器人模型，并且编写了其轨迹规划的程序进行仿真。仿真结果表明，差分进化算法是一种性能优良的，具有高效性、并行性、鲁棒性等优点的轨迹规划方法。
1.引言
机器人技术是综合了力学、机械学、电子学、生物学、控制论、计算机、人工智能、系统工程等多种学科领域知识的高新技术，是当代研究十分活跃、应用日益广泛的一门学科。机器人的应用情况，也是一个国家工业自动化水平的重要标志。
机器人的轨迹规划属于底层规划，是在机器人手部运动学的基础上，讨论机器人运动过程中的轨迹和轨迹生成方法。在实际机器人运动规划过程中，机器人的一次作业任务可能要经过多个作业点，这就可能导致产生多个可能的结果。这时，就需要采用一种策略从这些结果中选出一个最优的路径。同时还需要意识到，机器人运动过程中各关节运动轨迹函数必须是连续和平滑的。此外，操作臂的运动也应该平稳，不平稳的运动会加速机器部件磨损，并且导致对操作臂的振动和冲击。这就要求寻找到一条最优的轨迹规划，使其满足多种约束条件和性能指标。通常研究中以最短时间、最小耗能或者机械臂扫过的扇形面积最小作为优化目标。本文所要研究内容是基于最小耗能性能指标的机器人轨迹规划。
2.机器人轨迹规划算法的介绍
1、A*搜索算法
A*算法是一种启发式的图搜索算法，可以在有限的条件中得到一个最优解，并可以在理论上保证全局最优解的收敛性，可以较好地满足轨迹规划问题中的各种约束条件。
A*算法的核心思想是建立启发函数：
f(n)=g(n)+h(n)（2.1）式中，g(n)是从起始节点到当前节点n的实际代价值；h(n)是从当前节点n到目标节点的估计值。两者相加得到的就是当前节点的估计价值f(n)，然后再对f(n)
的大小做比较，选取f(n)的最小的节点作为有效节点，有效节点作为新的起点，继续搜索下一个有效节点，直至到达目标点。
2、人工势场法
人工势场法是通过设计目标和障碍的势能函数，使机器人处于人工势场中，同时受到目标点的引力和障碍物的斥力，选取合适的势能函数参数和移动步长，根据合力生产一系列路径点，最终完成路径规划。
机器人在人工势场中受到的合力表达式为：
F(n)=F a(n)+∑F r(n)（2.2）式中，向量F a(n)为当前点n受到目标点的引力，方向由机器人质心指向目标点；向量F r(n)为受到障碍物的斥力，方向由障碍物质心指向机器人质心；∑F r(n)为斥力合力；F(n)为机器人受到的总合力。
若当前点坐标和步长分别为p(n)和δ，则机器人下一节点的坐标为
p(n+1)=p(n)+δF(n)
（2.3）
‖F(n)‖
按照此方法搜索，一步一步到达目标点。
3、智能优化算法
前面两种轨迹规划方法的每一步并不是朝着目标点方向，这样得到的路径并非最优。智能算法通过随机搜索获得最优路径，在轨迹规划中具有较好的应用。
3.差分进化算法
本文介绍固定时间点位置运动的最优轨迹规划设计问题。最优轨迹的目标是使机器人在整个运动过程中消耗的能量最少。智能优化算法（如遗传算法、粒子群算法、差分进化算法等）可以用来优化任何形式的定点运动。为了设计最优轨迹，本文着重介绍基于差分进化的轨迹规划算法。
3.1标准差分进化算法
差分进化算法保留了基于种群的全局搜索策略。采用实数编码，基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性，同时它特有的记忆能力使其可以动态跟踪当前的搜索情况以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适合于求解一些利用常规的数学规划方法所无法求解的复杂环境中的问题。差分进化算法的主要优点可以总结为一下三点：持定参数少；不易陷入局部最优；收敛速度快。
差分进化算法根据父代个体间的差分矢量进行变异、交叉和选择操作，其基本思想是从某一随机产生的初始群体开始，通过把种群中任意两个个体的向量差加权后按一定的规则与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的适应度值优于与之相比较的个体的适应度值，则在下一代中就用新的个体取代旧个体，否则旧个体仍保存下来，通过不断地迭代运算，保留优良个体，淘汰劣质个体，引导搜索过程向最优解逼近。
3.2差分进化算法的基本流程
差分进化算法是基于实数编码的进化算法，整体结构与其他进化算法类似，由变异、交叉和选择三个基本操作构成。标准差分进化算法包括以下4个步骤：1.生成初始种群
在n维空间里随机产生满足约束条件的M个个体，第i个个体表示如下：x ij(0)=rand ij(0,1)(x ij U?x ij L)+x ij L（3.1）其中，x ij U和x ij L分别是第j个染色体的上界和下界；rand ij(0,1)是[0,1]之间的随机小数。
2.变异操作
从群体中随机选择3个个体x p1、x p2和x p3，且i≠p1≠p2≠p3，则基本的变异操作为：
?ij(t+1)=x p1,j(t)+F(x p2,j(t)?x p3,j(t))（3.2）如果无局部优化问题，变异操作可写为：
?ij(t+1)=x bj(t)+F(x p2,j(t)?x p3,j(t))（3.3）其中，x p2,j(t)?x p3,j(t)为差异化向量，此差分操作是差分进化算法的关键；F 为缩放因子；p1、p2和p3为随机整数，表示个体在种群中的序号；x bj(t)为当前代中种群中最好的个体。
3.交叉操作
交叉操作是为了增加群体的多样性，具体操作如下：
v ij(t+1)={?ij(t+1),rand l ij≤CR
x ij(t),rand l ij>CR（3.4）
其中，rand l ij为[0,1]之间的随机小数；CR为交叉概率，CR∈[0,1]。
4.选择操作
为了确定x i(t)是否成为下一代的成员，采用评价函数进行比较：
x i(t+1)={
v i(t+1),f a(v i1(t+1),…,v in(t+1))>f a(x i1(t),…,x in(t)) x ij(t),f a(v i1(t+1),…,v in(t+1))≤f a(x i1(t),…,x in(t))
其中f a(?)为适应函数。
反复执行步骤2到步骤4的操作，直至达到最大的进化代数G，差分进化算法基本流程如图1所示：
图1：差分进化算法基本流程
3.3差分进化算法的参数设置
对于进化算法而言，为了取得理想效果，需要对差分进化算法的各参数进行合理的设置。针对不同的优化问题，参数的设置往往是不同的。
差分进化算法的运行参数主要包括缩放因子F、交叉因子CR、群体规模M 和最大进化代数G。
1.变异因子F
变异因子F是控制种群多样性和收敛性的重要参数。一般在[0,2]之间取值。变异因子F值较小时，群体的差异度减小，进化过程不会跳出局部极值导致种群过早收敛。变异因子F值较大时，虽然容易跳出局部极值，但是收敛速度会减慢。变异因子值一般可选在F=0.3~0.6。
另外，可以采用如下线性调整变异因子F:
+F min（3.6）
F=(F max?F min)T?t
T
其中，t为当前进化代数；T为最大进化代数；F max和F min为选定的变异因子最大和最小值。在算法搜索初期，F取值较大，有利于扩大搜索空间，保持种群的多样性；在算法后期，收敛的情况下，F取值较小，有利于在最佳区域的周围进行搜索，从而提高了收敛速率和搜索精度。
2.交叉因子CR
交叉因子CR可控制个体参数的各维对交叉的参与程度，以及全局与局部搜索能力的平衡，一般在[0,1]之间。交叉因子CR越小，种群多样性减少，容易过早收敛。CR越大，收敛速度越大。但CR过大可能反而导致收敛速度变慢。交叉因子CR一般应选在[0.6,0.9]之间。CR越大，F越小，种群收敛逐渐加速，但随着交叉因子CR的增大，收敛对变异因子F的敏感度逐渐提高。
同样，可以采用如下线性公式调整交叉因子CR：
CR=CR min+(CR max?CR max)
t（3.7）
T
其中，CR max和CR max为交叉因子CR的最大值和最小值。
为了保证性能，CR max和CR max应选取合理的值。随着进化代数的增加，F 线性递减，CR线性递增，目的是改进DE算法在搜索初期能够保持种群的多样性，到后期有较大的收敛速率。
3.群体规模
群体所含个体数量M一般介于5D与10D之间（D为问题空间的维度），但不能少于4，否则无法进行变异操作，M越大，种群多样性越强，获得最优解概率越大，但是计算时间更长，一般取20~50。
4.最大迭代代数G
最大迭代代数G，一般作为进化过程的终止条件。迭代次数越大，最优解更精确，但计算的时间会更长，需要根据具体问题设定。
以上四个参数对差分进化算法的求解结果和求解效率都有很大的影响，因此要合理设定这些参数才能获得较好的效果。
4.最优轨迹的设计
差分进化算法是基于群体智能理论的优化算法，通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。由于其简单易用、稳健性好以及强大的搜索能力，差分进化算法已在多个领域取得成功，可以实现最优轨迹规划。4.1基于差分进化算法的最优轨迹的设计
不失一般性，最优轨迹可以在定点运动-摆线运动轨迹的基础上进行优化。摆线运动的表达式如下：
θr=(θd?θ0)[t
T E ?1
2π
sin(2πt
T E
)]+θ0（10.8）（4.1）
式中，T E是摆线周期；θ0和θd分别为初始角度和目标角度。
由于差分进化算法是一种离散型算法，因此需要对连续型参考轨迹公式（4.1）进行等时间间隔采样，取采样时间间隔为T E
2n
，则可得到离散化的参考轨迹为：
θ?r=[θ?r,0，θ?r,1，…θ?r,2n?1，θ?r,2n]（4.2）
其中，θ?r,j表示在时刻j
2n
T E对于θr的采样值（j=1,2,…n-1），θ?r是离散的参考轨迹。
定义?θ?j(k)为与参考轨迹的偏差(j=1，2，…，n-1)，k表示差分进化算法中的第k次迭代，则得
θ?opj(k)=θ?r,j+?θ?j(k)（4.3）
其中，θ?opj(k)表示在时刻t=j
2n
T E由差分进化算法的第k次迭代得到的关节角的修正角度。
4.2最优轨迹的求取
最优轨迹能够通过优化与参考轨迹的偏差来间接得到。假设系统达到稳态的最大允许时间为t =3T E ，根据能量守恒定理，用非保守力做功来表示系统在运动过程中消耗的总能量，选择的目标函数为：
J =ω∫|τθ|3T E 0dt +(1?ω)∫|dis(t)|3T E 0
dt （4.4） 其中，ω为权值，ω∈(0,1)；τ为控制输入信号；dis(t)为实际跟踪轨迹与理想轨迹之间的距离。
通过采用差分进化算法，优化轨迹公式（4.3），使目标函数最小，从而获得最优轨迹。差分进化算法的参数设定如下：最大迭代次数G ，种群数Size ，搜索空间的维数D ，放大因子F ，交叉因子CR 。经过差分进化算法可以得到一组最优偏差，进而得到最优的离散轨迹如下：
θ
?op =[θ?op,0，θ?op,1，…θ?op,2n?1，θ?op,2n ] （4.5） 为了获得连续型的最优轨迹，采用三次样条插值进行轨迹规划，即利用三次样条插值的方法对离散轨迹进行插值。插值的边界条件如下：
θop (0)=θ
?op,0=θ0 （4.6） θop (T E )=θ
?op,2n =θd （4.7） θop (0)=θop,0=θ0=0 （4.8）
θop (T E )=θop,2n =θd =0 （4.9）
插值节点为
θop (t j )=θ?op,j ，t j =j 2n
T E ，j=1,2,…,2n-1 （4.10） 将插值得到的连续函数θop (k )作为关节的最优轨迹。定义跟踪误差为e =θop ?θ，设计滑膜函数为
s =e?+ce （4.11）
其中，c >0。
则
s?=e?+ce?=θop ?θ+ce?=θop ?1I (τ+d ?bθ)+ce? （4.12）
设计控制律为
τ=bθ+φ2sgn (s )+I(ce?+θop +φ1s) （10.14） （4.13）
其中，φ1>0。
定义Lyapunov 函数为V =12s 2，则
V =?φ1s 2?s I (d +φ2sgn (s ))≤2φ1V ≤0 （4.14） 根据以下不等式求解引理：
引理：针对V:[0,∞)∈R ，不等式方程V ≤?αV +f,?t ≥t 0≥0的解为
V (t )≤e ?α(t?t 0)V (t 0)+∫e ?α(t?τ)t
t 0f(τ)dτ （4.15） 其中，α为任意常数。
解得
V (t )≤V(0)exp (?φ1t) （4.16）
可见，s (t )为指数收敛，收敛速度取决于φ1。
4.3基于差分进化算法的最优轨迹的实现
考虑简单的被控对象
Iθ+bθ=τ+d （4.17） 其中，I =1133，b =25133，d =sin (t)。
采样时间为ts =0.001，采用Z 变换进行离散化。仿真中，最大允许时间为3T E ，摆线周期T E =1，取摆线周期的一半离散点数为n=500，则采样时间为ts =T E 2n =0.001。
采用样条插值方法，插值点选取4个点，即D=4。通过插值点的优化来初始化路径，具体方法为：插值点横坐标固定取第200、第400、第600和第800个点，纵坐标取初始点和终止点之间的4个随机值，第i 个样本（i=1,2,…,size ）的第j 个插值点（j=1，2，3，4）的值取
θop (i,j )=rand (θd ?θ0)+θ0 （4.18）
其中，rand 为0~1之间的随机值。
采用差分进化算法设计最优轨迹θop ，取权值ω=0.30，样本个数Size=50，变异因子F=0.5，交叉因子CR=0.9，优化次数为30次。通过差分进化方法不断
优化4个插值点的纵坐标值，直到达到满意的优化指标或优化次数为止。
跟踪指令为θd=0.5，采用控制律式（4.13），取c=30,φ1=300，为降低抖动，用饱和函数替代符号函数，取?=0.05，φ2=1.01，仿真结果如图2~5所示。
图2：理想轨迹、最优轨迹及轨迹跟踪
图3：控制输入信号
图4：最优轨迹的优化效果
图5：目标函数的优化过程
参考文献：
[1]M.V asile,E.Minisci,M.Locatelli.An Inflationary Differential Evolution Algorithm for Space Trajectory Optimization[J].IEEE Transactions on Evolutionary Computation,2011,15(2):267-281.
[2] Das S, Konar A, Chakraborty U K. Two Improved Differential Evolution Schemes for Faster Global Search[C]. Proceedings of the 2005 Conference on Genetic and Evolutionary Computation.ACM,2005:991-998.
[3]蔡自兴.人工智能及其应用[M].北京：清华大学出版社，2010.
东南大学 硕士学位论文 移动机器人完全遍历路径规划算法研究 姓名：胡正聪 申请学位级别：硕士 专业：机械电子工程 指导教师：张赤斌 20080403
第一章绪论 第一章绪论 １．１移动机器人的发展史 社会的主体是人类，历史的推动者是人类，伟大的人类运用自己的智慧不断创造伟大的发明，不断推动社会的发展。邓小平同志说过：“科技是第一生产力。”生产力是社会发展的动力，所以人类推动社会发展就是要致力于发展生产力，致力于发展科技。人类不断发展生产力来提高自身认识自然、改造自然、得到自己所需物质的能力，这种能力的进化由最初的运用双手、简单工具、发展到运用畜力、发展到运用简单机器、发展到运用自动化设备、还会发展到我们无法想象的未来。 机器人就是生产力发展的产物。机器人的概念最早是在１９２０年的科幻小说中提出的，而早期的机器人如１９３９年美国纽约世界博览会上展出的西屋电气公司制造的家用机器人Ｅｌｅｋｔｒｏ和１９５６年美国人乔治?德沃尔制造出的世界上第一台可编程的机器人都是一些实用价值不高的机器人，它们是现代机器人的雏形。上世纪６０年代，由于传感器和计算机技术的发展及应用，兴起了全世界第二代机器人的研究热潮，并向人工智能进发。１９６８年，美国斯坦福研究所公布了他们研发成功的机器人Ｓｈａｋｅｙ。它带有视觉传感器，能根据人的指令发现并抓取积木。Ｓｈａｋｅｙ可以算是世界第一台智能机器人，它拉开了第三代机器人研发的序幕。到了上世纪８０年代，发达国家都组建各种机器人研究机构，尤其是以美国为代表的国家将机器人的研究列入了军事发展计划，带动各国把机器人的研究推上了高潮，日本和欧洲各国都成立了各自的机器人研究中心和规划了自己的研究计划。进入９０年代后，机器人的应用领域除了工业和军事外，还涉及到了服务和娱乐领域，以日本本田公司的ＡＳＩＭＯ人型机器人和索尼公司的ＡＩＢＯ娱乐机器人为代表的机器人展示了机器人领域各方面的先进研究成果。在欧洲，２００２年丹麦ｉＲｏｂｏｔ公司推出了吸尘器机器人Ｒｏｏｍｂａ，它能避开障碍，自动设计行进路线，还能在电量不足时，自动驶向充电座。Ｒｏｏｍｂａ是目前世界上销量最大、最商业化的家用机器人。２００６年６月，微软公司推出ＭｉｃｒｏｓｏＲＲｏｂｏｔｉｃｓＳｔｕｄｉｏ，机器人模块化、平台统一化的趋势越来截明显，比尔?盖茨预言：“家用机器人很快将席卷伞球。” 图１．１丹麦ｉＲｏｂｏｔ公司推出的吸尘机器人Ｒｏｏｍｂａ［
一种移动机器人的路径规划算法 作者：霍迎辉，张连明 (广东工业大学自动化研究所广州510090 文章来源：自动化技术与应用点击数：1419 更新时间：2005-1-24 摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。 关键词：移动机器人；路径规划；机器人避障 1引言 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物［1］。 障碍环境中机器人的无碰撞路径规划［2］是智能机器人研究的重要课题之一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的。 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法。这些方法都各有优缺点［3］，也没有一种方法能够适用于任何场合。 本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。 2最短切线路径算法 2.1算法基本原理 (1)首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其坐标 为(x Ｂ，y Ｂ ），以R、A分别代表机器人及障碍物，坐标为(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示机器人和障 碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器人可走直线直接到达目标位置，此时的直线方程可由两点式确定：
工业机器人的轨迹规划和控制 S. R. Munasinghe and Masatoshi Nakamura 1.简介 工业机器人操作臂被用在各种应用中来实现快速、精确和高质量的生产。在抓取和放置操作，比如对部分的操作，聚合等，操作臂的末端只执行器必须在工作空间中两个特定的位置之间移动，而它在两者之间的路径却不被关心。在路径追踪应用中，比如焊接，切削，喷涂等等，末端操作器必须在尽可能保持额定的速度下，在三维空间中遵循特定的轨迹运动。在后面的事例中，在对末端操作器的速度、节点加速度、轨迹有误等限订的情况下轨迹规划可能会很复杂。在没有对这些限制进行充分考虑的情况下进行轨迹规划，通常会得到很差的表现,比如轨迹超调，末端操作器偏离给定轨迹，过度的速度波动等。机器人在笛卡尔轨迹中的急弯处的的表现可能会更加恶化。到目前为止很多轨迹规划算法己经被提出，从笛卡尔轨迹规划到时间最优轨迹规划。然而，工业系统无法适应大多数的这些方法，有以下两点原因：（1）这些技术经常需要进行在目前机构中进行硬件的移动，生产过程必须被打断以进行系统重新配置，而这往往需要很长时间。（2）这些方法中很多通常只考虑到一种约束，而很少关注工业的需求和被请求的实际的约束。因此，它们很难在
工业中实现。 在本文的观点中，我们提出了一种新的轨迹规划算法，考虑到了末端操作器的速度限制，节点加速度限制，应用中的容错度。这些是在工业应用中实际的约束。其他工业操作臂中的技术问题是他们的动力学延迟，这导致末端操作臂在轨迹中的拐角处出轨。为了补救这个问题，我们设计了前向补偿，稍稍改变了拐角处的路径，使得即使在延迟动力学环节存在的情况下依然确保末端操作臂的实际跟踪轨迹。结合了前向补偿新的轨迹规划算法在控制系统中表现为单一的前向阻塞。它可以轻松地适应目前的工业操作臂系统，不冒风险，不花费时间重新配置硬件。 轨迹规划算法可以为所有操作臂的节点产生位置，速度和加速度的大体规划。在大多数工业操作臂中，系统输入是节点的位置数据，这在工业中是作为被给定的数据而广为人知的。为了用笛卡尔轨迹规划来控制操作臂，Paul描述了同类型的转换是怎样可以被用来代表一系列操作臂连杆的位置和原点的。Shin et.al.的工作和我们的很相似，但是实现在工业控制系统中的应用是很困难的，因为它需要知道很多操作臂的连杆和节点的参数。在大多数工业操作比系统中，这些参量并不能被精确的获知。 在我们之前的工作中我们解决了在二维空间中加速度和速度的约束，在目前的工作中，当我们考虑到容差度，我
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/0417017677.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
专题综述 课程名称工业自动化专题 题目名称工业机器人的运动轨迹学生学院____ _ 自动化________ 专业班级___ _ _ 学号 学生姓名___ _ _ 指导教师__________ 2013 年 6月 27日
工业机器人的运动轨迹综述 【摘要】：随着知识经济时代的到来，高技术已成为世界各国争夺的焦点，机器人技术作为高技术的一个重要分支普遍受到了各国政府的重视。自此，多种不同的研究方向都在工业机器人实时高精度的路径跟踪来实现预期目的。而工业机器人的运动轨迹又是重中之重，在得到反馈信息之后，如何作出应答，并且实时检查轨迹与所计算出的轨迹是否吻合，为此也要进行追踪与动作修正。 【关键词】：工业机器人，视觉，路径跟踪，轨迹规划，高精度 1.机器人视觉，运动前的准备 实际的工业现场环境复杂，多种因素都有可能导致系统在运行过程中产生一定的偏差、测量精度降低，引起误差的原因主要有温度漂移和关节松动变形等，使测量模型的参数值改变从而导致定位误差增大，因此需要定期对工业机器人视觉测量系统进行精确的校准，从而实现精确定位和视觉测量。更少不得必要的优化。 1.1基于单目视觉的工业机器人运动轨迹准确度检测 建立的工业机器人单目视觉系统，整个系统主要由单目视觉单元，监控单元和机器人执行单元三大单元组成。单目视觉单元为一台固定在机器人上方的CCD摄像机，负责摄取工作环境中的目标并存入图像采集卡缓冲区；监控单元负责监控各工作站的当前状态，并完成对存储图像进行相关处理的工作，达到识别定位目标的目的；执行单元负责驱动机械手实施抓取操作。 1.2基于双目视觉的工业机器人运动轨迹准确度检测 以立体视觉理论为基础，研究了基于空间直线的二维投影面方程。根据投影面的空间解析几何约束关系，建立基于直线特征匹配的双目视觉误差测量的数学模型。在该模型基础上采用将两台摄像机固定于工业机器人末端的方案．对关节型工业机器人运动轨迹的准确度进行了检测。结果表明，该检测方法简单实用，基本上可以满足工业机器人CP性能检测的要求。 1.3一种面向工业机器人智能抓取的视觉引导技术研究 为实现工业机器人自主识别并抓取指定的目标，提出了一种基于计算机视觉引导的解决 方法。该方法利用指定目标的3D数据模型，以及由两台或者多台CCD摄像机从工作场景中不同角度获；取到的数字图像，经过目标姿态估算、投影计算并生成投影图像，再利用投影
1.自主机器人近距离操作运动规划体系 在研究自主运动规划问题之前，首先需建立相对较为完整的自主运动规划体系，再由该体系作为指导，对自主运动规划的各项具体问题进行深入研究。本节将根据自主机器人的思维方式、运动形式、任务行为等特点，建立与之相适应的自主运动规划体系。并按照机器人的数量与规模，将自主运动规划分为单个机器人的运动规划与多机器人协同运动规划两类规划体系。 1.1单个自主机器人的规划体系 运动规划系统是自主控制系统中主控单元的核心部分，因此有必要先研究自主控制系统和其主控单元的体系结构问题。 自主控制技术研究至今，先后出现了多种体系结构形式，目前被广泛应用于实践的是分布式体系结构，其各个功能模块作为相对独立的单元参与整个体系。随着人工智能技术的不断发展，基于多Agent的分布式体系结构逐渐成为了主流，各功能模块作为独立的智能体参与整个自主控制过程，该体系结构应用的基本形式如图1所示。一方面，主控单元与测控介入处理、姿态控制系统、轨道控制系统、热控系统、能源系统、数传、有效载荷控制等功能子系统相互独立为智能体，由总线相连；另一方面，主控单元为整个系统提供整体规划，以及协调、管理各子系统Agent的行为。测控介入处理Agent保证地面系统对整个系统任意层面的控制介入能力，可接受上行的使命级任务、具体的飞行规划和底层的控制指令；各子系统Agent存储本分系统的各种知识和控制算法，自主完成主控单元发送的任务规划，并将执行和本身的健康等信息传回主控单元，作为主控单元Agent运行管理和调整计划的依据。 图1 基于多Agent的分布式自主控制系统体系结构基本形式示意图 主控单元Agent采用主流的分层递阶式结构，这种结构层次鲜明，并且十分利于实现，其基本结构如图2所示。主控单元由任务生成与调度、运动行为规划和控制指令生成三层基本结构组成，由任务生成与调度层获得基本的飞行任务，经过运动行为规划层获得具体的行为规划，再由控制指令生成层得到最终的模块控制指令，发送给其它功能Agent。各功能Agent发送状态信息给主控单元的状态检测系统，状态检测系统将任务执行情况和子系统状态反馈回任务生成与调度层，以便根据具体情况对任务进行规划调整。当遇到突发情况时，还可启用重规划模块，它可根据当时情况迅速做出反应快速生成行为规划，用以指导控制指令生成层得到紧急情况的控制指令。此外，地面控制系统在三个层次上都分别具有介入能
Business ! ·233· 机器人路径规划算法探讨 陈书光 作者简介：陈书光，（1980－），男，籍贯：河南省唐河县，汉族，学历：研究生，职称：讲师，研究方向：数据库技术、软件设计、 算法分析。 摘要：机器人路径规划问题被定义为一个障碍的工作环境中找到一个适当的从起点到终点的运动路径，机器人在运动过程中能安全无碰撞，绕过所有的障碍。屏障环境的机器人无碰撞路径规划是一个重要的研究课题，智能机器人，由于障碍物空间机器人运动规划的高度复杂性，使得这个问题一直没有得到很好的解决。路径规划问题的基础上，机器人的工作环境模型可以分为2类，一个是基于模型的路径规划，经营环境的整体的信息是可预测的；另一种是基于传感器的路径规划，环境信息完全未知或部分未知。 关键词：机器人路径规划算法一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下： （一）遗传算法概念 遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法 ，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。 （二）遗传算法的特点 作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。 （三）遗传算法的应用 遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、已是强的鲁棒性，所以广泛应用余许多科学：功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试：连续函数和离散函数，凸、凹函数、低维功能和高尺寸功能、单式功能和更多峰值函数。一些非线性、多模型、多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、组合优化问题的粒子非常有效。 二、蚁群算法及其应用（一）蚁群算法概念 蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo 于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。 （二）蚁群算法的特点 ①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。 ②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程 独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。 ③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。 ④蚁群算法具有较强的鲁棒性。比较与其他算法、蚁群算法、初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。 （三）蚁群算法应用 蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。 三、神经网络算法（一）神经网络的概念 人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。 特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP 网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。 神经网络的应用 人工神经网络的非线性自适应信息处理能力，克服了传统人工智能方法的直觉，作为模型，语音识别，非结构化信息处理方面的缺陷，使神经网络专家系统，模式识别，智能控制，组合优化，预测等领域得到成功应用。人工神经网络和其他传统方法相结合，将促进人工智能和信息处理技术的发展。近年来，人工神经网络模拟人类认知方式更深入的发展，模糊系统，遗传算法，进化机制相结合，形成智能计算，人工智能，已成为一个重要的方向，在实际的应用开发。信息几何学应用于人工神经网络的研究，人工神经网络理论开辟了一条新的途径。 机器人路径规划算法有很多，可以说有优点和缺点，目前还没有一个算法可以应用于任何场合。因此，各种新的算法被提出，一方面丰富了解决问题的手段，不同的情况下都能找到一个合适的算法；另一方面也不断吸收新的理论，促进学科发展。一个很好的算法，理论深度不高，但其使用；相反，原理简单，计算效率的算法是更容易被接受，关键是看最后达到的效果。（作者单位：柳州城市职业学院）