Two Approaches for Path Planning of Unmanned Aerial Vehicles with Avoidance Zones

Chuangchuang Sun，Yen-Chen Liu，Ran Dai等
Iowa State University(爱荷华州立大学)，AFRL(美国空军研究实验室)
JOURNAL OF GUIDANCE, CONTROL, AND DYNAMICS，2017-5-29

文章结构

1. 这里是列表文本引言
   
2. 问题建模
   
3. 数值优化法
     3.1 运动规划问题转化为QCQP问题：采用数值微分的方法将问题离散化，消除约束中的三角函数，将NLP问题转化为非凸QCQP问题
     3.2 使用IRM法求解一般QCQP问题
   
4. 启发式搜索法
     4.1 RRT算法
     4.2 改进的RRT算法
   
5. 仿真验证
   
6. 结论
   

收获

1. 求解一般QCQP问题的方法——IRM

  如果遇到的QCQP问题是非齐次的，通过引入一个新变量$\alpha \in \mathbb{R}$和一个新约束$\alpha^{2}=1$，将非齐次QCQP问题转化为齐次QCQP问题

$$ \begin{aligned} J=\mathrm{min}_{X} & \left \langle X,Q_{0} \right \rangle \\\\ \mathrm{s.t.} \left \langle X,Q_{j} \right \rangle \leqslant c_{j}, & \forall j=1,...,m \end{aligned} $$

将齐次QCQP问题转化为半定规划问题(semidefinite programming，SDP)

$$\begin{aligned} J=\mathrm{min}_{X} & \left \langle X,Q_{0} \right \rangle \\\\ \mathrm{s.t.} \left \langle X,Q_{j} \right \rangle \leqslant c_{j}, & \forall j=1,...,m \\\\ X \succcurlyeq & 0 \end{aligned}$$

  已知，当$X$是非零正定矩阵时，$X$是秩1矩阵的充要条件为$rI_{n-1}-V^{T} XV \succcurlyeq 0$，其中$V \in \mathbb{R}^{n \times (n-1)}$是$X$的$n-1$个较小特征值所对应的特征向量组成的矩阵，$r$是趋于0的正数。IRM法(The iterative rank minimization algorithm)通过迭代的方法，逐渐减小$X$的秩。所以可以将上述SDP问题转化为下面的凸优化问题

$$\begin{aligned} J=\mathrm{min}_{X_{k},r_{k}} & \left \langle X_{k}, Q_{0} \right \rangle + w^{k}r_{k} \\\\ \mathrm{s.t.} \left \langle X,Q_{j} \right \rangle \leqslant c_{j}, & \forall j=1,...,m \\\\ X_{k} \succcurlyeq & 0 \\\\ r_{k}I_{n-1}-V_{k-1}^{T} & X_{k}V_{k-1} \succcurlyeq 0 \end{aligned}$$

其中，$w>1$为$r_k$的权重系数。   IRM法通过求解上面的SDP问题获得$X_{0}$，通过$X_{0}$求得$V_{0}$，然后通过求解问题(3)获得$X_{k}$，求得$V_{k}$，不断迭代直到$r_{k}$足够小。 关于这一收获我总结并在微信上发表帖子——使用IRM法求解一般QCQP问题

2. CVX使用时的注意事项 约束中不能出现$x_{1}=0,x_{2}=2$等等这样的常数约束，添加这样的约束可能会出现以下警告和错误

• 警告: 秩亏，秩 = ×××，tol = ×××。
• 错误使用 eig 输入矩阵包含 NaN 或 Inf。
• 错误使用 eig 输出参数太多。当输入矩阵为稀疏矩阵时，仅支持一个输出参数。请使用 eigs 计算稀疏矩阵的特征向量和特征值的子集。

3. 考虑运动学的改进的RRTstar算法

• 先使用传统RRTstar算法求解一条可行路径$P$，Path_Opt()函数以$P$为输入，从路径$P$上随机采样不共线两点$p_{1},p_{2}$，如果$p_{1},p_{2}$连线不与障碍物冲突，用$p_{1},p_{2}$代替$p_{1},p_{2}$间的原本可行路径$P$中的路径点，这样可以求出一条比路径$P$短的路径。
• Steering_eval()函数判断路径是否满足方向角速率$\dot{\theta}$约束。路径上三个相邻点组成一个圆弧$s$，圆心角$\theta$除以通过该段圆弧所用时间$t$近似等于$\dot{\theta}$

优缺点

• 优点：本文将无人机路径规划这一非线性规划问题（NLP）转化为一般二次约束二次规划问题（QCQP），并使用IRM方法求解该QCQP问题。本文的方法不需要给定初值并且在保证线性收敛速率的情况下收敛到局部最小解，克服了NLP求解器和配点法（Collocation Method）初值难猜测和收敛到局部最小值速度很慢，甚至有时不能收敛到可行解的问题。
• 缺点：离散点多了之后，运算速度也很慢（论文中一个障碍，20个离散点运算时间也要几分钟）

难理解的句子

The novelty of QCQP formulation and its associated iterative method is that it does not involve linearization procedures in the formulation and optimization approach such that it will present errors generated from linearization of a highly nonlinear model. 将问题转化为QCQP问题并用相关联的迭代方法求解的新颖性体现在，它在建模和优化求解过程中不包括线性化过程，所以该方法能展现高非线性模型线性化带来的误差

参考

[1] Sun C , Liu Y C , Dai R , et al. Two Approaches for Path Planning of Unmanned Aerial Vehicles with Avoidance Zones[J]. Journal of Guidance Control & Dynamics, 2017, 40(8).
[2] Sun C , Dai R . An iterative approach to Rank Minimization Problems[C]// Decision & Control. IEEE, 2016.