Fair subdivision of multi-robot tasks

Abstract

We study the problem of distributing a single global task between a group of heterogeneous robots. We view this problem as a fair division game. In this setting, every robot defines a preference function over parts of the task according to its sensing and motion capabilities. These preferences are described by density functions over the task. With such interpretation, we want to find an allocation of the global task that maximizes the probability of task completion. We first formulate the task distribution problem as a fair subdivision problem and provide a centralized algorithm to compute the allocations for each robot. We provide a complexity analysis and computational results of the algorithm.