基于序列二次规划算法的再入轨迹优化研究
航 天 控 制Aer os pace Contr ol Dec 12009Vol 127,No .6
基于序列二次规划算法的再入轨迹优化研究
3
郑总准1
吴
浩2
王永骥
1
1.华中科技大学控制科学与工程系,武汉430074
2.北京航天自动控制研究所,北京100854
摘 要 介绍了序列二次规划算法在飞行器再入轨迹优化问题中的应用。首先
引入了能量替代变量对无量纲运动方程进行推导,使得运动方程和优化问题易于处理,考虑严格的过程约束和终端约束,以攻角和倾侧角为控制变量,总加热量最小为性能指标;然后通过直接配点法将最优控制问题转化为非线性规划问题,选取各节点的状态量和控制量作为优化参数;最后应用序列二次规划算法对非线性规划问题进行求解。针对多约束的再入飞行器的轨迹优化时对初值敏感的问题,提出一种参考轨迹快速规划算法,提高了优化速度。仿真结果表明提出的方法能够较快地搜索到最优轨迹,满足所有约束且落点精度高。关键词 轨迹优化;非线性规划;配点法;序列二次优化;参考轨迹中图分类号:V412 文献标识码:A 文章编号:100623242(2009)0620008206
3国家自然科学基金(60674105);教育部科研培育项目(20081383)和航天支撑基金(2008)资助
收稿日期:2008212212
作者简介:郑总准(1983-),男,福建福州人,博士研究生,研究方向为飞行器轨迹优化、制导与控制;吴 浩(1980-),男,湖北武汉人,博士,研究方向为飞行器制导与控制;王永骥(1955-),男,江西吉安人,教授,博士生导师,研究方向为网络控制、飞行器制导与控制。
Reen try Tra jectory O pti m i za ti on Usi n g Sequen ti a l
Quadra ti c Programm i n g
Z HE NG Z ongzhun 1
WU Hao 2
WANG Yongji
1
1.Huazhong University of Science and Technol ogy,W uhan 430074,China
2.Beijing Aer os pace Aut omati on Contr ol I nstitute,Beijing 100854,China
Abstract Sequen tial quadratic programm ing for trajectory opti m iza tion of reentry vehicle is proposed .
F irstly,Equations of m otion a re nor m a lized and an independen t variable is introduced to reduce the difficul 2ty of iterative co m putation .W ith the angle of a ttack and the bank ang le as control variables,the opti m al control proble m is set to m ini m ize hea t index,considering strict process and ter m inal constraints .A nd then,by choosing states and controls of discrete nodes as param eters,the opti m al control proble m is transfor m ed into a nonlinear programm ing proble m using direct colloca tion m ethod .F inally,sequential quadratic pro 2gramm ing is presented for solving the non linea r programm ing proble m.A ccord ing to the sensitivity to initial value in trajectory opti m ization for reen try vehicles w ith m ulti 2constraint,this paper develops a rapid refer 2ence trajectory prog ramm ing strategy .S i m ulation results sho w that the opti m al trajectory can consistently a 2chieve the desired target conditions w ithin allo w able tolerances and satisfy all the other constraints effectively .
Key words Tra jectory opti m ization;N onlinear prog ramm ing;D irect colloca tion m ethod;Sequential
?
8?
第27卷 第6期郑总准等:基于序列二次规划算法的再入轨迹优化研究quadratic programm ing;R eference tra jectory
再入飞行轨迹优化作为研发先进飞行器的关键技术之一,是飞行器总体设计和规划中的重要组成部分。轨迹优化可表述为一个非线性、带有控制约束、终端约束以及轨道约束的最优控制问题,即泛函的条件极值问题。由于问题高度非线性等原因,最优控制量的解析形式很难求得,因此轨迹优化问题的数值解法成为研究的重点。
轨迹优化中的数值方法主要可分为间接法和直接法。以Pontryagin极大值原理为代表的间接法,将问题转化为两点边值问题,并采用最速下降法、边值打靶法或临近极值法等进行求解。由于飞行器的高度非线性等原因,且间接法对协态变量的初始值十分敏感,因此难以求得最优控制量的精确解。基于非线性规划理论的直接法,将轨迹的状态和控制变量离散化,从而把最优控制问题转化为参数优化问题,使用非线性规划算法求解。直接法可以克服传统间接法对计算初始值要求过严的缺点,参数优化法、配点法和伪光谱法等转化方法己经被广泛应用,取得了令人注目的成果[1-3]。对于非线性规划问题,目前尚无统一的求解算法,共轭梯度法、拟牛顿法、单纯形法和序列二次规划法(Sequential Quad2 ratic Pr ogra mm ing,S QP)等都是解非线性规划的有效的算法。S QP法对原问题的近似中包含有二阶导数信息,因而在具有全局收敛性的同时保持局部超1次收敛性,被公认为是当今求解光滑的非线性规划问题最优秀的算法之一[4]。
本文通过引入更适合于优化数值算法求解的无量纲替代变量,建立了以总加热量最小作为优化目标的最优控制问题模型,考虑严格的过程约束和终端约束;然后采用直接配点法将最优控制问题转化为非线性规划问题,选取各节点的状态量和控制量作为优化参数;最后应用S QP法对非线性规划问题进行求解。由于选择不同的初始参考轨迹对优化算法的迭代时间和收敛结果具有不可忽视的影响,文章提出一种参考轨迹快速规划算法,提高了收敛速度,得到了满意的效果。
1 轨迹优化问题描述
1.1 运动方程
假设地球是一个均匀球体,考虑地球旋转引起的哥氏力和牵引力的影响,在飞行器侧滑角为零的条件下,文献[5]给出了飞行器的无量纲再入质点
运动方程。
在状态方程中一般采用时间t作为自变量,文中为了避免积分范围对时间的不确定而引入反值能量e替代时间,其表达式为
e=1/R-V2/2(1) e为飞行器单位质量所具有的负值机械能,零势能在无限远处,则飞行器质点运动方程为
d R
d e
=V sinγ(VD-VφV3)-1
dθ
d e
=
V cosγsinψ
R cos<
(VD-VφV3)-1
d<
d e
=
V cosγcosψ
R
(VD-VφV3)-1
d V
d e
=(-D-
sinγ
R2
+φV3)(VD-VφV3)-1(2) dγ
d e
=
1
V
[L cosσ+(V2-
1
R
)
co sγ
R
+φγ3+
φ
γ4](VD-V
φ
V3
)-1
dψ
d e
=
1
V
[
L sinσ
cosγ
+
V2co sγsinψtan<
R
-φψ3+
φ
ψ4](VD-V
φ
V3
)-1
式中,变量R表示飞行器质心距地心的距离,其无
量纲化参数为地球半径R
(R
=6378km);V表示飞
行器相对地球的速度,其无量纲化参数为V
=
g0r0(g0=9.81m/s2);θ,<,γ,ψ分别为经度、纬度、航迹倾角和航迹偏角;σ为倾侧角;式(2)后三项右边的φ函数均是由哥氏力和牵引力引起的附加项。
L和D分别是无量纲的升力加速度和阻力加速度,其表达式为
L=ρ(V0V)2C L S/2m g0
D=ρ(V0V)2C D S/2m g0
(3)
式中,S为飞行器有效面积,C
L
和C
D
分别为升力和阻力系数,可表示为攻角α和马赫数M a的插值函数。大气密度模型为
ρ=ρ
exp(-h/h
s
)(4)
其中,ρ
是海平面标准大气密度,h
s
为标量高度系
数,h=(R-1)r
。
转化后运动方程的积分区间为[e
,e f],起点和终点可以由再入的初始和终端条件唯一确定,且其终端的速度和高度只需满足一个,另一个自然满足,
?
9
?
航 天 控 制2009年
这样处理降低了求解的难度。
1.2 约束条件
飞行器在再入过程中面临着严重的气动受热、
过载及动压问题,为易于控制器的设计,要考虑平衡
滑翔约束。此外,再入段的终端状态受严格约束。
1)热流约束。为了不使表面温度过高,一般需
要对驻点热流的速度加以限制,即
Q
?
=kρV3.15≤Q?max(5)
式中,V为无量纲速度,k为常值系数。
2)过载约束。为了在再入时对飞行器进行保
护,需要对总过载进行限制,即
n=L2+D2≤n max(6)
3)动压约束。根据再入任务的要求,存在最大
动压约束
q=ρ(VV0)2/2≤q max(7)
4)平衡滑翔约束。理想的再入轨迹应该是无
跳跃现象且轨迹倾角变化平滑,即轨道倾角γ≤0,
且γ?≈0。
L co sσ+(V2/R-1/R2)≤0(8)
5)再入终端状态约束。为使飞行器更好地完
成对地攻击任务,终端处的(R,θ,<,V,γ,ψ)均严格
约束。
轨迹优化可表述为一个非线性、带约束的最优
控制问题。本文以再入过程飞行器的总吸热量最小
作为优化目标,即
J=∫e f e0Q?(d e dτ)-1d e(9)
其中,状态量x=[R θ < V γ ψ]T,控制量
u=[α σ]T。通常认为攻角α是马赫数M a的函
数,则问题就归结为求解控制变量σ(e)。
2 直接配点法
直接配点法的基本思想是离散化一个连续轨迹
的状态和控制变量,将节点处的状态和控制量的值
作为一组非线性规划的变量,并且用一组施加在每
个离散的节点上的误差等式约束来描述问题的微分
方程,从而将一个最优控制问题转化成一个具有多
个约束的非线性规划问题。该方法中,两节点间用
多项式代表状态变量随时间的变化关系,并假定控
制量的变化是线性的,误差等式约束和变量范围被
施加到所有的节点上。本文采用直接配点法中的三
阶Si m p s on法。
采用三阶Si m p s on法离散飞行器运动模型非线
性微分方程。将能量e的区间[e
,e f]分为N段(各
个区间的长度可以不相等),每个子区间为[e
i
,
e i+1],记步长h i=e i+1-e i,确定N+1个节点的位
置,并得到离散点初始值。
离散后的约束施加在各个节点和相邻节点的中
点上。在子区间的中点处,
x ci=
x i+x i+1
2
+
h i
8
(f
i
-f i+1)
x?ci=
3(x
i
+x i+1)
2h
i
-
1
4
(f
i
+f i+1)(10)
式中,f
i
,f
i+1
分别表示状态函数f(x,u,e)在第i个
子区间端点处的函数值,即
f i=f(x i,u i,e i)
f i+1=f(x i+1,u i+1,e i+1)(11)
三阶Si m p s on法将每个节点处的状态量和控制
量作为优化决策变量,即
Z=x T
1
,u T1,x T2,u T2,…,x T N,u T N(12)
其中,节点0不优化,只作为已知量参与运算,因此
决策变量个数为(6+1)×N。利用Si m p s on积分公
式在整个子区间上对状态方程积分,得
x i+1=x i+
h i
6
(f
i
+4f ci+f i+1)(13)
Si m p s on法的离散误差是
Δ
i
=x i+1-x i-
h i
6
(f
i
+4f ci+f i+1)(14)
式(14)形成的向量被称为Her m ite2Si m p s on De2
fect向量,它构成系统的非线性等式约束。此时,最
优控制问题转化为求解非线性规划问题。根据上述
思想,采用S QP法寻找满足约束方程组,并使性能
指标达到最优的参数集。
3 序列二次规划
序列二次规划算法的基本思想是在给定的近似
点处通过二次近似逐渐得到一个更好的迭代点,这
需要通过求解二次规划子问题得到,在当前迭代点
处算法通过求解一系列的二次规划子问题,使得迭
代点逐步接近原优化命题的最优点,算法最终收敛
到最优解处。
设f,g,h分别表示目标函数、等式约束和不等
式约束,且均二次连续可微,考虑非线性规划问题
(P):
m in
x∈R n
f(x)
?
1
?
第27卷 第6期郑总准等:基于序列二次规划算法的再入轨迹优化研究g i (x )=0 i =1,2,…,m e h j (x )≥0 j =m e +1,…,m
(15)
对于问题(P ),S QP 算法通过序列地求解一系列的二次规划子问题来逐步得到原问题的最优解。在迭代点x k ,与式(15)对应的二次规划子问题(QP )表示为:
m in d ∈R
n
12
d T B k d + f (x k )T
d g (x k )T d +g (x k )=0
h (x k )T
d +h (x k )≥0
(16)其中,d 为搜索方向, f (x k ), g (x k ), h (x k )分
别表示函数f,g,h 在点x k 处的梯度,矩阵B k 为问题(P )的Lagrange 函数
L (x ,λ,v )=f (x )+λT g (x )-v T
h (x )(17)
在(x k ,λk ,v k )处的Hessian 阵的拟牛顿近似矩阵。由于在实际过程中的二阶导数矩阵信息难以得到,或者需要大量的计算和构造才可以获得,所以在S QP 算法中二阶导数矩阵需要通过拟牛顿矩阵B k 来近似。若能使拟牛顿Hessian 阵B k 良好近似并能不断更新,则可以通过逐次计算子问题(QP )的解而得到问题(P )的稳定解。
为使算法具有收敛性,通常要求矩阵B k 对称正定。然而,以BFGS 公式更新B k 时经常得到非正定的B k +1。Powell 提出了一个修正BFGS 公式,更新方法如下:
B k +1=B k +y ～k y ～k T
y ～k T s k
-B k s k s k T
B k s k T
B k s k
(18)
其中
s k =x k
+1
-x k
y k = x L (x k
+1
,λk +1,v k )- x L (x k ,λk +1,v k )
θ=
1
(s k T
y k
≥βs k T
B k s k )
(1-β)s k T
B k s k s k T
B k s k -s k T
y k
(s k T y k <βs k T
B k s k )
y ～
k =θy k +(1-θ
)B k s k 经验表明以0.1≤β≤0.2为宜。由于β>0和
s k T y ～
k ≥
βs k T B k s k ,故只要B k 是正定的,则B k +1总是正定的。
为确保算法全局收敛,在通过解QP 子问题得到搜索方向d k 后,需要求取搜索步长t 以得到下个迭代点x k +1,搜索步长的选择应使下个迭代点的目标函数值和约束得到较好改善,这就需要评价函数。文中采用罚函数法和一维搜索相结合的方法,取恰当罚函数如下:
F r (x )=f (x )+r ‖g (x )‖1+r ‖m in {0,h (x )}‖1
(19)
其中,罚因子r 是固定而充分大的正数。由沿d k 方向进行对于F r 的一维搜索,可求得满足
F r (x k +t k d k ) (20)的步长t k >0。于是,取下一个迭代点为 x k +1=x k +t k d k (21) 若某次迭代中子问题(16)没有可行解,可引入松弛变量ξi ,ηi ,ζi ,考虑以下的二次规划问题(QP1): m in d ∈R n 12 d T B k d + f (x k )T d +r ∑m e 1 (ξi +ηi ) + ∑ m m e +1 ζj g i (x k )T d +g i (x k )+ξi -ηi =0,i =1,2,…,m e h j (x k )T d +h j (x k )+ζj ≥0,j =m e +1,…,m ξi ≥0,ηi ≥0, i =1,2,…,m e (22)ζj ≥0, j =m e +1,…,m 问题(QP1)等价于无约束最小化问题 F - r (x k ,d )=f (x k )+ f (x k )T d + 12 d T B k d +r ‖g (x k )+ g (x k )T d ‖1+(23) r ‖m in {0,h (x k )}+ h (x k )T d ‖1 的无约束最小化问题,因此问题(QP1)总是存在最优解d k 。进行一维搜索时采用比式(20)更宽松的t 作为t k ,即 F r (x k +t d k ) r (x k ,d k )-F r (x k ) (24) 其中,β为常数,且满足0<β<1。 根据以上结果,使S QP 法具有全局收敛性,但 当x k 接近非常弯曲的可行域边界时,d k 方向几乎是边界的切线方向,由式(20)确定的t k 取值非常小,因而使收敛缓慢,丧失了拟牛顿法应有的局部超1次收敛性,这种现象称为Marat os 效应。这是由于罚函数(19)的非光滑造成的,对此可求解如下二次规划问题(QP2): m in d ∈R n 12 d T B k d +p k T d a k T d +c i (x k )=0,i =1,2,…,m e (25) a k T d +c i (x k )≥0,i =m e +1,…,m 其中 p k = f (x k )+λk +1 T (g ～ k -g k )/2 a k =(g ～ k +g k )/2g k = c (x k ) g ～ k = c (x k +d k ) ? 11? 航 天 控 制2009 年 从而得到与式(24)相对应的条件 F r (x (t )) (27) 并置t k =t,x k +1=x ( t k ),这样可避免Marat os 效应, 保持拟牛顿法具有的快速局部收敛性。 S QP 算法的计算流程图如图1所示。 图1 S QP 算法流程图 4 参考轨迹快速规划 无论间接法或直接法,都需要给定一条初始参考轨迹。对于大多数的优化算法而言,其近似最优解难以保证全局最优,只能在某一可行范围内近似最优,所以参考轨迹对优化计算的速度和结果有较 大的影响。本文提出的参考轨迹规划方法[6] ,能够快速获得基本满足各项约束的参考轨迹,有助于在相对较短的时间内求解轨迹优化问题,提高S QP 算法的收敛速度。 参考轨迹规划算法分为纵向和横向部分分别设 计,利用飞行器的纵向运动只与倾侧角σ的大小有关的特点,在再入走廊中选取适当的高度曲线,使轨迹终端的高度、速度和倾角约束以及纵程满足要求。走廊的下边界由气动加热率约束曲线、动压约束曲线和过载约束曲线组成;上边界由准平衡滑翔约束条件形成。 根据平滑处理后得到的再入走廊的上界R U (V )和下界R L (V ),令指令高度 R C (V )=λH ?R U (V )+(1-λH )?R L (V ) (28) 其中,λH 为[0,1]之间的加权系数,当接近目标点时使高度-速度曲线过渡到(V f ,R f )。在飞行轨迹跟踪R C 的前提下,对方程组(2)进行积分,以速度小于终端速度作为退出条件,以终端的纵程作为指标搜索λH ,直至得到近似满足。 为实现搜索过程中对指令高度R C 的跟踪,利用纵向升力平衡来计算倾侧角σ的大小: L 0=(1/R 2-V 2 /R )co s γL C =L 0+K 1R C -K 2R -K 3V sin γσ=arccos (L C /L ) (29) 其中,L 0根据平衡滑翔条件(8)近似得到,K 1,K 2和K 3为根据粒子群算法寻优得到的系数。 参考轨迹在飞行走廊内的走向如图2所示。为了进一步在侧向上满足横程和航迹偏角约束,还需要确定倾侧角的反向点的个数和位置。传统的方法是采用方向角误差作为侧向再入走廊的边界,侧向 走廊为速度的分段函数[7] ,本文采用两次倾侧反向的策略。 图2 再入参考轨迹 根据求得的σ(e ),对式(2)在[e 0,e f ]进行积 分,可以得到落点的横程和航向偏差,采用黄金分割 ? 21? 航 天 控 制Aer os pace Contr ol Dec12009 Vol127,No.6 法搜索倾侧反向点e 1 ,使横程误差满足要求。但是 仅在e=e 1 时刻进行一次反向并不能同时满足航迹偏角要求,因此需要从目标点附近搜索第2个反向 点e 2使Δψ在允许范围内。事实上,引入e 2 又会带 来很小的横程偏差,所以要在e 1 附近稍稍进行调整第一次反向点的位置。由于每次一维搜索后的偏差 总是小于前次,多次反复迭代调整e 1和e 2 后必然能 够使得横程和速度偏角同时满足约束。 另外,在e 1和e 2 反向后,实际飞行的纵程发生 了变化。因此必须对纵向高度剖面的λ H 进行更新。由式(28)和式(29)可知σ的大小将会改变,重复上述步骤直到所有终端约束完全满足。完成参考轨迹规划所需的时间大约为3s。 5 仿真计算与结果分析 采用非降阶的动力学模型进行仿真计算,以美国X-33飞行器为仿真对象,其再入名义攻角剖面为[5]: α= 45°M a≥ 45-0.612(M a-10)2°2.5 (30) 假设再入点初始状态为:h =121.5km,θ0= 242.99°,<0=-18.26°,v0=7622m/s,γ0=-1.4°, ψ =38.239°;终端约束为:h f=30.427km,v f= 908115m/s,γf=-7.5°,│Δψf│≤5°;热流约束: Q?max=851.169k W/m2;过载约束:n max=2.5g;动压 约束:q max =14364Pa。 根据给定的初始值和约束条件,首先计算参考轨迹,然后将轨迹离散为50个节点,采用S QP法求解最优轨迹。图3为S QP法求得的最优倾侧角曲线(横坐标归一化到[0,1]),终端点高度为301545km,终端速度为906.88m/s,终端速度倾角为-7.267°,速度偏角误差为0.914°,即优化轨迹可以很好地收敛到终端约束值;图4为优化后的高度曲线;图5为速度变化曲线;飞行过程中,热流峰值为800.12k W/m2,最大过载为1.6116g,最大动压为7805.02Pa,均满足约束条件。 再入轨迹优化计算时间开销为63.3s。 本文所研究的再入飞行参考轨迹能够很好的满足高度、经度、纬度、速度、倾角和偏角的终端约束,且精度较高;飞行轨迹严格遵循过程约束,热流峰值、最大过载和最大动压都在约束条件之内,即再入过程中,飞行器不会因为热流过大、过载过大和动压过大而导致失败;再入过程中轨道平缓下降,速度倾角全程小于零,满足准平衡滑翔约束条件。 6 结论 1)针对再入轨迹优化问题,采用直接配点法将 (下转第18页) ? 3 1 ? 航 天 控 制2009 年 图3 单一尺度GPS/I N S 卡尔曼估计和多尺度 分布式融合估计的误差比较 可以看出基于多尺度多传感器的分布式融合估 计能提高位置的校正精度,比在单一尺度上观测所获得的估计效果要好,在实际中有重要的意义。 参 考 文 献 [1] 付梦印,邓志红,张继.Kal m an 滤波理论及其在导航 系统中的应用[M ].北京:科学出版社,2003:74277. [2] Chou K C,W illsky A S .Multiscale Recursive Esti m ati on, Data Fusi on,and Regularizati on [C ]//I EEE Transacti on on Aut omatic Contr ol,1994,39(3):4642487. [3] 潘泉,张磊,崔培玲,张洪才.动态多尺度系统轨迹理 论与应用[M ].北京:科学出版社,2007:65269. [4] 崔华.小波分析及其在信号处理中的应用[D ].西安: 西安电子科技大学,2005:31235. [5] 文成林,周东华.多尺度估计理论及其应用[M ].北 京:清华大学出版社,2002:1602164. (上接第13页) 最优控制问题转化为非线性规划问题,并提出一种 参考轨迹快速规划方法,最后利用S QP 法对非线性规划问题进行求解,得到优化轨迹; 2)仿真表明优化后的再入轨迹严格遵循过程约束条件,终端落点精度较高; 3)参考轨迹规划降低了对变量初始猜测的敏感度,提高了S QP 的寻优能力,具有良好的通用性。 参 考 文 献 [1] Ross IM ,Fahr oo F .Legendre Pseudos pectral App r oxi m a 2 ti ons of Op ti m al Contr ol Pr oble m [C ].Lecture Notes in Contr ol and I nf or mati on Sciences,Sp ringer 2Verlag,Ne w York,2003,295:3272342. [2] Lu P .Entry Guidance f or the X 233Vehicle [J ].Journal of Spacecraft and Rockets,1998,35(3):3422349.[3] Bens on A,Thorvaldsen T,Rao V.D irect Traject ory Op 2 ti m izati on and Co 2state Esti m ati on via an O rthogonal Col 2l ocati on M ethod [J ].Journal of Guidance,Contr ol and Dyna m ics,2006,29(6):143521440. [4] Boggs P T,Tolle J W.Sequential Quadratic Pr ogramm ing [J ].Acta Nu merica,1995,4:1251. [5] Shen Z,Lu P .Onboard Generati on of Three 2di m ensi onal Constrained Entry Traject ories [J ].Journal of Guidance,Contr ol and Dyna m ics,2003,26(1):1102121.[6] 郑总准,谢富强,王永骥.高超声速飞行器多约束参考 轨迹快速规划算法[J ].计算技术与自动化,2009,28 (1):88291. [7] 赵汉元.飞行器再入动力学和制导[M ].长沙:国防 科技大学出版社,1997. [8] Trent A,Venkatara man R,Doman D.Traject ory Genera 2 ti on U sing a Modified Si m p le ShootingMethod [C ].Pr o 2ceedings of the I EEE Aer os pace Conference,2004,4:6213. ? 81? 电子科技大学计算机学院标准实验报告 （实验）课程名称最短路径规划 电子科技大学教务处制表 实验报告 学生姓名：李彦博学号：2902107035 指导教师：陈昆 一、实验项目名称：最短路径规划 二、实验学时：32学时 三、实验原理：Dijkstra算法思想。 四、实验目的：实现最短路径的寻找。 五、实验内容： 1、图的基本概念及实现。 一、图的定义和术语 图是一种数据结构。 ADT Graph{ 数据对象V ：V是据有相同特性的数据元素的集合，称为顶点集。 数据关系R ： R={VR} VR={ 机器人轨迹规划算法的分析 摘要: 本文根据机器人最优轨迹规划的约束与要求，采用了一种新的基于最小耗能的轨迹规划方法。该方法在传统的差分进化算法的基础上，采用样条插值法来获得机器人连续型的最优轨迹。通过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) 航 天 控 制Aer os pace Contr ol Dec 12009Vol 127,No .6 基于序列二次规划算法的再入轨迹优化研究 3 郑总准1 吴 浩2 王永骥 1 1.华中科技大学控制科学与工程系,武汉430074 2.北京航天自动控制研究所,北京100854 摘 要 介绍了序列二次规划算法在飞行器再入轨迹优化问题中的应用。首先 引入了能量替代变量对无量纲运动方程进行推导,使得运动方程和优化问题易于处理,考虑严格的过程约束和终端约束,以攻角和倾侧角为控制变量,总加热量最小为性能指标;然后通过直接配点法将最优控制问题转化为非线性规划问题,选取各节点的状态量和控制量作为优化参数;最后应用序列二次规划算法对非线性规划问题进行求解。针对多约束的再入飞行器的轨迹优化时对初值敏感的问题,提出一种参考轨迹快速规划算法,提高了优化速度。仿真结果表明提出的方法能够较快地搜索到最优轨迹,满足所有约束且落点精度高。关键词 轨迹优化;非线性规划;配点法;序列二次优化;参考轨迹中图分类号:V412 文献标识码:A 文章编号:100623242(2009)0620008206 3国家自然科学基金(60674105);教育部科研培育项目(20081383)和航天支撑基金(2008)资助 收稿日期:2008212212 作者简介:郑总准(1983-),男,福建福州人,博士研究生,研究方向为飞行器轨迹优化、制导与控制;吴 浩(1980-),男,湖北武汉人,博士,研究方向为飞行器制导与控制;王永骥(1955-),男,江西吉安人,教授,博士生导师,研究方向为网络控制、飞行器制导与控制。 Reen try Tra jectory O pti m i za ti on Usi n g Sequen ti a l Quadra ti c Programm i n g Z HE NG Z ongzhun 1 WU Hao 2 WANG Yongji 1 1.Huazhong University of Science and Technol ogy,W uhan 430074,China 2.Beijing Aer os pace Aut omati on Contr ol I nstitute,Beijing 100854,China Abstract Sequen tial quadratic programm ing for trajectory opti m iza tion of reentry vehicle is proposed . F irstly,Equations of m otion a re nor m a lized and an independen t variable is introduced to reduce the difficul 2ty of iterative co m putation .W ith the angle of a ttack and the bank ang le as control variables,the opti m al control proble m is set to m ini m ize hea t index,considering strict process and ter m inal constraints .A nd then,by choosing states and controls of discrete nodes as param eters,the opti m al control proble m is transfor m ed into a nonlinear programm ing proble m using direct colloca tion m ethod .F inally,sequential quadratic pro 2gramm ing is presented for solving the non linea r programm ing proble m.A ccord ing to the sensitivity to initial value in trajectory opti m ization for reen try vehicles w ith m ulti 2constraint,this paper develops a rapid refer 2ence trajectory prog ramm ing strategy .S i m ulation results sho w that the opti m al trajectory can consistently a 2chieve the desired target conditions w ithin allo w able tolerances and satisfy all the other constraints effectively . Key words Tra jectory opti m ization;N onlinear prog ramm ing;D irect colloca tion m ethod;Sequential ? 8? MATLAB实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE，其中AB，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC的蚂蚁分别走过了BCD 和DCB，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁 序列二次规划法 求解一般线性优化问题: 12min (x) h (x)0,i E {1,...,m }s.t.(x)0,i {1,...,m } i i f g I =∈=?? ≥∈=? (1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。 1.1等式约束优化问题的Lagrange-Newton 法 考虑等式约束优化问题 min (x) s.t.h (x)0,E {1,...,m} j f j =∈= (1.2) 其中:,n f R R →:()n i h R R i E →∈都为二阶连续可微的实函数. 记1()((),...,())T m h x h x h x =. 则(1.3)的Lagrange 函数为： 1(,)()*()()*()m T i i i L x u f x u h x f x u h x ==-=-∑ （1.3） 其中12(,,...,)T m u u u u =为拉格朗日乘子向量。 约束函数()h x 的Jacobi 矩阵为：1()()((),...,())T T m A x h x h x h x =?=??. 对（1.3）求导数，可以得到下列方程组： (,)()A()*(,)0(,)()T x u L x u f x x u L x u L x u h x ??? ???-?===?????-???? （1.4） 现在考虑用牛顿法求解非线性方程（1.4）. (,)L x u ?的Jacobi 矩阵为： (,)()(,)() 0T W x u A x N x u A x ?? -= ?-?? 文章编号 2 2 2 一种快速神经网络路径规划算法α 禹建丽? ∏ √ 孙增圻成久洋之 洛阳工学院应用数学系日本冈山理科大学工学部电子工学科 2 清华大学计算机系国家智能技术与系统重点实验室日本冈山理科大学工学部信息工学科 2 摘要本文研究已知障碍物形状和位置环境下的全局路径规划问题给出了一个路径规划算法其能量函数 利用神经网络结构定义根据路径点位于障碍物内外的不同位置选取不同的动态运动方程并针对障碍物的形状设 定各条边的模拟退火初始温度仿真研究表明本文提出的算法计算简单收敛速度快能够避免某些局部极值情 况规划的无碰路径达到了最短无碰路径 关键词全局路径规划能量函数神经网络模拟退火 中图分类号 ×°文献标识码 ΦΑΣΤΑΛΓΟΡΙΤΗΜΦΟΡΠΑΤΗΠΛΑΝΝΙΝΓ ΒΑΣΕΔΟΝΝΕΥΡΑΛΝΕΤ? ΟΡΚ ≠ 2 ? ? ≥ 2 ≥ ∏ ΔεπαρτμεντοφΜατηεματιχσ ΛυοψανγΙνστιτυτεοφΤεχηνολογψ Λυοψανγ ΔεπαρτμεντοφΕλεχτρονιχΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν ΔεπαρτμεντοφΧομπυτερΣχιενχε Τεχηνολογψ ΣτατεΚεψΛαβοφΙντελλιγεντΤεχηνολογψ Σψστεμσ ΤσινγηυαΥνι?ερσιτψ Βει?ινγ ΔεπαρτμεντοφΙνφορματιον ΧομπυτερΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν Αβστραχτ ∏ √ √ √ × ∏ ∏ ∏ ∏ ∏ ∏ 2 ∏ √ × ∏ ∏ ∏ ∏ √ ∏ Κεψωορδσ ∏ ∏ ∏ 1引言Ιντροδυχτιον 机器人路径规划问题可以分为两种一种是基于环境先验完全信息的全局路径规划≈ 另一种是基于传感器信息的局部路径规划≈ ?后者环境是未知或者部分未知的全局路径规划已提出的典型方法有可视图法 ! 图搜索法≈ ! 人工势场法等可视图法的优点是可以求得最短路径但缺乏灵活性并且存在组合爆炸问题图搜索法比较灵活机器人的起始点和目标点的改变不会造成连通图的重新构造但不是任何时候都可以获得最短路径可视图法和图搜索法适用于多边形障碍物的避障路径规划问题但不适用解决圆形障碍物的避障路径规划问题人工势场法的基本思想是通过寻找路径点的能量函数的极小值点而使路径避开障碍物但存在局部极小值问题且不适于寻求最短路径≈ 文献≈ 给出的神经网络路径规划算法我们称为原算法引入网络结构和模拟退火等方法计算简单能避免某些局部极值情况且具有并行性及易于从二维空间推广到三维空间等优点对人工势场法给予了较大的改进但在此算法中由于路径点的总能量函数是由碰撞罚函数和距离函数两部分的和构成的而路径点 第卷第期年月机器人ΡΟΒΟΤ? α收稿日期 路径轨迹规划 （1）加减速控制简述 加减速控制算法的目标是建立加减速过程中速度相对于时间的函数关系式f=V(t)。 按照加减速控制算法与插补算法的先后位置关系，加减速控制方式可分为前加减速控制和后加减速控制。前加减速控制即插补计算前进行加减速运算，其优点在于对合成速度进行控制，不影响位置精度，但是需要预测减速点；后加减速控制即插补计算后进行加减速运算，它是对各插补轴分别进行加减速控制，由于各轴没有协调关系，因此合成位置可能不准确。后加减速控制只适用线性插补，在应用上有很大的局限性。 （2）几种速度控制模型 1）直线加减速速度控制模型 直线加减速是当机床启动、停止或者运动速速改变时，速度将按照一定斜率的直线上升或下降。 数学表达式为：at t +=0)(νν 直线加减速控制算法的主要优点是算法简单，机器人响应快，效率高，适合进行实时运算，但是机器人运动存在柔性冲击，速度的过渡不够平滑。 2）指数加减速速度控制模型 指数加减速是启动或停止时的速度发生突变，并且速度变化随时间按指数规律上升或下降。 速度数学表达式为： 加速时：)1()(τ t c e v t v --= 减速时：τ t c e v t v -=)( 加速度数学表达式为： 加速时：ττ t c e v t a -=)()( 减速时：ττ t c e v t a --=)()( 指数型加减速曲线的优点是数学表达式相对简单，可以实时计算，加减速结 束时加速度变小冲击变小；缺点是启动过程仍存在较大冲击。 2）S 曲线加减速速度控制模型 通过对启动阶段即高速阶段的加速度衰减，来保证电机性能的充分发挥和减小启动冲击。 正常情况下S 曲线加减速的运行过程分为7段：加加速段、匀加速段、减加速段、匀速段、加减速段、匀减速段、减减速段，如下图所示： GIS 环境下的最短路径规划算法 ―――此处最短路理解为路径长度最小的路径 02计算机1班刘继忠 学号：2002374117 1.整体算法说明： 将图的信息用一个邻接矩阵来表达，通过对邻接矩阵的操作来查找最短路进，最短路径的查找采用迪杰斯特拉算法，根据用户给出的必经结点序列、起点、终点进行分段查找。 2.各函数功能及函数调用说明。 1).void Welcome() 程序初始化界面，介绍程序的功能、特点及相关提示 2) void CreatGraph(MGraph *G,char buf[]) 把图用邻接矩阵的形式表示,并进行 初始化。 3).int ShortestPath(MGraph *G,int jump,int end,int avoid[],int P[MAXSIZE][MAXSIZE],int Dist[],int ShPath[])根据用户给出的起点、终点、必经结点、避开结点进行最短路径的分段查找。 4).void Print(int jump,int end,int Dist[],int ShPath[]) 输出找到的最短路径所经的 结点和路径长度。 函数调用图： 3.各函数传入参数及返回值说明： 1).void Welcome() 无传入和返回值 2) void CreatGraph(MGraph *G,char buf[ ]) MGraph *G为主函数中定义的指向存放图的信息的指针变量。 char buf[ ]为主函数中定义的用来存放在图的相关信息录入时的界面信息的数组，以便以后调用查看各结点的信息。 无返回值。 3).int ShortestPath(MGraph *G,int jump,int end,int avoid[],int P[MAXSIZE][MAXSIZE],int Dist[ ],int ShPath[ ]) MGraph *G指向存放图的信息的指针变量。 int jump起点，int end终点，int avoid[ ] 避开结点序列。 int P[MAXSIZE][MAXSIZE]用来记录各点当前找到的最短路径所经过 的结点。 int Dist[ ] 记录各结点的当前找到的最短路径的长度。 int ShPath[ ]用来存放用户需要的最短路径所经的各结点。 返回最短路径查找是否成功的信息。（return SUCCEED；return ERROR）4).void Print(int jump,int end,int Dist[],int ShPath[]) int jump起点，int end终点。 int Dist[ ] 记录各结点的当前找到的最短路径的长度。 int ShPath[ ]用来存放用户需要的最短路径所经的各结点。 无返回值。 4．用户说明： ①源程序经编译连接后运行，出现程序的初始化界面，其内容为介绍程序的 功能、特点及相关提示。如下： Welcome to shortest path searching system. Instructions Function: 1. Personal travelling route choosing. 2. Assistan helper in city's traffic design. 3. Shortes path choose in the comlicated traffic net of the city. Characteristic: It is convient,you could set vital point you must travel,and the point you must avoid. Prompt: If the condition is too secret ,maybe there will have no path available. Designer: Liu jizhong. Complate-data: 2004. 3. 21 CopyRight: Shared program,welcome to improve it. Press anykey to enter the program... ②按任意键进入图的信息录入界面根据提示即可完成图的信息的录入。 最短路径算法及其路径规划中的应用 摘要： 这篇文章把徒步运动的路径规划问题转化为求解图中任意两点间的最短路径问题，进而针对此问题介绍了Floyd算法，对该算法的时间花费进行分析，并介绍了在实际问题中如何灵活运用该算法解决路径决策中遇到的问题。 关键词：路径规划、最短路径、决策、Floyd算法 将实际地图的转化为有向图 在策划一次徒步旅行时，设计正确的旅行的线路特别重要，首先我们必须先要得到那个地区的地图，以便进行后续的线路规划。当我们拿到某一地区的地图时，我们可以把地图上的每一条线路用线段表示，用顶点表示地图上的岔路口，即多条线段的交点，这样就形成了一个由点和线段组成的图。我们可以在每条线段上标上数字，表示两点之间的实际距离，或者表示通过这条路径所需的时间。当然，如果两点之间没有线段相连，我们可以认为距离为无穷大，用∞表示。有时候某些线路是单向的，即只能从一个方向到另一个方向，不能逆行。这种情况在具体的路径设计中非常常见，比如，在繁华的都市内会有一些单行道，在山区景点中，常会出现一些上山索道，这些都是单向线路的常见例子。有时候，沿某条线路的两个方向所需的时间不同，这种例子更为常见，比如上山与下山，顺风与逆风等等。对于这两种情况，我们可以在表示路径的线段上加上箭头表示该路径的方向，形成有向图。 到达v2的距离为8，而从v2到v1的距离为3。 从点v1到v0的距离为5，而从v0到v1的距离 为∞。这种带有箭头的有向图，比不带箭头的无 向图能够表示更一般的情形，可以说无向图只是 有向图的一种特殊情况。 如果我们知道任意两点间的最短路径，这对 我们进行路径规划将会有很大的帮助，但当地图 较为复杂时，凭直觉估计最短路径的方法往往不 可靠，这时就必须借助计算机的强大计算能力，寻找最短路径。下面，我们就以 这种有向图为工具，来探究寻找最短路径的方法。 路径规划的分类： 一、按路径维数 根据医学影像设备的不同，穿刺手术可以分二维和三维影像导航手术。所以根据应用场合的不同，路径规划也可分为二维路径规划和三维路径规划。 二维路径规划主要应用在超声、CT、X 射线等设备的导航手术中，三维路径规划则主要应用在三维超声、MRI 等设备的导航手术中。 二、按路径形式 根据穿刺路径特点，路径规划又可按照路径形式的不同分为: R 型、S 型、H 型和混合型，即整个路径包含两种以上不同路径形式组合。 三、按规划方向 由路径形式可以看出路径是可逆的，即理论上针可以从目标靶点沿原路返回穿刺至入针点。所以根据路径规划方向可分为正向规划和逆向规划。正向规划即从入针点到目标靶点的穿刺规划，逆向规划是利用针路的可逆性，从目标靶点出发穿刺可以选择的入针区域，来优化入针位姿和整个路径。 四、按规划算法 路径规划按算法大体可分为数值法、搜索法和反解法三大类。 五、算法概述 (一)数值法是通过数值计算的方法来优化路径，通常是利用目标函数的最大或最小值来得到最优路径的方 法。 1)概率法是考虑路径误差的随机性，利用数学概率原理计算穿刺成功率最大的路径。 2)目标函数法是考虑一些优化的指标(如路径最短，绕开障碍物等)，建立目标函数，通过计算目 标函数得到最优解。 (二)搜索法是根据路径形式特点，利用计算机的人工智能搜索算法来搜索可行性路径。 1)路线图法主要思想是将自由空间转换成为一维线段所组成的网络,所要找的路径被局限在这个 网络之中,即将路径规划问题转化成图的搜索问题。 i.可视图法是由麻省理工学院的Tomás Lozano-Pérez和IBM研究院的MichaelA.Wesley 于1979年提出的。其最大特点是将障碍物用多边形包围盒来表达。图1表示某一环境 空间，s、g分别称为起始点和目标点。O1和O2表示两个障碍物。图2是构造出的对 应图1的可视图。利用搜索算法规划出从起始点至目标点的最优路径。 学号： 《算法设计与分析B》 大作业 题目多种方法解决多段图的最短 路径问题 学院计算机科学与技术学院专业软件工程 班级 姓名 指导教师 2014 年12 月26 日 多种方法解决多段图的最短路径问题 摘要 多段图的最短路径问题是求从源点到终点的最小代价路径。本文主要描述的是分别用动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况。文章首先阐述了各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运行时间，以之为基础来分析、讨论三者的性能区别。文章最后讲述了若这几种方法运行到有向图中的情况，几种方法的对比和它们比较适应的使用情况的讨论，并给出了自己的建议。 关键字：多段图最短路径问题；动态规划法；分支限界法；贪心法 目录 摘要................................................................. II 1 引言 (1) 2 问题描述 (1) 3 贪心法求解 (2) 3.1 贪心法介绍 (2) 3.2 问题分析 (3) 4 动态规划法求解 (3) 4.1 动态规划法介绍 (3) 4.2 问题分析 (4) 5 分支限界法求解 (5) 5.1 分支限界法介绍 (5) 5.2 问题分析 (5) 6 程序清单 (6) 6.1 源代码 (6) 6.2 结果截图 (9) 7 结果分析 (9) 8 课程体会 (10) 9 参考文献 (10) 1引言 当前社会，关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中，排除其它影响因素，从一个地点到另一点，这个时候必然是希望有一条距离最短的路程来尽量减少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很大的需求，因此，这里我将讨论多段图的最短路径的问题。 大二开设的《数据结构》课程中就包括最短路径这方面问题的讨论。当时老师介绍了分别面向单源（Dijkstra算法）与非单源（Floyd算法）两种问题的算法——这是我们最早的对最短路径方面的理解，也是我们接触的比较早的关于图的问题。 在这学期的《算法设计与分析》课程中，我们学习了很多基本的算法设计技术，蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等，它们把以前学习的诸多方法都命名并归纳分类起来，其中有多种算法都可以用来解决最短路径问题，并且该问题作为一个图的问题，对该问题的继续探讨优化的需求很大、本文将就不同算法在解决该最短路径问题时的不同方法进行对比并给出该问题在不同基础上不同的最终解决方案。由于时间的限制，本文将重点分析动态规划法下的情况，并会对图的情况加以简化、限制，最后会对其它的图做一些拓展。 2问题描述 设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n, 1≤i≤k），使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m（1≤i＜k, 1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。多段图的最短路径问题是求从源点到终点的最小代价路径。 由于多段图将顶点划分为k个互不相交的子集，所以，可以将多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。 这里我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图来说，图中是没有环的存在的。 收稿日期:2004-10-24;修订日期:2005-03-07基金项目:航空科学基金资助(04C 52019) 作者简介:孙丰诚(1979-) 男 山东泰安人 南京航空航天大学能源与动力学院博士 主要从事发动机数字控制方面研究. 第20卷第5期2005年10月 航空动力学报 Journal of Aerospace Power Vol.20No.5 : :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::Oct.2005 文章编号:1000-8055(2005)05-0862-06 基于序列二次规划算法的发动机 性能寻优控制 孙丰诚 孙健国 (南京航空航天大学能源与动力学院 江苏南京210016) 摘要:提出用非线性序列二次规划(SOP Seguential Ouadratic Programming )算法解决发动机性能寻优控制问题,分析了线性规划(LP Linear Programming )算法用于发动机性能寻优的固有缺陷以及SOP 算法的优点,给出了SOP 算法与LP 算法用于最大推力模式和最小油耗模式仿真结果对比曲线,数字仿真实验的结果表明 SOP 算法具有比LP 算法更好的优化效果 在工程实际中有很大的应用潜力,关 键 词:航空~航天推进系统;序列二次规划;线性规划;涡扇发动机;性能优化;最大推力模式; 最小油耗模式 中图分类号:V 231 文献标识码:A Aero -Engine Perf ormance Seeking control Based on Seguential Ouadratic Programming Algorithm SUN Feng -cheng SUN Jian -guo (College of energy and Power engineering Nanjing University of Aeronautics and Astronautics Beijing 210016 China )Abstract :A methodology based on the nonlinear algorithm of Seguential Ouadratic Programming (SOP )in aero -engine performance seeking control was presented .This article is aimed at analyzing the inherent limitation of Linear Programming used for aero -engine performance seeking control and to solve the problem of aero -engine performance optimization using nonlinear SOP method .The results of numerical simulations of maximum thrust mode and minimum fuel consumption mode using SOP and LP respectively show that SOP algorithm has better optimization result than LP algorithm .SOP algorithm has great application potential in engineering . Ke !words :aerospace propulsion system ; Seguential Ouadratic Programming (SOP )algorithm ;Linear Programming (LP )algorithm ;turbofan engine ;performance optimization ;maximum thrust mode ;minimum fuel consumption mode 推进系统性能优化是飞"推综合控制#1$ 研究 中非常重要的一个方面 系统性能优化可以在保 证发动机安全稳定工作的同时 最大限度地提高发动机的工作潜力,在不同飞行任务段 有不同的 MATLAB 实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则（如最小能量消耗，最短行走路线，最短行走时间等），在其工作空间中找到一条从起 始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm ，ACA ），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS ），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos 给出了最大-最小蚂蚁系统（MAX-MINAS ），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE ，其中AB ，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC ，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC 。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC 的蚂蚁分别走过了BCD 和DCB ，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性； （3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制， 最优路径规划算法设计 一、 问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。 兵力机动模型包括行军模型、战斗转移模型、机动能力评估模型。涉及的关键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、行军方案评估与优选等。 最优路径问题又称最短路问题。是网络优化中的基本问题，如TSP 问题等。下面先举例说明该问题。 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 旅行商问题（TSP －traveling salesman problem ） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地？） 最短路问题是组合优化中的经典问题，它是通过数学方法寻找离散时间的最优编排、分组、次序、或筛选等，这类问题可用数学模型描述为 min )(x f ..t s 0)(≥x g D x ∈. 其中，)(x f 为目标函数，)(x g 为约束函数，x 为决策变量，D 表示有限个点组成的集合。 一个组合最优化问题可用三个参数),,(f F D 表示，其中D 表示决策变量的定义域，F 表示可行解区域}0)(,|{≥∈=x g D x x F ，F 中的任何一个元素称为该问 题的可行解，f 表示目标函数，满足}|)(m in{)(*F x x f x f ∈=的可行解*x 称为该问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知，只要将D 中有限个点逐一判别是否满足0)(≥x g 的约束并比较目标值的大小，就可以得到该问题的最优解。 以上述TSP 问题为例，具体阐述组合优化问题： 此模型研究对称TSP 问题,一个商人欲到n 个城市推销产品，两个城市i 和j 之间的距离ji ij d d =，用数学模型描述为 ∑≠j i ij ij x d min 1..1 =∑=n j ij x t s n i ,,2,1Λ=， 1..1 =∑=n i ij x t s n j ,,2,1Λ=， },,,2,1{,2||2,1||,n s n s s x s j i ij Λ?-≤≤-≤∑∈ j i n j i x ij ≠=∈,,,2,1,},1,0{Λ 约束条件决策变量1=ij x 表示商人行走的路线包含从城市i 到j 的路，而0=ij x 表示商人没有选择走这条路；j i ≠的约束可以减少变量的个数，使得模型中共有 )1(-?n n 个决策变量。 每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时间为代价的，在TSP 问题中，用n 个城市的一个排列表示商人按这个排列序推销并返回起点。若固定一个城市为起终点，则需要)!1(-n 个枚举。以计算机s 1可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为：以第1个城市为起点，第2个到达城市有可能是第2个、第3个、……、第25个城市。决定前两个城市的顺序后，余下是23个城市的所有排列，枚举这23个城市的排列需要s 1，所以，25个城市的枚举需要24s 。类似地归纳，城市数与计算时间的关系如表1所示。最短路径规划实验报告
机器人轨迹规划算法的分析
基于序列二次规划算法的再入轨迹优化研究
基于蚁群算法的路径规划
二次规划问题
一种快速神经网络路径规划算法概要
路径轨迹规划
GIS环境下的最短路径规划算法
最短路径算法及其在路径规划中的应用
轨迹规划分类及算法
多种方法求多段图的最短路径问题 算法设计与分析课程设计
基于序列二次规划算法的发动机性能寻优控制
(完整word版)基于蚁群算法的路径规划
最优路径规划算法设计报告