Balanced Partitioning of Workspace for Efficient Multi-Robot Coordination

Multi-robot terrain coverage approaches that are based on Voronoi partitioning produce unbalanced partitions of the workspace resulting in uneven distribution of the workload to the individual robots. The proposed approach creates partitions of the workspace such that the regions to be covered by individual robots are maximally balanced. This type of partitioning can be especially useful in tasks like floor cleaning, surveillance etc. The proposed approach is suitable for use in indoor environments like office buildings, hospitals etc. It is assumed that the grid map of the workspace is already known. The workspace is transformed into a topological weighted connected graph. Vertex weight is defined by the size of the area it represents. This graph is then partitioned into sub-graphs that are maximally balanced in terms of vertex weights using genetic algorithm. These sub-graphs thus obtained represent balanced partitions which are assigned to the individual robots for further processing.