Harnessing Certainty to Speed Task-Allocation Algorithms for Multi-Robot Systems

Abstract

Some problems are best solved by systems of multiple robots, in which each robot is assigned one task. A multi-robot system can, upon the start of a series of tasks, compute the optimal task allocation for best performance of the team. For certain systems, during runtime, changes in the environment, tasks, and state of individual robots might change which allocation of tasks to robots is optimal, and the performance of the team would improve if the robots switched tasks. Because communication between robots is expensive, in some cases it is better to calculate an interval in which changes in the environment, tasks, and robots are not significant enough to render the original allocation suboptimal. This way, robots only initiate communication and correction if the system is likely to switch tasks, which limits the costs of communication and computation in the system. In the problem of task allocation of single robot, single task cases where environments and thus optimal assignments are expected to vary over time, some knowledge of the system might help reduce computation and make possible a more scalable algorithm for determining cost changes. In some systems, some costs may be known not to vary over time. This research proposes creating and analyzing cost matrices of assignments to examine if taking advantage of the certainty of some variables will improve performance. If 2 successful, models for exploiting certainty of task allocation will take less computation than calculating ranges for all variables, and will save resources during runtime.