Equitable workload partitioning for Multi-Robot exploration through pairwise optimization

Abstract

One of the main challenges when using multiple robots to explore unknown environments is the allocation of target points or regions to the individual units. To date, commonly used approaches produce uneven assignment of targets in situations where multiple targets have to be assigned to each robot. This imbalance can lead to increased overall exploration time and poses an interesting task for further investigation. Based on insights from Multi-Robot Routing and Traveling Salesman Problem research, we propose a specific algorithm for target point allocation that has advantageous properties in highly dynamic applications like exploration. The presented pairwise optimization procedure is suitable for application in distributed and challenging settings, not requiring central coordination or all to all communication, making our exploration strategy robust and flexible. We provide a theoretical analysis and statistical evaluations. Comparisons with representative approaches from the literature show that our algorithm is competitive with the best performing centralized approach.