Optimum Circle Formation by Autonomous Robots

摘要

This paper considers a constrained version of the circle formation problem for a set of asynchronous, autonomous robots on the Euclidean plane. The circle formation problem asks a set of autonomous, mobile robots, initially having distinct locations, to place themselves, within finite time, at distinct locations on the circumference of a circle (not defined a priori), without colliding with each other. The constrained circle formation problem demands that in addition the maximum distance moved by any robot to solve the problem should be minimized. A basic objective ofthe optimization constrain is that it implies energy savings ofthe robots. This paper presents results in two parts. First, it is shown that the constrained circle formation problem is not solvable for oblivious asynchronous robots under ASYNC model even if the robots have rigid movements. Then the problem is studied for robots which have O(1) bits of persistent memory. The initial robot configurations, for which the problem is not solvable in this model, are characterized. For other configurations, a distributed algorithm is presented to solve the problem for asynchronous robots. Only one bit of persistent memory is needed in the proposed algorithm.