Mixed-Integer Linear Programming Solution to Multi-Robot Task Allocation Problem

Abstract

Multi-robot systems require efficient and accurate planning in order to perform mission-critical tasks. This paper introduces a mixed-integer linear programming solution to coordinate multiple heterogenenous robots for detecting and controlling multiple regions of interest in an unknown environment. The objective function contains four basic requirements of a multi-robot system serving this purpose: control regions of interest, provide communication between robots, control maximum area and detect regions of interest. Our solution defines optimum locations of robots in order to maximize the objective function while efficiently satisfying some constraints such as avoiding obstacles and staying within the speed capabilities of the robots. We implemented and tested our approach under realistic scenarios. We showed various extensions to objective function and constraints to show the flexibility of mixed-integer linear programming formulation.