Online Interaction of a Human Supervisor with Multi-Robot Task Allocation

In this paper, an approach is presented that allows a human supervisor to efficiently interact with task allocation in a multi-robot team (MRTA). The interaction is based on online modification of the setting of the employed MRTA optimization algorithm during its computation. For the example of a computationally expensive mixed-integer linear programming algorithm it is demonstrated how to achieve up to optimal solution quality, while simultaneously reducing the required calculation time compared to a fully autonomous optimization. The supervisor is enabled to rate feasible, intermediate solutions based on objective or subjective quality criteria and personal expertise. In that way, also suboptimal solutions can be chosen to be satisfactory, and the solver can be terminated without the need to wait for the completion of the computation of the optimal solution. An event-based communication concept with queries is used as an efficient means of implementation of the interaction. Furthermore, the supervisor can support the MRTA solver in finding good solutions by defining crucial parts of the solution structure. These intuitive commands are internally translated into constraints and are added to the problem as lazy constraints. This combination of human expertise and state-of-the-art optimization algorithms allows to achieve up to potentially optimal task allocation in much shorter time.