返回全部动态
网格及更一般图上的无碰撞移动问题
原标题：Collision-free Movement on Grids and Beyond
AI 摘要
该论文研究图上的无碰撞移动问题，目标是在最小化总移动距离的前提下，协调一组机器人到达满足连通性要求的目标编队。作者针对网格图及其两种推广（平面图和单位圆图），分析了以主机器人数和总移动长度为参数时的参数化复杂度，并给出了可解与不可解情形之间的精细边界。这是首个处理「给定编队特征而非显式目标位置」的无碰撞运动规划问题的工作。
以上摘要由 AI 生成，可能存在误差。事实请以原文为准。
正文节选
Chair for Algorithm Engineering, Hasso Plattner Institute, Potsdam, Germany and Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israelhendrik.molter@hpi.dehttps://orcid.org/0000-0002-4590-798XSupported by the Israel Science Foundation, grant nr. 1470/24, by the European Union’s Horizon Europe research and innovation programme under grant agreement 949707, by the European Research Council, grant nr. 101039913 (PARAPATH), and by the Deutsche Forschungsgemeinschaft (
发布时间：2026-09-28 12:00
抓取时间：2026-09-28 12:55
来源机构：arXiv