Cost-efficient inter-robot delivery for resource-constrained and interdependent multi-robot schedules

Abstract

A multi-robot system in resource-constrained environments needs to obtain resources for task execution. Typically, resources can be fetched from fixed stations, which, however, can be costly and even impossible when fixed stations are unavailable, depleted or distant from task execution locations. We present a method that allows robots to acquire urgently required resources from those robots with superfluous residual resources, by conducting rendezvouses with these robots. We consider a scenario where tasks are organised into a schedule on each robot for sequential execution, with cross-schedule dependencies for inter-robot collaboration. We design an algorithm to systematically generate such rendezvouses for entire multi-robot system to increase the proportion of tasks whose resource demands are satisfied. We also design an algorithm that periodically reallocates tasks among robots to improve the cost-efficiency of schedules. Our experiment shows the synergetic effectiveness of both algorithms, when fixed stations are unavailable and all resources are fetched through inter-robot delivery. We also investigate the effectiveness of inter-robot delivery in scenarios where fixed stations are existent but distant from the locations of tasks.