Combining re-allocating and re-scheduling for dynamic multi-robot task allocation

Abstract

Multi-robot systems (MRS) working in open and dynamic environments are expected to deal with uncertain arrival of new tasks and environment changes, by repeatedly adapting the current task allocation and schedule, in order to maintain its performance (e.g., total utility, balance, etc.). This paper presents an adaptive approach to multi-robot task allocation (MRTA), which combines two adaptive measures corresponding to different levels of a MRS: (1) re-allocating at inter-robot level, for balancing task allocation, and improving total utility of the MRS, and (2) re-scheduling at intra-robot level, for maintaining each robot's utility against the influence of both re-allocating and environment changes. Our approach is expected to have significantly higher adaptation power than both re-allocating only and re-scheduling only cases. An experiment is conducted to evaluate our approach's capability of improving balance and total utility of the MRS, under different environment settings and different combinations of re-allocating and re-scheduling.