## 3 Methods and Materials
### Routing Problems  
To lower the number of trials of the MCTS algorithm, the authors suggest using a routing problem to provide a heuristic guiding the path of the planetary exploration system. The formulation used to estimate an optimal path between the waypoints is the \"open vehicle routing problem with reward with a distance constraint\". The formulation employed to define the problem is mixed-linear integer programming (MILP). There are formulations available for the \"closed vehicle routing problems\" [53], the \"closed vehicle routing problems with reward\" [54], and the \"open vehicle routing problem\" [55,56]. Indeed, the solving method used in this study circles back to the closed solution. The problem can be observed as a directional graph to which two phantom nodes are added if the initial point is not fixed:  
* The distance from the first phantom node and all the other nodes is zero. However, the distance between the other nodes and the initial one is infinite (or set to a high value). * The distance from all the nodes to the second phantom node is zero. However, the distance from the second phantom node is infinite for all but the first phantom node. For example, if the problem has five nodes, the obtained distance matrix would look like the one in Equation (4), where \(D_{ij}\) are the distance between the waypoints and \(y_{p1/2}\) are the phantom nodes. \[ \begin{array}{c}y_{p1}\quad\quad y_{1}\quad\quad y_{2}\quad\quad y_{3}\quad \quad y_{4}\quad\quad y_{5}\quad\quad y_{p2}\\ y_{p1}\left[\begin{array}{cccccccc}0&0&0&0&0&0&0\\ y_{1}&+inf&0&D_{12}&D_{13}&D_{14}&D_{15}&0\\ y_{2}&+inf&D_{21}&0&D_{23}&D_{24}&D_{25}&0\\ y_{3}&+inf&D_{31}&D_{32}&0&D_{34}&D_{35}&0\\ y_{4}&+inf&D_{41}&D_{42}&D_{43}&0&D_{45}&0\\ y_{5}&+inf&D_{51}&D_{52}&D_{53}&D_{54}&0&0\\ y_{p2}&0&+inf&+inf&+inf&+inf&+inf&0\end{array}\right]\end{array}  \tag{4}\]  
When the algorithm looks at the distance matrix, it can always evaluate a closed path using the two phantom nodes. The closed loop ensures an easy formulation. Let us assume that each vertex \(y_{i}\) is connected by a branch identified as \(x_{ij}\). If the routing problem is closed, then if that node is considered (\(y_{i}=1\)), the sum of \(x_{ij}\) on the column and row associated with \(y_{i}\) should equal one. This constraint is simple to enforce in a MILP formulation. If the initial position is fixed, the initial phantom node merges with the indicated initial position. Figure 4: Variation of the reward related to distance with the difference between the optimal and real distance travelled in the scenario with the variation of \(\beta\). Eventually, the MILP problem can be formulated as shown in Equations from (5) to (10): Maximize reward for every waypoint \(y_{i}\) in \(V\):  
\[max\sum_{i=1}^{n}y_{i}*R_{i}-\alpha*\sum_{i=1}^{n}\sum_{j=1}^{n}x_{ij}*D_{ij} \tag{5}\]  
Subject to:  
\[\sum_{i=1}^{n}\sum_{j=1}^{n}x_{ij}*D_{ij}\leq D_{max} \tag{6}\]  
\[\sum_{i=1,i\
eq j}^{n}x_{ij}=y_{j}\,\forall\,j\in V \tag{7}\]  
\[\sum_{j=1,j\
eq i}^{n}x_{ij}=y_{i}\,\forall\,i\in V \tag{8}\]  
\[\sum_{(i,j)\in(S)}x_{ij}\leq|S|-1\,\forall\,S\subseteq V\,,|S|>1 \tag{9}\]  
\[y_{i}\in\{0,1\},x_{ij}\in\{0,1\} \tag{10}\]  
where:  
* \(y_{i}\) are the waypoints indexes. If a waypoint is not considered, then \(y_{i}\) equals zero. * \(R_{i}\) is the scientific reward associated with those waypoints. * \(\alpha\) is a weight defining the importance of the second optimization target. The suggested value used in this paper is 0.01. * \(x_{ij}\) are the edges between the waypoints' indexes. * \(D_{ij}\) is the distance between the waypoint. * \(D_{max}\) is the maximum traversable distance under one battery discharge as evaluated from [57]. The scientific reward is evaluated as a specific waypoint's scientific interest or priority. Equation (5) describes the objective function: maximizing the accumulated reward touching different waypoints while minimizing the distance to touch them. Equation (6) imposes a constraint on the maximum traversable distance.