晨光
暗夜
晨光
极光
Bilingual Paper Reading · 中英对照精读

基于优化的碰撞避免（凸对偶平滑化方法）

准大一 · 轮机工程 × 智能航行 × 优化控制 —— 基于优化的碰撞避免精读材料
原文：arXiv:1711.03449 2017年11月9日发布 arXiv 预印本（math.OC · cs.RO · eess.SY） 凸优化 × 轨迹规划 × 碰撞避免 附英文摘要朗读音频

一、论文档案

英文标题Optimization-Based Collision Avoidance
中文标题基于优化的碰撞避免——用凸优化强对偶性把不可微避碰约束改写成光滑约束
作者张晓静, 亚历山大·利尼格尔, 弗朗切斯科·博雷利（机构未在素材中标注）
发布时间2017年11月9日（v1）｜分类：math.OC · cs.RO · eess.SY（优化与控制 · 机器人学 · 系统与控制）
原文链接arxiv.org/abs/1711.03449　·　全文 HTML 版
一句话概括用凸优化的强对偶性，把「不可微」的避碰约束精确改写成光滑非线性约束——不近似、不保守，还能算「侵入深度」找最小侵入轨迹；四旋翼导航与自动泊车都能实时求解。
💡 为什么选这篇给你：① 轨迹规划与避碰是无人船、自主航行船舶的核心技术栈（对应航海避碰规则 COLREGs 的工程化实现）；② 方法思想「用对偶理论把难的约束变成好算的约束」是控制与优化领域的高频考点，理解了受益整个本科后半程；③ 论文结构干净：问题 → 两种重表述（距离 / 符号距离）→ 两个真实实验，且有开源代码（OBCA），可动手复现。

二、核心术语表（先扫一遍再读正文）

英文术语中文大白话解释
collision avoidance constraint碰撞避免约束轨迹规划优化问题里「物体不能进入障碍物区域」的限制条件。
non-differentiable不可微的函数存在尖点、无法求梯度，梯度类优化算法用不了——这是避碰约束的老大难。
convex set凸集集合内任意两点连线仍落在集合内；多面体、椭球都是凸集，数学性质好。
finite union of convex sets凸集的有限并集多个凸集拼在一起描述更复杂的形状；本文要求物体和障碍都能这样表示。
strong duality of convex optimization凸优化的强对偶性原问题与对偶问题最优值相等——用对偶形式「重写」距离函数，从而保住光滑性。
reformulation重表述（等价改写）把同一数学约束写成另一种形式，性质不变但更好算；本文强调「精确、无近似」。
smooth nonlinear constraint光滑非线性约束处处可微的非线性约束，可配合梯度/海森类通用优化器使用。
signed distance符号距离带正负号的距离：物体在障碍外为正、侵入障碍内为负——同时描述「距离」与「侵入深度」。
penetration侵入深度物体「陷进」障碍物多深；实在躲不开时，用它衡量「侵入得多轻」。
least-intrusive trajectory最小侵入轨迹无法完全避碰时，侵入深度最小的折中轨迹。
polytope / ellipsoid多面体 / 椭球两类典型凸集障碍物/物体描述方式。
point-mass / full-dimensional质点 / 全尺寸物体质点模型把物体当点（障碍膨胀来补偿形状）；全尺寸模型直接考虑物体真实形状。
MPC (Model Predictive Control)模型预测控制反复求解「带系统动力学和约束的优化问题」的实时控制方法，轨迹规划的常用框架。
kinodynamically feasible运动动力学可行轨迹既满足运动学（速度/加速度关系）又满足动力学（受力和力矩约束），低级控制器能跟踪。
warm starting热启动用上一时刻的解作为本时刻优化初值，大幅加快实时求解。

三、摘要中英对照（精读核心）

🎧 音频在文末，可先听一遍原文再读；每个英文句都配了逐句翻译。

摘要 Abstract

EN · 原文
This paper presents a novel method for reformulating non-differentiable collision avoidance constraints into smooth nonlinear constraints using strong duality of convex optimization.
CN · 翻译
本文提出一种新方法：利用凸优化的强对偶性，把不可微的避碰约束重表述为光滑的非线性约束。
EN · 原文
We focus on a controlled object whose goal is to avoid obstacles while moving in an n-dimensional space.
CN · 翻译
我们关注一个在 n 维空间中运动、目标是避开障碍物的被控物体。
EN · 原文
The proposed reformulation does not introduce approximations, and applies to general obstacles and controlled objects that can be represented in an n-dimensional space as the finite union of convex sets.
CN · 翻译
所提重表述不引入任何近似，适用于能被表示为凸集有限并集的一般障碍物与被控物体。
EN · 原文
Furthermore, we connect our results with the notion of signed distance, which is widely used in traditional trajectory generation algorithms.
CN · 翻译
此外，我们把结果与传统轨迹生成算法中广泛使用的符号距离概念联系起来。
EN · 原文
Our method can be used in generic navigation and trajectory planning tasks, and the smoothness property allows the use of general-purpose gradient- and Hessian-based optimization algorithms.
CN · 翻译
该方法可用于通用导航与轨迹规划任务；光滑性使得通用的基于梯度/海森矩阵的优化算法得以使用。
EN · 原文
Finally, in case a collision cannot be avoided, our framework allows us to find "least-intrusive" trajectories, measured in terms of penetration.
CN · 翻译
最后，若碰撞确实无法避免，该框架还能以侵入深度为度量，找到「最小侵入」轨迹。
EN · 原文
We demonstrate the efficacy of our framework on a quadcopter navigation and automated parking problem, and our numerical experiments suggest that the proposed methods enable real-time optimization-based trajectory planning problems in tight environments.
CN · 翻译
我们在四旋翼导航与自动泊车问题上验证了框架的有效性；数值实验表明，所提方法能在狭窄环境中实现实时的优化式轨迹规划。
EN · 原文
Source code of our implementation is provided at https://github.com/XiaojingGeorgeZhang/OBCA.
CN · 翻译
实现代码已开源：github.com/XiaojingGeorgeZhang/OBCA。

关键词 Keywords：Collision Avoidance 碰撞避免 ｜ Trajectory Planning 轨迹规划 ｜ Convex Optimization 凸优化 ｜ Strong Duality 强对偶性 ｜ Signed Distance 符号距离（编者据内容归纳）

四、引言精选（为什么这个问题重要）

① 避碰是自主系统的「第一性能力」

EN · 原文
Maneuvering autonomous systems in an environment with obstacles is a challenging problem that arises in a number of practical applications including robotic manipulators and trajectory planning for autonomous systems such as self-driving cars and quadcopters. In almost all of those applications, a fundamental feature is the system's ability to avoid collision with obstacles which are, for example, humans operating in the same area, other autonomous systems, or static objects such as walls.
CN · 翻译
在有障碍物的环境中操纵自主系统是个难题，出现在许多实际应用中，包括机械臂以及自动驾驶汽车、四旋翼等自主系统的轨迹规划。几乎所有这类应用都有一个根本能力要求：避开障碍物——比如同区域作业的人、其他自主系统，或墙壁之类的静态物体。

② 为什么优化式轨迹规划（MPC）这么火

EN · 原文
Optimization-based trajectory planning algorithms such as Model Predictive Control (MPC) have received significant attention recently, ranging from (unmanned) aircraft to robots to autonomous cars [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. This can be attributed to the increase in computational resources, the availability of robust numerical algorithms for solving optimization problems, as well as MPC's ability to systematically encode system dynamics and constraints inside its formulation.
CN · 翻译
以模型预测控制（MPC）为代表的优化式轨迹规划算法近来备受关注，应用从（无人）飞行器到机器人再到自动驾驶汽车。原因有三：计算资源增长、求解优化问题的稳健数值算法成熟，以及 MPC 能系统性地把系统动力学与约束编码进问题表述。

③ 避碰约束的三宗罪：不可微、非凸、整数变量

EN · 原文
One fundamental challenge in optimization-based trajectory planning is the appropriate formulation of collision avoidance constraints, which are known to be non-convex and computationally difficult to handle in general. While a number of formulations have been proposed in the literature for dealing with collision avoidance constraints, they are typically limited by one of the following features: (i) The collision avoidance constraints are approximated through linear constraint, and it is difficult to establish the approximation error [9]; (ii) Existing formulations focus on point-mass controlled objects, and are not applicable to full-dimensional objects; (iii) When the obstacles are polyhedral, then the collision avoidance constraints are often reformulated using integer variables [13]. While this reformulation is attractive for linear systems with convex constraints since in this case a mixed-integer convex optimization problem can be solved, integer variables should generally be avoided when dealing with nonlinear systems when designing real-time controllers for robotic systems.
CN · 翻译
优化式轨迹规划的一个根本挑战，是如何恰当地表述避碰约束——它们已知是非凸的，一般很难计算。文献中的各种表述通常受限于以下问题之一：(i) 用线性约束近似避碰约束，但近似误差难以界定；(ii) 只适用于质点被控对象，不适用于全尺寸物体；(iii) 障碍是多面体时，常用整数变量重表述避碰约束。对线性系统 + 凸约束，这种表述很诱人（可解混合整数凸优化）；但为机器人系统设计实时控制器时，应尽量避免整数变量。

④ 本文思路：距离函数 + 强对偶 = 光滑且精确的避碰约束

EN · 原文
In this paper, we focus on a controlled object that moves in a general n-dimensional space while avoiding obstacles, and propose a novel approach for modeling obstacle avoidance constraints that overcomes the aforementioned limitations. Specifically, the contributions of this paper can be summarized as follows: 1. We show that if the controlled object and the obstacles are described by convex sets such as polytopes or ellipsoids (or can be decomposed into a finite union of such convex sets), then the collision avoidance constraints can be exactly and non-conservatively reformulated as a set of smooth non-convex constraints. This is achieved by appropriately reformulating the distance-function between two convex sets using strong duality of convex optimization. 2. We provide a second formulation for collision avoidance based on the notion of signed distance, which characterizes not only the distance between two objects but also their penetration. This reformulation allows us to compute "least-intrusive" trajectories in case collisions cannot be avoided. 3. We demonstrate the efficacy of the proposed obstacle avoidance reformulations on a quadcopter trajectory planning problem and autonomous parking application, where the controlled vehicles must navigate in tight environments. We show that both the distance reformulation and the signed distance reformulation enable real-time path planning and find trajectories even in challenging circumstances.
CN · 翻译
本文关注在一般 n 维空间中运动并避障的被控物体，提出克服上述局限的新方法。贡献如下：1. 若被控物体与障碍物可用多面体、椭球等凸集（或凸集的有限并集）描述，则避碰约束可精确且不保守地重表述为一组光滑的非凸约束——关键在于用凸优化的强对偶性恰当改写两个凸集间的距离函数。2. 给出基于符号距离的第二种表述，不仅刻画两物体间距，还刻画侵入深度——碰撞无法避免时据此计算「最小侵入」轨迹。3. 在四旋翼轨迹规划与自动泊车两个狭窄环境应用中验证：两种表述都能实时路径规划，即便环境严苛也能找到轨迹。
💡 这是全文最有味道的一句：“...the collision avoidance constraints can be exactly and non-conservatively reformulated as a set of smooth non-convex constraints.”——注意两个词：「exactly」（精确）和「non-conservatively」（不保守）。既有方法要么近似、要么保守，本文用数学技巧同时干掉两者，这才是「重表述」的真正价值。

五、论文贡献（3 个要点）

EN · 原文
1. Exact smooth reformulation via strong duality. We show that if the controlled object and the obstacles are described by convex sets such as polytopes or ellipsoids (or can be decomposed into a finite union of such convex sets), then the collision avoidance constraints can be exactly and non-conservatively reformulated as a set of smooth non-convex constraints. This is achieved by appropriately reformulating the distance-function between two convex sets using strong duality of convex optimization.
CN · 翻译
1. 强对偶实现精确光滑重表述。物体与障碍可用凸集（或其有限并集）描述时，避碰约束可精确、不保守地改写为光滑非凸约束——用强对偶改写两凸集间距离函数实现。
EN · 原文
2. Signed-distance formulation and least-intrusive trajectories. We provide a second formulation for collision avoidance based on the notion of signed distance, which characterizes not only the distance between two objects but also their penetration. This reformulation allows us to compute "least-intrusive" trajectories in case collisions cannot be avoided.
CN · 翻译
2. 符号距离表述与最小侵入轨迹。给出基于符号距离的第二种表述，同时刻画距离与侵入深度；碰撞无法避免时可计算「最小侵入」轨迹。
EN · 原文
3. Real-time feasibility in tight environments. We demonstrate the efficacy of the proposed obstacle avoidance reformulations on a quadcopter trajectory planning problem and autonomous parking application, where the controlled vehicles must navigate in tight environments. We show that both the distance reformulation and the signed distance reformulation enable real-time path planning and find trajectories even in challenging circumstances.
CN · 翻译
3. 狭窄环境下的实时可行性。在四旋翼轨迹规划与自动泊车中验证：两种表述都支持实时路径规划，即使严苛环境也能找到轨迹。

六、结论中英对照

EN · 原文
In this paper, we presented smooth reformulations for collision avoidance constraints for problems where the controlled object and the obstacle can be represented as the finite union of convex sets. We have shown that non-differentiable polytopic obstacle constraints can be dealt with via dualization techniques to preserve differentiability, allowing the use of gradient- and Hessian-based optimization methods. The presented reformulation techniques are exact and non-conservative, and apply equally to point-mass and full-dimensional controlled vehicles. Furthermore, in case collision-free trajectories cannot be generated, our framework allows us to find least-intrusive trajectories, measured in terms of penetration.
CN · 翻译
本文为「被控物体与障碍均可表示为凸集有限并集」的问题给出了避碰约束的光滑重表述：不可微的多面体障碍约束可通过对偶化技术保持可微性，从而使用基于梯度/海森的优化方法。所提重表述精确且不保守，对质点与全尺寸被控车辆同样适用；且无法生成无碰撞轨迹时，还能以侵入深度为度量找到最小侵入轨迹。
EN · 原文
Our numerical studies, performed on a quadcopter trajectory planning and autonomous car parking example, indicate that, when appropriately initialized, the proposed framework is robust, real-time feasible, and able to generate dynamically feasible trajectories. Furthermore, we have seen that the initialization method is problem-dependent, and should be chosen depending on the system at hand. Current research focuses on appropriately warm starting the discretization time T_opt, as well as on methods for further speeding up computation times.
CN · 翻译
在四旋翼轨迹规划与自动泊车上的数值研究表明：只要初始化得当，该框架稳健、实时可行，且能生成动力学可行的轨迹。同时发现初始化方法与系统相关，需按具体系统选择。当前研究聚焦于如何恰当地热启动离散化时间 T_opt，以及进一步加速计算的方法。

七、编者解读：这篇论文到底讲了什么（大白话版）

  1. 问题：想让无人船/无人机自己规划路径，通常写成「优化问题」——在「别撞障碍物」等约束下找最好走的轨迹。但「别撞上」这个约束天生带尖角（不可微），梯度类优化器一碰到它就「算不动」；老办法要么线性近似（误差说不清），要么只适用质点，要么引入整数变量（非线性系统实时求解要命）。
  2. 做法：用凸优化的强对偶性，把「两个凸集之间的距离」这个不可微函数，改写成一个光滑的等价形式——数学上精确、不保守、不丢信息。再进一步用符号距离，把「距离」和「侵入深度」统一起来：躲不开时，就找侵入最浅的折中轨迹。
  3. 结果：四旋翼穿窄缝、自动泊车贴身入库都能实时算出来；轨迹满足动力学约束，低级控制器跟得上。代价是初始化要选对（热启动），论文也坦承这一点。
  4. 最值钱的观点：同一个约束，换一种数学写法，就能从「算不动」变成「实时可算」——工程问题的解有时不在模型里，而在「怎么把约束写出来」。
  5. 工程意义：这正是无人船自主避碰的核心数学工具——把 COLREGs 规则、动态障碍物写成约束放进 MPC，船舶在狭窄航道也能实时规划；「最小侵入轨迹」对应航海里「让清」与「保向」的博弈权衡，思想是相通的。
🎯 对保研的启示：本文展示了顶级控制组的工作方式——抓住一个「约束表述」小问题，用对偶理论做出精确改写，再拿两个真实应用验证并开源。面试时若能讲清「强对偶为什么能把不可微变成可微」，比背十个模型名更能征服导师。

八、给准大一的阅读路线图 & 延伸方向

📖 怎么读这篇论文（三遍法）

  1. 第一遍（10 分钟）：只读摘要和术语表，回答三个问题——问题是什么？方法是什么？结果是什么？（不可微避碰约束 → 强对偶光滑化 → 实时可行）
  2. 第二遍（20 分钟）：读引言 + 结论，重点体会「现有三种表述各自的坑」以及「符号距离如何兼顾距离与侵入」。
  3. 第三遍（30 分钟）：读引言第④段的贡献描述，跳过公式与附录证明，只看文字逻辑；术语不懂回查术语表。

🚀 这个方向你能延伸做什么

九、英文摘要朗读（练听力用）

先盲听一遍→再看对照稿→再听一遍。目标是听出每个术语（strong duality、signed distance、penetration、least-intrusive trajectories）和链接（github.com/XiaojingGeorgeZhang/OBCA）。