文献：Fast Iterative Region Inflation for Computing Large 2-D/3-D Convex Regions of Obstacle-Free Space
期刊：IEEE Transactions on Robotics（IEEE-TRO），2025
作者：Qianhao Wang, Zhepei Wang, Mingyang Wang, Jialin Ji, Zhichao Han, Tianyue Wu, Rui Jin, Yuman Gao, Chao Xu, Fei Gao
IEEE Xplore：https://ieeexplore.ieee.org/document/10970076
相关开源实现参考：GCOPTER 中的旧版 FIRI：https://github.com/ZJU-FAST-Lab/GCOPTER/blob/main/gcopter/include/gcopter/firi.hpp；SDQP：https://github.com/ZJU-FAST-Lab/SDQP

---

1. 论文定位与核心结论

这篇论文研究的不是“如何直接规划一条轨迹”，而是轨迹规划前端与后端之间一个非常关键的几何抽象问题：如何从大量离散障碍物中快速构造一个尽可能大的、无碰撞的凸区域，并且保证这个凸区域必须包含给定的种子集合。种子可以是一个点、一段前端路径，也可以是具有实际尺寸的机器人几何形状。

论文将这一能力概括为三个同时需要满足的指标：

• Quality（质量）：生成的自由凸多面体应尽可能大，为后续轨迹优化提供更大的可行空间；
• Efficiency（效率）：应能在大量障碍点或多面体约束下快速计算，满足在线规划需求；
• Manageability（可控包含性）：生成区域必须可靠地包含指定种子，而不是只追求“某个大区域”。

FIRI 的核心思路是交替执行两个模块：Restrictive Inflation（RsI，限制性膨胀） 与 Maximum Volume Inscribed Ellipsoid（MVIE，最大体积内接椭球）。RsI 保证种子始终被包含、障碍物始终被排除；MVIE 则作为凸区域体积的可计算下界，通过迭代不断增大该下界。为了避免通用 QP、SDP/SOCP 求解器在“大量约束、小变量维度”问题上的高开销，作者又分别设计了 SDMN、基于 SOCP 的仿射缩放求解方法，以及二维场景下的线性复杂度解析 MVIE 算法。

图1 自由凸多面体的质量与可控包含性。 上部说明更大的凸区域能够给轨迹优化提供更充分的空间；下部说明若无法保证包含前端路径段或机器人本体，安全走廊可能出现断裂或直接失去可行解。图源：论文 Fig. 1。

图1实际上给出了全文的研究动机。传统方法通常只在“区域尽可能大”和“计算尽可能快”之间折中，而 FIRI 额外把“必须包含我指定的几何对象”作为算法本身的硬约束。这一点对于安全走廊、整车/全身规划尤其重要。

---

2. 论文要解决的关键科学问题与技术挑战

2.1 从障碍物中构造“大而安全”的凸自由空间

机器人环境通常是非凸的，而基于优化的轨迹规划更喜欢凸约束。若把一段自由空间表示为

P = { x ∈ R n ∣ A P x ≤ b P } , n ∈ { 2 , 3 } , \mathcal P=\{x\in\mathbb R^n\mid A_{\mathcal P}x\le b_{\mathcal P}\},\qquad n\in\{2,3\}, P={x∈Rn∣AP​x≤bP​},n∈{2,3},

那么后端可以直接使用这些半空间约束限制轨迹状态。问题在于：从海量障碍点中生成一个高质量凸区域并不容易。区域太小会压缩轨迹优化的自由度；区域太大又可能穿过障碍物。

2.2 “大区域”与“必须包含种子”存在直接冲突

论文定义种子为凸集

Q = conv ⁡ { v 1 , … , v s } , \mathcal Q=\operatorname{conv}\{v_1,\ldots,v_s\}, Q=conv{v1​,…,vs​},

第 $i$ 个凸障碍物为

O i = conv ⁡ { u i , 1 , … , u i , s i } , O = ⋃ i = 1 N O i . \mathcal O_i=\operatorname{conv}\{u_{i,1},\ldots,u_{i,s_i}\}, \qquad \mathcal O=\bigcup_{i=1}^{N}\mathcal O_i. Oi​=conv{ui,1​,…,ui,si​​},O=i=1⋃N​Oi​.

理想目标可以写成

$$\underset{\mathcal{P}}{\max }\mathrm{vol}(\mathcal{P}),\text{s.t.}\mathcal{Q}\subseteq \mathcal{P},\mathcal{O}\cap \mathrm{int}(\mathcal{P})=\varnothing .$$

这里第二个约束保证安全，第一个约束就是论文定义的 manageability。例如用一段路径作为种子构建 corridor 时，如果某个凸区域不完整包含对应路径段，就可能导致相邻 corridor 失去连续性；若用机器人几何形状作为种子，则不完整包含机器人意味着后端本体约束直接不可行。

2.3 原问题本身难以直接全局求解

论文指出，即使不考虑种子包含约束，最大自由凸区域问题在二维也具有很高的多项式复杂度，在三维则是 NP-hard；而凸多面体体积本身也并不是一个适合在线反复计算的目标。因此作者没有追求原问题的全局最优解，而采用 MVIE 体积作为多面体体积的可计算下界。

这使问题转化为：每次先生成一个安全且包含种子的多面体，再计算其最大体积内接椭球；只要内接椭球继续变大，就说明自由空间的“保守下界”还在改善。

2.4 低维、大约束是通用优化器的薄弱场景

FIRI 的两个核心子问题有共同结构：

• 状态维数仅为二维或三维；
• 但障碍点/半空间约束可能达到数千乃至上万；
• 在线规划要求单次计算在毫秒甚至亚毫秒级完成。

通用 QP、SDP、SOCP 求解器通常需要构建并求解随约束数量增长的大型线性系统，因此并不充分利用“变量很少、约束极多”的特殊几何结构。本文的主要算法工作，正是围绕这一结构进行专用求解器设计。

---

3. FIRI 总体框架

图2 FIRI 的总体计算流程。 输入种子、障碍物与初始椭球后，算法在 RsI 与 MVIE 两个模块之间迭代：RsI 构造满足种子包含约束的自由凸多面体，MVIE 再求该多面体的最大体积内接椭球并用于下一轮膨胀。图源：论文 Fig. 2。

3.1 输入与输出

FIRI 的输入包括：

1. 种子凸集 $\mathcal{Q}$；
2. 障碍物集合 $\mathcal{O}$；
3. 初始椭球 ${\mathcal{E}}_0$；
4. 终止阈值 $\rho$。

输出是一个 H-representation 的自由凸多面体 $\mathcal{P}$。论文实验中 FIRI 与 IRIS 采用相同的 $\rho =0.02$，即相邻两次迭代的 MVIE 体积增益低于约 2% 时停止。

3.2 一轮迭代的逻辑

第 $k$ 轮执行：

$${\mathcal{E}}_{k-1}\stackrel{\text{RsI}}{\to }{\mathcal{P}}_k\stackrel{\text{MVIE}}{\to }{\mathcal{E}}_k.$$

其中：

• RsI 根据当前椭球寻找一组切分障碍物的半空间，并要求每个半空间都包含种子；
• 半空间交集形成 ${\mathcal{P}}_k$；
• 求 ${\mathcal{P}}_k$ 的 MVIE 得到 ${\mathcal{E}}_k$；
• 下一轮继续以 ${\mathcal{E}}_k$ 为膨胀基准。

3.3 为什么这种迭代能够保证安全与收敛

FIRI 有两条很重要的性质。

第一，始终可行。 RsI 生成的每一个半空间都满足

$$\mathcal{Q}\subseteq {\mathcal{H}}_i,{\mathcal{O}}_i\cap \mathrm{int}({\mathcal{H}}_i)=\varnothing ,$$

因此它们的交集必然满足

$$\mathcal{Q}\subseteq {\mathcal{P}}_k,\mathcal{O}\cap \mathrm{int}({\mathcal{P}}_k)=\varnothing .$$

所以 manageability 不是概率意义或经验意义上的“通常包含”，而是由半空间构造方式直接保证。

第二，MVIE 体积单调不减。 RsI 保证上一轮椭球 ${\mathcal{E}}_{k-1}$ 被包含在新多面体 ${\mathcal{P}}_k$ 中，而 ${\mathcal{E}}_k$ 又是 ${\mathcal{P}}_k$ 内最大的椭球，因此

$$\mathrm{vol}({\mathcal{E}}_{k-1})\le \mathrm{vol}({\mathcal{E}}_k).$$

在有限 ROI 内，该体积有上界，因此序列收敛。FIRI 并不声称获得原始最大体积多面体问题的全局最优解，而是通过单调提升一个可计算的体积下界得到高质量可行解。

---

4. RsI：带种子包含约束的限制性膨胀

4.1 把任意椭球映射为单位球

若当前椭球写为

E = { p ∣ p = A E D E x + b E ,   ∥ x ∥ ≤ 1 } , \mathcal E=\{p\mid p=A_{\mathcal E}D_{\mathcal E}x+b_{\mathcal E},\ \|x\|\le1\}, E={p∣p=AE​DE​x+bE​, ∥x∥≤1},

则利用逆仿射变换

$$\bar{x}=D_{\mathcal{E}}^{-1}{A}_{\mathcal{E}}^{\mathsf{T}}(x-b_{\mathcal{E}})$$

可将当前椭球标准化为单位球。种子和障碍物的所有顶点也进行同样变换。这样，后续“椭球—障碍物”几何关系被化为更简单的“单位球—障碍物”关系。

4.2 限制性半空间

在变换空间中，对每个障碍物 ${\bar{\mathcal{O}}}_i$，FIRI 构造

H ( a i ) = { x ∈ R n ∣ a i T x ≤ a i T a i } . \mathcal H(a_i) =\{x\in\mathbb R^n\mid a_i^{\mathsf T}x\le a_i^{\mathsf T}a_i\}. H(ai​)={x∈Rn∣aiT​x≤aiT​ai​}.

向量 $a_i$ 同时决定：

• 半空间边界法向；
• 膨胀球与边界的接触位置；
• 对应可膨胀尺度。

原始限制性半空间问题为

$$\underset{a_i}{\max }{a}_i^{\mathsf{T}}{a}_i$$

满足

$$v^{\mathsf{T}}{a}_i\le a_i^{\mathsf{T}}{a}_i,\forall v\in \bar{\mathcal{Q}},$$

$$u^{\mathsf{T}}{a}_i\ge a_i^{\mathsf{T}}{a}_i,\forall u\in {\bar{\mathcal{O}}}_i.$$

这两组约束分别表示“种子在半空间内”和“障碍物在半空间外”。这就是 FIRI 相比传统 IRIS 在结构上的关键区别。

4.3 极对偶变换：把非凸最大化变成最小范数问题

令

$$a_i=\frac{b}{b^{\mathsf{T}}b},$$

则上述问题可等价转换为

$$\underset{b}{\min }{b}^{\mathsf{T}}b,$$

$$\text{s.t.}{v}^{\mathsf{T}}b\le 1,\forall v\in \bar{\mathcal{Q}},u^{\mathsf{T}}b\ge 1,\forall u\in {\bar{\mathcal{O}}}_i.$$

此时目标函数是严格凸二次型，约束全部是线性的。更重要的是，决策变量始终只有 2 或 3 维，约束数量却可以很大，正好进入 SDMN 的适用范围。

4.4 贪心选择半空间以减少面数

对所有障碍物计算候选半空间后，RsI 不是简单地全部保留，而是优先选取当前“最近”的半空间，并一次剔除已经被该半空间隔离掉的障碍物。这样能够减少最终多面体的面数。

这一点在工程上很重要：后端轨迹优化的约束数量往往与 corridor 面数直接相关。论文也在结论中承认，目前的面数控制仍主要依赖这种贪心机制，未来可把面数本身直接纳入区域质量指标。

---

5. SDMN：小维度、大约束最小范数的随机递归解析算法

FIRI 将 RsI 的半空间计算统一为

$$\underset{y\in {\mathbb{R}}^n}{\min }{y}^{\mathsf{T}}y,\text{s.t.}Ey\le f,$$

其中 n ∈ { 2 , 3 } n\in\{2,3\} n∈{2,3}，而约束数 $d\gg n$。作者称该专用方法为 SDMN（Small Dimensional Minimum-Norm）。

图3 SDMN 的二维递归过程示意。 若当前最小范数解不违反新约束，则解保持不变；若新约束被违反，则该约束必为活跃约束，问题被投影到该约束边界上的低一维子空间继续求解。图源：论文 Fig. 3。

5.1 从 Seidel 随机 LP 到严格凸最小范数

算法思想与 Seidel 小维线性规划类似：

1. 从无约束最优解 $y=0$ 开始；
2. 随机打乱约束顺序；
3. 逐个检查约束；
4. 若当前解满足新约束，则无需重新优化；
5. 若当前解违反新约束，则该约束在新最优解处必然活跃；
6. 将该约束变为等式，并把问题投影到其边界上的 $(n-1)$ 维空间；
7. 对降维问题递归调用 SDMN。

因为二维最多递归到一维，三维最多递归到二维再到一维，所以递归深度是常数级的。

5.2 Householder 投影保证数值稳定

若新增活跃约束的法向为 $v$，作者使用 Householder 反射构造正交矩阵

$$H=I-\frac{2u{u}^{\mathsf{T}}}{u^{\mathsf{T}}u},$$

把约束平面的法向对齐到某个坐标轴，再删除对应轴得到平面的正交基 $M$。在约束平面上的点可写为

$$y=M{y}^{\prime }+v_0,$$

从而把原问题降为 $(n-1)$ 维同型最小范数问题。与直接手工消元相比，正交变换对数值尺度更稳定。

5.3 复杂度

论文给出的期望复杂度为

$$O(n!d).$$

由于这里 $n=2$ 或 $3$ 是固定常数，因此算法对约束数量 $d$ 呈期望线性复杂度。这也是 SDMN 在障碍点数量很大时仍能保持极低计算时间的根本原因。

---

6. MVIE：从 SDP 思路改写为纯 SOCP

RsI 给出多面体 ${\mathcal{P}}_k$ 后，FIRI 需要计算其最大体积内接椭球。传统 IRIS 的瓶颈之一就在这里：使用 SDP 求 MVIE 时，约束数量增大后每轮线性代数开销很大。

6.1 椭球体积与包含约束

对椭球

E = { A E D E x + b E ∣ ∥ x ∥ ≤ 1 } , \mathcal E=\{A_{\mathcal E}D_{\mathcal E}x+b_{\mathcal E}\mid \|x\|\le1\}, E={AE​DE​x+bE​∣∥x∥≤1},

其体积与

$$\det (D_{\mathcal{E}})$$

成正比。若多面体为

P = { x ∣ A P x ≤ b P } , \mathcal P=\{x\mid A_{\mathcal P}x\le b_{\mathcal P}\}, P={x∣AP​x≤bP​},

“椭球完全位于每个半空间内”本质上可以表示成二阶锥范数约束。

6.2 用 Cholesky 因子消除正交约束

作者使用

$$A_{\mathcal{E}}{D}_{\mathcal{E}}^2{A}_{\mathcal{E}}^{\mathsf{T}}=L_{\mathcal{E}}{L}_{\mathcal{E}}^{\mathsf{T}},$$

其中 $L_{\mathcal{E}}$ 是对角元为正的下三角 Cholesky 因子。于是：

$$\det (D_{\mathcal{E}})=\det (L_{\mathcal{E}})=\prod _j(L_{\mathcal{E}}{)}_{jj}.$$

多面体第 $i$ 个半空间对椭球的约束可写成类似

$$\Vert a_i^{\mathsf{T}}{L}_{\mathcal{E}}{\Vert }_2\le b_i-a_i^{\mathsf{T}}{b}_{\mathcal{E}}.$$

由此，不再需要直接优化正交矩阵 $A_{\mathcal{E}}$，也避免了常见 SDP 表达中更复杂的正定矩阵约束。

6.3 几何平均锥处理行列式目标

由于 $L_{\mathcal{E}}$ 为下三角矩阵，最大化体积等价于最大化其正对角元乘积。论文进一步引入几何平均锥，把目标改写为线性变量 $t$ 的最大化，并把全部约束转换成 SOC。

最终得到一个：

• 目标函数线性；
• 约束全部为二阶锥；
• 决策变量规模仅为 $O(n^2)$；
• SOC 数量为 $O(m+n)$；

的纯 SOCP，其中 $m$ 是多面体半空间数量。

---

7. CAS：面向“大量锥约束、小变量维度”的仿射缩放法

论文没有止步于“把 SDP 换成 SOCP”，而是进一步针对这种特殊 SOCP 设计求解流程。实验章节将该方法记为 CAS。

将 SOCP 统一写成

$$\underset{x}{\min }{c}_{\mathcal{K}}^{\mathsf{T}}x$$

并用各锥约束构造对数障碍函数

$$\varphi (x)=-\sum _i\log f_i(x).$$

在当前严格可行点 $x_k$ 处计算障碍函数 Hessian $H_{\varphi }(x_k)$，仿射缩放更新为

$$x_{k+1}=x_k-\tau \frac{H_{\varphi }^{-1}{c}_{\mathcal{K}}}{\sqrt{c_{\mathcal{K}}^{\mathsf{T}}{H}_{\varphi }^{-1}{c}_{\mathcal{K}}}},\tau \in (0,1].$$

关键点不在于“仿射缩放一定优于所有内点法”，而在于这里的决策变量维数很小。即使约束很多，真正需要求逆/求解的 Hessian 维度仍然只跟低维椭球参数有关，而不是构造一个随约束数迅速增大的 KKT 系统。因此它特别适合 FIRI 的 MVIE 子问题。

---

8. 二维特化：线性复杂度的解析 MVIE 算法

二维场景中，作者进一步绕开数值 SOCP，提出论文声称的首个二维最大面积内接椭圆线性复杂度解析算法。实验中将其简称为 RAN。

8.1 为什么不能直接套用 MVEE 的 LP-type 算法

最小体积外接椭圆（MVEE）早已有基于 LP-type 结构的随机线性期望复杂度算法。但 MVIE 有两个难点：

1. 任意少量半空间的子集可能根本没有形成封闭多边形，此时“最大内接椭圆面积”没有正常定义；
2. 即使得到一个小规模 basis，仍需要对这些少量边界约束快速求解析的最大内接椭圆。

作者因此重新定义了能够同时描述“未闭合程度”和“闭合后椭圆面积”的字典序 value function，并在附录证明其满足 LP-type 问题所需的 monotonicity 与 locality。

8.2 Bottom-up basis computation

二维椭圆共有 5 个自由度，因此决定最大内接椭圆的有效边界不会无限增加。作者把 basis 计算分解为“与 $N$ 条边相切的最大椭圆”子问题，即 MENN（Maximal Ellipse tangent to N edges of the N-gon），其中只需处理 $N=3,4,5$。

图4 二维 MVIE 的自底向上 basis 计算策略。 先求更小约束子集的 MVIE/MENN，再逐步加入新边界；该结构用于处理未闭合子集与解析 basis 计算。图源：论文 Fig. 4。

这种“从低阶子问题逐级向上组合”的思路受到 GJK 距离子算法的启发。随机递归框架的组合维数为常数，因此期望原始操作次数随输入半空间数线性增长。

8.3 五边形、四边形与三角形的解析 MENN

作者采用射影几何中的极点—极线关系，将椭圆表示从点二次型转换到切线二次型。对于椭圆的 primal matrix $M_P$ 与 line matrix $M_L$，存在

$$M_L\propto M_P^{-1}.$$

• 五边形：5 条切线对称矩阵的 6 个独立元素形成 5 个齐次线性方程；解在比例尺度上唯一，由此恢复唯一与五边均相切的椭圆。
• 四边形：四条边只确定一族一参数内接椭圆。论文将一个接触点参数化为 $\lambda$，再最大化椭圆面积；一阶条件最终降为关于 $\lambda$ 的二次方程，可解析求解。
• 三角形：最大面积内接椭圆就是 Steiner inellipse，与三条边分别在中点处相切。其中心为三顶点的平均值，并可由两个共轭直径直接恢复椭圆参数。

图5 MENN 的解析计算示意。 左：四边形中由边上接触点参数化得到的一族内接椭圆；右：三角形中的 Steiner 最大面积内接椭圆。图源：论文 Fig. 5。

二维特化算法的意义非常直接：对于 2D 地面机器人、占据栅格投影、局部安全走廊等问题，MVIE 不再需要调用通用数值优化器，理论上即可达到随半空间数量线性增长的复杂度。

---

9. 实验设计

9.1 对比对象与统一环境

所有基准测试均在 Intel Core i7-12700KF、Linux、C++14、无硬件加速 条件下完成。

自由凸区域生成部分对比：

• FIRI；
• IRIS；
• Galaxy；
• RILS；
• FIRI(SI)：只执行一次 FIRI 的 RsI，相当于不进行迭代 MVIE 优化的单轮版本。

论文将环境分为 2D/3D 的 sparse、medium、dense 三档障碍密度。每一档创建 10 个随机环境，每个环境针对不同种子类型进行 500 次随机测试。2D 环境尺度为 50 m × 50 m，3D 额外具有 10 m 高度；局部 ROI 以种子中心为中心，边长 6 m。

9.2 输入适应性

表1 论文 Table I：不同自由凸区域生成方法的输入适应性。

FIRI 是对比方法中唯一同时原生支持点、线段、凸多面体种子，以及点障碍与凸多面体障碍的方法。这一点并不仅仅是接口更通用：当环境本身已经用凸多面体表达时，FIRI 可以直接处理，而不需要先把多面体离散成大量点。

9.3 Manageability 成功率

表2 论文 Table III：生成区域完整包含种子的成功率（%）。

结果最有代表性的不是点种子，而是线段和多面体种子。FIRI 在全部测试中保持 100% 包含成功率，而 IRIS/Galaxy/RILS 在高密度、复杂种子情况下明显下降。说明 manageability 确实是算法约束带来的确定性能力，而不是通过多次尝试“碰巧”获得。

---

10. 区域质量与计算效率

图6 不同方法生成自由凸区域的相对尺寸。 FIRI 被归一化为 1；IRIS 的区域尺寸通常与 FIRI 接近，而 Galaxy、RILS 与单轮 FIRI(SI) 更保守。图源：论文 Fig. 6。

图6揭示了 FIRI 的主要优势并不是“绝对区域大小远超 IRIS”，而是：以接近 IRIS 的区域质量，换取数量级更低的计算成本，同时额外获得种子包含保证。

10.1 点种子平均计算时间

表3 根据论文 Table IV 摘取的点种子平均计算时间。

在 2D 随机环境中，FIRI 已进入亚毫秒级；3D 稠密环境的平均时间约 2.116 ms。相比 IRIS，其主要收益来自专用的 RsI/SDMN 与 MVIE 求解流程。

图7 多面体障碍物条件下 FIRI 与 IRIS 的计算时间随障碍顶点数增长关系。 上行为 2D，下行为 3D。FIRI 在不同障碍密度下均保持明显优势。图源：论文 Fig. 7。

针对凸多面体障碍，论文改变单个障碍的顶点数并重复测试。随着障碍顶点和半空间规模增大，FIRI 仍能利用 SDMN 的线性约束尺度特性；论文报告在稠密多面体障碍场景中相对 IRIS 可减少超过 95% 的计算需求。

---

11. 区域质量是否真的会改善轨迹：轨迹规划案例

只比较多面体体积并不足以证明工程价值，因此论文进一步把 FIRI 和 RILS 生成的安全走廊接入同一个轨迹优化问题。

实验流程为：

1. 用 RRT* 生成起点到终点的无碰撞前端路径；
2. 将路径视为连续线段；
3. 依次用每段线作为种子构造相邻凸多面体，形成 corridor；
4. 使用 GPOPS-II 的 Gauss pseudospectral transcription 将时间最优轨迹问题离散成 NLP；
5. 使用 SNOPT 求解；
6. 每个阶段的轨迹限制在对应多面体内；
7. 速度上限 3 m/s，加速度上限 6 m/s²，时间代价权重为 20。

图8 FIRI 与 RILS 安全走廊及其最优轨迹对比。 FIRI 生成的 corridor 在关键狭窄区域提供更大的空间自由度，后端因此能得到更激进、更短时的速度/加速度过程；RILS 的局部狭窄凸区域限制了轨迹优化。图源：论文 Fig. 8。

这一实验说明，“凸区域质量”不是一个与最终控制无关的纯几何指标。安全走廊越保守，轨迹优化越容易在狭窄瓶颈处被限制，速度提前下降、加速度策略更保守。FIRI 的价值是把更多真实自由空间暴露给后端，而后端再根据动力学约束决定如何利用这些自由度。

---

12. SDMN 子求解器基准

作者将 SDMN 与 qpOASES、OSQP、HPIPM 对比。OSQP 同时测试默认参数与更严格的容差设置。

图9 不同方法求解小维度严格凸最小范数问题的计算时间。 随约束数量增大，SDMN 在 2D 与 3D 中均表现出明显的数量级效率优势。图源：论文 Fig. 9。

论文用到最活跃约束的误差定义求解精度。结果为：

表4 论文 Table V：小维度最小范数问题的精度指标。

这组实验不仅说明 SDMN 快，而且说明其优势不是通过放宽精度换来的。其随机递归与低维解析子问题本身可以获得非常高的约束精度。

---

13. MVIE 子求解器基准

MVIE 部分比较：

• IRIS 中使用的原始 MVIE 方案；
• Mosek SDP；
• Mosek SOCP；
• 论文提出的 CAS；
• 二维场景专用解析 RAN。

图10 不同 MVIE 方法的计算时间。 CAS 相比通用求解方案显著更快；二维 RAN 又在 CAS 基础上进一步降低计算时间。图源：论文 Fig. 10。

表5 论文 Table VI：不同 MVIE 求解方法的精度指标。

Mosek SOCP 的结果验证了“把 MVIE 从 SDP 改写成 SOCP”本身就能明显减少求解成本；CAS 又进一步利用小变量维度避免构建大规模线性系统；RAN 在 2D 下直接使用解析 basis computation，因而获得更进一步的数量级提升。

---

14. 实机实验一：二维地面车稠密安全走廊

论文使用差速 AgileX SCOUT MINI，机载计算平台为 Intel NUC（Core i7-1165G7），感知使用集成 IMU 的 Ouster OS1 LiDAR，并利用 FAST-LIO2 完成预建图和实时定位。环境障碍物以点形式提供。

前端使用 Hybrid A* 生成初始可行轨迹，然后在轨迹上细采样。每个采样状态对应的机器人几何形状直接作为 FIRI 的种子，因此生成的每个凸区域都必须完整覆盖该姿态下的机器人形状；后端使用多项式轨迹并施加 whole-body corridor 约束。

图11 地面车在杂乱环境中的 FIRI corridor。 (a)–(e) 展示从 G1 依次经过 G2–G5 并返回 G1 的走廊；(f) 为实机导航快照。图源：论文 Fig. 11。

该实验共生成 5 条走廊：

• 每条 corridor 平均包含 91.8 个凸多面体；
• 每个多面体平均输入 715.3 个障碍点；
• 单个多面体平均生成时间 0.131 ms；
• 一条 corridor 平均生成时间 12.02 ms。

这些数据说明 FIRI 的定位并不是一个低频离线几何工具，而是可以被放入在线/准在线轨迹生成链路。

---

15. 实机实验二：窄迷宫中的 whole-body 规划

图12 差速地面车穿越窄迷宫的 whole-body 规划。 上：由前端粗轨迹生成稠密 corridor，并在 corridor 内优化平滑全身安全轨迹；下：两个典型狭窄位置中，论文对比 FIRI、IRIS、Galaxy 与 RILS 对机器人本体的包含情况，并给出实机快照。图源：论文 Fig. 12。

这个实验最直接体现 manageability。机器人不是点，而是具有明显长宽的刚体。论文选取两个狭窄位置进行对比，结果显示只有 FIRI 生成的凸区域能够稳定满足“完整包含机器人”的要求。

整条窄迷宫 corridor 的统计为：

• 550 个凸多面体；
• 每个多面体平均 1307.1 个障碍点；
• 单个多面体平均 0.249 ms；
• 完整 corridor 总生成时间 136.74 ms。

若采用只针对点种子或线段种子的区域膨胀方法，即使几何区域看起来“够大”，也不能自动推出机器人本体一定被包含，这正是论文反复强调的区别。

---

16. 实机实验三：无人机三维局部重规划

论文还将 FIRI 用于未知稠密森林中的四旋翼局部轨迹重规划。平台使用 NVIDIA Orin NX 与 Livox MID-360，FAST-LIO2 提供状态估计，障碍点经过 occupancy grid filtering。由于无人机尺寸较小，此处采用点质量模型，并通过障碍膨胀保留安全裕度。

图13 FIRI 在四旋翼三维局部轨迹重规划中的应用。 上：无人机穿越稠密树林的实飞场景；下：若干局部重规划时刻的点云、轨迹和 FIRI 生成的透明凸多面体。图源：论文 Fig. 13。

实验设置与结果包括：

• 在线重规划频率 20 Hz；
• 飞行最大速度达到 4.5 m/s；
• 每次重规划生成约 3–7 个凸多面体；
• 每个多面体平均处理 8219.6 个障碍点；
• 单个多面体平均生成时间 2.76 ms。

该实验说明 FIRI 既可以用于 2D 地面车的 dense corridor，也可以作为 3D 飞行器局部规划中的 sparse corridor 生成器。

---

17. 论文主要创新点与学术贡献

17.1 首次把 quality、efficiency 与 manageability 统一到同一自由凸区域生成框架

过去的算法通常强调“大区域”或“快速”，但对指定种子的完整包含往往依赖初始化、启发式或额外补救。FIRI 直接把种子包含写进每一个分离半空间的约束，使 manageability 成为算法的结构性性质。

17.2 提出 RsI，并把复杂半空间构造统一成小维度严格凸最小范数问题

RsI 不只是给 IRIS“多加一个包含约束”。作者通过极对偶把原本的膨胀半空间最大化问题转化为统一线性约束下的 $L_2$ 最小范数问题，使种子约束和障碍分离约束具有同一代数形式，为专用快速求解创造条件。

17.3 将 Seidel 式随机递归推广到 SDMN

SDMN 把新违反约束视为活跃约束，并递归降维求解，结合 Householder 正交投影，在 2D/3D 固定维数下实现对约束规模的期望线性复杂度。它抓住了机器人几何计算中常见的“维度极低、约束极多”特点。

17.4 提出避免显式正定/正交矩阵处理的 MVIE SOCP 表达

通过 Cholesky 因子与几何平均锥，作者把 MVIE 改写为纯 SOCP，减少 SDP 形式带来的结构和数值开销。这一贡献不仅服务 FIRI，本身也可用于任何需要低维最大内接椭球的几何优化问题。

17.5 针对小变量、大约束 SOCP 使用仿射缩放求解

CAS 的重要性在于进一步利用问题结构：约束可以非常多，但真正的决策变量仍然很少，因此无需像通用 primal-dual interior-point 方案那样在每轮处理随约束规模膨胀的大型 KKT 系统。

17.6 给出二维最大面积内接椭圆的线性复杂度解析算法

这是本文理论上最突出的贡献之一。作者解决了 MVIE 不直接满足传统 LP-type 处理所需定义的问题，重新构造 value function，并给出 3/4/5 边 MENN 的解析 basis computation，从而得到期望线性复杂度随机算法。

17.7 用最终轨迹与多种实机平台验证几何模块的实际价值

论文不只展示“多面体更大、时间更短”，还把安全 corridor 接入时间最优轨迹优化、差速 whole-body 规划与四旋翼 20 Hz 局部重规划，证明了更大的可行凸空间会转化为更好的后端轨迹自由度。

---

18. 与 IRIS、RILS、Galaxy 的本质区别

表6 FIRI 与主要对比方法的结构性差异。

可以把 FIRI 理解为：试图保留 IRIS 的“高质量迭代膨胀”，同时补上种子包含能力，并用专门的低维算法把原本昂贵的优化步骤压到实时范围。

---

19. 对论文方法的深入理解

19.1 FIRI 本身不是轨迹规划器

FIRI 的输出是一个或一串自由凸多面体，不直接输出控制量、速度曲线或轨迹。典型系统链路是：

地图/点云 → 前端路径 → FIRI 安全凸区域/走廊 → 轨迹优化 → 跟踪控制。

因此评价 FIRI 时，不能拿它与 A*、RRT*、MPC、MPPI 等直接规划/控制算法做同层比较。它更接近“把非凸碰撞约束转化为后端友好的凸安全约束”这一基础模块。

19.2 MVIE 不是最终目标，而是多面体质量的 surrogate

论文真正想增大的是 $\mathrm{vol}(\mathcal{P})$，但直接求它太困难，于是用

$$\mathrm{vol}({\mathcal{E}}^{\ast }(\mathcal{P}))$$

作为下界。这个 surrogate 的优势是容易定义、唯一且适合迭代，但它并不保证“MVIE 最大的多面体一定是所有任务中最好的多面体”。例如某些轨迹更需要沿运动方向拉长，而不是各方向总体体积最大。

论文在 Discussion 中也明确指出：当前最大体积目标并不总能产生最有利于轨迹的膨胀方向。

19.3 多面体面数与多面体体积是两个不同的规划代价

一个区域很大，但如果由大量半空间构成，后端优化器仍可能承受很大约束负担。FIRI 当前通过贪心方式减少冗余/已分离障碍产生的面，但没有把“面数”直接写进区域质量目标。作者把这一点作为未来工作之一。

19.4 二维解析算法的适用范围非常明确

RAN 的理论优势建立在二维、半空间表示和最大面积内接椭圆的特殊结构之上。三维 MVIE 并没有对应的简单 5-constraint basis 结构，因此论文在 3D 中仍采用 SOCP + CAS，而不是把二维解析方法硬推广到三维。

---

20. 局限性与未来工作

论文最后给出的主要限制包括：

1. 只最大化区域体积，未显式考虑任务方向。 对轨迹规划而言，沿当前运动方向的自由空间可能比侧向体积更有价值；
2. 多面体面数没有进入优化目标。 当前主要通过贪心策略控制面数，未来可以直接把约束复杂度纳入质量指标；
3. 二维解析 MVIE 仍有进一步鲁棒化空间。 作者提到可结合 rational predicates、CGAL 等计算几何工具增强退化/数值边界情形下的鲁棒性；
4. FIRI 给出的是局部凸安全区域，并不解决全局拓扑路径搜索、动态障碍预测、动力学可行性或最终控制问题，这些仍需上层/下层模块共同完成。

---

21. 对机器人规划系统的工程意义

FIRI 最适合以下几类位置：

• 安全走廊生成：把 A*/RRT*/Hybrid A* 的离散路径变成一串连续凸可行域；
• whole-body 规划：直接把机器人 footprint/凸包作为种子，保证本体完整位于每个安全区域中；
• 局部轨迹重规划：从实时点云中快速提取少量凸空间，将碰撞约束转换为线性半空间约束；
• 非凸环境的凸化预处理：为 MINCO、B-spline、polynomial optimization、NLP/MPC 等后端提供结构良好的安全约束。

如果只需要“尽快得到一个包含种子的可行凸区域”，而不追求迭代增大区域，论文的 FIRI(SI) 也值得注意：它相当于只运行一次 RsI，保留 manageability，同时进一步降低耗时。

---

22. 全文技术路线总结

可以把本文的完整技术路线压缩为下面的逻辑链：

非凸障碍环境 + 指定种子
↓
FIRI：RsI 与 MVIE 交替迭代

其中 RsI 的技术链为：

椭球仿射归一化 → 限制性半空间优化 → 极对偶 → SDMN 随机递归期望线性复杂度求解。

MVIE 的技术链为：

椭球矩阵 → Cholesky 因子 → 纯 SOCP → CAS（2D/3D）或 RAN 解析线性算法（2D 特化）。

最终得到：高质量自由凸区域 + 确定性包含种子 + 毫秒/亚毫秒级计算。

本文真正有价值的地方，并不是单独发明了一个“区域膨胀技巧”，而是从问题定义、几何重构、低维优化、计算复杂度到实机轨迹规划形成了一套完整闭环：把机器人规划中经常出现的“大量障碍约束”重新看成固定低维计算几何问题，再用专用算法替代通用优化器。

---

23. 参考链接与复现入口

• arXiv 论文：https://arxiv.org/abs/2403.02977
• arXiv v3 HTML：https://arxiv.org/html/2403.02977v3
• IEEE Xplore：https://ieeexplore.ieee.org/document/10970076
• ZJU-FAST-Lab / GCOPTER：https://github.com/ZJU-FAST-Lab/GCOPTER
• GCOPTER 中旧版 FIRI：https://github.com/ZJU-FAST-Lab/GCOPTER/blob/main/gcopter/include/gcopter/firi.hpp
• ZJU-FAST-Lab / SDQP：https://github.com/ZJU-FAST-Lab/SDQP