姿势图优化是在机器人感知的许多领域遇到的非凸优化问题。它的收敛到准确的解决方案由两个因素来调节：使用成本函数的非线性和姿势变量的初始配置。在本文中，我们提出了Hipe，这是一种用于姿势图初始化的新型分层算法。我们的方法利用了一个粗粒图，该图编码了问题几何形状的抽象表示。我们通过结合来自输入本地区域的最大似然估计来构建此图。通过利用这种表示的稀疏性，我们可以以非线性方式初始化姿势图，而无需与现有方法相比，没有计算开销。最终的初始猜测可以有效地引导用于获得最终解决方案的细粒优化。此外，我们对不同成本函数对最终估计的影响进行了经验分析。我们的实验评估表明，HIPE的使用导致更有效，更健壮的优化过程，与最先进的方法相比。
translated by 谷歌翻译
我们为平面姿势图优化提供了一个强大的框架，该框架被环闭合离群值污染。我们的框架首先将截短的最小二乘内核包裹的强大的PGO问题拒绝了异常值，从而拒绝了异常值。然后，该框架引入了线性角度表示，以重写最初用旋转矩阵配制的第一个子问题。该框架配置为渐变的非凸度（GNC）算法，以连续解决两个非凸子问题，而无需初始猜测。得益于两个子问题的线性属性，我们的框架只需要线性求解器才能最佳地解决GNC中遇到的优化问题。我们在平面PGO基准中广泛验证了所提出的框架，称为Degnc-Laf（脱钩的非跨性别量均具有线性角度公式）。事实证明，它比标准和通用GNC的速度显着（有时达到30倍以上），同时导致高质量的估计值。
translated by 谷歌翻译
我们描述了一种使用机器人应用程序中常见的一类离散连续因子图进行平滑和映射的通用方法。虽然有公开可用的工具提供灵活且易于使用的接口，以指定和解决以离散或连续图形模型提出的优化问题，但目前尚无类似的一般工具，可以为混合离散性问题提供相同的功能。我们旨在解决这个问题。特别是，我们提供了一个库DC-SAM，将现有的工具扩展为以因子图定义的优化问题，以设置离散模型的设置。我们工作的关键贡献是一种新颖的解决方案，用于有效地回收离散连续优化问题的近似解决方案。我们方法的关键见解是，虽然对连续和离散状态空间的共同推断通常很难，但许多通常遇到的离散连续问题自然可以分为“离散部分”，并且可以轻松地解决的“连续部分” 。利用这种结构，我们以交替的方式优化离散和连续变量。因此，我们提出的工作可以直接表示离散图形模型的直接表示和近似推断。我们还提供了一种方法来恢复离散变量和连续变量的估计值的不确定性。我们通过应用于三个不同的机器人感知应用程序的应用来证明我们的方法的多功能性：点云注册，健壮的姿势图优化以及基于对象的映射和本地化。
translated by 谷歌翻译
在这项工作中，我们介绍了配备有明确性能的第一个初始化方法，该方法适用于姿势图同时定位和映射（SLAM）和旋转平均（RA）问题。 SLAM和旋转平均通常正义为大规模的非渗透点估计问题，具有许多糟糕的本地最小值，可以捕获通常应用的平滑优化方法来解决它们;因此，标准SLAM和RA算法的性能至关重要取决于用于初始化该本地搜索的估计的质量。虽然在文献中出现了SLAM和RA的许多初始化方法，但通常可以获得纯粹的启发式近似值，这使得难以确定是否（或在什么情况下）这些技术可以可靠地部署这些技术。相比之下，在这项工作中，我们研究通过光谱松弛镜头初始化的问题。具体而言，我们推出了SLAM和RA的简单谱弛豫，其形式使我们能够利用经典的线性代数技术（特征向量扰动界限）来控制从我们的光谱估计到（未知）地基实际和该距离作为测量噪声的函数的估计问题的全局最小化器。我们的结果揭示了测量网络在控制估计精度下播放的光谱图 - 理论性能的关键作用;此外，作为我们分析的副产物，我们在估计误差上获得了最大似然估计的估计误差，这可能具有独立兴趣。最后，我们在实验上展示了我们的光谱估计器在实践中非常有效，与现有的最先进技术相比，在较低的计算成本下生产可比或优异质量的初始化。
translated by 谷歌翻译
本文提出了Kimera-Multi，第一个多机器人系统，（i）是强大的，并且能够识别和拒绝由感知混叠产生的不正确和内部机器人循环闭合，（ii）完全分布，仅依赖于本地（点对点）通信实现分布式本地化和映射，（iii）实时构建环境的全球一致的度量标准三维网状模型，其中网格的面部用语义标签注释。 Kimera-Multi由配备有视觉惯性传感器的机器人团队实现。每个机器人都构建了局部轨迹估计和使用Kimera的本地网格。当通信可用时，机器人基于一种基于新型分布式刻度非凸性算法发起分布式地点识别和鲁棒姿态图优化协议。所提出的协议允许机器人通过利用机器人间循环闭合而鲁棒到异常值来改善其局部轨迹估计。最后，每个机器人使用其改进的轨迹估计来使用网格变形技术来校正本地网格。我们在光逼真模拟，SLAM基准测试数据集中展示了Kimera-Multi，以及使用地机器人收集的靠户外数据集。真实和模拟实验都涉及长轨迹（例如，每个机器人高达800米）。实验表明，在鲁棒性和准确性方面，kimera-multi（i）优于现有技术，（ii）在完全分布的同时实现与集中式大满贯系统相当的估计误差，（iii）在通信带宽方面是显着的（iv）产生精确的公制语义3D网格，并且（v）是模块化的，也可以用于标准3D重建（即，没有语义标签）或轨迹估计（即，不重建3D网格）。
translated by 谷歌翻译
我们考虑分布式姿势图优化（PGO）的问题，该问题在多机器人同时定位和映射（SLAM）中具有重要的应用。我们提出了用于分布式PGO（$ \ mathsf {mm \！\！\！\！\！pgo} $）的大量最小化方法（mm）方法，该方法适用于一类宽类强大的损失内核。 $ \ mathsf {mm \！\！ - \！\！pgo} $方法可以在轻度条件下收敛到一阶关键点。此外，请注意$ \ mathsf {mm \！\！ - ！ - \！\！pgo} $方法是让人联想到近端方法，我们利用Nesterov的方法并采用自适应重启来加速收敛。生成的分布式PGO的加速MM方法 - 既有网络中的主节点（$ \ Mathsf {amm \！\！\！\！\！\！ ！ - \！\！pgo}^{＃} $） - 与$ \ mathsf {mm \！\！\！ - \！\！pgo} $相比，收敛速度更快，而无需牺牲理论保证。特别是，$ \ mathsf {amm \！\！\！ - \！\！ $ \ mathsf {amm \！\！\！\！pgo}^*$使用主节点从所有其他节点汇总信息。这项工作的功效通过对2D和3D SLAM基准数据集的广泛应用以及与现有最新方法的全面比较来验证，这表明我们的MM方法更快地收敛，并为分布式PGO提供更好的解决方案。
translated by 谷歌翻译
现代状态估计通常被表达为优化问题，并使用有效的本地搜索方法解决。这些方法最能保证与本地最小值的融合，但是在某些情况下，全球最优性也可以得到认证。尽管此类全球最佳证书已经为3D姿势格言优化确定了，但是对于基于3D地标的SLAM问题，尚未确定细节，其中估计的状态包括机器人姿势和地图地标。在本文中，我们通过使用图理论方法来解决这一差距，将基于里程碑的SLAM的子问题投入到一种形式，该形式产生了足够的全球最优状态。存在计算这些子问题的最佳证书的有效方法，但首先需要构建大型数据矩阵。我们表明，该矩阵可以以复杂性构建，该复杂性在地标数量中保持线性，并且不超过一个局部求解器的最新计算复杂性。最后，我们证明了证书对基于模拟和现实世界标记的大满贯问题的功效。
translated by 谷歌翻译
本文提出了一种用于在线增量同时本地化和映射（SLAM）的强大优化方法。由于在存在感知混叠的情况下数据关联的NP硬度，可拖动（大约）数据关联方法将产生错误的测量。我们需要猛烈的后端，在达到在线效率限制的同时，在存在异常值的情况下，可以在存在异常值的情况下将其收敛到准确的解决方案。现有的强大SLAM方法要么对离群值敏感，对初始化越来越敏感，要么无法提供在线效率。我们提出了强大的增量平滑和映射（RISAM）算法，这是一种基于渐变的非跨识别性的稳健后端优化器，用于增量大满贯。我们在基准测试数据集上证明了我们的算法实现在线效率，优于现有的在线方法，并匹配或改善现有的离线方法的性能。
translated by 谷歌翻译
定位移动机器人的一种常见方法是测量已知位置点的距离，称为锚点。从距离测量值中定位设备通常是由于测量模型的非线性而作为非凸优化问题。当使用局部迭代求解器（如高斯 - 牛顿）时，非凸优化问题可能会产生次优的解决方案。在本文中，我们为连续范围的本地化设计了最佳证书。我们的公式可以整合运动，从而确保溶液的平滑度，并且对于仅从几个距离测量值进行定位至关重要。拟议的证书几乎没有额外的成本，因为它的复杂性与稀疏本地求解器本身的复杂性相同：位置数量的线性。我们在仿真和现实世界数据集中显示，有效的本地求解器通常会找到全球最佳解决方案（通过我们的证书确认），而当没有证书确认时，简单的随机重新初始化最终会导致可认证的最佳选择。
translated by 谷歌翻译
量化不确定性是主动同时本地化和映射（SLAM）的关键阶段，因为它允许确定执行的最有用的动作。但是，处理完整的协方差甚至Fisher信息矩阵（FIMS）在计算上是沉重的，并且很容易在线系统上棘手。在这项工作中，我们研究了通过\ textit {se（n）}提出的主动图 - 峰的范式，并提出了系统FIM与基础姿势的拉普拉斯矩阵之间的一般关系。此链接使使用图形连接索引作为具有最佳保证的实用程序函数，因为它们近似源于最佳设计理论的众所周知的最佳标准。实验验证表明，所提出的方法会导致在一小部分时间内进行主动猛击的等效决策。
translated by 谷歌翻译
我们提出了Theseus，这是一个有效的应用程序不合时宜的开源库，用于在Pytorch上构建的可区分非线性最小二乘（DNL）优化，为机器人技术和视觉中的端到端结构化学习提供了一个共同的框架。现有的DNLS实施是特定应用程序的，并且并不总是纳入许多对效率重要的成分。 Theseus是应用程序不可静止的，正如我们使用的几个示例应用程序所用的，这些应用程序是使用相同的基础可区分组件构建的，例如二阶优化器，标准成本功能和Lie组。为了提高效率，TheseUS纳入了对稀疏求解器，自动矢量化，批处理，GPU加速度和梯度计算的支持，并具有隐式分化和直接损耗最小化。我们在一组应用程序中进行了广泛的性能评估，显示出这些功能时显示出明显的效率提高和更好的可扩展性。项目页面：https：//sites.google.com/view/theseus-ai
translated by 谷歌翻译
姿势图优化是同时定位和映射问题的一种特殊情况，其中唯一要估计的变量是姿势变量，而唯一的测量值是施加间约束。绝大多数PGO技术都是基于顶点的（变量是机器人姿势），但是最近的工作以相对方式参数化了姿势图优化问题（变量是姿势之间的变换），利用最小循环基础来最大程度地提高范围的稀疏性。问题。我们以增量方式探索周期基础的构建，同时最大程度地提高稀疏性。我们验证一种算法，该算法逐渐构建稀疏循环基础，并将其性能与最小循环基础进行比较。此外，我们提出了一种算法，以近似两个图表的最小周期基础，这些图在多代理方案中常见。最后，姿势图优化的相对参数化仅限于使用SE（2）或SE（3）上的刚体变换作为姿势之间的约束。我们引入了一种方法，以允许在相对姿势图优化问题中使用低度测量值。我们对标准基准，模拟数据集和自定义硬件的算法进行了广泛的验证。
translated by 谷歌翻译
2022-08-22
Outier-bubust估计是一个基本问题，已由统计学家和从业人员进行了广泛的研究。在过去的几年中，整个研究领域的融合都倾向于“算法稳定统计”，该统计数据的重点是开发可拖动的异常体 - 固定技术来解决高维估计问题。尽管存在这种融合，但跨领域的研究工作主要彼此断开。本文桥接了有关可认证的异常抗衡器估计的最新工作，该估计是机器人技术和计算机视觉中的几何感知，并在健壮的统计数据中并行工作。特别是，我们适应并扩展了最新结果对可靠的线性回归（适用于<< 50％异常值的低外壳案例）和列表可解码的回归（适用于>> 50％异常值的高淘汰案例）在机器人和视觉中通常发现的设置，其中（i）变量（例如旋转，姿势）属于非convex域，（ii）测量值是矢量值，并且（iii）未知的异常值是先验的。这里的重点是绩效保证：我们没有提出新算法，而是为投入测量提供条件，在该输入测量值下，保证现代估计算法可以在存在异常值的情况下恢复接近地面真相的估计值。这些条件是我们所谓的“估计合同”。除了现有结果的拟议扩展外，我们认为本文的主要贡献是（i）通过指出共同点和差异来统一平行的研究行，（ii）在介绍先进材料（例如，证明总和证明）中的统一行为。对从业者的可访问和独立的演讲，（iii）指出一些即时的机会和开放问题，以发出异常的几何感知。
translated by 谷歌翻译
束调整（BA）是指同时确定传感器姿势和场景几何形状的问题，这是机器人视觉中的一个基本问题。本文为LIDAR传感器提供了一种有效且一致的捆绑捆绑调整方法。该方法采用边缘和平面特征来表示场景几何形状，并直接最大程度地减少从每个原始点到各自几何特征的天然欧几里得距离。该公式的一个不错的属性是几何特征可以在分析上解决，从而大大降低了数值优化的维度。为了更有效地表示和解决最终的优化问题，本文提出了一个新颖的概念{\ it point clusters}，该概念编码了通过一组紧凑的参数集与同一特征相关联的所有原始点，{\ it点群集坐标} 。我们根据点簇坐标得出BA优化的封闭形式的衍生物，并显示其理论属性，例如零空间和稀疏性。基于这些理论结果，本文开发了有效的二阶BA求解器。除了估计LiDAR姿势外，求解器还利用二阶信息来估计测量噪声引起的姿势不确定性，从而导致对LIDAR姿势的一致估计。此外，由于使用点群集的使用，开发的求解器从根本上避免了在优化的所有步骤中列出每个原始点（由于数量大量而非常耗时）：成本评估，衍生品评估和不确定性评估。我们的方法的实施是开源的，以使机器人界及其他地区受益。
translated by 谷歌翻译
我们研究了估计多元高斯分布中的精度矩阵的问题，其中所有部分相关性都是非负面的，也称为多变量完全阳性的顺序阳性（$ \ mathrm {mtp} _2 $）。近年来，这种模型得到了重大关注，主要是由于有趣的性质，例如，无论底层尺寸如何，最大似然估计值都存在于两个观察。我们将此问题作为加权$ \ ell_1 $ -norm正常化高斯的最大似然估计下$ \ mathrm {mtp} _2 $约束。在此方向上，我们提出了一种新颖的预计牛顿样算法，该算法包含精心设计的近似牛顿方向，这导致我们具有与一阶方法相同的计算和内存成本的算法。我们证明提出的预计牛顿样算法会聚到问题的最小值。从理论和实验中，我们进一步展示了我们使用加权$ \ ell_1 $ -norm的制剂的最小化器能够正确地恢复基础精密矩阵的支持，而无需在$ \ ell_1 $ -norm中存在不连贯状态方法。涉及合成和实世界数据的实验表明，我们所提出的算法从计算时间透视比最先进的方法显着更有效。最后，我们在金融时序数据中应用我们的方法，这些数据对于显示积极依赖性，在那里我们在学习金融网络上的模块间值方面观察到显着性能。
translated by 谷歌翻译
该博士学位论文的中心对象是在计算机科学和统计力学领域的不同名称中以不同名称而闻名的。在计算机科学中，它被称为“最大切割问题”，这是著名的21个KARP的原始NP硬性问题之一，而物理学的相同物体称为Ising Spin Glass模型。这种丰富的结构的模型通常是减少或重新制定计算机科学，物理和工程学的现实问题。但是，准确地求解此模型（查找最大剪切或基态）可能会留下一个棘手的问题（除非$ \ textit {p} = \ textit {np} $），并且需要为每一个开发临时启发式学特定的实例家庭。离散和连续优化之间的明亮而美丽的连接之一是一种基于半限定编程的圆形方案，以最大程度地切割。此过程使我们能够找到一个近乎最佳的解决方案。此外，该方法被认为是多项式时间中最好的。在本论文的前两章中，我们研究了旨在改善舍入方案的局部非凸照。在本文的最后一章中，我们迈出了一步，并旨在控制我们想要在前几章中解决的问题的解决方案。我们在Ising模型上制定了双层优化问题，在该模型中，我们希望尽可能少地调整交互作用，以使所得ISING模型的基态满足所需的标准。大流行建模出现了这种问题。我们表明，当相互作用是非负的时，我们的双层优化是在多项式时间内使用凸编程来解决的。
translated by 谷歌翻译
我们介绍了第一个分布式优化算法，该算法具有懒惰的通信，以进行协作几何估计，现代协作同时本地化和映射（SLAM）和结构 - 莫特 - 莫蒂（SFM）应用程序的骨干。我们的方法允许代理通过融合单个观察结果在中央服务器上合作重建共享的几何模型，但无需传输有关代理本身（例如其位置）的潜在敏感信息。此外，为了减轻迭代优化期间的通信负担，我们设计了一组通信触发条件，使代理能够选择性地上传针对性的本地信息的目标子集，该信息对全球优化有用。因此，我们的方法可实现大量的沟通减少，对优化性能的影响最小。作为我们的主要理论贡献，我们证明我们的方法以全球sublinear收敛速率收敛到一阶关键点。关于合作SLAM和SFM数据集的捆绑调整问题的数值评估表明，我们的方法在现有的分布式技术方面具有竞争力，同时达到了多达78％的总沟通减少。
translated by 谷歌翻译
我们解决了最小化一类能量功能的问题，该功能由数据和平滑度术语组成，这些术语通常发生在机器学习，计算机视觉和模式识别中。尽管离散优化方法能够提供理论最优保证，但它们只能处理有限数量的标签，因此会遭受标签离散偏置的困扰。现有的连续优化方法可以找到Sublabel精确的解决方案，但对于大型标签空间而言，它们并不有效。在这项工作中，我们提出了一种有效的Sublabel精确方法，该方法利用了连续模型和离散模型的最佳属性。我们将问题分为两个顺序的步骤：（i）选择标签范围的全局离散优化，以及（ii）在所选范围内的能量函数凸的有效连续连续的sublabel-carcurate局部改进。这样做可以使我们能够提高时间和记忆效率，同时实际上将准确性保持在与连续凸放放松方法相同的水平上，此外，在离散方法级别上提供了理论最佳保证。最后，我们显示了提出的对一般成对平滑度项的拟议方法的灵活性，因此它适用于广泛的正则化。图像授予问题的说明示例的实验证明了该方法的特性。代码复制实验可在\ url {https://github.com/nurlanov-zh/sublabel-accurate-alpha-expansion}获得。
translated by 谷歌翻译
因子图是用于代表机器人技术各种问题的图形模型，例如运动（SFM），同时定位和映射（SLAM）和校准。通常，在他们的核心上，他们有一个优化问题，其术语仅取决于一小部分变量。因子图解决器利用问题的局部性，以大大减少迭代最小二乘（ILS）方法的计算时间。尽管非常强大，但他们的应用通常仅限于无约束的问题。在本文中，我们通过引入Lagrange乘数方法的因子图版本来对因子图内的变量进行建模。我们通过根据因子图提供完整的导航堆栈来显示我们方法的潜力。与标准导航堆栈不同，我们可以使用因子图对本地规划和本地化的最佳控制建模，并使用标准ILS方法来解决这两个问题。我们在现实世界自主导航方案中验证了我们的方法，并将其与ROS中实现的事实上的标准导航堆栈进行了比较。比较实验表明，对于手头的应用程序，我们的系统优于运行时的标准非线性编程求解器内部优化器（IPOPT），同时实现了类似的解决方案。
translated by 谷歌翻译
我们考虑了一个类别级别的感知问题，其中给定的2D或3D传感器数据描绘了给定类别的对象（例如，汽车），并且必须重建尽管级别的可变性，但必须重建对象的3D姿势和形状（即，不同的汽车模型具有不同的形状）。我们考虑了一个主动形状模型，其中 - 对于对象类别 - 我们获得了一个潜在的CAD模型库，描述该类别中的对象，我们采用了标准公式，其中姿势和形状是通过非非2D或3D关键点估算的-convex优化。我们的第一个贡献是开发PACE3D*和PACE2D*，这是第一个使用3D和2D关键点进行姿势和形状估计的最佳最佳求解器。这两个求解器都依赖于紧密（即精确）半决赛的设计。我们的第二个贡献是开发两个求解器的异常刺激版本，命名为PACE3D＃和PACE2D＃。为了实现这一目标，我们提出了Robin，Robin是一种一般的图理论框架来修剪异常值，该框架使用兼容性超图来建模测量的兼容性。我们表明，在类别级别的感知问题中，这些超图可以是通过关键点（以2D）或其凸壳（以3D为单位）构建的，并且可以通过最大的超级计算来修剪许多异常值。最后的贡献是广泛的实验评估。除了在模拟数据集和Pascal数据集上提供消融研究外，我们还将求解器与深关键点检测器相结合，并证明PACE3D＃在Apolloscape数据集中在车辆姿势估算中改进了最新技术，并且其运行时间是兼容的使用实际应用。
translated by 谷歌翻译