多边形多机器人运动规划的FPTAS
该论文针对多边形环境中由常数复杂度多边形表示的 k 个平移机器人，给出首个对任意固定 k 均适用的全多项式时间近似方案（FPTAS），覆盖最小总行驶距离、最小单机器人最大距离、最小完工时间三种目标，并可直接推广到任意固定维度 d 的多面体环境与多面体机器人。该结果解决了 Agarwal、Halperin、Sharir、Steiger [SODA'24] 与 Agarwal、Holmgren、Steiger [SODA'26] 提出的开放问题——此前仅对 k=2 的单位正方形机器人给出 FPTAS，或对固定 k 的单位正方形/单位圆盘机器人给出双准则近似算法；作者称新算法显著更简单。
发布于 10-22 10:57来源：arXiv cs.RO
转载 · 官方发布原文：arXiv cs.RO ·《FPTAS for Polygonal Multi-Robot Motion Planning》查看原链
我们研究多边形环境中多边形机器人的多机器人运动规划问题。 该问题的设定包括一个具有 n 个顶点的多边形区域 W 和 k 个机器人 R_1,…,R_k，每个机器人在 W 中平移，且每个机器人由一个常数复杂度的多边形表示。 给定机器人在 W 中的起始构型 s 和目标构型 t，问题的目标是找到一条从 s 到 t 的无碰撞运动规划，且该规划在某个代价函数下最短。
我们提出了首个针对任意固定数量 k 个机器人的全多项式时间近似方案（FPTAS），涵盖最小和（min-sum）目标、最小最大（min-max）目标和最小完工时间（min-makespan）目标。 其中，最小和变体旨在最小化所有机器人的总行驶距离，最小最大变体旨在最小化单个机器人的最大行驶距离，最小完工时间变体旨在假设所有机器人以最大速度 1 移动时最小化总时间成本。
该算法可直接推广到任意固定维度 d 下的多面体环境与多面体机器人问题。 我们的结果解决了 Agarwal、Halperin、Sharir、Steiger [SODA'24] 以及 Agarwal、Holmgren、Steiger [SODA'26] 提出的一个开放问题；这两项工作分别针对 k=2 个单位正方形机器人给出了 FPTAS，并针对固定数量 k 个单位正方形或单位圆盘机器人给出了双准则近似算法。
与先前结果相比，我们的算法显著更简单。