多机器人运动规划的完全多项式时间近似方案（FPTAS）

该研究给出了多机器人运动规划问题的首个完全多项式时间近似方案（FPTAS），适用于多边形环境中固定数量k个平移多边形机器人，覆盖min-sum、min-max与min-makespan三种目标。算法可推广到任意固定维度d的多胞体环境与多胞体机器人，并解决了Agarwal等人此前关于k=2单位正方形单位圆盘机器人FPTAS的公开问题，且比已有结果更简单。论文将发表于SODA 2027。