Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management

Resilience:

We aim to develop a mission planning heuristic that maximizes the completion of critical objectives even under conditions where actual resource cost matches pessimistic assumptions. The resource budgets must be strictly enforced, thus guaranteeing safety.

Efficiency:

We aim to maximize the completion of non-critical objectives under conditions where actual resource cost matches optimistic assumptions, thus minimizing overdimensioning the system. Under stable conditions (whether optimistic or pessimistic), the planning process should produce results comparable with those achieved using a standard MCTS heuristic.

Robustness:

We aim to minimize the effect of adding new objectives on the number of higher-criticality objectives achieved. In particular, adding a new lowermost criticality level with new actions should not result in fewer higher-criticality objectives being achieved, even though the set of those higher-criticality objectives might change.

MCTS is composed of four phases: selection, expansion, simulation and backpropagation [3]. These four phases are executed iteratively to incrementally grow a tree, as shown in Figure 2. Each node $k$ of the tree represents a sequence of actions ${𝒙}_k=(x_1,x_2,\mathrm{\dots },x_k)$ and contains data about the expected reward of the subsequent sequences of actions. During each iteration, a new leaf node is added to the tree, and the statistics within the ancestor nodes are updated accordingly. This iterative process repeats until a computation budget is reached. Note that a computation budget is a standard notation in MCTS literature to designate processing limits to which the heuristic expands the tree. It should not be misunderstood with operating time budgets or worst-case execution time budgets.

In the selection phase, the heuristic selects an expandable and rewarding node. An expandable node is defined as a node that has at least one child that has not yet been visited during the search. The heuristic begins at the root node of the tree and recursively traverses child nodes until an expandable node is reached. In order to check whether an action $x_i$ is feasible at node $k$, we verify conditions such as whether the accumulated cost after executing the sequence $(x_1,x_2,\mathrm{\dots },x_k,x_i)$ does not surpass the budget. Therefore, cost uncertainties affect the result of this phase.

During the expansion phase, a leaf node $k+1$ is added to the selected node $k$ by choosing an action $x_{k+1}$ among the actions previously computed as possible to execute after ${𝒙}_k$. This phase is thus indirectly affected by the uncertainty of costs.

In the simulation phase, the expected value of the reward of the new node is computed by simulating possible scenarios after the execution of ${𝒙}_{k+1}$ using a rollout policy. This policy can be a random policy or a heuristic tailored to the problem. A maximum horizon is defined to limit the length of the action sequences simulated within this phase. During the execution of the rollout, it is important to know which sequences of actions are possible after ${𝒙}_{k+1}$, considering environment and budget. Therefore, cost uncertainties affect the result of this phase.

In the backpropagation phase, the result of the simulation phase for the new node is added to the statistics of all nodes along its path up to the root of the tree. These statistics are usually unbiased estimators of the rollout evaluations for the objective function. In this phase, the expected reward of each of the ancestor nodes is updated (backpropagated) with a more precise value, as we have more data about the child nodes resulting from the simulation. This phase is not impacted by the uncertainty of costs.

MCTS is an algorithm that can be greatly optimized by rebuilding the plan periodically during the mission execution, a process known as replanning. Usually, a replan occurs after an action has been completed and MCTS is executed to determine a new set of actions. As the system state is updated, the new plan is better adapted to the new possible outcomes of the mission execution. Replanning thus leads to a more efficient use of the remaining resources by adapting to the new reality of the situation. Thus, our approach can also benefit from replanning, since a change of mode is no substitute for updating the plan to reflect the current system state.

We first examine the simpler scenario involving two criticality levels. In our approach, each action has two costs, one in hi-mode, one in lo-mode. Thus, each node $k$ in the MCTS action tree has two associated accumulated costs $b_k^{\text{hi}}$ and $b_k^{\text{lo}}$, with the accumulated costs for the root node $b_0^{\text{hi}}$ and $b_0^{\text{lo}}$ being zero. The computation of these accumulated costs depend on the action sequence $𝒙=(x_1,x_2,\mathrm{\dots }{x}_k)$ assigned to nodes $1,2\mathrm{\dots }k$.

For lo-objectives, the accumulated costs for any resource $r$ are calculated as

whereas for hi-objectives, the accumulated costs are

where $h_k=\max \{n\in [1,k-1]\mid x_n\in {𝒙}^{\text{hi}}\}$ with the convention $\max \{\mathrm{\varnothing }\}=0$

In lo-mode, as all actions are executed, the accumulated costs for hi and lo actions are computed the same way. This means the accumulated cost is simply the sum of $C_{(k-1)\to k}^{\text{lo}}$ of every node $k$ in the branch, as shown in Equation 1 and Equation 3.

In case of a budget overrun, the system may change modes during the execution of a lo-objective and must proceed to execute the next hi-objective, if one exists. However, the cost of executing the hi-objective cannot be predetermined from an unknown intermediate system state, as the system state is only fully known at the end of each action. To address this, we ensure the current action completes by allocating it a budget in hi-mode, even if it is a lo-objective.

In hi-mode, since a lo-objective must complete its execution in hi-mode during a mode change, its cumulative cost in hi-mode is calculated by adding the cost of executing $x_i$ in hi-mode to the cumulative cost of executing the previous action in lo-mode (as outlined in Equation 2).

In hi-mode, the accumulated cost associated with a hi-objective $x_i$ must account for the worst-case scenario among several possible situations. Figure 3 show the possible executions for one branch: the system might have operated exclusively in hi-mode during the execution of the current action $x_i$ ($x_4$); it could have already been running in hi-mode while executing the previous hi-objective $x_{h_k}$ ($x_1$); or it might have transitioned from lo to hi-mode during the execution of a prior lo-objective $x_l$, where ($x_2$ or $x_3$). When node $i$ is added to the tree, its accumulated cost is determined by taking the maximum cost among these potential scenarios (as described in Equation 4).

Note that in the cases where there are no uncertainties, i.e. $\forall i,C_{j\to i}^{\text{lo}}=C_{j\to i}^{\text{hi}}=C_{j\to i}$, then $\forall k,b_k^{\text{lo}}=b_k^{\text{hi}}={\sum }_i{C}_{(k-1)\to k}$. This means that (MC)²TS behaves exactly as MCTS when the action costs do not change between lo and hi mode assumptions.

MCTS or (MC)²TS cannot guarantee that all hi-objectives will be achieved due to resource limits. To prevent lo-objectives from overriding hi-objectives, the rewards for hi-objectives should be greater than the sum of lo-objectives ones: . Thus, hi-objective rewards become the greatest contributors to the objective function.

Figure 4 illustrates how the outcome from the (MC)²TS step is mapped into instructions for the scheduler. In this example, the selected action sequence is $(x_0,x_1,x_2,x_3)$. $x_3$ is a hi-objective, while $x_0,x_1,x_2$ are lo-objectives.

For every action $x_k$, the accumulated cost in lo mode $b_k^{\text{lo}}[r]$ from the (MC)²TS tree is used as the budget corresponding to resource $r$. The systems starts in lo-mode. After executing any action $x_k$, the actual accumulated cost of each resource $r$ (e.g.,, duration, or energy) is compared against $b_k^{\text{lo}}[r]$. If the budget is exceeded for at least one resource, the system switches (or stays) in hi-mode.

When the system is running in hi-mode, it discards the next action $x_k$ if it is a lo-objective. This ensures that the resources consumption stays below the computed hi-mode accumulated cost $b_k^{\text{hi}}[r]$. In the setup shown on Figure 4, only $x_0,x_1,x_2$ can be dropped as $x_3$ is a hi-objective.

Figure 4 represents an example of a mode change. The first line shows the consumption of resource $r$ in lo-mode, while the second one is a possible scenario where an action surpasses its lo-mode cost. Line represents the progressive usage of the available resources. When the mode change occurs, we let lo-objective $x_1$ complete its execution in hi-mode, lo-objective $x_2$ is discarded and hi-objective $x_3$ is executed after $x_1$ completion.

After transitioning to hi-mode, the system may incur costs similar to those in lo-mode, which can cause the actual accumulated cost for each resource $r$ to fall below $b_k^{\text{lo}}[r]$ after executing action $x_k$. In this case, the system reverts to lo-mode and executes the upcoming lo-objectives as usual. Although this allows for potential frequent mode changes if actual accumulated costs fluctuate around the accumulated cost in lo-mode, mode changes introduce no overhead: the mode is only consulted before each action to determine if the next action can be executed. Furthermore, hi-actions will be completed as planned, and lo-actions are scheduled whenever it is safe.

However, the system needs to check whether any previously dropped lo-objective $x_i$ is a dependency of the lo-objective $x_k$ it is about to execute. If this is the case, then action $x_k$ must be dropped as well. This ensures a seamless mode change to lo-mode, since lo-actions will have every required dependency before their execution. hi-actions do not have this issue as only lo-objectives can depend on lo-objectives.

Replanning, which involves rebuilding the plan during mission execution, often after completing an action, is a key process for optimizing the MCTS algorithm by generating new action sequences. When a replanning occurs, the resources are reallocated completely, and the system restarts in lo-mode after a new plan has been adopted. Note that replanning is no substitute for a mode change. Indeed, the mode change inherently adapts to new execution conditions by integrating this adaptation during its plan building phase, whereas replanning requires creating a completely new plan to address the new conditions. It is important to note that the robot must have the knowledge of which actions were already completed in order to replan accordingly, both to know which actions are still available and which dependencies of future actions were already completed.

The frequency of replanning is a trade-off determined during system design. On the one hand, frequent replanning enhances robot autonomy and reduces data exchanges but increases the risk of skipping multiple lo-objectives when transitioning to hi-mode. This conservative approach may lead to overly cautious actions, as the robot will prioritize safety based on assumed worst-case resource consumption for hi-objectives.

On the other hand, frequent replanning facilitates better adaptation to real conditions. If an objective requires fewer resources than initially estimated, a more ambitious plan can be formulated during the replanning process. However, it is crucial that the replanning executes promptly to avoid delays that consume additional resources, which could otherwise be used for executing objectives.

Finally, if $b_k^{\text{hi}}[r]$ is exceeded for any resource $r$ during or by the end of $x_k$ execution, it implies either wrong system design or accidental operation outside safe conditions, such as due to a hardware failure. In such scenarios, (MC)²TS outperforms MCTS in safety by eliminating lo-mode actions, enabling the system to recover and return to its nominal operating conditions.

(MC)²TS can be adapted to $L>2$ levels of criticality, with the lowest being the least critical. Each action $x_k$, assigned a criticality level ${\chi }_k$, will have $L$ worst-case costs and accumulated worst-case costs, one for each mode, even for criticality levels higher than ${\chi }_k$. Indeed, actions $x_k$ must be allocated a sufficient budget to guarantee their completion without interruption in the event of a mode change to a higher criticality level $\mathrm{\ell }>{\chi }_k$.

To ensure that lower criticality actions do not take priority over actions of higher criticality levels, the system designer must ensure that the action rewards enforce .

An important consideration is how much (MC)²TS impacts the computation time of MCTS. MCTS has been previously successfully applied to real-time environments [8, 15, 21]. Therefore, if (MC)²TS has a similar execution time, then its applicability is guaranteed. We first evaluate the time complexity of MCTS in our application. MCTS executes $I$ iterations, each one executing the four phases. Consider the current depth of the tree is $d$, the number of possible actions is $n$, the simulation horizon is $h$, the number of different scenarios simulated at each simulation phase is $m$, and the complexity of computing the accumulated worst-case costs for one node is $c$.

In the selection phase, we traverse $d$ nodes in the tree, making $n-i$ comparisons at each node $i$, having a time complexity of $O_{MCTS}^{slc}=𝒪(\sum _0^{d-1}(n-i))=𝒪(\frac{d^2}{2}+d(n-\frac{1}{2}))$. The expansion phase has a constant time complexity. In the simulation phase, we run one simulation traversing $d$ nodes while computing costs, then $m$ simulations traversing $h$ nodes, having a time complexity of $O_{MCTS}^{sim}=𝒪((d+hm)c)$. Moreover, the rollout can be trivially parallelized, making its complexity in a processor with $C$ cores become $\frac{hm}{C}c$ and $O_{MCTS}^{sim}=𝒪((d+\frac{hm}{C})c)$. In the backpropagation phase, we traverse the tree backwards by $d$ nodes, having a complexity of $O_{MCTS}^{bck}=𝒪(d)$. Since $d$ is bound by the number of actions $n$, as a completed objective will not be executed again, the complexity of one MCTS iteration in this application is:

The difference in complexity between MCTS and (MC)²TS is the complexity $c$ of computing the worst-case accumulated costs for a node, and thus the complexity of the simulation phase. For MCTS, we can consider $c$ as $𝒪(1)$, and $O_{MCTS}^{sim}$ becomes $𝒪(n+\frac{hm}{C})$. As for (MC)²TS, we have to compute every possible cost $C_{j\to i}^{\mathrm{\ell }}$ to compute the accumulated costs. Each action $x_i$ of criticality ${\chi }_i$ in an action sequence has $L$ possible completions. Following each completion in mode $\mathrm{\ell }$, the next action to be executed will be a different action $x_j$ with a criticality ${\chi }_j\ge \mathrm{\ell }$. The costs in modes $(\mathrm{\ell },\mathrm{\ell }+1,\mathrm{\dots },L)$ must be computed. Modes are not concerned, since when an action completes in mode $\mathrm{\ell }$, it will skip actions of criticality inferior to $\mathrm{\ell }$, and completing in lower modes will inevitably be less costly. Therefore, at each node of the chosen branch, there are ${\sum }_{\mathrm{\ell }=0}^{L-1}(L-\mathrm{\ell })=\frac{L^2+L}{2}$ costs that will be computed throughout the execution, and the time complexity $O_{(MC)\text{<sup class="ltx\_sup"><span class="ltx\_text" style="font-size:70\%;">2</span></sup>}TS}^{sim}$ becomes:

This analysis leads to three conclusions. First, the complexity of both MCTS and (MC)²TS depends quadratically on the number of objectives, $n^2$. Indeed, $L$ typically ranges between 2 and 3. While some systems, such as those complying to the DO-178C standard for avionics [2], may use up to 5 criticality levels, larger values are uncommon. As a result, in most systems, $n$ will be significantly larger than $L^2$, making $𝒪(2n^2)$ the dominant factor in the time complexity of the algorithm. Second, the complexity of (MC)²TS depends quadratically on the number of criticality levels, $L^2$, meaning the increase in time complexity is impacted by the value of $L$. At last, given the existence of efficient real-time MCTS implementations, our complexity analysis demonstrates the feasibility of a real-time (MC)²TS implementation.

Our model integrate budget constraints at both the robot level (e.g., mission deadline) and the objective level (e.g., objective deadlines). Our analysis has so far focused on robot-centric resource budget constraints, particularly battery capacity and mission deadline. This timing constraint is enforced during planning by ensuring the accumulated worst-case time costs ($b_k^{\text{lo}}[time]$) never exceeds the mission deadline, effectively treating it as a resource budget constraint.

However, objective-level timing budgets are equally crucial. For example, a sensor may exhaust its energy or storage before the mission deadline. To address this, system designers can impose per-objective time budget constraints, requiring each objective to be completed by its specified deadline. Missing this deadline could result in the loss or degradation of the reward associated with achieving that objective.

Within the (MC)²TS framework, objective timing constraints follow the same budget overrun management approach as mission timing constraints. For each objective $x_i$, the robot operates within its allocated worst-case time budget ($b_k^{\text{lo}}[time]$). When this budget is exhausted – indicating a deadline miss – the system transitions to hi mode. In this state, lo-objectives are automatically discarded while hi-objectives remain active, with the system ensuring their completion by reallocating time originally designated for lower-priority objectives.

However, discarding objectives because they are classified as lo-objectives might be seen as a disproportionate response, while categorising them as hi-objectives could be viewed as an inappropriate design choice. The MC approach proposes alternatives to the discard model, such as the elastic task model [6] or the weakly hard degradation model [10]. In the case of the elastic task model, when the system switches modes, lo-tasks in hi-mode have their period or deadline lengthened, freeing up resources for hi-tasks. In the same way, a weakly hard system will harvest fewer results in order to use fewer resources.

While our approach can be extended to incorporate mechanisms such as elastic deadlines or weakly hard constraints, this extension remains outside the scope of the current paper. Future work could explore its integration and assess its impact on system performance. In the next paragraph, we provide to the interested reader the main ideas on how to incorporate these alternative approaches into our model.

Since robots and objectives are not inherently connected in our framework, a robot detecting a resource overrun cannot directly instruct an objective to modify its behavior. Instead, the objective itself may transition to a degraded mode when approaching or missing its deadline. For example, upon reaching its initial deadline, an objective could autonomously adopt weakly hard constraints or extend its deadline. The robot can be preconfigured with knowledge of this degradation mechanism, eliminating any need for real-time communication between the robot and objectives. To prevent degraded behavior, any objective that transitions to this behaviour must receive a corresponding reduction in reward. Importantly, the revised reward value must still satisfy the criticality hierarchy constraint: remaining strictly greater than the sum of rewards for all lower-criticality objectives (Section 4.2).

Let us consider a scenario in which a drone is deployed to collect data from a set of sensors distributed across an agricultural field. The drone operates under constraints related to both energy consumption and operating time (flight duration or mission deadline). Each of the sensors can be visited independently of the others. Since some sensors are approaching battery depletion, it is crucial to prioritize retrieving their data before they lose power. However, the energy and time required for navigation are subject to stochastic variations due to potential environmental disturbances, such as wind conditions or unforeseen obstacles that may impact the drone’s motor efficiency.

The energy and time consumption associated with movement exhibit a lower bound under ideal conditions but increase as uncertainties arise. Specifically, the more adverse the conditions, the greater the expected cost. To model this variability, we represent the movement cost as a random variable following a half-normal distribution. The minimum possible cost is defined as half of the worst-case cost in lo-mode, denoted by $C^{\text{lo}}$. The standard deviation of this distribution is environment-dependent: under optimistic operating conditions, it is set to $\frac{C^{\text{lo}}}{10}$, whereas in more challenging scenarios, it is increased to $\frac{C^{\text{lo}}}{3}$, thereby increasing the probability of incurring higher movement costs.

The environment is represented as a $100\times 100$ grid, within which the robot can navigate freely. The movement and data retrieval costs considered in this study are presented in Table 1. A unit of movement corresponds to the side length of a single tile in the grid. In hi-mode, each hi-objective is permitted to consume up to twice the previously allocated budget, while lo-objectives are discarded. Energy costs are expressed as a percentage of the total battery capacity. To investigate the impact of resource constraints, the maximum energy budget is set to 60% of the total battery level. The decision-making process employs a random rollout policy in conjunction with the Upper Confidence Bound for Trees (UCT) [20] selection policy – a best-first approach that computes an upper confidence bound to evaluate the optimality of selected nodes.

The implemented action set consists of navigating to an objective location and retrieving data from the sensor at that location. The computation budget, defined as the number of times the Monte Carlo Tree Search (MCTS) executes the selection phase, is set to 600. The horizon, representing the maximum sequence length of actions tested during rollouts, is fixed at 5. Furthermore, the C parameter in UCT, which governs the balance between exploration of alternative paths and exploitation of the best current path, is set to 0.5. The cost of an action is calculated based on the distance between the current objective location and the next objective.

The robot initiates its trajectory from one corner of the grid and is expected to reach the diagonally opposite corner. To demonstrate the effects of a mode change, replanning occurs every two actions, allowing the robot operating under (MC)²TS to execute portions of the mission in hi-mode. This prevents an immediate return to lo-mode after each mode transition, which would occur if replanning were performed after every action. A total of 50 distinct scenarios were generated, each comprising 15 randomly distributed objective locations, 4 of which are designated as high-critical objectives and 11 as low-critical objectives. Both MCTS and (MC)²TS were executed 100 times per scenario, and performance was analyzed under varying time budget constraints.

The objective function considered is

where $𝒙$ is the set of actions already completed, $r_i$ is the reward for completing action $x_i$, $t$ is the time consumed from the beginning of the mission until the end of the last action and $B[time]$ is the total time budget available (or the mission deadline).

The $\frac{t}{B[time]}$ expression is used to prioritize plans that achieve the same objectives in less time. The ${10}^{-4}$ weight is used to ensure this value is always below the reward of achieving an objective. The $\sum _i{r}_i$ factor ensures the total value is always below $1$, which is necessary for UCT. For (MC)²TS, we use $b^{\text{lo}}[time]$ as $t$, as it is the accumulated cost in lo-mode. The reward for reaching the recharge site is 1.0, while the one for performing any other hi-action is 0.2 and for completing any lo-objective 0.0166. Note that as hi-objectives are our priority. As reaching the recharge site is the main hi-objective we want to ensure is in the plan, its reward is greater than the sum of the rewards of the other hi-objectives.

We want to assess each algorithm’s ability to find a plan where the robot retrieves data from objective points and reaches the charging site before exhausting its allocated budget. A robot can fail to reach the recharging site due to unexpected high action costs. In this situation, the number of achieved objectives will be counted as zero.

We evaluate the performance of (MC)²TS in comparison to MCTS, where the latter is configured to generate plans that optimize the number of actions under optimistic assumptions. As the plans do not guarantee resource constraints in the most pessimistic scenarios, these plans may fail to ensure a safe return to the charging site.

If we consider our efficiency goal, for which we try to optimize the optimistic case, this MCTS configuration produces plans achieving a greater number of objectives. Consequently, if we compare its performance with that of (MC)²TS under conditions where the costs in mode lo are never exceeded, it will often achieve more objectives. However, if we consider conditions where the costs in mode lo are exceeded, the MCTS configuration generates unsafe plans that require more resources than are available. This is relevant for our resilience goal. Consequently, we evaluate how often MCTS plans fail to handle such situations. We also evaluate the number of total objectives achieved by (MC)²TS versus MCTS during these missions.

The experimental results are presented in Figure 5 .The first graph shows that optimistic MCTS frequently fails midway through mission execution under lower budgets, significantly reducing its effectiveness. In contrast, as illustrated in the second graph, (MC)²TS achieves more objectives even with higher budgets. This is attributed to its capability to revert to lo-mode once cumulative costs fall below optimistic assumptions. Consequently, (MC)²TS provides a safer and more reliable execution under pessimistic cost conditions.

We evaluate the performance of (MC)²TS in comparison to MCTS, where the latter is configured to exclusively generate plans that never exceed the allocated resource budget.

When focusing our safety objective where we only consider conditions where actual costs are pessimistic, this MCTS configuration is optimal as it is designed to never surpass the allocated budget. Indeed, every action in the plan will always be executed. In the most pessimistic scenario, (MC)²TS will drop every lo-objective and execute a plan that only contains hi-objectives. It will compute the accumulated cost as the sum of $C^{\text{hi}}[r]$, just as the pessimistic MCTS configuration. Therefore, under conditions where actual costs are pessimistic, both approaches will execute similar amounts of hi-objectives, making them equal when it comes to safety.

When considering an optimistic situation and our efficiency objective, MCTS may execute less lo-objectives than (MC)²TS due to its pessimism. Thus, we evaluate the number of objectives achieved by (MC)²TS compared with that of MCTS by simulating situations where the budget in lo mode is never exceeded.

The experimental results, shown in Figure 6, reach a peak in values due to the constrained energy budget. In this scenario, where MCTS is configured to generate plans exclusively based on pessimistic costs while operating under optimistic resource costs, (MC)²TS outperforms MCTS when the budget is insufficient to achieve all objectives. This is because (MC)²TS maintains an accumulated cost closer to that of execution under optimistic actual costs, allowing it to explore more action sequences by leveraging the previously conserved budget. As a result, (MC)²TS makes less pessimistic assumptions about the environment, effectively reducing system oversizing and improving overall efficiency.

As shown previously, (MC)²TS outperforms MCTS when MCTS uses either optimistic or pessimistic costs. In this subsection, we evaluate whether MCTS can outperform (MC)²TS when considering costs that lie between these two extremes. Intermediate costs may offer a balanced trade-off, ensuring safety while maintaining efficiency. Such costs would be less pessimistic, preserving a degree of efficiency while providing the robot with a safety margin sufficient for most scenarios. To cover this possibility, we conducted the same simulations as those used for optimistic MCTS, but compared them with an MCTS implementation that incorporates higher costs for movement and data retrieval. We implemented the same simulation of a mode change used in the optimistic MCTS simulation to give these MCTS implementations a higher chance of being safe.

We simulated 4 costs considered by MCTS in the range between $C^{\text{lo}}$ and $C^{\text{hi}}$ for both time and energy resources. The costs were rounded for the time cost to be always an integer.

The experimental results are displayed in Figure 7. While increasing the considered cost reduces the unsafety of MCTS, no cost configuration below the pessimistic threshold makes it entirely safe. Additionally, for budgets exceeding 800, (MC)²TS consistently achieves more objectives than MCTS. Thus, even MCTS implementations with less pessimistic assumptions fail to provide a better solution in terms of balancing safety and performance.

To assess the impact of respecting the deadlines for hi-objectives, increasing the resilience on (MC)²TS’s plan building, we simulate a scenario in which each hi-objective has a deadline of 500 time units. We compare it to the plan generated by (MC)²TS for a scenario where no objective deadlines are imposed.

Figure 8 shows the distribution of the objectives in the map used. The hi-objectives are agglomerated close to the charging station. The robot must then haste to complete these objectives first to avoid missing their deadline in the pessimistic case. The lo-objectives are separated in two groups at opposite corners of the grid. In this scenario, the robot needs a higher budget to visit all lo-objectives than in the scenario where hi-objectives do not have any deadlines.

The experimental results are shown in Figure 9. In lower budgets, the robot only completes the hi-objectives, as it does not have enough budget to return and complete lo-objectives after. As the budget increases, the robot is then capable of visiting one lo-objectives group after completing the hi-objectives, and both cases are capable of completing every objective given enough budget. However, from a time budget of 800 onward, the robot in the scenario with deadlines completes less objectives. This is due to the robot having to traverse a longer path to respect the hi-objective deadlines.

Therefore, we successfully guaranteed the completion of objectives before a deadline, increasing the resilience of the system. However, respecting objective deadlines even in hi-mode during planning may produce worse results under conditions where the execution is always in lo-mode. Thus, respecting deadlines in hi-mode should be reserved for hi-actions. For lo-actions, it is more coherent to respect deadlines only in lo-mode, even though they may execute in hi-mode.

To evaluate the effects of adding objectives of lower criticality levels, we compared (MC)²TS with $L=4$ and with $L=2$ criticality levels. To achieve our robustness goal, we expect that the addition of actions of criticality levels should not change the average results in level $4$.

To verify this result, we simulated both (MC)²TS implementations in random scenarios where each criticality level has 4 objectives. The simulations were conducted under conditions where resource costs are optimistic estimates and the battery budget was set to 100%.

The results are shown in Figure 10. When considering the different criticality levels, increasing the budget never reduces the average number of objectives achieved at any criticality level. The average number of objectives of highest criticality achieved are shown side by side. As the time budget increases, more objectives are achieved in both configuration. Therefore, the possibility of completing more objectives of lower criticality does not reduce the number of objectives completed at the highest level. Moreover, this is similar for both implementations of (MC)²TS with every time budget. This demonstrates the robustness of our algorithm, as adding actions of lower criticality does not influence the results for higher criticality levels.

However, the computational overhead increases with the number of criticality levels. Therefore, if replanning is done often, this might impact on the overall performance of the robot considering L=4, especially if computing costs is computationally heavy. Thus, adding more levels of criticality should be reserved for systems where the computation of extra costs will not significantly impact on the planning time.

An essential consideration is whether the results from previous experiments remain consistent across different computational budgets and how this value impacts the comparison between the heuristics. To evaluate possible degradation, we simulate the scenario using pessimistic plans with a fixed time budget of 600 while varying the computational budget.

The experimental results are shown in Figure 11. As the computational budget increases, the algorithms are capable of finding more optimal plans. With higher budgets, both algorithms degenerate into a standard tree search, and they reach a peak number of objectives. As (MC)²TS cost assumptions are more optimistic, it consistently achieves more objectives on average than pessimistic MCTS. Therefore, (MC)²TS benefits are achievable with any computational budget.

(MC)²TS outperforms optimistic MCTS by achieving more objectives across varying budgets, leveraging its ability to revert to lo-mode when costs match those of lo-mode, ensuring safer and more reliable execution under conditions where resource costs match those of hi-mode. (MC)²TS also outperforms pessimistic MCTS by maintaining costs closer to the optimistic ones, enabling exploration of more action sequences through conserved resources, reducing execution under hi-mode conditions, minimizing oversizing, and enhancing efficiency. Moreover, even under less pessimistic assumptions, (MC)²TS successfully provides a better solution by effectively balancing safety and performance. Therefore, our solution is better adapted to uncertain environments than MCTS, whether it is configured with an adjusted objective function or built only on pessimistic assumptions. (MC)²TS also monitors multiple uncertain resources, such as energy and action duration, while ensuring that critical objective deadlines are respected. Finally, (MC)²TS demonstrates its robustness, as incorporating lower-criticality actions does not compromise the results for higher-criticality levels.

In mixed-criticality systems, researchers have focused on Real-Time Scheduling [5]. As we consider Decision Making Heuristics, we rather focus on the different system models than on the MC scheduling algorithms themselves.

The majority of the mixed-criticality models consider a system with two criticality levels, even though the original paper by Vestal [30] generalizes the approach to a system with multiple levels of criticality. However, many papers extend their approaches to multiple levels, as it is important for common multi-criticality avionics and automotive standards [4]. Fleming extended the Adaptive Mixed Criticality scheduling methods (AMC-rtb and AMC-max) to an arbitrary number of criticality levels [9]. When tasks are non-preemptive, similarly to our model, Novak et al. proposed a static scheduling approach to minimize the schedule makespan when the system has an arbitrary number of criticality levels [24].

Two mechanisms are usually considered to address a resource failure event: either discard the lo-tasks in hi-mode, or degrade the quality of lo-tasks [4]. Gu et al. have criticized the strategy of discarding lo-tasks in hi-mode [12] and propose an unused budget reclamation scheme. Though resource-efficient to some extent, it adopts a pessimistic outlook, degrading the overall efficiency potential. A few studies have proposed to attempt the minimum service level of lo-tasks in hi-mode. Liu et al. propose continuing to execute lo-tasks in hi-mode but with a smaller WCET [23]. However, such an alternative is outside the scope of our case study. Several works also propose increasing the tasks’ period in hi-mode [18, 28, 6], but our system is not periodic.

In the context of energy-aware mixed-criticality systems, some studies propose Dynamic Voltage and Frequency Scaling (DVFS) or DVFS with Earliest Deadline First (EDF-VD) scheduling [23, 17]. While they aim to reduce energy consumption by gracefully degrading lo-tasks in hi-mode, they lack inherent prioritization of hi-tasks over lo-tasks. In these studies, DVFS serves merely a mechanism for degrading the execution of a lo-task. Our approach differs in that it considers energy as an uncertain parameter of the problem, and not just as a resource to be managed. Therefore, we treat energy (as well as action duration) as a first-class citizen within the MC system, equally important as execution time.

Monte Carlo Tree Search (MCTS) has proven to be pivotal in addressing complex decision-making problems, such as gaming, planning, optimization, and scheduling [16, 3]. Its exploration-exploitation properties make it particularly valuable in path planning applications. Dam et al. extended the application of Monte Carlo methods to improve exploration strategies for robot path planning [8]. Kartal et al. proposed hybrid approach, combining MCTS with Branch and Bound for multi-robot action allocation problem with time windows and capacity constraints [19]. These constraints and time windows only consider one lower and upper bound, which differs from the MC approach.

Most existing studies consider a known environment where cost is fixed. Given a dynamic environment, Patten et al. have proposed a method for using different samples of the robot’s current knowledge to simulate future events [25]. However, it does not consider the uncertainties associated with the robot’s actions. Unlike other approaches that may consider the uncertainty of the rewards of an action [3, 29, 7, 22], we specifically focus on the uncertainties associated with the robot’s resources, introducing a novel aspect of uncertain costs.

Additionally, we highlight mode-change and replanning in (MC)²TS. We demonstrate how they are complementary techniques that increase the safety and efficiency. This emphasizes our adaptability even in the face of future cost changes.