# Managing Redundancy in a Multiple-Robot Orienteering Problem for Equilibrium and Robustness
## 2 Materials and Methods
### Algorithm for RMOPWB  
This section proposes an efficient method for solving RMOPWB. Figure 4 illustrates the entire process of the algorithm. In Algorithm 1, the main procedure of the algorithm for solving RMOPWB is shown. To achieve workload balancing, perform Monte Carlo sampling on the solution set \(\mathcal{S}^{*}\). After setting the Monte Carlo sampling times \(K\) and the load function \(h\), the algorithm executes \(K\) loops, and each loop obtains a sample (i.e., a solution to the first two stages of RMOPWB) through two functions (_RMOP_ and _PR_). After sampling, calculate the load of each solution according to the load function \(h\) and select the most balanced solution.  
Figure 4: Description of the entire process of the algorithm. Our algorithm has three main modules, which correspond to the three stages of the RMOPWB. The three modules are (1) RMOP Solver, (2) Path Replan, and (3) Workload Balance. The input information has three blocks: map information, robot cluster information, and attacker information. The RMOP Solver takes the three input information and some configuration information as inputs and outputs the walks of the multi-robot system. The Path Replanning module replans the walks. After sampling these two steps several times, the workload balancing module processes the sampling results.  
The _RMOP_ function serves as the solver for the RMOP (Stage #1). This stochastic solver typically generates multiple optimal RMOP solutions. The _PR_ function, designed for stage #2, reconstructs input walks to minimize path redundancy through an optimization process. For a formal algorithm description, let \(L\) denote the workload balancing metric, derived from the load function \(h\). The metric is formally expressed as \(L(\mathcal{S})=\max_{\mathcal{W}_{i}\in\mathcal{S}}\ h(\mathcal{W}_{i})\).  
```
Input: problem 1 requires the following inputs: \(\bullet\) Metric graph \(G\); \(\bullet\) Robots \(\mathcal{R}\) and starting vertices \(v_{s}\); \(\bullet\) Number of attacks \(\alpha\) and budget \(B\); \(\bullet\) Monte Carlo sampling times \(K\) and load function \(h\). Output: Set \(\mathcal{S}\) of walks for each robot \(L=+\infty\), \(\mathcal{S}=\emptyset\); // Perform Monte Carlo sampling \(K\) times. while\(i=1,2,\ldots,K\)do // Stage #1:RMOP Solver(employ an existing solver) \(\mathcal{S}_{1}\gets RMOP(\mathcal{R},G,v_{s},B,\alpha)\); // Stage #2:Path Replan(see Algorithm 2) \(\mathcal{S}_{2}\gets PR(\mathcal{R},G,\mathcal{S}_{1},\alpha)\); // Stage #3:Workload Balance(choose a more balanced solution) if\(L(\mathcal{S}_{2})<L\)then \(\mathcal{S}\leftarrow\mathcal{S}_{2}\); \(L\gets L(\mathcal{S}_{2})\);  end if  end while return \(\mathcal{S}\)
```  
**Algorithm 1**Solve RMOPWB  
```
Input: problem 1 requires the following inputs: \(\bullet\) Robots \(\mathcal{R}\) and metric graph \(G\); \(\bullet\) Set \(\mathcal{S}_{1}\) obtained in stage #1; \(\bullet\) Number of attacks \(\alpha\). Output: Set \(\mathcal{S}\) of walks after Path Replanning \(N=length(\mathcal{R})\), \(\mathcal{S}=\emptyset\); // Reduce redundancy of a walk(see Algorithm 3) for\(i=1,2,\ldots,n\)do \(\mathcal{W}_{i}\leftarrow\mathcal{S}_{1}(i)\); \(\mathcal{S}_{1}(i)\leftarrow CutCircle(\mathcal{R},G,\mathcal{W}_{i})\);  end for // Reduce redundancy between walks(see Algorithm 3) \(\mathcal{S}\leftarrow\textit{BackWalks}(\mathcal{R},G,\mathcal{S}_{1},\alpha)\);  return \(\mathcal{S}\)
```  
**Algorithm 2**Function _PR_ (Path Replanning)