DMPC
论文：《Trajectory Generation for Multiagent Point-To-Point
Transitions via Distributed Model Predictive Control》
摘要
- 介绍了 一种基于分布式模型预测控制（DMPC）的多智能体offline轨迹生成算法。
- 通过预测未来状态并与附近的agents共享此消息，agent 能够在朝着目标前进的同时检测并进行避障。
- 提出的算法以分布式（distributed）方式实现，与基于顺序凸规划（sequential convex programming）SCP的优化方法相比计算时间减少了85%，同时对最优性的影响最小。
介绍
-
Multiagent point-to-point transition：多智能体点对点的转换有两个变量
- the labelled agent problem：每一个agent都有一个固定的不能与另外一个agent交换的固定的最终位置。（本文着重讨论的）
- the unlabelled agent problem：算法可以自由的将goals分配给agents，以减轻转换问题的复杂度。
-
the labelled agent problem的解决方法：
- 将他看做一个优化问题，比如混合整数线性规划MILP（Mixed Integer Linear Programming），使用二进制变量（0和1）构建碰撞约束。有一个致命的缺点就是计算复杂度太大，导致不适用于多agents。
- 顺序凸规划SCP比MILP的计算时间少，而且SCP是用于计算四旋翼集群的最佳能量轨迹；但是缺点也很明显，就是算法不能随着agent的数量增加而扩展，但是好像最近提出了一种decoupled版本的SCP，但是随着agent的增加，成功率也下降了。
- 分布式优化方法与集中式方法相比减少了计算时间。ORCA利用速度障碍（velocity obstacles）来雀儿包完整性agent和非完整性agent的无碰撞轨迹。因为他假设在一段时间内具有恒定的速度，所以该方法比较保守（conservative）。
- 关于本文介绍的DMPC。
问题陈述
the agents
\[p_i[k+1]=p_i[k]+hv_i[k]+\frac{h^2}{2}a_i[k] \]\[v_i[k+1]=v_i[k]+ha_i[k] \]第i个agent在k时刻的position、velocity、acceleration。其中\(a_i[k]\)是输入，h是离散化步骤h（discretization step h）。
Constraints
首先约束驱动约束：
- 加速度有一个最大和最小的约束
- 因为是在室内（indoor）进行试验，位置会有一个范围约束
Collision Avoidance
agent i和agent j之间的碰撞约束为：
\[\Vert\Theta^{-1}(p_i[k]-p_j[k]) \Vert_n \geq r_{min} \]n一般取2，rmin就是agent之间的最小距离，\(\Theta\)是缩放矩阵（scaling matrix），定义为\(\Theta=diag(a,b,c)\)，a=b=1，c>1，这样的话就会要求竖直轴（z轴）方向上的最小距离为rz,min=crmin。
DMPC
在问题陈述部分提出的问题，可以看做一个优化问题，在每个时间步进解决一个问题，该问题基于描述agent动力学模型在给定的预测范围内找到最佳输入序列。该序列的第一个输入应用于真实系统并且测量结果状态（resulting state），这是下一个优化问题的起点（starting point）。但是这篇文章在输入之后不测量agents的状态，因为还没有布置实际的agent，而是将输入直接应用于模型用来计算生成下一步的轨迹。重复上一步直到生成全部的轨迹。
所以我们以分布式方式应用，就是让每个agent执行上述的迭代的优化问题去生成轨迹，并且和临近的agent分享信息。
Synchronous Algorithm
计算新的输入序列步骤：
-
使用在k~i~-1步计算的临近的agent的最新预测状态检查未来是否会发生碰撞。
-
构建包括状态（state）、动力（actuation）以及碰撞（collision）在内的约束优化问题。
-
在获得下一个最优序列之后，将序列的第一个元素应用于模型，agent向前移动一步。
The Agent Prediction Model
数学公式太难打了，大致的思想就是自己定义了一个算数运算符\([k\vert k_t]\)，然后代到上面（1）（2）式子中去，
后面的东西就看不懂了。
Objective Function
目标函数主要有三个组成部分：
-
轨迹误差（trajectory error）
这一部分主要是驱使agent到达goal，定义误差和为$$e_i=\sum^K_{k=K-j}\Vert p_i[k\vert k_t]-p_{d,i}\Vert_2$$
其中j为最后的time step，\(p_{d,i}\)是desired final position。
j越大，会导致agent的行为比较激进，agent会更快的朝着目标移动，但是也可能会导致目标位置超调（overshoot）
我在这里盲猜一手激进的j选取会导致collision constraint很难满足。
-
控制作用（control effort）
-
输入变化（input variation）
用于最小化加速度的变化，从而生成平滑的输入轨迹
其中u是输入，只能写到这了，后面是能力有限。
-
物理限制（Physical Limits）
就是前面驱动约束：提到的constraint
-
凸优化问题，无碰撞（Convex Optimization Problem）
把上面所有目标函数和约束结合起来可以看成一个3K决策变量和12K个不等式约束的二次规划问题。
