单个机器人高效重排积木网格，保持连接性并最小化总时间。
Efficient Reconfiguration of Tile Arrangements by a Single Active Robot
- 用单个机器人通过搬运和移动实现网格重构，保持连通性。
- 对不相交区域场景给出多项式时间近似算法，最优携带距离可达2倍缩放实例。
- 首次引入带权移动成本，证明问题为NP难，适合机器人路径规划研究者。
我们研究在二维连通网格布局中，利用单个可动机器人将被动积木从起始配置重新排列到目标配置的问题。该机器人可在积木上移动，可移除某位置的积木，并通过步行将积木搬运至新位置。目标是设计调度方案以最小化总完成时间（makespan），同时保证积木布局始终连通。本文给出正负结果：(1) 推广问题，引入依赖是否携带的权重移动成本，证明此变体为NP-hard；(2) 针对起始与目标边界框不相交的情况，提出多项式时间常数因子近似算法，且对2倍缩放实例达到最优携带距离。
原文摘要 · Abstract (English)
We consider the problem of reconfiguring a two-dimensional connected grid arrangement of passive building blocks from a start configuration to a goal configuration, using a single active robot that can move on the tiles, remove individual tiles from a given location and physically move them to a new position by walking on the remaining configuration. The objective is to determine a schedule that minimizes the overall makespan, while keeping the tile configuration connected. We provide both negative and positive results. (1) We generalize the problem by introducing weighted movement costs, which can vary depending on whether tiles are carried or not, and prove that this variant is NP-hard. (2) We give a polynomial-time constant-factor approximation algorithm for the case of disjoint start and target bounding boxes, which additionally yields optimal carry distance for 2-scaled instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。