Static and Time-Extended 1-on-1 Multi-Agent Task Allocation with Implements and Limited Autonomy

Abstract

In this paper, we propose and formulate the static and time-extended one-on-one multi-agent task allocation problem with implements and limited autonomy (MATAILA). The objective is to assign tasks to a team of agents statically or over a receding time horizon, while minimizing the overall multi-agent team's cost of performing the tasks and the penalty cost for unaccomplished tasks, all while maintaining sufficient battery level across the team. The basis of the studied problem is the (static one-on-one) axial 3-index assignment problem with the extensions on the time horizon and agents' autonomy. Time-extended MATAILA is a computationally expensive problem, that we simplify by a static MATAILA which focuses only at the tasks pending in the present period and is myopic towards the tasks appearing in the future. We compare the performance of the proposed models in scenarios where all tasks are known a priori. We analyze the performance and scalability of the two approaches experimentally in simulations and show their efficiency in dynamically changing scenarios.