# Managing Redundancy in a Multiple-Robot Orienteering Problem for Equilibrium and Robustness
## 1 Introduction  
In various missions, whether drone is conducting post-disaster search and rescue operations [1, 2, 3, 4] or a ground mobile robot is exploring and perceiving the surrounding environment [5, 6, 7, 8, 9], the initial goal usually involves exploring and mapping the environment. The task of an agent exploring its surroundings can be modeled as the Orienteering Problem (OP) in many scenarios [7, 8, 9]. OP refers to determining a walk with a given budget from a given starting point, maximizing the total reward collected along the walk [7]. The reward depends on the vertices visited along the walk. The focus of robotic exploring tasks is gradually shifting to unmanned systems composed of multiple robots. Such autonomous systems can help solve new problems or improve existing solutions. In exploring unknown environments, using multiple robots can shorten the overall exploration time, improve accuracy, and be more robust to failures [10, 11, 12, 13]. In [14], a Multiple-robot Orienteering Problem (MOP) aims to design paths for \(n\) robots, maximizing the sum of rewards collected by all robots. Recently, [PERSON] et al. proposed the Robust Multiple-robot Orienteering Problem (RMOP) [15], which further considers robots operating in adversarial or fail-prone environments.  
The applications of this methodology extend far beyond military domains, holding significant potential in numerous civilian scenarios as well. For instance, in a large-scalepost-disaster search and rescue operation, as illustrated in Figure 1, the disaster area can be abstracted as a network where nodes and links represent the critical elements of the rescue mission. The nodes are categorized into two types: target points for searching for survivors (mission points) and waypoints that serve as relays. In the complex and hazardous post-disaster environment, direct communication and passage between mission points are often obstructed, necessitating that the drone fleet first establishes a reliable communication relay network. These relay points can also be assigned additional functions, such as serving as temporary drone maintenance, recharging, or data-uplink stations. By assigning differentiated reward values to different types of nodes (both mission and relay points), they can be handled uniformly. Considering the urgency of disaster rescue missions and the dynamic nature of the environment (e.g., aftershocks, building collapses), the planning of rescue routes must possess a high degree of robustness. Therefore, the RMOP methodology can provide powerful decision support for such tasks, ensuring that in a worst-case scenario where some drones fail or lose contact, the overall mission reward (such as search and rescue coverage and communication network integrity) is still maximized. Beyond disaster response [4; 16; 17], this robust multi-robot path planning method shows broad application prospects in various other fields, including environmental monitoring [15; 18], precision agriculture[18], logistics and transportation [7; 19], and tourist route planning [7; 19].  
RMOP focuses on selecting collections that can withstand the worst-case scenario of removing certain subsets of projects. Under certain circumstances, RMOP can effectively balance the trade-off between excessive overlap (resulting in insufficient reward) and insufficient overlap (resulting in insufficient redundancy). However, its effectiveness diminishes for sparse graphs--a common characteristic of networks formed by drones operating deep within enemy territory with minimal connections. To overcome these challenges, we propose the Robust Multiple-robot Orienteering Problem with Workload Balancing (RMOPWB). It can realize the redundancy balance of the system well.