跳到正文
热点事件持续更新

宽松邻近约束下多智能体路径规划被证 NP 难

1 篇报道1 个报道来源9 小时前更新

先了解这件事

AI 综述

Takahiro Suzuki 与 Keisuke Okumura 发表论文,证明在通信距离 r 满足 2≤r=O(|V|^{1-ε})(ε 为固定常数、|V| 为顶点数)时,为 r-Connected Unlabeled Multi-agent Pathfinding(rCUMAPF)问题寻找 makespan 不超过 2 的解是 NP 难的。 该问题要求可互换的智能体在有限通信距离内始终保持单一连通群体。这一结果说明,即使邻近约束相对宽松,求最短完工时间的最优解仍然计算困难。

AI 根据报道生成 · 13 分钟前更新

报道时间线

沿着报道,了解事件的不同侧面。

11月18日
  1. arXiv cs.MA
    即使宽松的邻近约束也会让 makespan 最优的无标签多智能体路径规划变难

    针对可互换智能体需在有限通信距离 r 内始终保持单一连通群体的 r-Connected Unlabeled Multi-agent Pathfinding(rCUMAPF)问题。

本事件热度走势

还没有足够的连续观测数据,暂不绘制趋势。