WikiEdge:ArXiv-2409.06486v1/abs

编辑

• 标题：Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain
• 中文标题：多机器人路径规划：在密集填充、有限域中的多智能体路径寻找
• 发布日期：2024-09-10T13:15:32+00:00
• 作者：Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Jonas Neutzner, Christian Rieck, Christian Scheffer
• 分类：cs.CG, cs.DS, F.2.2
• 原文链接：http://arxiv.org/abs/2409.06486v1

摘要：我们研究了在一个简单连通域内部的标记代理的多智能体路径规划问题：给定每个代理的唯一起始位置和目标位置，目标是找到一系列平行的、无碰撞的代理运动，以最小化所有代理到达各自目标所需的总时间（即完工时间）。一个自然的情况是简单连通的多边形域，具有轴平行的边界和整数坐标，即简单多米诺，这相当于一个简单连通的格子单位方块或单元的并集。我们专注于密集打包代理的特别具有挑战性的设置，即每个单元一个代理，这极大地限制了代理的机动性，并需要复杂的运动协调。我们为这个问题提供了一系列新结果，包括（1）对保证存在重新配置计划的多米诺的特征描述；（2）对导致完工时间最坏情况界限的形状参数的特征描述；（3）一套算法，以在机动性严重受限的情况下实现渐近最坏情况的最优性能。这对应于界定获得的完工时间与任何代理的起始位置和目标位置之间的最大最小距离所提供的下界及我们的形状参数之间的比率。我们的结果扩展了Demaine等人（SIAM计算杂志，2019年）对固体矩形域问题的研究，以及Alpert等人（计算几何，2022年）在与之密切相关的排列路由领域的研究。