Managing Redundancy in a Multiple-Robot Orienteering Problem for Equilibrium and Robustness

In our work, the Robust Multiple-robot Orienteering Problem with Workload Balancing is constructed for the first time. Our primary contribution lies in the rigorous formulation of this problem as a three-stage optimization task. It leverages the Robust Multiple-robot Orienteering Problem (RMOP) as the initial stage. The Path Replanning stage and the workload balancing stage are introduced to minimize walk redundancy and achieve workload equilibrium. The resultant solution upholds the optimality inherent to the original RMOP. Additionally, we craft a suite of heuristic strategies to mitigate redundancy and employ Monte Carlo sampling to tackle the problem. Our algorithm analysis indicates that the method has asymptotic convergence properties and a feasible time complexity under certain conditions. Local parallelization of the algorithm can further improve its performance. Our simulation studies demonstrate that our approach can efficaciously attain a balance between robustness and workload without compromising performance in the presence of adversarial challenges.