## 3 Methods and Materials
### Markov Decision Process
In that case, routing problems can be used to suggest optimal movement strategies, as analysed in Section 3.3. Focusing back on the MDP-solving technique, the most used simulation-based optimization to find optimal policies of MDP with reinforcement learning is Q-learning [47]. However, this study suggests tree-based reinforcement learning algorithms such as the Monte Carlo tree search to solve operational problems similarly to [48]. A tree view is more adapted to represent the possible actions taken by an exploration system during its mission. Figure 2 shows a partial view of the decision tree, where an autonomous system should decide its following action. Each of the state-action pairs has an associated reward. Monte Carlo Tree Search is a policy-free reinforcement learning algorithm. The algorithm is often applied to find the winning strategies for board or video games, Figure 3. The algorithm learns from its trials, and when well-defined, it can provide a near-optimal or optimal operational plan respecting a series of constraints. In Monte Carlo Tree Search, a tree of states connected by the action is incrementally built, preserving data about the times the node was visited and the reward accumulated at the node. The root of this tree corresponds to the agent's present position. The basic version of MCTS consists of four iterative phases:  
* Selection: a root node is selected accordingly to a selection policy that can be random or guided by a heuristic. * Expansion: the possible children of the selected node are identified. * Roll-out: a complete simulation is played out starting from one of the added states. The moves can be again random or guided by a heuristic. * Backpropagation: the simulated roll-out results are propagated back to the root node. The root node visit index and cumulative reward are updated. An application of the Monte Carlo Tree Search and MDP for the scheduling of satellite operations is presented in [50; 51]. On the other hand, in [46], a similar scheme is used to model a rover control problem. With respect to the work of this study, Ref. [46] lacks a  
Figure 3: Monte Carlo tree search algorithm (adapted from [49]). Figure 2: Partial view of a decision tree for a rover exploring an unknown environment, touching different waypoints during its mission. The different actions bring to different states defined in terms of the rover energy, data, and sampling storage. knowledge base derived from the MBSE model to choose the most impactful state variables. Moreover, the study in [46] targeted implementation and operational phases. Its application pointed to the direct use of MDP onboard the robotic surface systems. In Monte Carlo techniques, a complete simulation is run before associating a value to a specific state-action function. An exploration depth can be introduced if the possibility tree is remarkably ample. Instead of running the complete simulation, the algorithm simulates the next n-steps and then provides an indication of the goodness of that random path. The algorithm can take some exploration action to avoid local minima or follow the most promising path. The time the algorithm spends exploring or following the heuristic depends on an exploration weight that usually varies between 0.5 and 2 [52]. MCTS needs a good definition of the reward per each scenario. The simulations of this paper use a reward defined as a linear combination of: (i) the reward provided by exploring different sites \(R_{observing}\), (ii) the reward provided by sampling the sites \(R_{sampling}\), (iii) the reward associated with an optimal path \(R_{distance}\), as shown in Equation (1). \[R_{scenario_{results}}=w_{1}*R_{sampling}+w_{2}*R_{observing}+w_{3}*R_{ distance}-w_{4}*\frac{N_{comm}}{N_{total}}-w_{5}*\frac{N_{ncharge}}{N_{total}} \tag{1}\]  
where:  
* \(R_{sampling}\) and \(R_{observing}\) are the ratios between the effective scenario reward and the maximum reward for observation and sampling for that scenario. * \(R_{distance}\) is the reward linked to the distance.