Arbitrary Pattern Formation on a Continuous Circle by Oblivious Robot Swarm

摘要

In the field of distributed system, Arbitrary Pattern Formation (APF) problem is an extensively studied problem. The purpose of APF is to design an algorithm to move a swarm of robots to a particular position on an environment (discrete or continuous) such that the swarm can form a specific but arbitrary pattern given previously to every robot as an input. In this paper the solvability of the APF problem on a continuous circle has been discussed for a swarm of oblivious and silent robots without chirality under a semi synchronous scheduler. Firstly a class of configurations called \textit{Formable Configuration}($FC$) has been provided which is necessary to solve the APF problem on a continuous circle. Then considering the initial configuration to be an $FC$, an deterministic and distributed algorithm has been provided that solves the APF problem for $n$ robots on a continuous circle of fixed radius within $O(n)$ epochs without collision.