论文标题
通过异步机器人在无限网格上进行移动和时间最佳的任意模式形成
Move and Time Optimal Arbitrary Pattern Formation by Asynchronous Robots on Infinite Grid
论文作者
论文摘要
\ textsc {任意模式形成}（\ textsc {apf}）是在分布式计算中广泛研究的，用于群体机器人。此问题要求设计一种分布式算法，该算法允许由相同的自主移动机器人组成的团队形成任何任意模式为输入。本文认为机器人在二维无限网格上运行。机器人最初位于形成不对称配置的不同网格点上（没有两个机器人具有相同的快照）。他们在完全异步的调度程序下运行，无法访问全球坐标系，但是它们将沿网格线路对齐本地坐标系统的轴。与\ textsc {apf}问题有关的以前的工作将其求解在$ o（\ mathcal {d}^2k）$机器人运动中，在相似条件下，其中$ \ mathcal {d} $是可以包含初始配置和目标配置的最小正方形的一面，并且$ k $是机器人的数量。令$ \ mathcal {d}'= \ max \ {\ Mathcal {d}，k \} $。本文在无限网格上介绍了\ textsc {apf}的两种算法。第一种算法使用$ O（\ Mathcal {d}'）$渐变地移动最佳。第二个算法在$ o（\ Mathcal {d}'）$ epochs中求解\ textsc {apf}问题，我们显示的是渐近的最佳功能。
The \textsc{Arbitrary Pattern Formation} (\textsc{Apf}) is a widely studied in distributed computing for swarm robots. This problem asks to design a distributed algorithm that allows a team of identical, autonomous mobile robots to form any arbitrary pattern given as input. This paper considers that the robots are operating on a two-dimensional infinite grid. Robots are initially positioned on distinct grid points forming an asymmetric configuration (no two robots have the same snapshot). They operate under a fully asynchronous scheduler and do not have any access to a global coordinate system, but they will align the axes of their local coordinate systems along the grid lines. The previous work dealing with \textsc{Apf} problem solved it in $O(\mathcal{D}^2k)$ robot movements under similar conditions, where $\mathcal{D}$ is the side of the smallest square that can contain both initial and target configuration and, $k$ is the number of robots. Let $\mathcal{D}'=\max\{\mathcal{D},k\}$. This paper presents two algorithms of \textsc{Apf} on an infinite grid. The first algorithm solves the \textsc{Apf} problem using $O(\mathcal{D}')$ asymptotically move optimal. The second algorithm solves the \textsc{Apf} problem in $O(\mathcal{D}')$ epochs, which we show is asymptotically optimal.
