Distributed Uniform Partitioning of a Region using Opaque ASYNC Luminous Mobile Robots

摘要

The uniform partitioning problem, driven by the need for an equitable distribution of workload, finds numerous practical applications in the real world. For that purpose, in this paper, we consider N autonomous mobile robots, deployed inside a bounded region. The robots are opaque which means that three collinear robots are unable to see each other as one of the robots acts as an obstruction for the other two. They operate in classical Look-Compute-Move (LCM) activation cycles. Moreover, the robots are oblivious except for a persistent light (which is why they are called Luminous robots) that can determine a color from a fixed color set. Obliviousness does not allow the robots to remember any information from past activation cycles. The Uniform Partitioning problem requires the robots to partition the whole region into sub-regions of equal area, each of which contains exactly one robot. Due to application-oriented motivation, we, in this paper consider the region to be well-known geometric shapes such as rectangle, square and circle. We investigate the problem in asynchronous setting where there is no notion of common time and any robot gets activated at any time with a fair assumption that every robot needs to get activated infinitely often. To the best of our knowledge, this is the first attempt to study the Uniform Partitioning problem using oblivious opaque robots working under asynchronous settings. We propose three algorithms considering three different regions: rectangle, square and circle. Robots partition the region in a distributed way and reach their respective positions in the partitions. The algorithms proposed for rectangular and square regions run in O(N) epochs whereas the algorithm for circular regions runs in O(N2) epochs, where an epoch is the smallest unit of time in which all robots are activated at least once and execute their LCM cycles.