【轨迹规划论文整理(1)】UAV轨迹规划的开山之作Minimum Snap Trajectory

【轨迹规划论文整理(1)】UAV轨迹规划的开山之作Minimum Snap Trajectory Generation and Control for Quadrotors

本系列主要是对精读的一些关于无人机、无人车的轨迹搜索论文的整理,包括了论文所拓展的其他一些算法的改进思路。
这是本系列的第一篇文章,也是UAV轨迹规划的开山之作,是所有学习无人机方向的需要精读的第一篇文章,两个作者来自于宾夕法尼亚大学的GRASP Lab,是全球顶尖的机器人团队,也是UAV方向研究的开山鼻祖之一。

Mellinger D , Kumar V .Minimum snap trajectory generation and control for quadrotors[J].IEEE, 2011.DOI:10.1109/ICRA.2011.5980409.

1. Introduction

1.1 轨迹规划的定义

在机器人导航过程中,如何控制机器人从A点移动到B点,通常称之为运动规划。运动规划一般分为两步:

  • 路径搜索:在地图(包括给栅格、八叉树、点云地图等等) 搜索一条从A到B点的路径,这条路径通常是由一系列离散的空间点(waypoint)组成。该部分称之为前端。
  • 轨迹规划:由于路径点可能比较稀疏、而且不平滑,为了更好地控制机器人运动,需要将稀疏的路径点变成平滑的曲线或稠密的轨迹点,即轨迹。这部分称之为后端。

本文的主要工作就是一种无人机轨迹生成的方法,额外还包括了建模和控制器的设计。

2. Model

在这里插入图片描述

图中是本文定义的坐标关系,利用Z-X-Y欧拉角定义横滚角、俯仰角、偏航角(roll,pitch,yaw)作为本地坐标系统。从B至W的旋转矩阵通过 R B W = R C W R B C R_B^W=R_C^WR_B^C RBW=RCWRBC来表示, R C W R_C^W RCW代表偏航角旋转至中间坐标系(Z轴方向与世界坐标Z轴方向一致)。UAV机体在世界坐标系的角速度计算如下,p、q、r分量在记载坐标系中的分量为:

ω B W = p X B + q Y B + r Z B \omega_B^W=pX_B+qY_B+rZ_B ωBW=pXB+qYB+rZB

每个电机有角速度 ω i \omega_i ωi,产生一个力 F i F_i Fi M i M_i Mi,关系为:

F i = k F ω i 2 M i = k M ω i 2 F_i=k_F\omega_i^2 \\ M_i=k_M\omega_i^2 Fi=kFωi2Mi=kMωi2

控制输入记为u, u 1 u_1 u1为净升力, u 2 、 u 3 、 u 4 u_2、u_3、u_4 u2u3u4是机体力矩可以通过电机转速表示为(L是电机旋转中心到电机中心的距离)

u = [ k F k F k F k F 0 k F L 0 − k F L − k F L 0 k F L 0 k M − k M k M − k M ] [ ω 1 2 ω 2 2 ω 3 2 ω 4 2 ] \mathbf{u}=\begin{bmatrix}k_F&k_F&k_F&k_F\\0&k_FL&0&-k_FL\\-k_FL&0&k_FL&0\\k_M&-k_M&k_M&-k_M\end{bmatrix}\begin{bmatrix}\omega_1^2\\\omega_2^2\\\omega_3^2\\\omega_4^2\end{bmatrix} u= kF0kFLkMkFkFL0kMkF0kFLkMkFkFL0kM ω12ω22ω32ω42

机体的线加速度,其中系统受力为 − z W -z_W zW方向上的重力和四个电机的合力为 z B z_B zB方向上的 u 1 u_1 u1

m r ¨ = − m g z W + u 1 z B \begin{aligned}m\ddot{\mathbf{r}}=-mg\mathbf{z}_W+u_1\mathbf{z}_B\end{aligned} mr¨=mgzW+u1zB

用欧拉公式计算角速度如下,其中I是惯性矩矩阵:

ω ˙ B W = I − 1 [ − ω B W × I ω B W + [ u 2 u 3 u 4 ] ] \left.\dot{\omega}_{\mathcal{BW}}=\mathcal{I}^{-1}\left[-\omega_{\mathcal{BW}}\times\mathcal{I}\omega_{\mathcal{BW}}+\left[\begin{array}{c}u_2\\u_3\\u_4\end{array}\right.\right]\right] ω˙BW=I1 ωBW×IωBW+ u2u3u4

UAV系统的状态向量由质心的位置和速度、方向和角速度给出:

X = [ x , y , z , ϕ , θ , ψ , x ˙ , y ˙ , z ˙ , p , q , r ] X=[x,y,z,\phi,\theta,\psi,\dot{x},\dot{y},\dot{z},p,q,r] X=[x,y,z,ϕ,θ,ψ,x˙,y˙,z˙,p,q,r]

3. 微分平坦性

UAV的平坦输出可以写作:

σ = [ x , y , z , ψ ] T \sigma=[x,y,z,\psi]^T σ=[x,y,z,ψ]T

其中 r = [ x , y , z ] T r=[x,y,z]^T r=[x,y,z]T是世界坐标系中质心的坐标,而ψ是偏航角,这里定义轨迹 σ ( t ) \sigma(t) σ(t)为平坦输出空间中的平滑曲线:

σ ( t ) : [ t 0 , t m ] → R 3 × S O ( 2 ) \sigma(t):[t_0,t_m]\to\R^3\times SO(2) σ(t):[t0,tm]R3×SO(2)

根据微分平坦性,系统的状态和控制输入可以用 σ \sigma σ及其导数表示,具体推导参考博客。

4. 控制

本文设计了一个控制器去跟踪特定轨迹 σ T ( t ) = [ r T ( t ) T , ψ T ( t ) ] T \sigma_T(t)=[r_T(t)^T,\psi_T(t)]^T σT(t)=[rT(t)T,ψT(t)]T。首先定义位置和速度误差为

e p = r − r T , e v = r ˙ − r ˙ T e_p=r-r_T,e_v=\dot{r}-\dot{r}_T ep=rrT,ev=r˙r˙T

计算控制器所需要的力矢量:

F d e s = − K p e p − K v e v + m g z W + m r ¨ T F_{des}=-K_pe_p-K_ve_v+mgz_W+m\ddot{r}_T Fdes=KpepKvev+mgzW+mr¨T

将所需的力矢量投影到实际的身体坐标系z轴上,从而计算第一输入的所需力:

u 1 = F d e s ⋅ z B u_1=F_{des}\cdot z_B u1=FdeszB

理想的 Z B , d e s Z_{B,des} ZB,des一定沿着理想推力方向:

Z B , d e s = F d e s ∣ ∣ F d e s ∣ ∣ Z_{B,des}=\frac{F_{des}}{||F_{des}||} ZB,des=∣∣Fdes∣∣Fdes

此时,理想的旋转 R B W R_B^W RBW为:

R d e s e 3 = Z B , d e s R_{des}e_3=Z_{B,des} Rdese3=ZB,des

其他理想状态量:

x C , d e s = [ cos ⁡ ψ T , sin ⁡ ψ T , 0 ] T , and y B , d e s = z B , d e s × x C , d e s ∥ z B , d e s × x C , d e s ∥ , x B , d e s = y B , d e s × z B , d e s , \mathbf{x}_{C,des}=\left[\cos\psi_T, \sin\psi_T, 0\right]^T,\\\text{and}\\\mathbf{y}_{B,des}=\frac{\mathbf{z}_{B,des}\times\mathbf{x}_{C,des}}{\|\mathbf{z}_{B,des}\times\mathbf{x}_{C,des}\|}, \mathbf{x}_{B,des}=\mathbf{y}_{B,des}\times\mathbf{z}_{B,des}, xC,des=[cosψT,sinψT,0]T,andyB,des=zB,des×xC,deszB,des×xC,des,xB,des=yB,des×zB,des,

Z B , X B , Y B Z_B,X_B,Y_B ZB,XB,YB构成了旋转矩阵,从而获得了理想的旋转矩阵

定义旋转误差:

e R = 1 2 ( R d e s T R B W − R B W T R d e s ) ∨ \mathbf{e}_R=\frac{1}{2}(R_{des}^T{}R_B^W-R_B^W{}^TR_{des})^\vee eR=21(RdesTRBWRBWTRdes)

角速度误差(机身系):

e ω = ω − ω T e_\omega=\omega-\omega_T eω=ωωT

另外三个输入的计算如下,两个K都是对角增益矩阵:

[ u 2 , u 3 , u 4 ] T = − K R e R − K ω e ω [u_2,u_3,u_4]^T=-K_Re_R-K_\omega e_\omega [u2,u3,u4]T=KReRKωeω

5. 轨迹生成(本文最重要部分)

生成的轨迹可以写成m个时间间隔上的n阶分段多项式函数:

σ T ( t ) = { ∑ i = 0 n σ T i 1 t i t 0 ≤ t < t 1 ∑ i = 0 n σ T i 2 t i t 1 ≤ t < t 2 ⋮ ∑ i = 0 n σ T i m t i t m − 1 ≤ t ≤ t m \sigma_T(t)=\left\{\begin{array}{cc}\sum_{i=0}^n\sigma_{Ti1}t^i&t_0\leq t<t_1\\\sum_{i=0}^n\sigma_{Ti2}t^i&t_1\leq t<t_2\\\vdots\\\sum_{i=0}^n\sigma_{Tim}t^i&t_{m-1}\leq t\leq t_m\end{array}\right. σT(t)= i=0nσTi1tii=0nσTi2tii=0nσTimtit0t<t1t1t<t2tm1ttm

根据上一节的微分平坦性,这里的 σ T = [ x T , y T , z T , ψ T ] T \sigma_T=[x_T,y_T,z_T,\psi_T]^T σT=[xT,yT,zT,ψT]T σ i = [ x i , y i , z i , ψ i ] T \sigma_i=[x_i,y_i,z_i,\psi_i]^T σi=[xi,yi,zi,ψi]T。上述中要求相邻两段轨迹相同的时间节点是 r T r_T rT微分连续。

建立二次规划问题,c是一个4nm*1的向量,包含了 σ T i j = [ x T i j , y T i j , z T i j , ψ T i j ] T \sigma_{T_{ij}}=[x_{T_{ij}},y_{T_{ij}},z_{T_{ij}},\psi_{T_{ij}}]^T σTij=[xTij,yTij,zTij,ψTij]T及它们的导数:

min ⁡ c T H c + f T c s . t . A c ≤ b \min c^THc+f^Tc\\s.t. Ac\le b mincTHc+fTcs.t.Acb

接下来的解析我觉得文章本身不是很清晰,但是结合深蓝学院的课程和其他博客的思路,重新解读一下。

5.1 一段多项式轨迹

N+1个已知参数点可以拟合N次函数,对于首尾位置、速度、加速度已知的条件(相当于6个已知参数),可以唯一确定一个五次多项式。

5.2 多段多项式轨迹

本文提出了一个经过多个中间航迹点的轨迹,分别使用多个轨迹段进行拟合。但是相对于一段轨迹我们指定了节点的PVA,对于多段轨迹的中间点我们很难给定UAV经过这些航点的VAJ等信息,此时我们将中间速度、加速度等信息看作一个可以自由变化的状态,对于中间状态不确定的问题,可以构建一个优化问题,使得中间状态取得某一个值时,制定的代价函数达到最小值。

Minimum Snap的核心思路就是多端轨迹的中间航点的变量如何取值可以使机器人能量耗费最少。

5.3 Minimum Snap

UAV的轨迹再各个坐标轴上是独立的,因此可以对其分别进行轨迹拟合。即xyz轴上路径生成可以直接将三个轴合成就得到一个完整的空间轨迹。下面的推导均在一维上进行。

第m段轨迹表示如下:

P m ( t ) = p m , 0 t 0 + p m , 1 t 1 + ⋯ + p m , N t N = [ p m , 0 p m , 1 ⋯ p m , N ] [ t 0 t 1 ⋮ t N ] \mathrm{P_m\left(t\right)=p_{m,0}t^0+p_{m,1}t^1+\cdots+p_{m,N}t^N}\\=\begin{bmatrix}\mathrm{p_{m,0}}&\mathrm{p_{m,1}}&\cdots&\mathrm{p_{m,N}}\end{bmatrix}\begin{bmatrix}\mathrm{t^0}\\\mathrm{t^1}\\\vdots\\\mathrm{t^N}\end{bmatrix} Pm(t)=pm,0t0+pm,1t1++pm,NtN=[pm,0pm,1pm,N] t0t1tN

这个多项式就有N+1个未知系数。

对其分别求一阶、二阶、三阶导,获得它的速度、加速度、Jerk函数函数如下:

d P ( t ) d t = [ p m , 0 p m , 1 ⋯ p m , N ] [ 0 1 ⋮ N t N − 1 ]   d 2 P ( t ) d t 2 = [ p m , 0 p m , 1 ⋯ p m , N ] [ 0 1 ∗ 0 2 ∗ 1 ⋮ N ( N − 1 ) t N − 2 ] \begin{aligned}\frac{\mathrm{dP}\left(\mathrm{t}\right)}{\mathrm{dt}}&=\begin{bmatrix}\mathrm{p}_{\mathrm{m},0}&\mathrm{p}_{\mathrm{m},1}&\cdots&\mathrm{p}_{\mathrm{m},\mathrm{N}}\end{bmatrix}\begin{bmatrix}0\\1\\\vdots\\\mathrm{N} \mathrm{t}^{\mathrm{N}-1}\end{bmatrix}\\\\\ \frac{\mathrm{d}^2\mathrm{P}\left(\mathrm{t}\right)}{\mathrm{d}\mathrm{t}^2}&=\begin{bmatrix}\mathrm{p}_{\mathrm{m},0}&\mathrm{p}_{\mathrm{m},1}&\cdots&\mathrm{p}_{\mathrm{m},\mathrm{N}}\end{bmatrix}\begin{bmatrix}0\\1*0\\2*1\\\vdots\\\mathrm{N}\left(\mathrm{N}-1\right)\mathrm{t}^{\mathrm{N}-2}\end{bmatrix}\end{aligned} dtdP(t) dt2d2P(t)=[pm,0pm,1pm,N] 01NtN1 =[pm,0pm,1pm,N] 01021N(N1)tN2

d 3 P ( t ) d t 3 = [ p m , 0 p m , 1 ⋯ p m , N ] [ 0 ∗ 0 ∗ 0 1 ∗ 0 ∗ 0 2 ∗ 1 ∗ 0 ⋮ N ( N − 1 ) ( N − 2 ) t N − 3 ] d 4 P ( t ) d t 4   =   [ p m , 0 p m , 1 ⋯ p m , N ]   [ 0 ∗ 0 ∗ 0 ∗ 0 1 ∗ 0 ∗ 0 ∗ 0 2 ∗ 1 ∗ 0 ∗ 0 3 ∗ 2 ∗ 1 ∗ 0 ⋮ N ( N − 1 ) ( N − 2 ) ( N − 3 ) t N − 4 ] \frac{\mathrm{d}^3\mathrm{P}\left(\mathrm{t}\right)}{\mathrm{d}\mathrm{t}^3}=\begin{bmatrix}\mathrm{p}_{\mathrm{m},0}&\mathrm{p}_{\mathrm{m},1}&\cdots&\mathrm{p}_{\mathrm{m},\mathrm{N}}\end{bmatrix}\begin{bmatrix}0*0*0\\1*0*0\\2*1*0\\\vdots\\\mathrm{N}(\mathrm{N}-1)(\mathrm{N}-2)\mathrm{t}^{\mathrm{N}-3}\end{bmatrix} \\\mathrm{\frac{d^4P(t)}{dt^4}}\:=\:\begin{bmatrix}\mathrm{p_{m,0}}&\mathrm{p_{m,1}}&\cdots&\mathrm{p_{m,N}}\end{bmatrix}\:\begin{bmatrix}0*0*0*0\\1*0*0*0\\2*1*0*0\\3*2*1*0\\\vdots\\\mathrm{N(N-1)(N-2)(N-3)t^{N-4}}\end{bmatrix} dt3d3P(t)=[pm,0pm,1pm,N] 000100210N(N1)(N2)tN3 dt4d4P(t)=[pm,0pm,1pm,N] 0000100021003210N(N1)(N2)(N3)tN4

在论文中提出了一个代价函数 J m J_m Jm,对应的是一段多项式轨迹的四阶导数(snap)平方的积分,具体公式如下:

J m = ∫ T m − 1 T m ( d 4 P ( t ) d t 4 ) 2 = ∫ T m − 1 T m [ p N p N − 1 ⋮ p 0 ] T [ N ( N − 1 ) ( N − 2 ) ( N − 3 ) t N − 4 ⋮ 3 ∗ 2 ∗ 1 ∗ 0 2 ∗ 1 ∗ 0 ∗ 0 1 ∗ 0 ∗ 0 ∗ 0 0 ∗ 0 ∗ 0 ∗ 0 ] [ N ( N − 1 ) ( N − 2 ) ( N − 3 ) t N − 4 ⋮ 3 ∗ 2 ∗ 1 ∗ 0 2 ∗ 1 ∗ 0 ∗ 0 1 ∗ 0 ∗ 0 ∗ 0 0 ∗ 0 ∗ 0 ∗ 0 ] T [ p N ⋮ p N − 1 ⋮ p 0 ] = P m T Q m P m \mathrm{J_m=\int_{T_{m-1}}^{T_m}(\frac{d^4P\left(t\right)}{dt^4})^2}\\=\int_{\mathrm{T_{m-1}}}^{\mathrm{T_m}}\begin{bmatrix}\mathrm{p_N}\\\mathrm{p_{N-1}}\\\vdots\\\mathrm{p_0}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\mathrm{N(N-1)(N-2)(N-3)t^{N-4}}\\\vdots\\3*2*1*0\\2*1*0*0\\1*0*0*0\\0*0*0*0\end{bmatrix}\begin{bmatrix}\mathrm{N(N-1)(N-2)(N-3)t^{N-4}}\\\vdots\\3*2*1*0\\2*1*0*0\\1*0*0*0\\0*0*0*0\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\mathrm{p_N}\\\vdots\\\mathrm{p_{N-1}}\\\vdots\\\mathrm{p_0}\end{bmatrix}\\=P_m^TQ_mP_m Jm=Tm1Tm(dt4d4P(t))2=Tm1Tm pNpN1p0 T N(N1)(N2)(N3)tN43210210010000000 N(N1)(N2)(N3)tN43210210010000000 T pNpN1p0 =PmTQmPm

其中 Q m Q_m Qm如下:

[ N ( N − 1 ) ( N − 2 ) ( N − 3 ) N ( N − 1 ) ( N − 2 ) ( N − 3 ) ( T m − T m − 1 ) N + N − 7 N + N − 7 N ( N − 1 ) ( N − 2 ) ( N − 3 ) ( N − 1 ) ( N − 2 ) ( N − 3 ) ( N − 4 ) ( T m − T m − 1 ) N + N − 1 − 7 N + N − 1 − 7 ⋯ ⋮ ⋮ ⋮ ⋯ i ( i − 1 ) ( i − 2 ) ( i − 3 ) ( i − 1 ) ( i − 2 ) ( T m − T m − 1 ) i + 1 − 7 i + 1 − 7 ⋯ ⋮ ⋮ ⋮ 0 0 ⋯ ] \begin{bmatrix}\frac{\mathrm{N}\left(\mathrm{N}-1\right)\left(\mathrm{N}-2\right)\left(\mathrm{N}-3\right)\mathrm{N}\left(\mathrm{N}-1\right)\left(\mathrm{N}-2\right)\left(\mathrm{N}-3\right)\left(\mathrm{T}_{{\mathrm{m}}}-\mathrm{T}_{{\mathrm{m}-1}}\right)^{{\mathrm{N}+\mathrm{N}-7}}}{\mathrm{N}+\mathrm{N}-7}&\frac{\mathrm{N}\left(\mathrm{N}-1\right)\left(\mathrm{N}-2\right)\left(\mathrm{N}-3\right)\left(\mathrm{N}-1\right)\left(\mathrm{N}-2\right)\left(\mathrm{N}-3\right)\left(\mathrm{N}-4\right)\left(\mathrm{T}_{{\mathrm{m}}}-\mathrm{T}_{{\mathrm{m}-1}}\right)^{{\mathrm{N}+\mathrm{N}-1-7}}}{\mathrm{N}+\mathrm{N}-1-7}&\cdots\\\varvdots&\varvdots&\varvdots\\\cdots&\frac{\mathrm{i}\left(\mathrm{i}-1\right)\left(\mathrm{i}-2\right)\left(\mathrm{i}-3\right)\left(\mathrm{i}-1\right)\left(\mathrm{i}-2\right)\left(\mathrm{T}_{{\mathrm{m}}}-\mathrm{T}_{{\mathrm{m}-1}}\right)^{{\mathrm{i}+1-7}}}{\mathrm{i}+1-7}&\cdots\\\varvdots&\varvdots&\varvdots\\0&0&\cdots\end{bmatrix} N+N7N(N1)(N2)(N3)N(N1)(N2)(N3)(TmTm1)N+N70N+N17N(N1)(N2)(N3)(N1)(N2)(N3)(N4)(TmTm1)N+N17i+17i(i1)(i2)(i3)(i1)(i2)(TmTm1)i+170

上式中 T m − T m − 1 T_m-T_{m-1} TmTm1实际就是该段轨迹运动所用的时长,为了不让每一段轨迹的时间差过大,这里采用相对时间来表示,对于每一段轨迹认为它们的时间都是 ( 0 , T m ) (0,T_m) (0,Tm)

总的代价函数

假设现在有M段轨迹,那么每段轨迹都是一个高阶的多项式函数,写出代价函数如下:

J = J 0 + J 1 + ⋯ + J M = ∑ m = 0 M P m ⃗ T Q m P m ⃗ = [ P 0 P 1 ⋮ P M ] T [ Q 0 0 ⋯ ⋯ 0 0 Q 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋯ ⋮ 0 0 0 ⋯ Q M ] [ P 0 P 1 ⋮ P M ] \begin{gathered}\mathrm{J}=\mathrm{J}_{0}+\mathrm{J}_{1}+\cdots+\mathrm{J}_{\mathrm{M}} \\=\sum_{\mathrm{m=0}}^\mathrm{M}\vec{\mathrm{P_m}}^\mathrm{T}\mathrm{Q_m}\vec{\mathrm{P_m}} \\\left.=\begin{bmatrix}\mathrm{P}_0\\\mathrm{P}_1\\\vdots\\\mathrm{P}_\mathrm{M}\end{bmatrix}\right.^\mathrm{T}\begin{bmatrix}\mathrm{Q}_0&0&\cdots&\cdots&0\\0&\mathrm{Q}_1&0&\cdots&0\\\vdots&\vdots&\vdots&\cdots&\vdots\\0&0&0&\cdots&\mathrm{Q}_\mathrm{M}\end{bmatrix}\begin{bmatrix}\mathrm{P}_0\\\mathrm{P}_1\\\vdots\\\mathrm{P}_\mathrm{M}\end{bmatrix} \end{gathered} J=J0+J1++JM=m=0MPm TQmPm = P0P1PM T Q0000Q100000QM P0P1PM

代价函数完成了,但是还缺少约束,即每个中间航点在前后两段轨迹的速度、加速度或者jerk是连续的,如此运动轨迹才是平滑的。

5.4 约束

连续性约束

限制中间的航迹点在两段轨迹的接合处是左右两边状态连续的,写成数学形式如下:

P m ( k ) ( T m ) = P m + 1 ( k ) ( T m ) P_m^{(k)}(T_m)=P_{m+1}^{(k)}(T_m) Pm(k)(Tm)=Pm+1(k)(Tm)

即轨迹段 P m P_m Pm P m + 1 P_{m+1} Pm+1 T m T_m Tm时刻具有相同的k阶导数。

P m ( k ) ( T m ) = P m + 1 ( k ) ( T m ) ⇒ ∑ i ≥ k i ! ( i − k ) ! T m i − k p m , i − ∑ l ≥ k l ! ( l − k ) ! T m l − k p m + 1 , l = 0 ⇒ [ A m − A m + 1 ] [ P m P m + 1 ] = 0 \begin{aligned}\mathrm{P_{m}^{(k)}(T_{m})=P_{m+1}^{(k)}(T_{m})}\\\Rightarrow\sum_{{\mathrm{i\geq k}}}\frac{\mathrm{i!}}{(\mathrm{i-k})!}\mathrm{T_{m}^{i-k}p_{m,i}-\sum_{{\mathrm{l\geq k}}}\frac{l!}{(l-k)!}T_{m}^{l-k}p_{m+1,l}=0}\\\Rightarrow\begin{bmatrix}\mathrm{A_{m}}&-\mathrm{A_{m+1}}\end{bmatrix}\begin{bmatrix}\mathrm{P_{m}}\\\mathrm{P_{m+1}}\end{bmatrix}=0\end{aligned} Pm(k)(Tm)=Pm+1(k)(Tm)ik(ik)!i!Tmikpm,ilk(lk)!l!Tmlkpm+1,l=0[AmAm+1][PmPm+1]=0

微分约束

启动和终点的PVA使用确定值限制,即 P 0 ( 0 ) , P 0 ( 1 ) ( 0 ) , P 0 ( 2 ) ( 0 ) , P M ( T M ) , P M ( 1 ) ( T M ) , P M ( 2 ) ( T M ) P_0(0),P_0^{(1)}(0),P_0^{(2)}(0),P_M(T_M),P_M^{(1)}(T_M),P_M^{(2)}(T_M) P0(0),P0(1)(0),P0(2)(0),PM(TM),PM(1)(TM),PM(2)(TM)已知。

中间航迹点的位置确定,即 P m ( 0 ) 和 P M ( T m ) P_{m}(0)和P_{M}(T_m) Pm(0)PM(Tm)已知。

融合上述的约束得到:

[ A 0 0 0 0 ⋯ 0 A 0 − A 1 0 0 ⋯ 0 0 A 1 0 0 ⋯ 0 0 A 1 − A 2 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 0 0 0 A M ] [ P 0 P 1 P 2 P 3 ⋮ P M ] = [ d 0 0 d 1 0 ⋮ d M ] \begin{bmatrix}\mathrm{A}_0&0&0&0&\cdots&0\\\mathrm{A}_0&-\mathrm{A}_1&0&0&\cdots&0\\0&\mathrm{A}_1&0&0&\cdots&0\\0&\mathrm{A}_1&-\mathrm{A}_2&0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\0&0&0&0&0&\mathrm{A}_\mathrm{M}\end{bmatrix}\begin{bmatrix}\mathrm{P}_0\\\mathrm{P}_1\\\mathrm{P}_2\\\mathrm{P}_3\\\vdots\\\mathrm{P}_\mathrm{M}\end{bmatrix}=\begin{bmatrix}\mathrm{d}_0\\0\\\mathrm{d}_1\\0\\\vdots\\\mathrm{d}_\mathrm{M}\end{bmatrix} A0A00000A1A1A10000A200000000000AM P0P1P2P3PM = d00d10dM

到此,整个QP问题构建完毕。

5.5 求解QP

多项式轨迹中的系数 p p p没有具体的物理意义,通过无约束方程求解的p可能会出现一些特别小的值,受计算精度影响,导致数值不稳定。

Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments, Charles Richter, Adam Bry, and Nicholas Roy.

为了解决这个系数不稳定的问题,在上文中提出了将系数通过一个映射矩阵转换成轨迹端点的导数,也就是说我们不再优化轨迹的系数,而是对轨迹在端点处的位置、速度、加速度、Jerk等进行优化,由于这些量都是有实际物理含义,不会出现太离谱的数值,所以在一定程度上是比较稳定的。

以最小化Jerk为例,此时是多项式是一个5次多项式轨迹,那么它有6个未知的系数,需要提供轨迹两端的位置、速度、加速度约束,对轨迹进行过次求导:

[ P m ( t ) P m ( 1 ) ( t ) P m ( 2 ) ( t ) ] = [ p m , 5 t 5 p m , 4 t 4 p m , 3 t 3 p m , 2 t 2 p m , 1 t 1 p m , 0 t 0 5 p m , 5 t 4 4 p m , 4 t 3 3 p m , 3 t 2 2 p m , 2 t 1 p m , 1 t 0 0 5 ∗ 4 p m , 5 t 3 4 ∗ 3 p m , 4 t 2 3 ∗ 2 p m , 3 t 1 2 ∗ 1 p m , 2 t 0 0 0 ] = [ t 5 t 4 t 3 t 2 t 1 t 0 5 t 4 4 t 3 3 t 2 2 t 1 t 0 0 5 ∗ 4 t 3 4 ∗ 3 t 2 3 ∗ 2 t 1 2 ∗ 1 t 0 0 0 ] [ p m , 5 p m , 4 p m , 3 p m , 2 p m , 1 p m , 0 ] \begin{aligned}\begin{bmatrix}\mathrm{P}_{\mathrm{m}}\left(\mathrm{t}\right)\\\mathrm{P}_{\mathrm{m}}^{\left(1\right)}\left(\mathrm{t}\right)\\\mathrm{P}_{\mathrm{m}}^{\left(2\right)}\left(\mathrm{t}\right)\end{bmatrix}&=\begin{bmatrix}\mathrm{p}_{\mathrm{m},5}\mathrm{t}^5&\mathrm{p}_{\mathrm{m},4}\mathrm{t}^4&\mathrm{p}_{\mathrm{m},3}\mathrm{t}^3&\mathrm{p}_{\mathrm{m},2}\mathrm{t}^2&\mathrm{p}_{\mathrm{m},1}\mathrm{t}^1&\mathrm{p}_{\mathrm{m},0}\mathrm{t}^0\\5\mathrm{p}_{\mathrm{m},5}\mathrm{t}^4&4\mathrm{p}_{\mathrm{m},4}\mathrm{t}^3&3\mathrm{p}_{\mathrm{m},3}\mathrm{t}^2&2\mathrm{p}_{\mathrm{m},2}\mathrm{t}^1&\mathrm{p}_{\mathrm{m},1}\mathrm{t}^0&0\\5*4\mathrm{p}_{\mathrm{m},5}\mathrm{t}^3&4*3\mathrm{p}_{\mathrm{m},4}\mathrm{t}^2&3*2\mathrm{p}_{\mathrm{m},3}\mathrm{t}^1&2*1\mathrm{p}_{\mathrm{m},2}\mathrm{t}^0&0&0\end{bmatrix}\\&=\begin{bmatrix}\mathrm{t}^5&\mathrm{t}^4&\mathrm{t}^3&\mathrm{t}^2&\mathrm{t}^1&\mathrm{t}^0\\5\mathrm{t}^4&4\mathrm{t}^3&3\mathrm{t}^2&2\mathrm{t}^1&\mathrm{t}^0&0\\5*4\mathrm{t}^3&4*3\mathrm{t}^2&3*2\mathrm{t}^1&2*1\mathrm{t}^0&0&0\end{bmatrix}\begin{bmatrix}\mathrm{p}_{\mathrm{m},5}\\\mathrm{p}_{\mathrm{m},4}\\\mathrm{p}_{\mathrm{m},3}\\\mathrm{p}_{\mathrm{m},2}\\\mathrm{p}_{\mathrm{m},1}\\\mathrm{p}_{\mathrm{m},0}\end{bmatrix}\end{aligned} Pm(t)Pm(1)(t)Pm(2)(t) = pm,5t55pm,5t454pm,5t3pm,4t44pm,4t343pm,4t2pm,3t33pm,3t232pm,3t1pm,2t22pm,2t121pm,2t0pm,1t1pm,1t00pm,0t000 = t55t454t3t44t343t2t33t232t1t22t121t0t1t00t000 pm,5pm,4pm,3pm,2pm,1pm,0

带入两端的时间,得到多项式系数到运动微分的映射关系:

[ P ( 0 ) P ( 1 ) ( 0 ) P ( 2 ) ( 0 ) P ( T ) P ( 1 ) ( T ) P ( 2 ) ( T ) ] = [ 0 5 0 4 0 3 0 2 0 1 0 0 5 ∗ 0 4 4 ∗ 0 3 3 ∗ 0 2 2 ∗ 0 1 0 0 0 5 ∗ 4 ∗ 0 3 4 ∗ 3 ∗ 0 2 3 ∗ 2 ∗ 0 1 2 ∗ 1 ∗ 0 0 0 0 T 5 T 4 T 3 T 2 T 1 T 0 5 ∗ T 4 4 ∗ T 3 3 ∗ T 2 2 ∗ T 1 T 0 0 5 ∗ 4 ∗ T 3 4 ∗ 3 ∗ T 2 3 ∗ 2 ∗ T 1 2 ∗ 1 ∗ T 0 0 0 ] [ p 5 p 4 p 3 p 2 p 1 p 0 ] ⇒ d m = A m P m ⇒ P m = A m − 1 d m \begin{aligned}\begin{bmatrix}\mathrm{P}\left(0\right)\\\mathrm{P}^{\left(1\right)}\left(0\right)\\\mathrm{P}^{\left(2\right)}\left(0\right)\\\mathrm{P}\left(\mathrm{T}\right)\\\mathrm{P}^{\left(1\right)}\left(\mathrm{T}\right)\\\mathrm{P}^{\left(2\right)}\left(\mathrm{T}\right)\end{bmatrix}&=\begin{bmatrix}0^5&0^4&0^3&0^2&0^1&0^0\\5*0^4&4*0^3&3*0^2&2*0^1&0^0&0\\5*4*0^3&4*3*0^2&3*2*0^1&2*1*0^0&0&0\\\mathrm{T}^5&\mathrm{T}^4&\mathrm{T}^3&\mathrm{T}^2&\mathrm{T}^1&\mathrm{T}^0\\5*\mathrm{T}^4&4*\mathrm{T}^3&3*\mathrm{T}^2&2*\mathrm{T}^1&\mathrm{T}^0&0\\5*4*\mathrm{T}^3&4*3*\mathrm{T}^2&3*2*\mathrm{T}^1&2*1*\mathrm{T}^0&0&0\end{bmatrix}\begin{bmatrix}\mathrm{p}_5\\\mathrm{p}_4\\\mathrm{p}_3\\\mathrm{p}_2\\\mathrm{p}_1\\\mathrm{p}_0\end{bmatrix}\\&\Rightarrow\mathrm{d}_{\mathrm{m}}=\mathrm{A}_{\mathrm{m}}\mathrm{P}_{\mathrm{m}}\\&\Rightarrow\mathrm{P}_{\mathrm{m}}=\mathrm{A}_{\mathrm{m}}^{-1}\mathrm{d}_{\mathrm{m}}\end{aligned} P(0)P(1)(0)P(2)(0)P(T)P(1)(T)P(2)(T) = 055045403T55T454T3044034302T44T343T2033023201T33T232T1022012100T22T121T001000T1T000000T000 p5p4p3p2p1p0 dm=AmPmPm=Am1dm

得到映射矩阵:

A m = [ 0 N 0 N − 1 ⋯ 0 2 0 1 0 0 N ∗ 0 N − 1 ( N − 1 ) ∗ 0 N − 2 ⋯ 2 ∗ 0 1 0 0 0 N ( N − 1 ) ∗ 0 N − 2 ( N − 1 ) ( N − 2 ) ∗ 0 N − 3 ⋯ 2 ∗ 1 ∗ 0 0 0 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ T N T N − 1 ⋯ T 2 T 1 T 0 N ∗ T N − 1 ( N − 1 ) ∗ T N − 2 ⋯ 2 ∗ T 1 T 0 0 N ( N − 1 ) ∗ T N − 2 ( N − 1 ) ( N − 2 ) ∗ T N − 3 ⋯ 2 ∗ 1 ∗ T 0 0 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ] \mathrm{A_m=\begin{bmatrix}0^N&0^{N-1}&\cdots&0^2&0^1&0^0\\\mathrm{N*0^{N-1}}&(\mathrm{N-1})*0^{N-2}&\cdots&2*0^1&0^0&0\\\mathrm{N(N-1)*0^{N-2}}&(\mathrm{N-1})(\mathrm{N-2})*0^{N-3}&\cdots&2*1*0^0&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\mathrm{T^N}&\mathrm{T^{N-1}}&\cdots&\mathrm{T^2}&\mathrm{T^1}&\mathrm{T^0}\\\mathrm{N*T^{N-1}}&(\mathrm{N-1})*\mathrm{T^{N-2}}&\cdots&2*\mathrm{T^1}&\mathrm{T^0}&0\\\mathrm{N(N-1)*T^{N-2}}&(\mathrm{N-1})(\mathrm{N-2})*\mathrm{T^{N-3}}&\cdots&2*1*\mathrm{T^0}&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\end{bmatrix}} Am= 0NN0N1N(N1)0N2TNNTN1N(N1)TN20N1(N1)0N2(N1)(N2)0N3TN1(N1)TN2(N1)(N2)TN3022012100T22T121T001000T1T000000T000

将代价函数中的系数向量通过映射矩阵 A m A_m Am进行替换,得到下式:

min ⁡ [ P 0 P 1 ⋮ P M ] T [ Q 0 0 ⋯ ⋯ ⋯ 0 0 Q 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ Q M ] [ P 0 P 1 ⋮ P M ] min ⁡ [ d 1 d 1 ⋮ d M ] T [ A 0 0 ⋯ ⋯ 0 0 A 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ A M ] T [ Q 0 0 ⋯ ⋯ 0 0 Q 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ Q M ] [ A 0 0 ⋯ ⋯ 0 0 A 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ A M ] − 1 [ P 0 P 1 ⋮ P M ] ⇒ min ⁡ d T A − T Q A − 1 d \min\left[\begin{array}{c}\mathrm{P_{0}}\\\mathrm{P_{1}}\\\vdots\\\mathrm{P_{M}}\end{array}\right]^{\mathrm{T}}\begin{bmatrix}\mathrm{Q_{0}}&0&\cdots&\cdots&\cdots&0\\0&\mathrm{Q_{1}}&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&\mathrm{Q_{M}}\end{bmatrix}\begin{bmatrix}\mathrm{P_{0}}\\\mathrm{P_{1}}\\\vdots\\\mathrm{P_{M}}\end{bmatrix}\\\min\left[\begin{array}{c}\mathrm{d_{1}}\\\mathrm{d_{1}}\\\vdots\\\mathrm{d_{M}}\end{array}\right]^{\mathrm{T}}\begin{bmatrix}\mathrm{A_{0}}&0&\cdots&\cdots&0\\0&\mathrm{A_{1}}&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\mathrm{A_{M}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\mathrm{Q_{0}}&0&\cdots&\cdots&0\\0&\mathrm{Q_{1}}&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&\mathrm{Q_{M}}\end{bmatrix}\begin{bmatrix}\mathrm{A_{0}}&0&\cdots&\cdots&0\\0&\mathrm{A_{1}}&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&\mathrm{A_{M}}\end{bmatrix}^{-1}\begin{bmatrix}\mathrm{P_{0}}\\\mathrm{P_{1}}\\\vdots\\\mathrm{P_{M}}\end{bmatrix}\\\Rightarrow\min\mathrm{d^{T}A^{-T}QA^{-1}d} min P0P1PM T Q0000Q10000QM0 P0P1PM min d1d1dM T A0000A100AM00 T Q0000Q100000QM A0000A100000AM 1 P0P1PM mindTATQA1d

如此一来,微分约束已经融入到了PQ问题当中,但是连续性约束还没有引入到代价函数当中。

本文中引入了一个permutation Matrix(置换矩阵)C来将连续性约束引入到代价函数当中。C矩阵本身是一个只包含0和1的矩阵,它的作用是将向量 [ d 0 , d 1 , . . . , d M ] [d_0,d_1,...,d_M] [d0,d1,...,dM]进行一个组合,将固定的变量放在头部,将需要优化的变量放在尾部,并且对于连续性约束的变量值相等,因此只选择其中一个来表达连续性变量。

换言之,首尾状态和中间点航点是已知的设为 d m F d_{mF} dmF,中间点除位置信息外其他状态是代价函数再优化时需要分配的最优值,即需要优化的变量设为 d m P d_{mP} dmP

将置换矩阵带入到代价函数当中:

J = min ⁡ [ d F d P ] T C A − T Q A − 1 C T [ d F d P ] \mathrm{J}=\min\begin{bmatrix}\mathrm{d}_{\mathrm{F}}\\\mathrm{d}_{\mathrm{P}}\end{bmatrix}^{\mathrm{T}}\mathrm{C}\mathrm{A}^{{-\mathrm{T}}}\mathrm{Q}\mathrm{A}^{-1}\mathrm{C}^{\mathrm{T}}\begin{bmatrix}\mathrm{d}_{\mathrm{F}}\\\mathrm{d}_{\mathrm{P}}\end{bmatrix} J=min[dFdP]TCATQA1CT[dFdP]

R = C A − T Q A − 1 C T R=CA^{-T}QA^{-1}C^T R=CATQA1CT。对R矩阵根据 d F d_F dF d P d_P dP的尺寸进行分块,得到如下变换:

J = min ⁡ [ d F d P ] T C A − T Q A − 1 C T [ d F d P ] = J = min ⁡ [ d F d P ] T R [ d F d P ] = min ⁡ [ d F d P ] T [ R F F R F P R P F R P P ] [ d F d P ] = d F T R F F   d F   + d F T R F P   d P   + d P T R P F   d F   + d P T R P P   d P \begin{gathered}\mathrm J=\operatorname*{min}\left[\begin{matrix}{\mathrm d_{\mathrm F}}\\{\mathrm d_{\mathrm P}}\\\end{matrix}\right]^{\mathrm T}\mathrm C\mathrm A^{-\mathrm T}\mathrm Q\mathrm A^{-1}\mathrm C^{\mathrm T}\left[\begin{matrix}{\mathrm d_{\mathrm F}}\\{\mathrm d_{\mathrm P}}\\\end{matrix}\right]=\mathrm J=\operatorname*{min}\left[\begin{matrix}{\mathrm d_{\mathrm F}}\\{\mathrm d_{\mathrm P}}\\\end{matrix}\right]^{\mathrm T}\mathrm R\left[\begin{matrix}{\mathrm d_{\mathrm F}}\\{\mathrm d_{\mathrm P}}\\\end{matrix}\right] \\=\min\begin{bmatrix}\mathrm{d_F}\\\mathrm{d_P}\end{bmatrix}^\mathrm{T}\begin{bmatrix}\mathrm{R_FF}&\mathrm{R_FP}\\\mathrm{R_PF}&\mathrm{R_PP}\end{bmatrix}\begin{bmatrix}\mathrm{d_F}\\\mathrm{d_P}\end{bmatrix} \\=\mathrm{d_F^TR_{FF}~d_F~+d_F^TR_{FP}~d_P~+d_P^TR_{PF}~d_F~+d_P^TR_{PP}~d_P} \end{gathered} J=min[dFdP]TCATQA1CT[dFdP]=J=min[dFdP]TR[dFdP]=min[dFdP]T[RFFRPFRFPRPP][dFdP]=dFTRFF dF +dFTRFP dP +dPTRPF dF +dPTRPP dP

对于上式J是一个标量,并且Q矩阵是对称阵,所以R矩阵也是对称阵,则 R P F = R F P T R_{PF}=R_{FP}^T RPF=RFPT。对于上式我们要求的变量是 d p d_p dp,对其求导得到

∂ J ∂ d P = 2 d F T R F P + 2 R P P   d P = 0 ⇒ d P ∗ = − R P P − 1 R F P T   d F \begin{aligned}\frac{\partial\mathcal{J}}{\partial\mathcal{d}_{{\mathcal{P}}}}&=2\mathrm{d}_{{\mathcal{F}}}^{{\mathcal{T}}}\mathcal{R}_{{\mathcal{F}\mathcal{P}}}+2\mathrm{R}_{{\mathcal{P}\mathcal{P}}}\mathrm{~d}_{{\mathcal{P}}}=0\\&\Rightarrow\mathrm{d}_{{\mathcal{P}}}^{*}=-\mathrm{R}_{{\mathcal{P}\mathcal{P}}}^{-1}\mathrm{R}_{{\mathcal{F}\mathcal{P}}}^{{\mathcal{T}}}\mathrm{~d}_{{\mathcal{F}}}\end{aligned} dPJ=2dFTRFP+2RPP dP=0dP=RPP1RFPT dF

然后反求得到多项式系数:

P   = A − 1 C T   [ d F d P ∗ ] \mathrm{P~=A^{-1}C^T~\begin{bmatrix}d_F\\d_P^*\end{bmatrix}} P =A1CT [dFdP]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/726015.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

人工智能发展历程了解和Tensorflow基础开发环境构建

目录 人工智能的三次浪潮 开发环境介绍 Anaconda Anaconda的下载和安装 下载说明 安装指导 模块介绍 使用Anaconda Navigator Home界面介绍 Environment界面介绍 使用Jupter Notebook 打开Jupter Notebook 配置默认目录 新建文件 两种输入模式 Conda 虚拟环境 添…

参数量Params和每秒浮点运算次数FLOPs的单位是多少

先看一下yolov8的表 模型计算量(FLOPs)和参数量(Params)是衡量深度学习算法复杂度的两个重要指标&#xff0c;它们可以用来评估一个模型的性能和实用性。以下是对这两个指标的理解&#xff1a; 1、Params - 参数量 即模型中需要学习的参数数量&#xff0c;它是衡量模型复杂度的…

Elsevier曝光73篇论文操纵同行评审,涉嫌操纵同行评审和人为引用

近日&#xff0c;全球知名学术出版商爱思唯尔&#xff08;Elsevier&#xff09;旗下期刊《Engineering Analysis with Boundary Elements》对73篇论文发出了关注声明&#xff0c;这些论文涉嫌操纵同行评审和人为引用。去年7月&#xff0c;该期刊前编委Masoud Afrand被指涉嫌论文…

第 7 章: 对象关系映射

在第 6 章中&#xff0c;我们大概了解了如何通过 JDBC 来进行简单的数据库操作。通过 SQL 来执行操作虽然不算复杂&#xff0c;但在面向对象的语言中&#xff0c;这类操作多少显得有些格格不入&#xff0c;毕竟我们都是在与“对象”打交道。把对象与关系型数据库关联起来&#…

VMare连接Centos7无法连接网络

VMare连接Centos7无法连接网络 打开ifcfg-ens33文件检查ONBOOT是否为yes&#xff0c;如果是no需要修改成yes vi /ect/syscong ig/network-scripts/ifcfg-ens33 保存后输入ip a命令&#xff0c;能看到自己的ip就是成功了 ip就是成功了

C++ | Leetcode C++题解之第165题比较版本号

题目&#xff1a; 题解&#xff1a; class Solution { public:int compareVersion(string version1, string version2) {int n version1.length(), m version2.length();int i 0, j 0;while (i < n || j < m) {long long x 0;for (; i < n && version1[…

leetCode-hot100-链表专题

leetCode-hot100-链表专题 链表简介单链表单链表的使用例题206.反转链表19.删除链表的倒数第N个结点24.两两交换链表中的节点25.K个一组翻转链表 双向链表双向链表的使用 循环链表61.旋转链表141.环形链表142.环形链表Ⅱ LinkedListLinkedList的使用 链表简介 参考博客&#x…

泛微开发修炼之旅--21关于泛微Ecology实现CAS服务端支持内网认证重定向至内网,外网认证重定向至外网的解决方案

文章详情链接&#xff1a;http://21关于泛微Ecology实现CAS服务端支持内网认证重定向至内网&#xff0c;外网认证重定向至外网的解决方案

秋招突击——6/16——复习{(单调队列优化DP)——最大子序和,背包模型——宠物小精灵收服问题}——新作{二叉树的后序遍历}

文章目录 引言复习&#xff08;单调队列优化DP&#xff09;——最大子序和单调队列的基本实现思路——求可移动窗口中的最值总结 背包模型——宠物小精灵收服问题思路分析参考思路分析 新作二叉树的后续遍历加指针调换 总结 引言 复习 &#xff08;单调队列优化DP&#xff09…

修改yarn、npm、pnpm为国内镜像源

国内由于网络的原因&#xff0c;使用官方的npm、yarn、pnpm访问下载依赖库会很慢&#xff0c;有时候还会出现无法访问的情况&#xff0c;这时候就需要我们给npm、yarn、pnpm换一个国内的镜像源的&#xff0c;一般的我们可以将镜像换成淘宝的源&#xff0c;由于平时比较常用到的…

Vue65-组件之间的传值

1、收数据 2、传数据 3、批量的数据替换 若是info里面有四个数据&#xff0c;传过来的dataObj里面有三个数据&#xff0c;则info里面也只有三个数据了 解决方式&#xff1a; 该写法还有一个优势&#xff1a;传参的时候&#xff0c;顺序可以随意&#xff01;

谈论实时摄像头的稳定性,防抖算法

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

C语言的基本输入输出函数+构造类型数据——数组

C语言的基本输入输出函数 1. 字符输入输出函数 getchar()、putchar() getchar()&#xff1a;从标准输入&#xff08;通常是键盘&#xff09;读取一个字符&#xff0c;并返回其ASCII值。putchar()&#xff1a;将指定的字符&#xff08;由其ASCII值表示&#xff09;写入标准输出…

模版与策略模式

一&#xff0c;怎么选择 如果需要固定的执行流程&#xff0c;选模版 如果不需要固定的执行流程&#xff0c;只需要对一个方法做具体抽象&#xff0c;选策略 参考文章&#xff1a; 常用设计模式汇总&#xff0c;告诉你如何学习设计模式 二&#xff0c;常用写法 子类 exten…

龙讯旷腾PWmat计算vdW异质结中热载流子冷却 | 复刻《Phys. Chem. Chem. Phys 》文献

01 NAMD 背景介绍 在各类光物理与光化学过程当中&#xff0c;均会牵涉到激发态载流子动力学过程&#xff0c;诸如电荷弛豫、复合以及输运等等。光激发或者电子注入将初始的平衡状态打破&#xff0c;所产生的热载流子在其演化进程中&#xff0c;会与原子核产生强烈耦合。此时&a…

关于车规级功率器件热可靠性测试的分享

随着中国电动汽车市场的稳步快速发展和各大车企布局新能源的扩散&#xff0c;推动了车规级功率器件的快速增长。新能源汽车行业和消费电子都会用到半导体芯片&#xff0c;但车规级芯片对外部环境要求很高&#xff0c;涉及到的一致性和可靠性均要大于工业级产品要求&#xff0c;…

利用Systemverilog+UVM搭建SOC及ASIC的RTL验证环境

在集成电路设计的复杂世界中&#xff0c;验证环节是确保设计满足预期功能和性能要求的关键步骤。随着系统级芯片&#xff08;SOC&#xff09;和特定应用集成电路&#xff08;ASIC&#xff09;的规模和复杂性不断增加&#xff0c;传统的验证方法已经难以满足高效、准确的验证需求…

基于顺序表的排序

任务内容 基于一个顺序表&#xff0c;实现如下排序算法&#xff1a; 直接插入排序&#xff1b;交换排序 &#xff08;冒泡&#xff09;&#xff1b;简单选择排序 代码实现 #include<iostream> #include<string> using namespace std; #define keytype int type…

Javaweb登录校验

登录校验 JWT令牌的相关操作需要添加相关依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version> </dependency>一、摘要 场景&#xff1a;当我们想要访问一个网站时&am…

真空玻璃可见光透射比检测 玻璃制品检测 玻璃器皿检测

建筑玻璃检测 防火玻璃、钢化玻璃、夹层玻璃、均质钢化玻璃、平板玻璃、中空玻璃、真空玻璃、镀膜玻璃夹丝玻璃、光栅玻璃、压花玻璃、建筑用U形玻璃、镶嵌玻璃、玻璃幕墙等 工业玻璃检测 钢化安全玻璃、电加温玻璃、玻璃、半钢化玻璃、视镜玻璃、汽车安全玻璃、汽车后窗电热…