Mar, 2022

关于多机器人最小最大延迟巡逻问题的循环解决方案

PDF
TL;DR这篇论文考虑了关于在度量空间中把 k 个机器人分配给 n 个位置完成巡逻的最优方案问题。作者提出了一种环状巡逻方案，并证明了这种方案的最优解可用 1+ε 倍近似算法求得，并且提出了一个 2 (1-1/k) 的近似算法。
surveillance problempatrol scheduletravelling salesman problemcyclic solutionsapproximation
发现论文，激发创造
  • 局部搜索在双倍指标下为 k-Means 提供 PTAS

    使用局部搜索启发式策略，本文证明了在任何固定维度的欧几里得空间中，k-means 问题均可提供 PTAS。

    Mar, 2016

  • 基于图形的多机器人最优路径规划：完整算法和有效的启发式算法

    通过与网络流的等价性和整数线性规划，我们设计了用于解决四个不同目标的新颖和完整算法，从而解决了最佳多机器人路径规划问题。采用基于 ILP 算法模型和启发式算法的组合方法，能够在几秒钟内计算出包含数百个机器人，环境密集的问题的 1.x - 最优解。

    Jul, 2015

  • 在图上为多个机器人规划最优路径

    本文研究基于图的多机器人路径规划问题，提出两种多流基于整数线性规划算法，计算最小到达时间和最小总距离的解决方案，其算法性能表现得到评估，并能够适应其他 MPP 问题变体。

    Apr, 2012

  • T*$\varepsilon$ -- 平面曲率约束系统最短时间有效运动规划的有界次优算法

    该研究考虑在存在障碍物的情况下，寻找曲率受限的系统的无碰撞路径，同时将执行时间最小化。通过找到有界次优的解，而不是时间最优解，可以显著降低使用的时间最优转换的数量，并仍然保证解的质量。

    Apr, 2022

  • 有界拉伸标记群体机器人重新配置的协同运动规划

    该研究论文在协同运动规划和群体机器人方面取得了突破，提出了一种恒定算法以最小化协同平行运动计划的执行时间，并证明了最小执行时间的找到是 NP 难问题。

    Jan, 2018

  • iMTSP: 用命令式学习解决最小 - 最大多旅行商问题

    该论文提出了一种新颖的自我监督、双层优化学习框架（imperative MTSP），将多旅行商问题（MTSP）通过强制性学习的方式分解为多个单旅行商问题（TSP），并使用控制变量梯度估计算法克服了梯度方差问题，实验证明该方法在大规模问题下比先进的强化学习基线收敛更快，并找到比 Google OR-Tools MTSP 求解器短 80% 的最优旅行路径。

    May, 2024

  • 多智能体路径规划的精确算法和下界：树状拓扑的威力

    在多智能体路径规划问题中，我们通过参数化复杂性框架提出了系统研究，给出了问题的难度结果和固定参数可解性结果。

    Dec, 2023

  • 学习巡回：运算符设计用于解决方案可行性映射的接送旅行推销员问题

    本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送 TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。

    Apr, 2024

  • 提前预计以避免迟到：解决困难约束旅行推销员问题

    使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。

    Mar, 2024

  • 圆上 Monge 成本的快速运输优化

    研究采用局部优化运输计划的理论进行解决图像处理的问题。得到所有局部最优输运计划都与移动呈共轭关系的结论，并验证了局部最优输运计划的费用是以移动参数的凸函数。提出了一种算法可以近似优化费用，当所有质量是 1/M 的整数倍时，该算法可以在 O (NlogM) 操作中实现准确解决方案。

    Feb, 2009