# Managing Redundancy in a Multiple-Robot Orienteering Problem for Equilibrium and Robustness
## 2 Materials and Methods
### Problem Formulation
#### 2.2.1 Minimizing Total Workload  
To minimize the total workload, the initial step is termed _Path Replanning_ (stage #2 in Figure 3). This stage must satisfy certain criteria to be formally represented. Following stage #1, there emerges a set of \(n\) walks, denoted as \(\{\mathcal{W}_{1},\mathcal{W}_{2},\ldots,\mathcal{W}_{n}\}\). For each walk \(\mathcal{W}_{i}\), the objective is to eliminate unnecessary vertices while ensuring that the resulting condensed connected graph remains a subgraph of \(\mathcal{W}_{i}\). Drawing on the concept of an induced subgraph, the post-replanning walk \(\mathcal{W}_{i}^{\prime}\) should correspond to a variant of the Traveling Salesman Problem (TSP) walk on some induced subgraph. Let \(T(I_{i})\) denote a variant TSP walk on a connected undirected graph \(I_{i}\). The walk \(T(I_{i})\) starts at vertex \(v_{s_{i}}\) and traverses all vertices in \(I_{i}\) without returning to the starting vertex, optimizing the budget expenditure for robot \(i\). The set of reconfigured walks \(\{\mathcal{W}_{1}^{\prime},\mathcal{W}_{2}^{\prime},\ldots,\mathcal{W}_{n}^{ \prime}\}\) must satisfy the following four conditions:  
1. Budget constraint: \(C(\mathcal{W}_{i}^{\prime})\leq B,\ \forall\ i\in\{1,\ldots,n\}\).
2. TSP-variant walk: \(\mathcal{W}_{i}^{\prime}=T(I_{i}),\ \exists\ I_{i}\in I(\mathcal{W}_{i}),\ \forall\ i\).
3. Reward preservation: \(Rd(\mathcal{W}_{i},\alpha)=Rd(\mathcal{W}_{i}^{\prime},\alpha),\ \forall\ i\).  
It can be shown that the walks \(\{\mathcal{W}_{i}^{\prime}\}\) must be optimal for stage #1. Through the above discussion, we formalize the Path Replanning stage:  
**Problem 2** (Stage #2).: _After stage #1, we obtain a collection of \(n\) walks, denoted as \(\mathcal{S}_{1}=\{\mathcal{W}_{1},\mathcal{W}_{2},\dots,\mathcal{W}_{n}\}\). The objective function for stage #1 reaches its optimal value \(R\). The Path Replanning problem is formulated as follows:_  
\[\begin{split}\min_{I_{i}\in I(\mathcal{W}_{i})}& C(T(I_{1}))+C(T(I_{2}))+\dots+C(T(I_{n}))\\ s.t.&\min_{\mathcal{A}}f(\mathcal{D}\backslash \mathcal{A})=R,\ |\mathcal{A}|\leq\alpha,\ \mathcal{A}\subseteq\mathcal{D}\\ &\mathcal{D}=\{T(I_{1}),\dots,T(I_{n})\},\ C(T(I_{i}))\leq B.\ \forall i\end{split} \tag{3}\]  
_The optimal solution \(\{I_{1},I_{2},\dots,I_{n}\}\) yields a new set of \(n\) walks denoted as \(\mathcal{S}_{2}=\{T(I_{1}),\dots,T(I_{n})\}\). For notational convenience, we may refer to \(\{I_{1},I_{2},\dots,I_{n}\}\) simply as \(\mathcal{S}_{2}\)._  
**Example 1**.: _As illustrated in Figure 3, the red robot in subfigure (1-1) traverses a path in 5 steps. However, the final step proves redundant as it duplicates the path of the yellow robot, creating unnecessary overlap. By eliminating this superfluous movement, the solution maintains its optimality for Problem 1. This demonstrates that removing such redundancies preserves the solution's optimal characteristics._  
**Remark 1**.: _To mitigate excessive redundancy, one could impose budget constraints \(B\) on individual robots. Although this approach effectively prevents path overpopulation, it requires a priori budget allocation for each robot. Furthermore, in multi-robot systems with heterogeneous budget requirements, this method demonstrates limited adaptability to dynamic environments with frequent budget variations. In contrast, Problem 2's solution achieves superior redundancy balancing._  
Figure 3: All processes of solving our orienteering problem. There are four processes, which are the graph model of a scene, stage #1, stage #2, and stage #3. The RMOP Solver obtains the walks of stage #1. These three stages correspond to (2), (3), and (4), respectively. There is a loop between stage #1 and stage #2. When the loop is over, obtain the optimal solution of stage #3 by (4). The upper right corner of the subgraph shows the total budget for the two drones.