A novel distributed scheduling algorithm for time-critical multi-agent systems

This paper describes enhancements made to the distributed performance impact (PI) algorithm and presents the results of trials that show how the work advances the state-of-the-art in single-task, single-robot, time-extended, multiagent task assignment for time-critical missions. The improvement boosts performance by integrating the architecture with additional action selection methods that increase the exploratory properties of the algorithm (either soft max or e-greedy task selection). It is demonstrated empirically that the average time taken to perform rescue tasks can reduce by up to 8% and solution of some problems that baseline PI cannot handle is enabled. Comparison with the consensus-based bundle algorithm (CBBA) also shows that both the baseline PI algorithm and the enhanced versions are superior. All test problems center around a team of heterogeneous, autonomous vehicles conducting rescue missions in a 3-dimensional environment, where a number of different tasks must be carried out in order to rescue a known number of victims that is always more than the number of available vehicles.